Алгоритм поиска отсутствующих букв

Question

Итак, я должен искать слова, которые содержат недостающие буквы (используется в кроссворде), а также содержать список возможных слов для остальных пространств.

Теперь мой вопрос в том, что у меня есть googled, что взрыв-trie, если самый быстрый алгоритм для поиска. Но если я закодирую это в trie и как бы тяжело мне было переходить на «взрыв-трю».

Принесите мне, если что-то не получилось, вы можете прокомментировать, чтобы прояснить любую точку.

Answer 1

Во-первых, отказ от ответственности, я не написал прорыв. Но, прочитав ваш вопрос, я нашел исходную статью, в которой предлагалось взрыв-три, Burst Tries: A Fast, Ecient Data Structure for String Keys, и это звучит прямо. Я написал несколько баз данных и многочисленные вспомогательные функции.

Из того, что я читал, звучит так, как будто вы пишете trie, следуя стандартным подходам, и просто добавьте опцию bst в свою структуру и используйте ее для последней последовательности символов. Затем добавьте функцию «всплеска» к вашему классу trie и при настройке, «выложите» bst на новый уровень trie struct и продолжите с деревом суффиксов bst.

Итак, я думаю, что ответ на ваш вопрос: «Да, легко превратить твой в трюк».

Answer 2

На самом деле довольно просто превратить trie в серийный трек, если у вас есть правильные слои абстракции. Там есть Scala implementation этой взрывающейся бумаги (которая смешивается в некоторых идеях из реализаций GWT), которая действительно эффективна по размеру (и ограничение пространства является наиболее очевидным при работе с trie).

Если вы хотите создать свой собственный, взгляните на эту реализацию для руководства. Он немного общий, поэтому его можно использовать по-разному; но он должен работать для вашего случая использования, если вы находитесь в JVM и не против потащить библиотеку scala.