如何找到多个字符串中最长的公共子字符串?
问题描述:
我正在写一个python脚本,我有多个字符串。如何找到多个字符串中最长的公共子字符串?
例如:
x = "brownasdfoersjumps"
y = "foxsxzxasis12sa[[#brown"
z = "[email protected];"
在所有这三个字符串,它们都有一个共同的子字符串,它是brown
。我想用我想创建字典的方式进行搜索:
dict = {[commonly occuring substring] =>
[total number of occurrences in the strings provided]}
这样做的最佳方法是什么?考虑到每次我会有超过200个字符串,那么做一个简单/有效的方法是什么?
答
这是一个相对优化的朴素算法。您首先将每个序列转换为一组所有的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",
"[email protected];"]
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",
"[email protected];"]
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,
'[email protected]': 1,
'[email protected]': 1,
'[email protected];': 1,
...
您:
更新
其中每个NGRAM发生
from collections import Counter
sequences = ["brownasdfoersjumps",
"foxsxzxasis12sa[[#brown",
"[email protected];"]
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}
请参见[最长的公共子序列实现-python](http://*.com/questions/25930671/longest-common-subsequence-implementation-python)。 –
@WiktorStribiżew我的问题与您所评论的完全不同。他试图只比较两个字符串,这很简单,因为我需要使用多个字符串来查找不止一次出现的公共元素。 – Elisha512
天真的方法是选择最短的单词并搜索所有其他字符串中所有尺寸增加的ngram。 –