автозаполнение алгоритмов, статей, стратегий и т. д.

Question

Мне интересно, есть ли у кого-нибудь хорошие ресурсы для чтения или код для эксперимента "autcomplete"

Я хотел бы знать, какова теория автозаполнения, с чего начать, каковы распространенные ошибки и т. Д.

Мне показалось удивительным, как такие продукты, как Enso, Launchy, Google chrome и даже tcsh, выполняют свое автоматическое завершение, я просто для любопытства попробовал некоторый пример кода и пришел к выводу, что эта область должна быть широко исследована прежде.

Буду признателен, если кто-нибудь поделится каким-нибудь хорошим техническим ресурсом о том, как это реализовать.

Заранее спасибо.

Answer 1

• http://humanized.com/weblog/2007/03/30/what_makes_a_good_autocomplete/ -
• http://social.msdn.microsoft.com/Forums/en-US/vblanguage/thread/2ccb37b9-c7e1-4113-86ac-ad3d33b4b4b1/ - в мире .Net
• A противный патент на подход к автозаполнению (все еще возможно стоит прочитать для теории ) http://www.patentstorm.us/patents/5845300/description.html
• http://ask.metafilter.com/91068/Fuzzy-text-completion-algorithm для обсуждения на высоком уровне стратегий.

Answer 2

Посмотрите этот блог о реализации автозаполнения с использованием GWT:

http://jroller.com/glongman/entry/gwt_autocompleter

Но я бы порекомендовал вам сначала начать с чего-то очень простого, чтобы понять, как осуществляется реализация. Я бы начал с Trie, может быть, даже полностью сохранил его на клиенте, а затем приступил к оптимизации запросов к серверу, если вы считаете, что они необходимы.

Answer 3

Автозаполнение обычно выполняется с использованием одного из следующих:

• Деревья . Индексируя текст с возможностью поиска в древовидной структуре (дерево префиксов, дерево суффиксов, dawg и т. Д.), Можно выполнять очень быстрый поиск за счет хранения памяти. Обход дерева может быть адаптирован для приблизительного соответствия.
• Разделение по шаблонам . Разбивая текст на токены (нграммы), можно выполнять поиск вхождений в шаблон с использованием простой схемы хеширования.
• Фильтрация . Найдите набор потенциальных совпадений, а затем примените последовательный алгоритм для проверки каждого кандидата.

Пара статей на эту тему:

• Борживой Меличар. Приблизительное сопоставление строк конечными автоматами;
• Гонсало Наварро. Экскурсия по приблизительному сопоставлению строк;
• Леонид Бойцов. Методы индексации при приближенном поиске в словаре: сравнительный анализ;
• Мариос Хаджилефтериу и Дивеш Шривастава. Примерная обработка строк;
• Сураджит Чаудхури и Рагхав Каушик. Расширение автозаполнения для допущения ошибок;

Взгляните на полностью , библиотеку автозаполнения Java.