如何找到多個字符串中最長的公共子字符串？

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}