Как сделать Поиск анаграмм в заданном словаре?

Question

[turchik2808]

Здравствуйте, подскажите идею, как реализовать поиск анаграмм в заданном словаре (хотя бы визуально, как это может выглядеть). Просто не совсем понимаю принцип поиск из словаря, из текста более менее понятно.

Comments

[xmoonlight]

Для чего вообще нужен поиск анаграмм? (чтобы увеличить скорость поиска в словаре или ещё какая-то цель?)

[turchik2808]

xmoonlight, курсовой проект такой

[xmoonlight]

turchik2808, интересно... А им то зачем именно через анаграммы?)
Это же крайне медленно!))

[xmoonlight]

Sumor, Андрей Власов, подскажите ответ на мой первый коммент к вопросу..
Спасибо.

[turchik2808]

xmoonlight, суть этой курсовой, как раз таки найти слова-анаграммы

[xmoonlight]

turchik2808, так это понятно. Но для чего их искать? Смысл какой в этом?

[turchik2808]

xmoonlight, тоже об этом задумываюсь

[xmoonlight]

turchik2808, ))

[turchik2808]

xmoonlight, тут по своей глупости я выбрал эту тему, не подумав так сказать. Надо было и взять создание игры какой-либо, больше информации есть, да и интереснее

[xmoonlight]

turchik2808, может и анаграммы не менее интереснее, если знать смысл)

[Андрей Власов]

xmoonlight, Ну я делал для курсовой игру, аналог игры "слова из слова", т.е. загадавыется случайное слово, например "гидроэлектростанция" и пользователь должен найти все слова, которые можно составить из этого слова ("стан", "станция", "трос" и т.д.). Соответственно поиск анаграмм применялся для проверки пользовательского решения, не вручную же мне для каждого слова все решения прописывать. Насчет скорости, на моем ноуте для слова "гидроэлектростанция" находится 1961 анаграмма среди 48053 слов за 7 мс, думаю это относительно быстро, чем полный перебор :)

[turchik2808]

xmoonlight, соглашусь

[xmoonlight]

Андрей Власов, примеры - это подстроки... (просто так совпало, думаю).
1. Гиря - подходит?
2. Таран - подходит?
3. Аэродрон - подходит?

И то, что это только для игр - вряд ли)

[xmoonlight]

Андрей Власов,

Насчет скорости, на моем ноуте для слова "гидроэлектростанция" находится 1961 анаграмма среди 48053 слов за 7 мс, думаю это относительно быстро, чем полный перебор :)

Смотря какой конфиг и это на c#?!

Если правильно составить дерево из словаря - то будет точно менее 1ms.

Отсюда - и вопрос про анаграммы!)))

[Андрей Власов]

xmoonlight, Не обязательно подстроки (просто так быстрее было пример написать), "гиря" и "аэродрон" подойдет, "таран" уже нет. Игру я как пример привел, где такой алгоритм обоснован (сомневаюсь, что это где-то применимо в реальных задачах). Насчет 7 мс, это первый запуск метода; второй и последующие, занимают уже около 4 мс, а для слов меньше 15 букв, результат действительно меньше 1мс. Конфиг: (Intel i5 7200u, 8gb ram, ssd nvme). Про использование деревьев не думал, но мне кажется построение дерева займет существенную часть времени.

[xmoonlight]

Андрей Власов, ясно. Спасибо!
Дерево строится/модифицируется только в момент модификации словаря.
Иначе - оно просто всегда есть)

Answer 1

[Sumor]

Простая идея для русского языка.
Для словаря строите следующий индекс:
Каждой букве (кроме Е=Ё) ставите в соответствие число: А=0 Б=1 ... Я=31
Если буква встречается в слове, то взводите соответствующий бит числа (вне зависимости от количества букв)
В этом случае вам для русского языка хватит UInt32 (unsigned int).
АБАК = 1000000011

Для поиска анаграммы составляете такое же число и отбираете претендентов из словаря. Затем претендентов окончательно выбираете по точному совпадению встречающихся букв.

Comments

[turchik2808]

Спасибо

Answer 2

[Андрей Власов]

Для поиска анаграмм состоящих из одинакового количества букв или меньшего числа букв я делал так:
Для того чтобы слово из словаря можно было считать анаграммой нашего слова должно совпасть три условия:
1. Количество букв в словарном слове не должно превышать количество букв в нашем слове (простая проверка на длину слова).
2. Также слово в словаре не должно содержать такие буквы, которые отсутствует в нашем слове. Например - слово "бур" не является анаграммой слова "робот".
3. Количество одинаковых букв в словарном слове не должно превышать их количество в искомом слове. Данный пункт проверял через составление и сравнение двух ассоциативных массивов вида: "буква" -> "количество ее повторений". Например: "тара" - [т] -> 1, [а] -> 2, [р] -> 1.
Когда эти три условия совпадут слово можно считать анаграммой.
Вот рабочий код: https://tinyurl.com/rskes9g

Comments

[turchik2808]

Спасибо