模糊正则表达式

Question

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

作为一个例子,我想匹配一个字母"纽约",前面加一个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

匹配是模糊的.

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和
  • 计算每个模式/文本 -对多少个qgrams是相同的.
  • 每次击中都会将得分提高1.
• 得分最高的文本是您最好的点击率.

如果你这样做,你可以通过以下方式调整此算法:

• 在你的所有文本(以及搜索前的模式)之前加上q-1特殊的字符,所以即使你的短文也会得到一个不错的个人资料.例如New York变成^^NEW YORK$$.
• 您甚至可以用"x"替换所有辅音,用"o"替换元音等等.以这种方式玩几个字符类,甚至通过将一组字符替换为另一个来创建超级符号,即CK变为K,或SCH变为$.
• 当通过qgram-hit提高分数时,您可以通过其他方式调整1的值,例如文本与模式的长度差异.
• 存储2克和3克两者,并且在计数时,然后以不同的方式称重.

请注意,该算法在这里描述的基本形式的搜索,即在没有一个良好的运行时间O(|T|*|P|)(与|T|和|P|您的总长度的文字和图案).这是因为我描述你遍历所有的文本,然后在你的格局.因此,这仅适用于中等大小的文本库.如果你多花些心思,你可以创建一个先进的索引结构在Q-克(也许使用哈希表),所以这可能是巨大的实际文本 -bases为好.