?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
fuzzy search grep своими руками
nyaload
_winnie
Если нужно провести неточный поиск слова по большому файлу (напр. по дампу википедии), то самое простое - это сгенерить регулярное выражение со всеми нужными вариантами опечаток, и сунуть в хорошую библиотеку регулярных выражений ( стандартный grep - OK, PCRE/python.re - NOT OK ).

Например, слово WORD превращается в регулярку:
.ORD|ORD|W.RD|WRD|W.ORD|WO.D|WOD|WO.RD|WOR.|WOR|WOR.D

Если нужен поиск по UTF-8 файлу - то можно ускорить поиск, используя вместо точки и UTF8-локали - "[^\x80-\xbf][\x80-\xbf]*" и C-локаль.

Если нужен case-insensitive поиск - то при генерации регулярки вместо СЛОВО писать (С|с)(Л|л)(О|о)(В|в)(О|о). И вы сами определяете, что вы хотите - [iI] или [Iiı], ẞ или (ß|ẞ|SS|S-S|ss|SSS|SZ), ё или (е|ё).

Пример генератора, который генерирует регулярку для всех вариантов на расстоянии 1 по Левенштейну: https://gist.github.com/dobrokot/6150988
Tags:


  • 1
У Норвига на схожую тему было - http://norvig.com/spell-correct.html - но чуть-чуть по-другому, там наоборот из каждого слова в документе пытаемся найти слово из словаря на расстоянии редактирования в 1 или 2 символа от обрабатываемого слова.

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

Да, перестановки встречаются даже чаще чем замены/вставки пропуски. Но это не проблема, добавить перестановки - (a[:i] + a[i+1] + a[i] + a[i+2:])

если все равно качать либу регекспа для питона, не легче ли сразу установить http://lucene.apache.org/pylucene/ и насладжаться кучей плюшек: fuzzy, levenstein-distance, bayesian classifier ...

Это называется deletion neighborhoods и было придумано (правда не в контексте грепа) товарищами Мором и Франкелем 30 лет назад.

Они наверное, даже про UTF-8 не слыхали

Не вижу, чтобы UTF-8 играла существенную роль в данном алгоритме.

любопытно, что когда-то давно Яндекс был препроцессором к Альтависте - генерировал все словоформы и делал запрос типа

каша|каши|кашу|кашей|о каше

  • 1