2024-10-01 19:21:14 发布
网友
我正在编写一个python脚本,其中有多个字符串。在
例如:
x = "brownasdfoersjumps" y = "foxsxzxasis12sa[[#brown" z = "thissasbrownxc-34a@s;"
在这三个字符串中,它们有一个共同的子字符串brown。我想用创建字典的方式搜索它:
brown
最好的办法是什么?考虑到我每次都会有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) -> 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长度(即最长的公共子串)。对于这种启发式方法,一个明显的值可能是最短序列的长度。在
这可能仍然需要太长时间(或使您的机器内存不足),所以您可能需要阅读一些最佳算法(请参阅我在评论中留下的对您的问题的链接)。在
更新
计算每个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的子类,因此其实例具有类似的接口:
Counter
dict
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}
n
{string: count for string, count in counts.items() if count >= n}
这是一个相对优化的天真算法。您首先将每个序列转换为其所有ngram的集合。然后求所有集合的交集,并在交集中找到最长的ngram。在
虽然这可能会让你通过短序列,但这种算法在长序列上效率极低。如果你的序列很长,你可以添加一个启发式来限制最大可能的ngram长度(即最长的公共子串)。对于这种启发式方法,一个明显的值可能是最短序列的长度。在
^{pr2}$这可能仍然需要太长时间(或使您的机器内存不足),所以您可能需要阅读一些最佳算法(请参阅我在评论中留下的对您的问题的链接)。在
更新
计算每个ngram出现的字符串数
Counter
是dict
的子类,因此其实例具有类似的接口:您可以过滤计数,使子字符串至少出现在
n
字符串中:{string: count for string, count in counts.items() if count >= n}
相关问题 更多 >
编程相关推荐