Python 如何提取两个字符串中的相同部分？

[blueboyggh]

要求相同部分在原字符串中是连续的，而且长度要达到 4 个字符：
举个例子：
A 字符串：我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。
B 字符串：今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。
然后从上面两个字符串中提取出“中了 500 万彩票”和“是个好日子”
除了每个字符串挨个字符遍历，还有其他好办法吗？主要是需要比对的字符串数量是几千这个数量级。

[blueboyggh]

@NoOneNoBody 期待新代码共享

[blueboyggh]

@Pipecraft 使用 18#的代码后，测试 100 条数据时间从 63 秒变成 59 秒，好像变化不多，是不是我的问题？

[blueboyggh]

@szdosar 感谢，测试使用新代码，结果里没有相互包含的子元素了

[NoOneNoBody]

@blueboyggh #63
就此题来说，@szdosar #49 帖的代码足够好了，你是用这个测出最短时间的吧？
我现在只是翻翻 more_itertools 有没有可用的东西，如果没有，也就不会写出更高效率的了

https://stackoverflow.com/questions/66668405/python-sliding-windows-of-a-list
这里有个关于 moving window （移动窗口）的例子，感觉也差不多

[blueboyggh]

@NoOneNoBody 好的，确实是#49 的时间最短，感谢

[NoOneNoBody]

more_itertools 有个有趣的东西

more_itertools.substrings(iterable)

Yield all of the substrings of iterable.

>>> [''.join(s) for s in substrings('more')]
['m', 'o', 'r', 'e', 'mo', 'or', 're', 'mor', 'ore', 'more']

不过也是完全穷举，字符串越长应该效率越低

[Pipecraft]

@blueboyggh #62 差不多会那样，毕竟相比匹配用的时间，compile 表达式的时间没有多少。

[NoOneNoBody]

@blueboyggh #65
我这边测还是自己写的快

把
l = len(s)
前面重新加上
s = ''.join([x for x in s if x in ss])

这个看样子是不能省略的，因为这个逻辑是，原 s 所有和 ss 包含的字符连起来，过滤了不能匹配的字符
意味着最大匹配长度不会超过这个新字符串的长度，而且连续匹配的子串也一定在这个新的字符串内
这样会大幅度降低后面的循环次数 range(l - minlen + 1)

PS: 用这个分别过滤 s 和 ss 后，正则的方式就快了很多了……我这里测试反而正则变成最快的方法

[NoOneNoBody]

@NoOneNoBody #68
秀逗了，长度 len 可以用这个，但匹配不能用这个，逻辑不对

abcdef vs abdf 结果是 ab
过滤后 abdf vs abdf 结果是 abdf
就不正确了

算了，今天到此为止，脑子都打结了，去娱乐一下

[cy18]

用 pygtrie 写了个，这库不支持部分前缀的查找，建树比较慢，查找比较快。优化下 trie 库内部的建树或者查找过程的话应该可以再快几个数量级。

import pygtrie

def build_tree(str1, min_len=4):
tree = pygtrie.CharTrie()
for begin in range(len(str1)):
for end in range(begin+min_len, len(str1)):
tree[str1[begin:end]] = (begin, end)
return tree

def find_prefixes(tree, str2, min_len=4):
result = set()
sub_len = 0 # Used to remove unnecessary substrings
for start in range(len(str2)):
longest_prefix = tree.longest_prefix(str2[start:])
if (longest_prefix.key is not None
and len(longest_prefix.key) >= min_len
and len(longest_prefix.key) > sub_len):
result.add(longest_prefix.key)
sub_len = len(longest_prefix.key)
sub_len -= 1
return result


str1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"*10
str2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。"*10
tree = build_tree(str1)
result = find_prefixes(tree, str2)
print(result)

[blueboyggh]

@Pipecraft
@NoOneNoBody

由于现在数据量上升到了将近 10w 条，现在跑完一遍数据需要二十多个小时，这个滑动窗口的方法，还有什么能优化的地方吗？比如上多线程啥的？

[NoOneNoBody]

@blueboyggh #71
10w 条的话
1. 向量化函数
2. 一些机器学习方向的包，#70 那个不知道是不是，这种包都是需要花时间建模，然后应用很快
3. 多进程并发，多线程因为 GIL 没用

前两个需要学习成本，但学会就很有用，可以用到其他工作，不仅是字符串，尤其是大批量的数值计算
并发的话比较快上手，因为单例函数已经存在，建进程池而已，花点时间比较一下其他并发包的 performance ，有不少比原生更快的

[Pipecraft]

@blueboyggh #71 可以保存跑过的数据的结果，下次不再计算这个部分，只计算增量的部分。

但是，如果每天都有新的 10 w 条数据，可以考虑多个机器同时跑然后汇总，毕竟都是可以独立运算的。