Нечеткие регулярные выражения
В моей работе у меня есть с большими результатами используемые приблизительные алгоритмы сопоставления строк, такие как Damerau-расстояние-Левенштейна для создания моего кода менее уязвимым для орфографических ошибок.
Теперь у меня есть потребность к строкам совпадения против простых регулярных выражений такой TV Schedule for \d\d (Jan|Feb|Mar|...). Это означает что строка TV Schedule for 10 Jan должен возвратиться 0 в то время как T Schedule for 10. Jan должен возвратиться 2.
Это могло быть сделано путем генерации всех строк в regex (в этом случае 100x12) и найти лучшее соответствие, но это не делает практичного шва.
У Вас есть какие-либо идеи, как сделать это эффективно?
3 ответа
Я нашел библиотеку TRE, которая, похоже, может делать именно нечеткое соответствие регулярных выражений. Пример: 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
Большое спасибо за все ваши предложения.
Думали ли вы об использовании лексера ?
Я никогда не использовал его, поэтому ничем не могу помочь, но похоже, что он подходит!
Здесь - это ресурс по заданному вами вопросу. Это своего рода тизер для компании. Более полезной могла бы быть эта статья . Я видел реализацию, вдохновленную этой статьей, которая могла бы выполнять нечеткий поиск, ориентированный на специальный язык (например, арабский или английский), в большом наборе данных.
В общем, вы не сможете сделать то, о чем просили. Вы можете сделать поиск по регулярному выражению нечетким, заменив символы классами эквивалентности, или вы можете искать в базе данных близкие совпадения, определяемые расстоянием Левенштейна. Попытка расширить (n) DFA за регулярным выражением, чтобы включить в него близкие по расстоянию, быстро стала бы невероятно сложной.