查找最佳子字符串匹配

Question

我正在寻找一个库或一个使用现有库（^{}，^{}，^{}）的库或方法来查找文本（query）中字符串（query）的最接近匹配

我开发了一种基于difflib的方法，在这个方法中，我将corpus分成大小为n（长度为query）的ngram。在

import difflib
from nltk.util import ngrams

def get_best_match(query, corpus):
    ngs = ngrams( list(corpus), len(query) )
    ngrams_text = [''.join(x) for x in ngs]
    return difflib.get_close_matches(query, ngrams_text, n=1, cutoff=0)

当查询和匹配字符串之间的差异只是字符替换时，它的工作方式与我希望的一样。在

^{pr2}$

但当区别是字符删除时，就不是了。在

query = "ipsum dolor"
corpus = "lorem 1psum dlr sit amet"

match = get_best_match(query, corpus)
# match = "psum dlr si"
# expected_match = "1psum dlr"

有没有一种方法可以获得更灵活的结果大小（对于expected_match）？在

编辑1：

• 此脚本的实际用途是将查询（字符串）与 ocr输出混乱。在
• 正如我在问题中所说的，ocr可能会混淆字符，甚至会错过他们。在
• 如果可能，还应考虑单词之间缺少空格的情况。在
• 最佳匹配是指不包含查询中其他单词的字符。在

编辑2：

我现在使用的解决方案是用(n-k)-grams for k = {1,2,3}扩展ngram，以防止3个删除。它比第一个版本好得多，但是在速度方面没有效率，因为我们要检查的ngram数量是ngram的3倍多。这也是一个不可归纳的解决方案。在

Answer 1

求解的主要途径是使用某种有限状态自动机（FSA）。如果您想获得主题的详细摘要，请查看此dissertation页（PDF链接）。基于误差的模型（包括Levenshtein自动机和传感器，Sergei提到了前者）是解决这一问题的有效方法。然而，随机模型，包括与FSAs集成的各种机器学习方法，是目前非常流行的。在

由于我们关注的是编辑距离（实际上是拼写错误的单词），Levenshtein方法很好而且相对简单。This paper（以及论文；也是PDF）给出了一个不错的基本思想大纲，并明确提到了在OCR任务中的应用。不过，我将回顾一下下面的一些要点。在

基本思想是，您希望构建一个FSA来计算有效字符串和所有字符串，直到某个错误距离（k）。在一般情况下，这个k可能是无限大的，或者是文本的大小，但这对OCR来说基本上是无关的（如果您的OCR甚至可以返回bl*h，其中*是整个文本的其余部分，我建议您找到一个更好的OCR系统）。因此，我们可以从搜索字符串blah的有效答案集中限制regex的类似bl*h。对于您的上下文，一个通用、简单和直观的k可能是字符串的长度（w）减去2。这允许b h成为blah的有效字符串。它也允许bla h，但没关系。另外，请记住，错误可以是您指定的任何字符，包括空格（因此“多字”输入是可解决的）。在

下一个基本任务是建立一个简单的加权传感器。任何OpenFST Python端口都可以做到这一点（here's one）。逻辑很简单：插入和删除增加了权重，而相等增加了输入字符串中的索引。你也可以像Sergei评论链接里的人那样手工编码。在

一旦有了权重和权重的相关索引，就只需排序并返回。计算复杂度应为O（n（w+k）），因为我们将针对文本中每个字符（n）预测最坏情况下的w+k字符。在

从这里，你可以做任何事情。你可以把传感器转换成DFA。您可以通过将文本分解为w+k-gram来并行化系统，这些w+k-gram被发送到不同的进程。您可以开发一个语言模型或混淆矩阵，定义输入集中每个字母存在哪些常见错误（从而限制有效转换的空间和相关FSA的复杂性）。文献是庞大的，而且还在不断增长，所以可能会有很多修改和解决方案（如果不是更多的话）。在

希望它能回答你的一些问题，而不需要给出任何代码。在

Answer 2

我将尝试从查询字符串构建正则表达式模板。然后可以使用模板在语料库中搜索可能与查询匹配的子字符串。然后使用difflib或fuzzyfuzzy检查子字符串是否与查询匹配。在

例如，一个可能的模板将匹配查询的前两个字母中的至少一个，以及查询的最后两个字母中的至少一个，并且在这两个字母之间有大约正确的数量：

import re

query = "ipsum dolor"
corpus = ["lorem 1psum d0l0r sit amet",
          "lorem 1psum dlr sit amet",
          "lorem ixxxxxxxr sit amet"]

first_letter, second_letter = query[:2]
minimum_gap, maximum_gap = len(query) - 6, len(query) - 3
penultimate_letter, ultimate_letter = query[-2:]

fmt = '(?:{}.|.{}).{{{},{}}}(?:{}.|.{})'.format
pattern = fmt(first_letter, second_letter,
              minimum_gap, maximum_gap,
              penultimate_letter, ultimate_letter)

#print(pattern) # for debugging pattern

m = difflib.SequenceMatcher(None, "", query, False)

