#php #алгоритм #математика #поиск
На вход программе подаётся набор английских букв. Имеется словарь из слов.
Как сгенерировать такие предложения из слов, чтобы каждое из предложений состояло
только из тех букв, что были поданы на вход, учитывая количество повторений.
Пример
Входящий набор символов: hellomyfriend
Вывод программы:
Feed Hilly Morn
Feed Hilly Norm
Feed Horny Mill
Freehold Nil My
Refilled Hon My
Defiler Hymn Lo
и т.д.
Выбрать слова которые удовлетворяют входному набору символов у меня получилось. А
вот быстро составлять из них предложения не получается.
Я делал методом перебора всех слов. Для фразы myfavoritegame скрипт отрабатывал около
5 минут. На сайте предложения отдаются мгновенно.
Можете что-нибудь посоветовать?
Ответы
Ответ 1
Предположим, вам нужно просто найти все возможные комбинации слов из данного словаря, удовлетворяющие условию. Не отвлекаясь на особенности именно языка. Важно для поиска: наличие букв в слове. Исключаем содержащие буквы вне заданных. Исключаем, по мере составления фразы, уже использованные. считаем буквы. В любой момент составления фразы известно, слова какой длины подходят, или точно не подходят. повторы букв. Не важно: порядок букв в словарном слове. смысл слова. Для скорости нужно сделать поиск по важным признакам максимально быстрым, при необходимости убрав неважные аспекты. Для быстрого нахождения слов с подходящим набором букв, но без учёта повторов, можно сделать битный индекс, как предложил @Mirdin: 26 букв английского алфавита = 26 бит. Пронумеровать слова в словаре (или просто индексом считать номер строки) и составить отдельный индекс в две колонки: id слова - битовая маска имеющихся букв. Для словаря меньше 65 тыс. слов, такой индекс будет "весить" 6 байт на слово, менее 400k. Можно держать в оперативной памяти для почти-мгновенного поиска. Так можно быстро найти например, первое слово фразы – просто, чтобы точно были выключены биты "лишних" букв. Стоит сделать копию словаря, где буквы слова отсортированы по алфавиту, и слова отсортированы по алфавиту. Т.е. опять отдельный индекс: сортированные_буквы - id_слова. Этот индекс будет тяжелее самого словаря на (число слов * 2 или 3 байта). В этом индексе можно быстро находить подходящие слова и отбрасывать точно-неподходящие. Алгоритм примерно такой. Ищем первое слово. Хочется найти первое же слово наибольшей возможной длины. Перебор по длине, от большего к меньшему. Ест допустимый набор букв и длина. Нашли первое слово, обновили допустимый набор букв и длины слов – ищем следующее слово.Ответ 2
Делаете структуру (таблицу в БД, хеш-таблица, словарь и тд что там есть в пхп) из двух полей на запись: хэш и собственно говоря слово. Забиваем эту структуру словами. Хэш примерно делается так: индекс буквы в алфавите - степень двойки, все буквы слова складываем (32 бит для русского языка должно хватить). Это простейший вариант, возможно будет необходимо придумать более сложную функцию. Получив слово которое надо заанаграмить - вычисляем его хэш и ищем по нему в нашей структуре UPD: Это для одного слова, с фразами будет сложнее, но принцип тот же
Комментариев нет:
Отправить комментарий