regex - 模糊正则表达式

Question

我正在寻找一种使用正则表达式进行模糊匹配的方法。 我想使用 Perl，但如果有人可以推荐任何方法来做到这一点，那将会很有帮助。

作为示例，我想要匹配前面带有 2 位数字的单词“New York”上的字符串。困难来了，因为文本来自 PDF 的 OCR，所以我想做一个模糊匹配。我想匹配:

12 New York
24 Hew York
33 New Yobk

以及其他“接近”的匹配(在编辑距离的意义上)，但不是:

aa New York
11 Detroit

显然，我需要指定匹配的允许距离(“模糊度”)。

据我了解，我不能使用String::Approx Perl模块来执行此操作，因为我需要在匹配中包含正则表达式(以匹配前面的数字)。

另外，我应该注意到，这是我真正想要匹配的一个非常简单的示例，因此我并不是在寻找一种暴力方法。

编辑添加:

好吧，我的第一个例子太简单了。我并不是想让人们对前面的数字感到困惑——对这个不好的例子感到抱歉。这是一个更好的例子。考虑这个字符串:

分配器，通过网格分配 1IBNTS，分配给 ALUSCHALME&S MANOTAC/rURINGCOMPANY，延迟/ABE 的 COBPOBATlOH。

这实际上说的是:

由 MESNE ASSIGNMENTS 委托(delegate)给 ALLIS-CHALMERS MANUFACTURING COMPANY, A CORPORATION OF DELAWARE

我需要做的是提取短语“ALUSCHALME&S MANOTAC/rURINGCOMPANY”和“DELAY/ABE”。 (我意识到这可能看起来很疯狂。但我是一个乐观主义者。)一般来说，该模式看起来像这样:

/Assignor(, 通过中间赋值,)?致(公司名称)，(州)/i 的一家公司

匹配模糊。

Answer 1

如果您有一个模式，想要针对文本集合找到最佳匹配，您可以尝试q-gram距离。它很容易实现并适应特殊需求。

您的第二个描述实际上在这里很有帮助，因为模式和文本应该相当长。 q-gram 距离不适用于“York”等单词，但如果您的典型模式是整个地址，那应该没问题。

尝试这样:

• 将您的文本和模式转换为简化的字符集，例如仅大写、剥离、单词化(单词之间有一个空格)所有符号替换为“#”或其他内容。
• 选择要使用的 q-gram 长度。尝试 3 或 2。我们称之为 q=3。
• 然后，为每个文本构建一个qgram-profile:
• 将每个文本分割成q个单词，即。 NEW_YORK 变为 [NEW, EW_, W_Y, _YO, ORK]，将其与每个文本一起存储。
• 如果您搜索您的模式，那么您会对您的模式执行相同的操作，
• 循环遍历你的text-qgram-database并且
  • 计算每个模式/文本对有多少qgram是相同的。
  • 每击中一次，分数就会提高 1。
• 得分最高的文本就是您的最佳命中。

如果您这样做了，您可以通过以下方式调整此算法:

• 在所有文本(以及搜索之前的模式)前面添加 q-1 特殊字符，这样即使您的简短单词也会获得不错的配置文件。例如，New York 变为 ^^NEW YORK$$。
• 您甚至可以尝试将所有辅音替换为“x”，将元音替换为“o”等。以这种方式尝试使用几个字符类，甚至通过替换一组字符来创建 super 符号，即CK变为< em>K，或 SCH 变为 $。
• 当通过 qgram-hit 提高分数时，您可以通过其他因素调整 1 的值，例如文本与模式的长度差异。
• 同时存储 2 克和 3 克，并在计数时以不同的方式称重。

<小时/>

请注意，这里描述的基本形式中的该算法在搜索期间没有良好的运行时间，即 O(|T|*|P|) (使用 |T| 和 |P| 您的文本和图案的总长度。这是因为我描述了您循环遍历所有文本，然后遍历您的模式。因此，这仅适用于中等大小的文本库。如果您花点心思，您可以在 q-gram 上创建高级索引结构(也许使用哈希表)，因此这对于大型文本库也可能很实用.