for c in corpus:
    for match in re.finditer(pattern1, c, re.IGNORECASE):
        substring = match.group()
        m.set_seq1(substring)
        ops = m.get_opcodes()

        # EDIT fixed calculation of the number of edits
        #num_edits = sum(1 for t,_,_,_,_ in ops if t != 'equal')
        num_edits = sum(max(i2-i1, j2-j1) for op,i1,i2,j1,j2 in ops if op != 'equal' )
        print(num_edits, substring)

输出：

^{pr2}$

另一个想法是在构建regex时使用ocr的特性。例如，如果ocr总是正确地获得某些字母，那么当这些字母中有任何一个在查询中时，就在正则表达式中使用其中一些。或者“ocr”混合了，'l'和'i'，但从不替换其他字母，那么如果查询中有一个字母，请在regex中使用[1!il]。在

Answer 3

此函数用于查找可变长度的最佳匹配子字符串。在

该实现将语料库视为一个长字符串，因此避免了对空格和未分隔词的关注。在

代码摘要：1.以step为步长扫描语料库中的匹配值，以找到最大匹配值的近似位置pos。 2.通过调整子串的左/右位置，找到匹配值最高的pos附近的子串。在

from difflib import SequenceMatcher

def get_best_match(query, corpus, step=4, flex=3, case_sensitive=False, verbose=False):
    """Return best matching substring of corpus.

    Parameters
         
    query : str
    corpus : str
    step : int
        Step size of first match-value scan through corpus. Can be thought of
        as a sort of "scan resolution". Should not exceed length of query.
    flex : int
        Max. left/right substring position adjustment value. Should not
        exceed length of query / 2.

    Outputs
       -
    output0 : str
        Best matching substring.
    output1 : float
        Match ratio of best matching substring. 1 is perfect match.
    """

    def _match(a, b):
        """Compact alias for SequenceMatcher."""
        return SequenceMatcher(None, a, b).ratio()

    def scan_corpus(step):
        """Return list of match values from corpus-wide scan."""
        match_values = []

        m = 0
        while m + qlen - step <= len(corpus):
            match_values.append(_match(query, corpus[m : m-1+qlen]))
            if verbose:
                print query, "-", corpus[m: m + qlen], _match(query, corpus[m: m + qlen])
            m += step

        return match_values

    def index_max(v):
        """Return index of max value."""
        return max(xrange(len(v)), key=v.__getitem__)

    def adjust_left_right_positions():
        """Return left/right positions for best string match."""
        # bp_* is synonym for 'Best Position Left/Right' and are adjusted 
        # to optimize bmv_*
        p_l, bp_l = [pos] * 2
        p_r, bp_r = [pos + qlen] * 2

        # bmv_* are declared here in case they are untouched in optimization
        bmv_l = match_values[p_l / step]
        bmv_r = match_values[p_l / step]

        for f in range(flex):
            ll = _match(query, corpus[p_l - f: p_r])
            if ll > bmv_l:
                bmv_l = ll
                bp_l = p_l - f

            lr = _match(query, corpus[p_l + f: p_r])
            if lr > bmv_l:
                bmv_l = lr
                bp_l = p_l + f

            rl = _match(query, corpus[p_l: p_r - f])
            if rl > bmv_r:
                bmv_r = rl
                bp_r = p_r - f

            rr = _match(query, corpus[p_l: p_r + f])
            if rr > bmv_r:
                bmv_r = rr
                bp_r = p_r + f

            if verbose:
                print "\n" + str(f)
                print "ll:   value: %f   snippet: %s" % (ll, corpus[p_l - f: p_r])
                print "lr:   value: %f   snippet: %s" % (lr, corpus[p_l + f: p_r])
                print "rl:   value: %f   snippet: %s" % (rl, corpus[p_l: p_r - f])
                print "rr:   value: %f   snippet: %s" % (rl, corpus[p_l: p_r + f])

        return bp_l, bp_r, _match(query, corpus[bp_l : bp_r])

    if not case_sensitive:
        query = query.lower()
        corpus = corpus.lower()

    qlen = len(query)

    if flex >= qlen/2:
        print "Warning: flex exceeds length of query / 2. Setting to default."
        flex = 3

    match_values = scan_corpus(step)
    pos = index_max(match_values) * step

    pos_left, pos_right, match_value = adjust_left_right_positions()

    return corpus[pos_left: pos_right].strip(), match_value

示例：

^{pr2}$

一些好的启发性建议是始终保持step < len(query) * 3/4，和{}。我还增加了区分大小写的功能，以防这很重要。当您开始使用step和flex值时，它非常有效。较小的步长值可以获得更好的结果，但计算时间较长。flex控制结果子字符串的长度允许的灵活性。在

需要注意的是：这只会找到第一个最佳匹配项，因此如果有多个同样好的匹配项，则只返回第一个匹配项。为了允许多个匹配，更改index_max()以返回输入列表中n最高值的索引列表，并在该列表中的值的adjust_left_right_positions()上循环。在