50

在我的工作中，我使用了近似字符串匹配算法（例如 Damerau-Levenshtein 距离）来使我的代码不易受到拼写错误的影响，取得了很好的效果。

现在我需要将字符串与简单的正则表达式进行匹配，例如TV Schedule for \d\d (Jan|Feb|Mar|...). 这意味着字符串TV Schedule for 10 Jan应该返回 0 而T Schedule for 10. Jan应该返回 2。

这可以通过在正则表达式中生成所有字符串（在本例中为 100x12）并找到最佳匹配来完成，但这并不实用。

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

4

6 回答 6

27

我找到了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

非常感谢您的所有建议。

于 2010-03-04T10:54:24.653 回答
9

另请参阅：Python regex（较新版本，14 年 10 月）（在文档中搜索“fuzzy”）。

如果您不是 Python 人（我也不是），您可以将代码编译为 C（exe/dll）。然后，您甚至可以从旧的 vb6（等）使用您的 dll。

其他库可供选择：

  • TRE/agrep ('classic, good, old and fast) (搜索 'agrep performace'), 但你需要编写 POSIX 兼容的正则表达式 (搜索'regular expressions info posix') 当然，所有使用 TRE 的库/示例都有此限制（搜索“hackerboss 在 python 中近似正则表达式匹配”）。对于海量数据：搜索“agrep 算法的快速 CUDA 实现”。
  • FREJ (Java) - 一些（更多）限制（例如，不向前看/向后看）
  • 模糊-wuzzy（基于Python）-值得一看，未经测试...

也搜索：

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

（抱歉无法发布真实链接）

于 2014-10-26T23:23:53.847 回答
4

我只是使用regex模块：'替代正则表达式模块，替换 re。' 它提供了熟悉re但包括模糊匹配的选项，以及对re.

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

于 2013-04-12T15:46:39.237 回答
3

这是有关您所问问题的资源。对于一家公司来说，这有点像预告片。更有用的可能是这篇论文。我看到了一个受论文启发的实现，它可以在大型数据集上进行模糊搜索，偏向于特殊语言（例如阿拉伯语与英语）。

一般来说，您将无法按照您的要求进行操作。您可以通过用等价类替换字符来使正则表达式搜索变得模糊，或者您可以在数据库中搜索由 Levenshtein 距离定义的近似匹配。试图扩展正则表达式后面的 (n)DFA 以包含距离上的近似匹配将很快变得非常复杂。

于 2010-02-28T16:33:06.267 回答
1

您是否考虑过使用词法分析器？

我从来没有真正使用过，所以我帮不上什么忙，但听起来很合适！

于 2010-02-28T16:18:47.827 回答
0

我开始实现一个名为 prex 的 Java 工具，用于近似正则表达式匹配。该工具确定字符串s与正则表达式r匹配的距离，即至少需要对s进行多少次插入、删除和替换（最小成本），以使结果字符串s'可以被r接受。如果您有兴趣，可以从https://github.com/julianthome/prex查看代码。我很乐意得到一些反馈。请注意，该方法仍然有点慢，但我目前正在结合一些启发式方法来提高其性能。

于 2016-09-18T12:36:36.610 回答