如何找到多个字符串中最长的公共子字符串？

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) -> Iterator[str]: 
    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长度（即最长可能的常见子字符串）。这种启发式的一个显而易见的值可能是最短序列的长度。

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），所以你可能想了解一些优化算法（看到你的问题我离开的链接在我的评论）。

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, 
     ... 

您：

更新

其中每个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子类，所以它的情况下，也有类似的接口来计算串的数量可以过滤计数以留下至少在发生的子字符串字符串：{string: count for string, count in counts.items() if count >= n}