Нечеткие регулярные выражения
В своей работе я с отличными результатами использовал приближенные алгоритмы сопоставления строк, такие как расстояние Дамерау – Левенштейна, чтобы сделать мой код менее уязвимым к орфографическим ошибкам.
Теперь мне нужно сопоставить строки с простыми регулярными выражениями, такими как TV Schedule for \d\d (Jan|Feb|Mar|...), Это означает, что строка TV Schedule for 10 Jan должен вернуть 0 пока T Schedule for 10. Jan должен вернуть 2.
Это можно сделать, сгенерировав все строки в регулярном выражении (в данном случае 100x12) и найти лучшее соответствие, но это не представляется практичным.
У вас есть идеи, как сделать это эффективно?
6 ответов
Я нашел библиотеку 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
Большое спасибо за все ваши предложения.
Также смотрите: регулярное выражение Python (более новая версия, октябрь '14) (поиск "нечеткий" внутри документа).
Если вы не парень Python (как и я), вы можете скомпилировать свой код в C (exe/dll). Тогда вы сможете использовать свой dll даже из старого доброго vb6 (и тому подобное).
Другие библиотеки на выбор:
- TRE / agrep ('classic, good, old and fast) (ищите' agrep performancemace'), но вам нужно написать POSIX-совместимое регулярное выражение (ищите' posix регулярных выражений '). Конечно, все библиотеки / примеры, использующие TRE, имеют это ограничение (ищите "примерное совпадение регулярных выражений в python"). Для больших данных: поиск "Быстрая реализация алгоритма agrep в CUDA".
- FREJ (Java) - некоторые (более) ограничения (например, не смотреть вперед / смотреть назад)
- fuzzy-wuzzy (на основе Python) - стоит посмотреть, не проверено...
Поиск также для:
- 'Comparison_of_regular_expression_engines'
- "Инструменты регулярных выражений"
(извините за невозможность размещать реальные ссылки)
Я просто использую regex module: 'Альтернативный модуль регулярных выражений, чтобы заменить re.' Это обеспечивает знакомство re но включает в себя варианты нечеткого соответствия, а также несколько других улучшений re,
Для двоичных файлов Windows см. Этот ресурс.
Вот ресурс по вопросу, который вы задаете. Это немного тизер для компании. Более полезной может быть эта статья. Я видел реализацию, основанную на статье, которая могла выполнять нечеткий поиск, ориентированный на специальный язык (например, арабский язык против английского), в большом наборе данных.
В общем, вы не сможете делать то, о чем просили. Вы можете сделать поиск регулярных выражений нечетким, заменив символы классами эквивалентности, или вы можете искать в базе данных близкие совпадения, определенные расстоянием Левенштейна. Попытка расширить (n)DFA за регулярным выражением для включения близких совпадений по расстоянию быстро станет невероятно сложной.
Вы рассматривали возможность использования лексера?
Я никогда не использовал его, поэтому я не могу помочь, но звучит так, как будто он подходит!
Я начал реализовывать инструмент Java под названием prex для приблизительного сопоставления регулярных выражений. Инструмент определяет, насколько далека строка s от соответствия регулярному выражению r, то есть сколько вставок, удалений и подстановок на s по меньшей мере требуется (минимальная стоимость), так что результирующая строка s ' приемлема для r. Если вы заинтересованы, вы можете проверить код с https://github.com/julianthome/prex. Я был бы очень рад получить обратную связь. Обратите внимание, что этот подход все еще немного медленный, но я в настоящее время включаю некоторую эвристику для улучшения его производительности.