模糊正则expression式

在我的工作中,我使用了近似的string匹配algorithm,如Damerau-Levenshtein距离,使我的代码更容易受到拼写错误的影响。

现在我需要匹配string对简单的正则expression式,例如TV Schedule for \d\d (Jan|Feb|Mar|...) 。 这意味着TV Schedule for 10 Jan的stringTV Schedule for 10 Jan应该返回0,而TV Schedule for 10 Jan T Schedule for 10. Jan应该返回2。

这可以通过生成正则expression式中的所有string(在本例中为100×12)并find最佳匹配来完成,但是这并不实际。

你有什么想法如何有效地做到这一点?

6 Solutions collect form web for “模糊正则expression式”

我find了TRE库 ,巫缝可以做正则expression式的模糊匹配。 例如: http : //hackerboss.com/approximate-regex-matching-in-python/它只支持插入,删除和replace。 没有换位。 但我想这个工作正常。

我试着在下面的文件中使用正则expression式的附带的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 

非常感谢您提出的所有build议。

我只是使用regex模块 :'替代正则expression式模块,以取代'。 它提供了对re的熟悉,但包括模糊匹配的选项,以及对re其他一些改进。

对于Windows二进制文件,请参阅此资源 。

另请参阅: Python正则expression式(更新的版本,2014年10月 )(在文档中search“模糊”)。

如果你不是一个Python家伙(不是我),你可以编译你的代码到C(exe / dll)。 那么你甚至可以使用你的DLL甚至从旧的vb6(等)。

其他图书馆可供select:

  • TRE / agrep ('classic,good,old and fast)(search'agrep performace'),但是你需要编写POSIX兼容的正则expression式(search'正则expression式info posix')当然,所有使用TRE的库/例子这个限制(search'hackerboss近似正则expression式在Python中匹配')。 对于海量数据:search“快速CUDA实现的agrepalgorithm”。
  • FREJ (Java) – 一些(更多)限制(例如,不要向前看/看后面)
  • 模糊 – 模糊 (基于Python) – 值得一看,没有testing…

还search:

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

(对不起,不能发表真实的链接)

这是你问的问题的资源。 对于一家公司来说,这有点夸张。 本文可能更有用。 我已经看到一篇文章的启发,可以做一个模糊的search,在一个大型的数据集上有特殊的语言偏好(如阿拉伯语和英语)。

一般来说,你将无法做你所问的。 您可以通过用等价类replace字符来进行正则expression式search,也可以在数据库中search由Levenshtein距离定义的近似匹配。 尝试将正则expression式后面的(n)DFA扩展为包含近距离匹配,将很快变得不可能非常复杂。

你有没有考虑过使用词法分析器 ?

我从来没有真正使用过,所以我不能帮上太多的忙,但听起来很合适!

我开始实现一个称为prex的Java工具,用于近似正则expression式匹配。 该工具确定string与正则expression式r的匹配程度, 至less需要多less个插入,删除和replace(最小代价),使得得到的strings'可被r接受。 如果您有兴趣,可以从https://github.com/julianthome/prex查看代码。 我会很乐意得到一些反馈。 请注意,这种方法还是有点慢,但我目前采用了一些启发式方法来提高性能。