logo标签列表

模糊正则表达式

regexperlfuzzy-comparison
30
我正在寻找一种使用正则表达式进行模糊匹配的方法。我想使用Perl，但如果有人能推荐任何可以做到这一点的方式，那将很有帮助。
例如，我想在一个由PDF的OCR生成的文本中匹配包含以两位数字开头的“纽约”单词的字符串。困难在于我想进行模糊匹配。我希望匹配：
12 New York
24 Hew York
33 New Yobk

还有其他“接近”匹配（按Levenshtein距离的意义），但不包括：

aa New York
11 Detroit
显然，我需要指定匹配的允许距离（“模糊度”）。
据我了解，我不能使用Perl模块String::Approx来做到这一点，因为我需要在我的匹配中包含正则表达式（以匹配前面的数字）。
此外，我应该注意，这只是我真正想要匹配的非常简化的示例，所以我不希望采用蛮力方法。
编辑后添加：
好吧，我的第一个示例太简单了。我并不是想让人们在前面的数字上卡住——对于糟糕的例子感到抱歉。以下是一个更好的例子。考虑这个字符串： ASSIGNOR, BY MESHS ASSIGN1IBNTS, TO ALUSCHALME&S MANOTAC/rURINGCOMPANY, A COBPOBATlOH OF DELAY/ABE. 实际上它表示： ASSIGNOR, BY MESNE ASSIGNMENTS, TO ALLIS-CHALMERS MANUFACTURING COMPANY, A CORPORATION OF DELAWARE 我需要提取短语"ALUSCHALME&S MANOTAC/rURINGCOMPANY"和"DELAY/ABE"。（我意识到这可能看起来像疯狂。但我是个乐观主义者。）通常，模式看起来像这样： /Assignor(, by mesne assignments,)? to (company name), a corporation of (state)/i 其中匹配是模糊的。
嘿，那很容易：使用agrep：http://www.tgries.de/agrep/ 检查它的许可证是否可以劫持和使用源代码。 - towi
@tchrist：称其为系统二进制文件有什么问题吗？它是一个稳定的、老派的UNIX实用程序... - Charles Stewart
@Charles，我对那个想法没有问题，但很多人有意见。 - tchrist
如果您正在进行OCR，您应该考虑是否可以添加用户词典。听起来您已经有了一个重要但被错误识别的单词列表。 - Ben Jackson
@Ben：谢谢你的提示。可惜我拿到数据时OCR已经完成了，我只有文本文件。 - itzy
显示剩余5条评论
10个回答
17
如果您有一个模式要在文本集合中找到最佳匹配，可以尝试使用q-gram距离。它非常易于实现和适应特殊需求。
第二个描述在这里实际上是有帮助的，因为模式和文本应该相当长。q-gram距离不适用于像"York"这样的单词，但如果您的典型模式是整个地址，那么应该没问题。
请按照以下方式尝试：
- 将您的文本和模式转换为缩小字符集（例如仅大写字母），去除所有符号并将其变成一个单词（单词之间只有一个空格），所有符号替换为“#”或其他东西。 - 选择一个要使用的q-gram长度。尝试3或2。我们称其为q = 3。 - 然后，对每个文本建立一个qgram-profile： - 将每个文本分成q-words，即NEW_YORK变成[NEW, EW_, W_Y, _YO, ORK]，并将其存储在每个文本中。 - 如果要搜索模式，则执行相同操作， - 循环遍历您的文本-qgram-database， - 对于每个模式/文本对，请计算相同的qgrams数目。 - 每次击中都会将得分提高1分。 - 具有最高分数的文本是您的最佳匹配。
如果您这样做，可以通过以下方式调整此算法：
- 在搜索之前，将所有文本（以及模式）附加到q-1个特殊字符，以便即使是短单词也会得到合理的轮廓。例如，“New York”变成“^^NEW YORK $$”。 - 您甚至可以尝试将所有辅音替换为"x"，将元音替换为"o"等等，以玩弄几个字符类别，或者通过将一组字符替换为另一个字符来创建超级符号，即CK变成K，SCH则变成$。 - 当通过qgram-hit提高分数时，您可以按其他内容（例如文本与模式之间的长度差异）调整1的值。 - 存储2-grams和3-grams，并在计算时进行不同的加权。
请注意，此算法以基本形式进行搜索时运行时间不佳，即O（|T | * |P |）（其中| T | 和| P | 是您的文本和模式的总长度）。这是因为我描述了您遍历所有文本，然后遍历模式。因此，它只适用于中等规模的文本库。如果您考虑一些想法，可以在q-gram上创建高级索引结构（可能使用哈希表），因此对于巨大的文本库也可能实用。
3
正则表达式有特定的规则，不是为了做你想做的事情而设计的。最好的方法是进行两次操作。使用正则表达式去除数字，然后使用一个模块来匹配你所需的内容。
假设你的输入是文件中的行，可以采用以下方式：
while( my $line = <$fh> ) {
    chomp $line;

    # do we have digits?
    if( $line =~ /^\d+/ ) {
         # removes spaces and digits from the beginning of the line
         $line =~ s/^[\d\s]*//g;

         # use your module to determine if you have a match in the remaining text.
         if( module_match ) {
             # do something
         }
         else {
             #no match
         }
    }
    else {
        # no match
    }
}
3
你有没有考虑使用 CPAN 上的 Jarkko's String::Approx 模块？它包含了 agrep 算法，但比 Udi 的算法慢得多。
3
你可以尝试使用类似 Web 1T 5-gram Version 1 和条件似然极大化方法。
如果我没记错的话，Beautiful Data 的第14章专门讲解了这个数据集以及如何使用它来发现拼写错误等问题。
2

