Нечеткие регулярные выражения - PullRequest
Новая
       29

Нечеткие регулярные выражения

46 голосов
/ 28 февраля 2010

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

Теперь мне нужно сопоставить строки с простыми регулярными выражениями, такими как TV Schedule for \d\d (Jan|Feb|Mar|...). Это означает, что строка TV Schedule for 10 Jan должна возвращать 0, а T Schedule for 10. Jan должна возвращать 2.

Это можно сделать, сгенерировав все строки в регулярном выражении (в данном случае 100x12) и найти лучшее совпадение, но это не представляется практичным.

У вас есть идеи, как сделать это эффективно?

Ответы [ 6 ]

24 голосов
/ 04 марта 2010

Я обнаружил библиотеку TRE , которая, кажется, способна выполнять нечеткое сопоставление регулярных выражений. Пример: http://hackerboss.com/approximate-regex-matching-in-python/ Это только поддерживает вставку, удаление и замену все же. Нет транспозиции. Но я думаю, это работает нормально.

Я попробовал сопроводительный инструмент agrep с регулярным выражением в следующем файле: 

TV Schedule for 10Jan
TVSchedule for Jan 10
T Schedule for 10 Jan 2010
TV Schedule for 10 March
Tv plan for March

и получил 

$ agrep -s -E 100 '^TV Schedule for \d\d (Jan|Feb|Mar)$' filename
1:TV Schedule for 10Jan
8:TVSchedule for Jan 10
7:T Schedule for 10 Jan 2010
3:TV Schedule for 10 March
15:Tv plan for March

Большое спасибо за все ваши предложения.

6 голосов
/ 27 октября 2014

См. Также: регулярное выражение Python (более новая версия, октябрь '14 ) (поиск «нечеткий» внутри документа).

Если вы не парень Python (как и я), вы можете скомпилировать свой код в C (exe / dll). Тогда вы сможете использовать свою dll даже из старого доброго vb6 (и тому подобного).

Другие библиотеки на выбор:

  • TRE / agrep ('классический, хороший, старый и быстрый) (ищите' agrep Performace '), но вам нужно написать регулярное выражение, совместимое с POSIX (ищите' регулярные выражения info posix ') Конечно, все библиотеки / примеры, использующие TRE, имеют это ограничение (ищите «примерное совпадение регулярных выражений hackerboss в python»). Для больших данных: найдите «Быстрая реализация алгоритма agrep в CUDA».
  • FREJ (Java) - некоторые (дополнительные) ограничения (например, не смотреть вперед / смотреть назад)
  • fuzzy-wuzzy (на основе Python) - стоит посмотреть, не проверено ...

Искать также по:

  • Comparison_of_regular_expression_engines '
  • 'инструменты регулярных выражений.info'

(извините за невозможность опубликовать реальные ссылки)

4 голосов
/ 12 апреля 2013

Я просто использую модуль regex : «Альтернативный модуль регулярных выражений, чтобы заменить re.» Он знаком с re, но включает опции нечеткого сопоставления, а также несколько других улучшений re.

Для двоичных файлов Windows см. этот ресурс .

3 голосов
/ 28 февраля 2010

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

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

1 голос
/ 28 февраля 2010

Рассматривали ли вы использовать лексер ?

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

0 голосов
/ 18 сентября 2016

Я начал реализовывать инструмент Java под названием prex для приблизительного сопоставления регулярных выражений. Инструмент определяет, как далеко строка s совпадает с регулярным выражением r , т.е. сколько вставок, удалений и подстановок в s как минимум требуются (минимальная стоимость), чтобы полученная строка s ' была приемлема для r . Если вы заинтересованы, вы можете проверить код из https://github.com/julianthome/prex. Я был бы очень рад получить некоторые отзывы. Обратите внимание, что этот подход все еще немного медленный, но я в настоящее время включаю некоторую эвристику для улучшения его производительности.

...