Легкая нечеткая библиотека поиска

Question

Можете ли вы предложить легковесную библиотеку нечеткого текстового поиска?

Я хочу разрешить пользователям находить правильные данные для условий поиска с опечатками.

Я мог бы использовать полнотекстовые поисковые системы, такие как Lucene, но я думаю, что это излишнее количество.

Edit:
Чтобы прояснить вопрос, вот основной сценарий для этой библиотеки:
У меня есть большой список строк. Я хочу иметь возможность поиска в этом списке (что-то вроде intellisense MSVS), но должна быть возможность фильтровать этот список по строке, которой нет в нем, но достаточно близко к какой-то строке, которая есть в списке.
Пример:

• красный
• зеленый
• синий

Когда я набираю 'Gren' или 'Geen' в текстовом поле, я хочу видеть 'Green' в наборе результатов.

Основным языком для индексированных данных будет английский.

Я думаю, что Lucene слишком тяжел для этой задачи.

Обновление

Я нашел один товар, соответствующий моим требованиям. Это ShuffleText .
Знаете ли вы какие-либо альтернативы?

Answer 1

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

Для нечеткого поиска вам действительно нужно решить, какой алгоритм вы бы хотели использовать. С поиском информации я успешно использую технику n-грамм с Lucene. Но это особая техника индексации, а не «библиотека» сама по себе.

Не зная больше о вашем приложении, будет нелегко порекомендовать подходящую библиотеку. Сколько данных вы ищете? В каком формате данные? Как часто обновляются данные?

Answer 2

Я не уверен, насколько хорошо Lucene подходит для нечеткого поиска, лучше выбрать пользовательскую библиотеку. Например, этот поиск выполняется в Java и работает довольно быстро, но он специально сделан для такой задачи: http://www.softcorporation.com/products/people/

Answer 3

Попробуйте Walnutil, основанный на Lucene API, интегрированный в SQL Server и Oracle DB. Вы можете создать любой тип индекса, а затем использовать его. Для простого поиска вы можете использовать некоторые методы от walnutilsoft, для более сложных поисковых запросов вы можете использовать Lucene API. Смотрите веб-пример, где использовались индексы, созданные из Walnutil Tools. Также вы можете увидеть пример кода, написанного на Java и C #, который вы можете использовать для создания различных типов поиска. Этот инструмент бесплатный. http://www.walnutilsoft.com/

Answer 4

Вы не указали свою платформу разработки, но если ее PHP, тогда предложите взглянуть на библиотеку ZEND Lucene:

http://ifacethoughts.net/2008/02/07/zend-brings-lucene-to-php/ http://framework.zend.com/manual/en/zend.search.lucene.html

Поскольку он LAMP намного легче, чем Lucene на Java, и может быть легко расширен для других типов файлов, при условии, что вы можете найти библиотеку преобразования или преобразователь строки cmd - для этого есть множество решений OSS.

Answer 5

Если вы можете использовать базу данных, я рекомендую использовать PostgreSQL и его функции нечеткого сопоставления строк .

Если вы можете использовать Ruby, я предлагаю заглянуть в библиотеку amatch .

Answer 6

Soundex очень «английский» в своей кодировке - Daitch-Mokotoff работает лучше для многих имен, особенно европейских (германских) и еврейских имен. В моем британском мире это то, что я использую.

Wiki здесь .

Answer 7

Проверьте эту ссылку. Он использует метрики расстояния Левенштейна, но работает намного быстрее. http://narenonit.blogspot.com/2012/07/fuzzy-matching-autocomplete-library.html

Answer 8

Мощное, легкое решение - сфинкс .

Это меньше, чем Lucene, и поддерживает неоднозначность.

Он написан на c ++, он быстрый, проверенный в бою, имеет библиотеки для каждого env и используется крупными компаниями, такими как craigslists.org

Answer 9

@ aku - ссылки на рабочие библиотеки soundex находятся прямо внизу страницы.

Что касается расстояния Левенштейна, в статье Википедии об этом также есть реализации, перечисленные внизу.