python - 如何找到多个字符串的最长公共(public)子串？

Question

我正在编写一个有多个字符串的 python 脚本。

例如:

x = "brownasdfoersjumps"
y = "foxsxzxasis12sa[[#brown"
z = "thissasbrownxc-34a@s;"

在所有这三个字符串中，它们有一个共同的子字符串，即brown。我想以一种我想创建字典的方式搜索它:

dict = {[commonly occuring substring] => 
           [total number of occurrences in the strings provided]}

这样做的最佳方式是什么？考虑到我每次都会有超过 200 个字符串，什么是一种简单/有效的方法？

Answer 1

这是一个相对优化的朴素算法。您首先将每个序列转换为一组所有 ngram。然后你将所有集合相交并找到交集中最长的 ngram。

from functools import partial, reduce
from itertools import chain
from typing import Iterator


def ngram(seq: str, n: int) -> Iterator[str]:
    return (seq[i: i+n] for i in range(0, len(seq)-n+1))


def allngram(seq: str) -> set:
    lengths = range(len(seq))
    ngrams = map(partial(ngram, seq), lengths)
    return set(chain.from_iterable(ngrams))


sequences = ["brownasdfoersjumps",
             "foxsxzxasis12sa[[#brown",
             "thissasbrownxc-34a@s;"]

seqs_ngrams = map(allngram, sequences)
intersection = reduce(set.intersection, seqs_ngrams)
longest = max(intersection, key=len) # -> brown

虽然这可能会让您完成短序列，但该算法在处理长序列时效率极低。如果你的序列很长，你可以添加一个启发式来限制最大可能的 ngram 长度(即最长可能的公共(public)子串)。这种启发式的一个明显值可能是最短序列的长度。

def allngram(seq: str, minn=1, maxn=None) -> Iterator[str]:
    lengths = range(minn, maxn) if maxn else range(minn, len(seq))
    ngrams = map(partial(ngram, seq), lengths)
    return set(chain.from_iterable(ngrams))


sequences = ["brownasdfoersjumps",
             "foxsxzxasis12sa[[#brown",
             "thissasbrownxc-34a@s;"]

maxn = min(map(len, sequences))
seqs_ngrams = map(partial(allngram, maxn=maxn), sequences)
intersection = reduce(set.intersection, seqs_ngrams)
longest = max(intersection, key=len)  # -> brown

这可能仍然需要很长时间(或使您的机器耗尽 RAM)，因此您可能想阅读一些最佳算法(请参阅我在对您的问题的评论中留下的链接)。

更新

计算每个ngram出现的字符串数

from collections import Counter
sequences = ["brownasdfoersjumps",
             "foxsxzxasis12sa[[#brown",
             "thissasbrownxc-34a@s;"]

seqs_ngrams = map(allngram, sequences)
counts = Counter(chain.from_iterable(seqs_ngrams))

Counter是 dict 的子类, 所以它的实例有相似的接口(interface):

print(counts)
Counter({'#': 1,
         '#b': 1,
         '#br': 1,
         '#bro': 1,
         '#brow': 1,
         '#brown': 1,
         '-': 1,
         '-3': 1,
         '-34': 1,
         '-34a': 1,
         '-34a@': 1,
         '-34a@s': 1,
         '-34a@s;': 1,
         ...

您可以过滤计数以保留至少出现在 n 中的子字符串字符串:{string: count for string, count in counts.items() if count >= n}