模糊正则表达式

Question

在我的工作中,我得到了很好的结果,使用了近似字符串匹配算法,如Damerau-Levenshtein距离,使我的代码不易受到拼写错误的影响.

现在我需要将字符串与简单的正则表达式匹配TV Schedule for \d\d (Jan|Feb|Mar|...).这意味着字符串TV Schedule for 10 Jan应返回0,同时T Schedule for 10. Jan应返回2.

这可以通过在正则表达式中生成所有字符串(在这种情况下为100x12)并找到最佳匹配来完成,但这并不实用.

您有任何想法如何有效地做到这一点？

Answer 1

我找到了TRE库,它似乎能够完全模糊匹配正则表达式.示例:http://hackerboss.com/approximate-regex-matching-in-python/ 但它仅支持插入,删除和替换.没有换位.但我想这样可行.

我在以下文件中使用regexp尝试了附带的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

非常感谢你的所有建议.

Answer 2

另请参阅:Python正则表达式(更新版本,2014年10月)(在文档中搜索"模糊").

如果你不是Python人(我也不是),你可以将代码编译为C(exe/dll).那么你甚至可以从优秀的旧版vb6(等等)中使用你的dll.

其他库可供选择:

• TRE/agrep('经典,好,旧,快)(搜索'agrep performace'),但你需要编写POSIX兼容的正则表达式(搜索'正则表达式信息posix')当然,使用TRE的所有库/示例都有这个限制(在python中搜索'hackerboss近似正则表达式匹配').对于海量数据:搜索"agrep算法的快速CUDA实现".
• FREJ(Java) - 一些(更多)限制(例如,没有向前看/ 向后看)
• fuzzy-wuzzy(基于Python) - 值得一看,未经测试......

搜索还:

• 'Comparison_of_regular_expression_engines'
• 'regular-expressions.info工具'

(抱歉无法发布实际链接)