Как сделать нечеткий поиск строки без тяжелой базы данных? - PullRequest
Новая
       7

Как сделать нечеткий поиск строки без тяжелой базы данных?

6 голосов
/ 07 мая 2009

У меня есть отображение каталожных номеров на названия продуктов: 

35  cozy comforter
35  warm blanket
67  pillow

и нужен поиск, который нашел бы смешанные имена с ошибками, например "warm cmfrter" .

У нас есть код, использующий расстояние редактирования (difflib), но он, вероятно, не масштабируется до 18000 имен.

Я добился чего-то похожего с Lucene, но PyLucene оборачивает только Java, что усложняет развертывание для конечных пользователей.

В SQLite обычно не скомпилированы полнотекстовые или скоринговые данные.

Xapian-привязки подобны C ++ и имеют некоторую кривую обучения.

Свист еще недостаточно документирован, но включает в себя проверку правописания, которую можно использовать.

Что еще там?

Ответы [ 6 ]

4 голосов
/ 04 июля 2009

Видимо, единственный способ сделать нечеткие сравнения быстро - это сделать их меньше;)

Вместо того, чтобы писать другой поиск в n-граммах или улучшать его в Whoosh, мы теперь храним индекс слов, извлекаем все записи, которые имеют хотя бы одно (правильно написанное) слово, общее с запросом, и используем difflib для их ранжирования. Работает достаточно хорошо в этом случае.

2 голосов
/ 07 мая 2009

С реализацией SOUNDEX вы получите слишком много ложных срабатываний. Существует только 26 000 (максимум) возможных кодов SOUNDEX.

Хотя алгоритм Metaphone был разработан для английских фамилий, он работает довольно хорошо для орфографических ошибок; Я использовал это однажды в локаторе веток, и это было довольно успешно.

Добавьте поле с переводом метафона и сопоставьте его, если точное совпадение не найдено. Вы все равно получите ложные срабатывания, но меньше, чем с другими алгоритмами.

2 голосов
/ 07 мая 2009

Nucular имеет полнотекстовый поиск, но не поддерживает совпадения с ошибками из коробки. Вы можете попробовать добавить дополнительное поле к каждой записи который индексирует SOUNDEX перевод терминов, а затем поиск с использованием перевода soundex пользовательского ввода. Я действительно не знаю, насколько хорошо это будет работать ...

Взгляните на advas http://advas.sourceforge.net/news.php, в котором есть хорошая демонстрация, сравнивающая различные методы, подобные soundex: 

advas/examples Aaron$ python phonetic_algorithms.py 
                    soundex       metaphone           nyiis      caverphone 
====================================================================================================
 schmidt :             S253           sxmtt          sssnad      SKMT111111
  schmid :             S253            sxmt          sssnad      SKMT111111
 schmitt :             S253            sxmt         sssnatt      SKMT111111
   smith :             S530            sm0h           snatt      SMT1111111
  smythe :             S530           smy0h           snatt      SMT1111111
 schmied :             S253            sxmt         sssnaad      SKMT111111
   mayer :             M600             myr           naaar      MA11111111
   meier :             M600              mr           naaar      MA11111111
....

Не знаю, подходит ли какой-нибудь из них для вашего неназванного языка ...

1 голос
/ 17 ноября 2011

sqlite3 поддерживает функции обратного вызова Python. Регулярное выражение Мэтью Барнетта (http://code.google.com/p/mrab-regex-hg/) теперь поддерживает приблизительное соответствие.

Итак, вот так: 

try:
    import regex
except ImportError:
    sys.stderr.write("Can't import mrab-regex; see http://pypi.python.org/pypi/regex\n")
    sys.exit(1)

def _sqlite3_regex(expr, item):
    return (not (not regex.search(expr, item)))

def main():
    ...
    database = sqlite3.connect(dbfile)
    database.create_function("regexp", 2, _sqlite3_regex)
    pattern = '(?:%s){e<=%d}' % (queriedname, distance)
    print [x for x in database.cursor().execute(
         "SELECT * FROM products WHERE (productname regexp '%s')" % pattern)]
1 голос
/ 15 мая 2009

Sybase SQL Anywhere имеет бесплатную веб-версию / версию для разработчиков и поставляется с полнотекстовым индексированием / поиском и оператором FUZZY (и некоторыми ограничениями реализации).

Цитировать из документации: 

Specifying 'FUZZY "500 main street"' is equivalent to 
'500 OR mai OR ain OR str OR tre OR ree OR eet'.

Другой подход заключается в использовании оценки при полнотекстовом поиске.

1 голос
/ 08 мая 2009

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

Один из моих любимых методов нечеткого сопоставления строк - сопоставление триграмм . Сравнение двух строк с использованием этого метода имеет линейную сложность по времени, что намного лучше, чем упомянутое расстояние редактирования. Вы можете найти мою реализацию Python на Github . Также для этого есть модуль PostgreSQL contrib . Не должно быть слишком сложно адаптировать его для работы с SQLite3.

...