python - 查找最佳子字符串匹配

Question

我正在寻找使用现有库(difflib、fuzzywuzzy、python-levenshtein)的库或方法来查找文本中字符串(query)的最接近匹配项(语料库)

我开发了一个基于 difflib 的方法，我将我的 corpus 拆分为 ngram，大小为 n( 的长度)查询)。

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)

当查询和匹配字符串之间的差异只是字符替换时，它可以按我的意愿工作。

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

match = get_best_match(query, corpus)
# match = "1psum d0l0r"

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

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 数量超过 3 倍。这也是一个不可推广的解决方案。

Answer 1

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

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

代码总结: 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(range(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

例子:

query = "ipsum dolor"
corpus = "lorem i psum d0l0r sit amet"
match = get_best_match(query, corpus, step=2, flex=4)
print(match)
('i psum d0l0r', 0.782608695652174)

一些好的启发式建议是始终保留 step < len(query) * 3/4 , 和 flex < len(query) / 3 .我还添加了区分大小写，以防万一这很重要。当您开始使用 step 和 flex 值时，它工作得很好。小步长值可提供更好的结果，但计算时间更长。 flex 控制生成的子字符串长度的灵 active 。

重要提示:这只会找到第一个最佳匹配，因此如果有多个同样好的匹配，则只会返回第一个。要允许多个匹配，请更改 index_max()返回 n 的索引列表输入列表的最高值，并循环 adjust_left_right_positions()对于该列表中的值。