Я ищу эффективный алгоритм скремблирования набора букв в перестановку, содержащую максимальное количество слов.
Например, скажем, мне прислан список букв: {e, e, h, r, s, t}. Мне нужно заказать их таким образом, чтобы содержать максимальное количество слов. Если я закажу эти письма в "theres", они содержат слова "the", "there", "her", "here" и "ere". Таким образом, этот пример может иметь 5 баллов, так как он содержит 5 слов. Я хочу заказать буквы таким образом, чтобы иметь наивысший балл (содержать большинство слов).
Наивным алгоритмом было бы попытаться оценить каждую перестановку. Я считаю, что это O (n!), Поэтому 720 разных перестановок будут проверяться только на 6 букв выше (включая некоторые дубликаты, так как пример имеет e дважды). Для большего количества писем наивное решение быстро становится невозможным, конечно.
Алгоритм не должен на самом деле производить самое лучшее решение, но он должен найти хорошее решение за разумное время. Для моего приложения просто угадывание (Monte Carlo) на нескольких миллионах перестановок работает довольно плохо, так что в настоящее время метка бить.
В настоящее время я использую алгоритм Aho-Corasick для оценки перестановок. Он ищет каждое слово в словаре всего за один проход через текст, поэтому считаю его достаточно эффективным. Это также означает, что у меня есть все слова, хранящиеся в trie, но если другой алгоритм требует отличного хранения, это тоже хорошо. Я не беспокоюсь о настройке словаря, просто времени выполнения фактического заказа и поиска. При необходимости можно использовать нечеткий словарь, например Bloom Filter.
Для моего приложения список букв составляет около 100, а словарь содержит более 100 000 записей. Словарь никогда не меняется, но нужно заказать несколько разных списков букв.
Я рассматриваю возможность попробовать алгоритм поиска пути. Я считаю, что я мог бы начать с случайного письма из списка в качестве отправной точки. Затем каждая оставшаяся буква будет использоваться для создания "пути". Я думаю, что это будет хорошо работать с алгоритмом скоринга Ахо-Корасика, поскольку баллы могут быть построены по одной букве за раз. Я еще не пробовал найти путь; может быть, это даже не хорошая идея? Я не знаю, какой алгоритм поиска пути может быть лучшим.
Другой алгоритм, о котором я думал, также начинается со случайной буквы. Затем в словаре trie будут найдены "богатые" ветки, содержащие оставшиеся буквы. Отделения в словаре, содержащие недоступные буквы, будут обрезаны. Я немного туманно о деталях того, как это будет работать точно, но это может полностью устранить скоринговые перестановки.
