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

Question

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

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

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

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

• Красный
• Зеленый
• Синий

Когда я типа 'Грен' или 'Geen' в текстовом поле, я хочу видеть 'Зеленый' в результате задавать.

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

Я думаю, что Луцену тяжело для этой задачи.

Update:

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

Answer 1

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

Что касается расстояния Левенштейна, то Wikipedia article on that также имеет варианты, перечисленные внизу.

Answer 2

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

Wiki here.

Answer 3

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

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

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

Answer 4

Если вы можете использовать базу данных, я рекомендую использовать PostgreSQL и ее fuzzy string matching functions.

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

Answer 5

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

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 6

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

Answer 7

Мощным, легким решением является sphinx.

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

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

Answer 8

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

Answer 9

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