29

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

例如，我想匹配单词“New York”上的一个字符串，前面有一个 2 位数字。困难在于文本来自PDF的OCR，所以我想做一个模糊匹配。我想匹配：

12 New York
24 Hew York
33 New Yobk

和其他“近距离”匹配（在 Levenshtein 距离的意义上），但不是：

aa New York
11 Detroit

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

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

另外，我应该注意，这是我真正想要匹配的一个非常简化的例子，所以我不是在寻找一种蛮力的方法。

编辑添加：

好吧，我的第一个例子太简单了。我的意思不是让人们沉迷于前面的数字——对这个不好的例子感到抱歉。这是一个更好的例子。考虑这个字符串：

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

其中匹配是模糊的。

4

10 回答 10

17

如果您有一种模式，您想找到与文本集合的最佳匹配，您可以尝试q-gram distance。它很容易实现和适应特殊需求。

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

试试这样：

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

如果你这样做了，你可以通过以下方式调整这个算法：

  • 在所有文本（以及搜索前的模式）之前添加q-1特殊字符，因此即使是简短的单词也会得到不错的配置文件。例如New York变成^^NEW YORK$$.
  • 你甚至可以用“x”替换所有辅音，用“o”替换元音等等。以这种方式玩几个字符类，甚至通过将字符组彼此替换来创建超级符号，即CK变为K，或SCH变为$。
  • 当通过 qgram-hit 提高分数时，您可以通过其他方式调整 1 的值，例如text 与 pattern的长度差异。
  • 存储 2 克和 3 克两者，计数时，称重不同。

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

于 2010-11-21T12:55:03.500 回答
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
    }
}
于 2010-11-11T15:20:11.213 回答
3

您可以尝试使用Web 1T 5-gram Version 1和条件似然最大化方法。

如果我没记错的话，Beautiful Data的第 14 章专门介绍了这个数据集以及如何使用它来发现拼写错误等。

于 2010-11-11T15:46:25.137 回答
3

您是否考虑过在 CPAN 上使用Jarkko 的 String::Approx模块？它有agrep算法，但比 Udi 慢得多。

于 2010-11-19T05:14:46.963 回答
2

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

于 2010-11-11T15:20:05.037 回答
2

把问题分成两部分：

  1. 匹配两位数。
  2. 模糊匹配残基与“纽约”。

在示例中，您知道“纽约”由 2 个单词组成；您也许可以利用它来更轻松地消除“底特律”（但不一定是“旧金山”）之类的替代方案。

毕竟，您甚至可以使用“ String::Approx ”，尽管它提到：

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

（我的 Perl 无法通过 CPAN 找到 Text::PhraseDistance - 其他的可用并安装好。）

于 2010-11-11T15:20:39.107 回答
2

好吧，您可以通过与限制进行比较来缩小您的候选人范围，Text::Levenshtein以获得编辑距离和 grepping。

但是另一个想法是，您可以采用正确的形式并创建一个哈希键，从指向正确形式的未遂事件中键入，以便这些也可能成为候选者。

对于正则表达式，您可能必须使用实验代码部分，可能是这样的：

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

尽管在这种情况下，您可能必须为每个适当的值设置一个正则表达式。您可能需要一些标志来指示您何时错过了目标。

于 2010-11-11T15:23:41.327 回答
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+)"位可选，因此您可以了解它的要点。为此，您可能需要使用命名捕获和(?:)非捕获组。我不想深入研究所有这些，只是想帮助您了解我将如何处理这个问题。

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

于 2010-11-15T01:40:13.313 回答
1

尽管您指定了 perl，但 R 中内置了一个有用的算法，可以实现 Levenshtein 编辑距离。

agrep()

此命令还允许使用任何正则表达式或模式进行匹配。我建议你看看它。http://stat.ethz.ch/R-manual/R-devel/library/base/html/agrep.html

于 2010-11-19T05:09:12.580 回答
1

Python 正则表达式模块提供了一种在正则表达式中进行模糊匹配的方法：

https://pypi.org/project/regex/（寻找近似“模糊”匹配）

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,')

但是给它一些更多的调整（例如，你可以为每个捕获组指定最大错误数）你应该能够达到你的目标。

于 2019-11-28T16:53:51.007 回答