python - 字符串列表中最常见的部分字符串匹配

Question

我有一个很大的字符串列表(不超过 2k)，我想在列表中找到最常见的部分字符串匹配。例如，我试图以有效的方式满足以下测试用例。

data = [
    'abcdef',
    'abcxyz',
    'xyz',
    'def',
]
result = magic_function(data)
assert result == 'abc'

我尝试过这个，灵感来自 this stackoverflow post ，但列表中的某些元素完全不同这一事实让它变得不那么重要。

def magic_function(data):
    return ''.join(c[0] for c in takewhile(lambda x: all(x[0] == y for y in x), zip(*data)))

Answer 1

您可能需要对此进行调整并对其进行性能测试。

我基本上将所有部分子字符串提供给 data into a Counter 中每个单词的长度。并根据 len(substring)*occurrence 创建排名 - 通过乘以 0.1 来惩罚仅出现 1 次的情况:

data = [
    'abcdef',
    'abcxyz',
    'xyz',
    'def',
]    

def magic(d):
    """Applies magic(tm) to the list of strings given as 'd'.
    Returns a list of ratings which might be the coolest substring."""
    from collections import Counter
    myCountings = Counter()

    def allParts(word):
        """Generator that yields all possible word-parts."""
        for i in range(1,len(word)):
            yield word[:i]

    for part in d:
        # count them all
        myCountings.update(allParts(part))

    # get all as tuples and sort based on heuristic length*occurences
    return sorted(myCountings.most_common(), 
                  key=lambda x:len(x[0])*(x[1] if x[1] > 1 else 0.1), reverse=True)

m = magic(data)    
print( m ) # use  m[0][0] f.e. 

输出:

 [('abc', 2), ('ab', 2), ('a', 2), ('abcde', 1), ('abcxy', 1), 
  ('abcd', 1), ('abcx', 1), ('xy', 1), ('de', 1), ('x', 1), ('d', 1)]

您必须稍微调整排序标准，并且仅使用结果列表中的第一个 - 但您可以将其用作启动器。

如果您更喜欢较长的而不是多个较短的，则可以通过将长度乘以一个因子来完成调整 - 这取决于您的数据...