你可以使用Text::Levenshtein缩小候选人范围，以获取编辑距离，并通过与限制的比较来进行筛选。

另一个想法是，您可以取正确的形式并创建一个哈希表，以近似匹配为键指向正确的形式，这样那些近似匹配也可能成为候选人。

对于正则表达式，您可能需要使用实验性的代码部分，例如：

m/ (?i: [new] | \p{Alpha} (?{ $misses++ }) ){2,4}
   \s+
  (?i: [york] | \p{Alpha} (?{ $misses++ }) ){3,5}
 /x

在这种情况下，您可能需要针对每个正确值使用一个正则表达式。您可能希望设置某个标志来指示您是否错过了目标。

在Perl中，“grep”具有特定的含义（与Unix的“grep”松散相关），似乎不太可能在此上下文中有所帮助。您可能需要重新表达您的答案。 - Jonathan Leffler
2

你是否考虑过使用两个阶段的测试，首先使用正则表达式来强制要求[0-9]{2,2} (.*)，然后捕获剩余文本并对其进行模糊匹配？试着将问题看作是正则表达式和模糊字符串的交集。

2
将问题分为两个部分：
  1. 匹配双位数。
  2. 模糊匹配剩余部分与“纽约”。
在这个例子中，你知道“纽约”由两个单词组成；你可以利用这一点更容易地消除“底特律”等选项（但不一定是“旧金山”）。
你甚至可以尝试使用“String::Approx”，尽管它提到了以下内容：

...CPAN 中的 Text::Levenshtein 和 Text::LevenshteinXS 模块。还请参阅 Text::WagnerFischer 和 Text::PhraseDistance。

（我的 Perl 无法通过 CPAN 找到 Text::PhraseDistance - 其他模块都可用并安装正常。）
那些真的很有用，谢谢！顺便问一下，StackOverflow是如何解析@somebody提醒的？它只是使用/\@(\w+)/，还是/\@(\S+)/或/\@([\w\s]+)\s*\pP/等等？换句话说，它是如何知道在寻找用户名时何时停止扫描的？这个扫描代码是否可用？ - tchrist
@tchrist：我不确定解析是在哪里完成的 - 可能不是在客户端代码中（因此对我们不可见）。 它使用名称的前三个字母并将其与先前的评论等进行匹配。 我不缩写以最小化去错误地联系到错误的人。 我认为如果您查看SO博客（一年或更久以前），您会发现有关它如何工作的讨论。 - Jonathan Leffler
谢谢，但我不认为这些允许正则表达式。我想我可以尝试将距离与正则表达式结合使用，但坦白地说，我不认为这种方法能处理我上面提到的第二个例子。 - itzy
@itzy：是的，你的需求比第一版问题所暗示的要复杂得多。我假设扫描到的字符串是真实的例子（或者足够接近而我无法分辨出差异）。你只有“ASSIGNOR”、“BY”、“TO”、“A”、“OF”这几个词来分析 - 我也不确定这些词不会被错误地识别。很多事情都取决于单词的可能值列表。例如，在这个例子中，“OF”后面跟着一个州名。但如果一个公司叫做“爱达荷的艾伦”（当然是特拉华州的公司），那么你就会再次遇到问题。 - Jonathan Leffler
2

