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

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

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

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

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

Ответ 1

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

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

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

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

Ответ 2

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

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

Ответ 3

Также смотрите: Regex Python (более новая версия, октябрь ') (поиск "нечетких" внутри документ).

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

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

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

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

'Comparison_of_regular_expression_engines'
'regular-expressions.info tools'

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

Ответ 4

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

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

Ответ 5

Считаете ли вы использование lexer?

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

Ответ 6

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