模糊正则表达式

Question

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

作为一个例子，我想匹配一个字符串上的单词“纽约”前面有一个2位数的数字。因为文本来自PDF的OCR，所以我想要做一个模糊匹配。我想匹配：

12 New York 
24 Hew York 
33 New Yobk 

等“亲密”的比赛（在莱文斯坦距离感），但不是：

aa New York 
11 Detroit 

很显然，我需要指定允许距离（“模糊性”）。

据我了解，我不能使用String::Approx Perl模块来做到这一点，因为我需要在我的比赛正则表达式（匹配前面的数字）。

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

编辑补充：

好了，我的第一个例子是太简单了。我的意思并不是让人们挂上前面的数字 - 抱歉，这个坏例子。这是一个更好的例子。考虑这个字符串：

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 &小号MANOTAC/rURINGCOMPANY” 和“DELAY/ABE ”。 （我知道这看起来是疯狂的，但我是个乐观主义者。）一般情况下，该模式将是这个样子：

/Assignor(, by mesne assignments,)? to (company name), a corporation of (state)/i

其中，匹配是模糊的。

Answer 1

如果你有一个模式你想找到针对文本集合最佳匹配你可以尝试Q-克距离。这是很容易实施和采取特殊需求。

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

试试这样说：

• 改变你的文字和图案为缩减的字符集，如大写，只有，剥离，wordifying（单词之间有一个空格）替换为“＃”或所有符号一些东西。
• 选择一个q-gram长度来处理。尝试3或2.我们称之为q=3。
• 比，建立一个qgram配置文件每个文本：
• 将每个文本分成q字，即。 NEW_YORK变成[NEW, EW_, W_Y, _YO, ORK]，将其与每个文本一起存储。
• ，如果你搜索你模式那么，你
• 循环通过你的文章，qgram数据库和
  • 计数每个模式/文本 -pair多少做你的模式相同， qgrams是一样的。
  • 每一击都会由1
• 的文本最高分数（S）提高分数是你最好的命中。

如果你这样做，你可以调整这个算法是：

• 在前面加上你的文本（也搜索之前的模式），与q-1特殊字符，所以即使你的短的话会得到一个体面个人资料。例如New York变为^^NEW YORK$$。
• 你甚至可以用“x”和“o”等替换所有的辅音。玩弄一对夫妇字符类这种方式，甚至通过一个其他创建的角色的替换组超级符号，即CK成为ķ，或SCH成为$。
• 当通过qgram-hit提高分数时，您可以通过其他东西来调整值1，如长度差文本与模式。
• 同时存储2克和3克，计数时称重不同。

---

注意，该算法在这里所描述的基本形式的搜索过程中没有一个良好的运行时间，即O(|T|*|P|)（与|T|和|P|您文本总长度和模式）。这是因为我描述了你循环了所有的文本，然后遍历了你的模式。因此，这仅适用于中型文本 -base。如果你花费一些思想，你可以在q-gram上使用指数结构来创建高级的10，所以这对于庞大的文本也是可行的。

Answer 2

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

Answer 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 
    } 
} 

Answer 4

独立的问题分为两个部分：

1. 匹配的双位数字。
2. 模糊匹配“纽约”的残留物。

在这个例子中，你知道'纽约'由2个单词组成;你可能可以利用它来更容易地消除“底特律”（但不一定是“旧金山”）等替代品。

你甚至可以毕竟使用“String::Approx”，但它提到：

...文本::莱文斯坦和文本:: LevenshteinXS在CPAN模块。另请参阅Text :: WagnerFischer和Text :: PhraseDistance。

（我的Perl无法通过CPAN找到文本:: PhraseDistance - 别人都可以，并安装好。）

Answer 5

那么您可以将候选人缩小与Text::Levenshtein得到编辑距离和grepping通过与极限进行比较。

但是，另一个想法是，你可以采取正确的形式，并创建一个从几乎错过指向正确的形式键入散列，以便这些也可能成为候选人。

对于正则表达式，你可能将不得不使用实验代码部分，也许是这样的：

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

虽然在这种情况下，你可能必须有正确的每一个价值正则表达式。您可能需要一些标志，指示您何时错过了目标。

Answer 6

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

如果我没有记错，章Beautiful Data 14是专门用于该数据集以及如何使用它来发现拼写错误等经验

Answer 7

规则：当你有去堆栈溢出，并询问“如何我可以在一个正则表达式中做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+)"位可选，以简化正则表达式，所以你可以得到它的要点。要做到这一点，您可能需要使用命名捕获和非捕获组。我不想深究这一切，只是想帮助你理解我将如何解决这个问题。

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

Answer 8

虽然您指定了perl，但在R中内置了实现Levenshtein编辑距离的有用算法。

agrep() 

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

Answer 9

你看过CPAN上的Jarkko’s String::Approx模块吗？它有agrep算法，但比Udi慢得多。