经验法则：当你需要去Stack Overflow问“如何在一个正则表达式中实现X？”时，你应该考虑使用不止一个正则表达式来实现X。

根据您的编辑，我建议这样做：

while(<>) {
  chomp;
  if(/assignor, by (\w+) (\w+), to (\w+), a (\w+) of (\w+)/i) {
    # now use String::Approx to check that $1, $2, $3, $4, and $5 match
  } else {
    warn "Errors!\n";
  }
}

我并没有把", by (\w+) (\w+)"部分作为可选项，以简化正则表达式并让你能够理解其要点。为了做到这一点，您可能需要使用命名捕获和(?:)非捕获组。我不想深入探讨所有这些内容，只是想帮助您了解我如何处理这个问题。

记住：如果您必须问“我如何在一个正则表达式中完成所有操作？”那么您应该停止尝试在单个正则表达式中完成所有操作。

此外，您可能需要检查“assignor”的拼写，但如果您完成其余部分，这应该是非常容易添加的。另外，您可能希望将正则表达式中的所有空格更改为\s+（或者也许是 +），以防有人意外输入了两个空格。 - Chris Lutz
谢谢。实际上我不是在寻找一行代码就能解决的东西。我写出那样的模式只是为了让大家对它的一般外观有所了解，但我会接受任何方法。我想遵循你的建议，但基本问题在于可能会有拼写错误——没有保证“buy”或“to”是正确的。我希望有一个匹配可以允许一些错误（模糊匹配），但不能太多。我认为这就是使这个问题如此困难的原因。我希望有人知道一些适合这种类型问题的软件包。 - itzy
1
1
Python正则表达式模块提供了一种在正则表达式内进行模糊匹配的方法：
请查看https://pypi.org/project/regex/（搜索Approximate“fuzzy” matching）。
The fuzziness of a regex item is specified between “{” and “}” after the item.

Examples:

foo match “foo” exactly
(?:foo){i} match “foo”, permitting insertions
(?:foo){d} match “foo”, permitting deletions
(?:foo){s} match “foo”, permitting substitutions
(?:foo){i,s} match “foo”, permitting insertions and substitutions
(?:foo){e} match “foo”, permitting errors
If a certain type of error is specified, then any type not specified will not be permitted.

In the following examples I’ll omit the item and write only the fuzziness:

{d<=3} permit at most 3 deletions, but no other types
{i<=1,s<=2} permit at most 1 insertion and at most 2 substitutions, but no deletions
{1<=e<=3} permit at least 1 and at most 3 errors
{i<=2,d<=2,e<=3} permit at most 2 insertions, at most 2 deletions, at most 3 errors in total, but no substitutions

"所以你可以写，例如："
import regex, pprint

m = regex.compile( r'(?:Assignor(, by mesne assignments,)? to (company name), a corporation of (state)){e}', regex.IGNORECASE ).match('ASSIGNOR, BY MESHS ASSIGN1IBNTS, TO ALUSCHALME&S MANOTAC/rURINGCOMPANY, A COBPOBATlOH OF DELAY/ABE.')

pprint.pprint(m)
pprint.pprint(m.groups())

这并不能立即生效，结果将会是：

<regex.Match object; span=(0, 71), match='ASSIGNOR, BY MESHS ASSIGN1IBNTS, TO ALUSCHALME&S MANOTAC/rURINGCOMPANY,', fuzzy_counts=(45, 0, 0)>
(', BY MESHS ASSIGN1IBNTS', ' ALUSCHALME&', 'PANY,')

但是如果进行一些微调（例如，您可以为每个捕获组指定最大错误数），您应该能够达到您的目标。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接