Алгоритм JavaScript для сопоставления слов в словаре

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

Есть ли уже поисковая библиотека для чего-то подобного? Я не хочу изобретать велосипед, если в этом нет необходимости. Если нет, есть ли у кого-нибудь идеи для высокопроизводительного решения. Я полагаю, что это делалось уже миллионы раз.


javascript full-text-search algorithm anagram
person juicejonjon    schedule 28.03.2011    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Джон Резиг, известный по jQuery, тоже думал об этой проблеме:

http://ejohn.org/blog/dictionary-lookups-in-javascript/

person duffymo    schedule 28.03.2011

arrow_upward
1
arrow_downward

Об этом тоже кое-что написал Стив Ханов:

http://stevehanov.ca/blog/index.php?id=120

person Juan-Carlos    schedule 28.03.2011

arrow_upward
1
arrow_downward

Что вам нужно сделать, так это преобразовать массив слов в хеш-таблицу, где ключом являются отсортированные буквы каждого слова. Бывший:

['car', 'shoe', 'train']
=> {'acr': ['car'],
     'ehos': ['shoe'],
     'ainrt': ['train']}

Затем вы берете письма пользователя, сортируете их и выполняете поиск по хеш-таблице (подойдет любой словарь, но в этом случае наиболее эффективны хэш-таблицы), используя отсортированные буквы в качестве ключа. Список, соответствующий вашему ключу, — это список слов, которые вы можете составить из этих букв. Это имеет то преимущество, что имеет временную сложность O (n) = 1.

person Ioan Alexandru Cucu    schedule 28.03.2011
comment
Мне очень нравится идея этого метода, но есть ли у вас какие-либо советы, когда вы также разрешаете использовать подмножество предоставленных букв? Например. буквы «с», «а», «р» и «с» могут означать «автомобиль» и «автомобили». - person Michiel; 17.07.2012
comment
Тогда вам, вероятно, понадобятся попытки: en.wikipedia.org/wiki/Trie , хотя я не уверен, что это реализовано в какой-либо js-библиотеке. - person Ioan Alexandru Cucu; 21.05.2013