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

[blueboyggh]

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

[cy18]

先 O(n^2)建个字典树，再做 n 次 O(n)的查询，总计 O(n^2)，不知道有没有其他更快或者更简单的办法。

[blueboyggh]

@cy18 虽然看不懂，但还是谢谢

[ladypxy]

这是要做关键词过滤/审核？

[xuanbg]

字符串转成字符的集合，取交集。

[cdwyd]

才几千个，循环完全扛得住。除非你对比的字符串长度不是你举例的长度

[cy18]

接收 O(n^3)的话，用 set 实现估计 10 行以内代码就能搞定。
搜了下有个现成的库 https://pygtrie.readthedocs.io/en/latest/，先把第一个字符串的按照起始位置生成 n 个字符串全塞到字典树里，再用对第二个字符串用 longest_prefix 函数做 n 次查询就搞定了。

[blueboyggh]

@cdwyd 确实不是举例的长度，字符串字数可能一百多字，甚至更多

[blueboyggh]

@ladypxy 没必要什么都往这上面想吧

[ClericPy]

使用 Python 提取两个字符串中长度超过 4 个字符的公共子串. 问了俩 gpt 类的答案都是遍历.
先抄答案实现一个试试, 性能不够再考虑 KMP 或者 trie 树优化, 还有那种带缓存的递归优化优化

[em70]

最长公共子序列（ Longest Common Subsequence ，简称 LCS ）是一种常见的字符串匹配问题，可以用动态规划来解决。下面是 Python 中求解最长公共子序列的示例代码：

```python
def longest_common_subsequence(str1, str2):
m = len(str1)
n = len(str2)

# 创建一个二维数组来存储最长公共子序列的长度
dp = [[0] * (n + 1) for _ in range(m + 1)]

# 填充 dp 数组
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

# 从 dp 数组中恢复最长公共子序列
i, j = m, n
lcs = []
while i > 0 and j > 0:
if str1[i - 1] == str2[j - 1]:
lcs.append(str1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1

return ''.join(reversed(lcs))

# 测试示例
str1 = "ABCBDAB"
str2 = "BDCAB"
result = longest_common_subsequence(str1, str2)
print("最长公共子序列:", result)
```

这段代码中，`longest_common_subsequence` 函数接受两个字符串 `str1` 和 `str2`，并返回它们的最长公共子序列。动态规划的核心思想是创建一个二维数组 `dp`，其中 `dp[i][j]` 表示 `str1` 的前 `i` 个字符和 `str2` 的前 `j` 个字符的最长公共子序列的长度。然后，通过填充这个数组，最终可以从 `dp` 数组中找到最长公共子序列。

在示例中，最长公共子序列为 "BCAB"。

from chatgpt

[NoOneNoBody]

这个我写过好几个方案，基本没跳出两个思路
这两个思路都是定位一个尾字符向前或向后组 n 个字符，然后再匹配，跟 #6 所说是一样的
1. itertools.accumulate
2. 是 numpy 模拟 pandas.rolling
载入 pandas/numpy 很耗时，但如果项目本身就需要载入的话，用这个比较大量文字数据，倒是很好用
这个用的是向量函数，没什么优化空间，但数据量很大的话，反而有有优势

还有一个想法是 AC 自动机，主要是有些项目一早就预载了 AC 自动机的字典，匹配目标主要也是在字典范围内，没必要再去各个文字语句都拆解一遍，不过这个没有去做，因为这个暂时没有应用场景，前两个已经很快了

[Pipecraft]

OP 想要的是提取所有长度大于 4 的公共子序列，而上面一些回复说的是最长公共子序列，两个是不同问题。

如果只是执行一次的任务，那可以怎么简单怎么来。
比如，利用正则表达式可以 1 行代码解决。

```python
import re

str1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
str2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。"

result = re.compile(r'([^,.，。]{4,})(?=.*####.*?(?=\1))').findall(str1 + "####" + str2)

print(result)
# 输出: ['是个好日子', '中了 500 万彩票']
```

正则的贪婪匹配，比较契合 OP 这个的问题。

[blueboyggh]

@Pipecraft 十分感谢，再麻烦问一下，如果长度要求不是 4 ，而是 8 ，是不是只把正则代码里的 4 改成 8 就行了？

[flyqie]

要求相同部分在原字符串中是连续的，而且长度要达到 4 个字符

你这个提取结果是固定的吗，还是说根据句子动态调整？

[blueboyggh]

@flyqie 不太理解您的固定和动态调整的意思？

[flyqie]

@blueboyggh #15

不好意思看错了，请忽略该回复。

楼上老哥代码似乎已经解决了你的问题，4 改 8 的话#号数量也得改一下。

[blueboyggh]

@flyqie 我测试了一下，好像不用改#号数量也能用

[Pipecraft]

@blueboyggh #17 如果长度要求不是 4 ，而是 8 , `{4,}` 改成 `{8,}` 即可。
`####` 是分割两个字符串的，可以换成其他任意字符串。
`[^,.，。]` 可以把其他要排除的标点符号加进去，比如 !?; 等。
正则表达式里的 `?=\1` 改成 `?:\1` 可能性能会更好一点。

后来想了想，有些情况，提取的不完整。
比如
str1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
str2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心，我也想中 500 万彩票。"
只提取了 '是个好日子', '中了 500 万彩票'。
‘ 500 万彩票’ 没有提取出来。
要完整的提取，str1, str2 换个位置，再执行一次，然后两个结果取并集就完整了。

```python
import re

pattern = re.compile(r'([^,.，。]{4,})(?=.*####.*?(?:\1))')

def find_common_subsequences(str1, str2):
result1 = pattern.findall(str1 + "####" + str2)
result2 = pattern.findall(str2 + "####" + str1)
return list(set(result1).union(set(result2)))

# TEST
str1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
str2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心，我也想中 500 万彩票。"
result = find_common_subsequences(str1, str2)
print(result)

# 输出: ['是个好日子', ' 500 万彩票', '中了 500 万彩票']
```

[szdosar]

试试这个，运行结果是：['是个好日子，', '中了 500', '中了 500 万彩票', '中了 500 ', '是个好日', '中了 500 万', '中了 50', '是个好日子', '中了 5', '中了 500 万彩']
[Finished in 89ms]
```
def find_common_substrings(s1, s2, min_length=4):
# 创建一个二维数组，用于存储公共子串的长度
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
longest = 0
common_substrings = set()

for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] >= min_length:
common_substrings.add(s1[i - dp[i][j]:i])
else:
dp[i][j] = 0

return list(common_substrings)

# 示例
s1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
s2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。"
print(find_common_substrings(s1, s2))
```

[blueboyggh]

@Pipecraft 十分感谢您！祝您中 500 万！

[blueboyggh]

@szdosar 好的，我先用了楼上老哥的代码，先测试，回头再试试您的

[maocat]

这种需求以前我会安心写代码，现在我只想扔给 langchain

[ruanimal]

用 difflib.SequenceMatcher

[MoYi123]

1. 把 A 变成 suffix array, => O(A)
2. 遍历 B[idx :idx+4] ,找出所有的起始 index => O((4 * B) * log(A))
3 对 A 和 B 都算出 rabin-karp 数组 => O(A+B)
4. 遍历第二步得到的起始 index, 用二分算法 + 第三步的哈希, 确定结束位置 => O( B * log(B))

[qianckjuan]

不是 kmp 算法吗

[blueboyggh]

@Pipecraft
@szdosar

我发现用二位的代码，用我题目中的例子就可以正常运行，但是用我实际需要匹配的字符串，就找不到匹配项，可是明明里面就有匹配项。哪位能加个联系方式帮帮忙...有偿也可以

[szdosar]

你改一下 min_length=9 ，结果就是
['中了 500 万彩票', '中了 500 万彩']
[Finished in 133ms]
所以是不是这个的原因，长度问题？

[blueboyggh]

@szdosar 实际我的长度需求是 8 ，我改成 8 了，也不行，我题目中这个例子是可以的，但是我实际需要用的字符串不行

[blueboyggh]

@szdosar 我发现了，因为我是从 excel 表格里提取的内容，如果内容里有换行符，就会影响判断，即使换行符并不在需要提取的相同文本内，也不行，这是因为换行符会影响字符串提取吗？

[Pipecraft]

@blueboyggh #29 建议删除换行符以后，提取。
正则参数加上 multiline flag 可以匹配带换行符的字符串，
但是有换行符可能会匹配不到一些结果。

比如
str1="ABC\nD123"
str2="A\nBCD456"

这两个字符串去掉换行符，应该可以匹配 ‘ABCD’，如果不去掉换行符，就匹配不到了。

[szdosar]

你把要比较的内容放在两个文本文件中试试：
'''
def find_common_substrings(s1, s2, min_length=8):
# 创建一个二维数组，用于存储公共子串的长度
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
longest = 0
common_substrings = set()

for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] >= min_length:
common_substrings.add(s1[i - dp[i][j]:i])
else:
dp[i][j] = 0

return list(common_substrings)

# 添加一个函数来读取文件内容
def read_file_content(filename):
with open(filename, 'r', encoding='utf-8') as file:
return file.read()

# 使用上面的函数来读取 file1.txt 和 file2.txt 的内容
s1 = read_file_content('file1.txt')
s2 = read_file_content('file2.txt')

# 使用 find_common_substrings 函数来对比这两个文件的内容
print(find_common_substrings(s1, s2))
'''

[blueboyggh]

@szdosar 主要是我需要对比的数据是上千条的 excel ，一个一个复制到文本文档，效率太低了吧

[szdosar]

方法有不是只有一套，对吧？
'''
#find_common_substrings_excel
#读取 Excel 文件，使用 pandas 库。确保你已经安装了 pandas 和 xlrd 库。可以使用以下命令进行安装：pip install pandas xlrd openpyxl
import pandas as pd

def find_common_substrings(s1, s2, min_length=4):
# 创建一个二维数组，用于存储公共子串的长度
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
longest = 0
common_substrings = set()

for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] >= min_length:
common_substrings.add(s1[i - dp[i][j]:i])
else:
dp[i][j] = 0

return list(common_substrings)

# 添加一个函数来读取 Excel 文件的内容
def read_excel_content(filename):
# 读取 Excel 文件的第一个工作表
df = pd.read_excel(filename, sheet_name=0)
# 获取第一列的内容并将其转换为字符串
return df.iloc[:, 0].astype(str).str.cat(sep=' ')

# 使用上面的函数来读取 Excel 文件的内容
s1 = read_excel_content('file1.xlsx')
s2 = read_excel_content('file2.xlsx')

# 使用 find_common_substrings 函数来对比这两个文件的内容
print(find_common_substrings(s1, s2))
'''

[blueboyggh]

@szdosar 感谢，目前正在测试之前的代码，跑了 3 个小时，跑了 1300 条数据了

[NoOneNoBody]

@Pipecraft
正则的表现让我有点失望，本以为正则比循环快，实测不是
不过你写的这个正则很精彩，我留下了，其他地方有用，先谢

@blueboyggh
下面两个是我之前写的，效率还可以

下面两个 if minlen>l: return [] 及相关可以省略，因为我的应用场景有词语，不少是“没必要比较”的，所以直接返回空。如果基本是长句，这个判断反而没必要
==================
def matchSubstrings(s:str, ss:str, minlen:int=2, reverse:bool=False):
'''
按出现先后顺序，寻找 s 中，与 ss 任意子串相同的子串\n
叠加的部分只选首个匹配，例如 638 vs 63/38 -> 只返回 63\n
minlen: int 最短匹配长度\n
reverse: bool->True 反向，寻找目标为 ss ，参考为 s
'''
if reverse: s, ss = ss, s
ac = itertools.accumulate
l = len(s)
if minlen>l: return []
lll, pos = 0, 0
for i in range(l - minlen + 1):
sss = [x for x in ac(s[i:])]
sss.reverse()
ll = len(sss)
for j,x in enumerate(sss[:ll - minlen + 1]):
if j>ll-lll and i<pos+lll: break
if x in ss:
lll = len(x)
pos = i
yield x
break
==================
缩进自行处理，基本是遇到冒号结尾的，后面的都向右缩进，没有向左回退的，大概能看懂
1. 说明中的“叠加”情况是比较麻烦的，如果需求不同，写法就不同了
2. 这个主要考虑“顺序”，是全匹配；匹配长度优先是另一种写法，需要 itertools.accumulate(s[::-1])类似，但思路有点区别，参照#6 ；长度优先可以适时 break 只返回“最长匹配”

下面这个是基于 numpy 和 pandas 的，因为是向量函数列操作，所以是全匹配，如果只需要“最长”的话，在某个 yield 后打 break ，或者要在返回结果中再筛选
===================
def rollingByNumpy(s:pd.Series, window):
v = np.lib.stride_tricks.as_strided(s, (len(s) - (window - 1), window), (s.values.strides * 2))
return pd.Series(v.tolist(), index=s.index[window - 1:])

def matchSubstrings4(s:str, ss:str, minlen:int=2, reverse:bool=False, whole:bool=True):
'''
按最大匹配长度的顺序，寻找 s 中，与 ss 任意子串相同的子串\n
叠加的部分默认只选首个匹配，例如 638 vs 63/38 -> 只返回 63 ； whole=False 时则全部返回，返回 63 和 38\n
minlen: int 最短匹配长度\n
reverse: bool->True 反向，寻找目标为 ss ，参考为 s\n

如果之前已经载入 pandas ，此函数略微快些，否则 载入 pandas 耗时较多
'''
if reverse: s, ss = ss, s
s1 = ''.join([x for x in ss if x in s])
l = len(s1)
if minlen>l: return []
s2 = pd.Series(list(s))

if whole:
for w in range(l, minlen-1, -1):
ser = rollingByNumpy(s2, w).str.join('')
ii = ser.index.min()
for i,x in ser.items():
if i<=ii+w: continue
if x in ss:
ii = i
yield x
else:
for w in range(l, minlen-1, -1):
ser = rollingByNumpy(s2, w).str.join('')
for x in ser:
if x in ss: yield x
==================
缩进自行处理，遇到冒号结尾的，后面的都向右缩进，基本没有向左回退的，大概能看懂
else 那行和 if whole 对应，没有缩进，其他都是向右缩进，回复没缩进会混乱

1. rollingByNumpy 因为用途很广，我好多地方用到，不仅是字符串，所以独立一个函数分开
pandas.rolling 不能用在整数、浮点以外的类型，所以需要用 numpy 模拟
rollingByNumpy 不是原创，是参考 so 的答案改的
2. 我原来的函数是重组一个 dataframe 返回的(也不需要 ss 参数)，因为后续根据需求不同（不一定是求子串），可以整个 dataframe 统一用一个函数(这里才使用到 ss)同时处理，没必要逐个处理；这里只是按 op 需求跑了一遍循环 yield 结果

[RuiCBai]

这不就是最长公共子数列嘛 （比最长公共子序列还简单一些）

[KAAAsS]

DP+1 ，稍微调整一下 @szdosar 的代码应该就可以改成同一序列取最长的了。时空复杂都是 O(M * N)，滚动数组优化的话空间还可以做到 O(2 * min{M, N})。而且从比较次数来看应该比前缀树之类方法要更快。

```python
def find_common_substrings(s1, s2, min_length=4):
# 创建一个二维数组，用于存储公共子串的长度
s1 += '\0'
s2 += '\1'
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
common_substrings = set()

for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
elif dp[i - 1][j - 1] >= min_length:
common_substrings.add(s1[i - dp[i - 1][j - 1] - 1:i - 1])

return list(common_substrings)
```

[szdosar]

「 https://drive.google.com/file/d/1-Kv19SR2HITSiWnzs6XzI_JqyqcjpK2w/view?usp=sharing 」
- - - - - - - - - - - - - - -
感谢指点，我也就是半桶水，上面这个链接是源码。

[RedisMasterNode]

可以很暴力解决，如果数据量不太大

https://pastebin.com/raw/q3wf0h23

测试例子：
>>> str1 = "abcdefgandhahaok"
>>> str2 = "acsdefokokhhaha00"
>>> find_common_substrings(str1, str2, 3)
['def', 'hah', 'haha', 'aha']

[RedisMasterNode]

>>> find_common_substrings(str1, str2, 4)
['haha']

[RedisMasterNode]

补充一句刚刚测试了一下大约 2000 字符的对比，其实很快很快，主要看楼主希望达到什么程度，例如最差最差接受 1 秒执行完，那是非常轻松的，如果是真的有 1ms 内处理的需求再考虑其他方案就是了

[SaberJack]

动态规划可以解决
def longest_common_substring(s1, s2, min_length=4):
m = len(s1)
n = len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0
end_index = 0

for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_length:
max_length = dp[i][j]
end_index = i
else:
dp[i][j] = 0

if max_length >= min_length:
return s1[end_index - max_length:end_index]
else:
return ""

A = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
B = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。"

print(longest_common_substring(A, B))

[Tstxxy]

两个字符串的公共子序列肯定包含楼主要的连续 4 个以上相同字符的序列。
其实只需要在状态表格中加多一个字段，表示已经有连续几个字符相同了。
以上算法的复杂度为 o(mn)
楼主可以先了解公共子序列的算法。

[blueboyggh]

https://pastebin.com/raw/irdJS0iK


@NoOneNoBody 麻烦给看看我处理的缩进和完善的 demo 是否有问题？测试结果只能输出一个“ 万彩票”

[liuhai233]

https://leetcode.cn/problems/longest-common-subsequence/

[szdosar]

我处理了一下你这个代码的缩进 https://pastebin.com/raw/6mEqdaZG
输出是：
'''
是个好日子，
[Finished in 131ms]
'''

[NoOneNoBody]

@blueboyggh #41
不对
1.交换 s/ss 那行缩进多了，但不影响
2.从 sss.reverse()开始到结束，都是在第一个 for 内部的，所以全部需要再增加缩进一层

[blueboyggh]

@szdosar
@NoOneNoBody

对，现在输出能出第一个相同字符串“是个好日子，”了，但是“中了 500 万彩票”没有，是因为我对 yield 返回的 x 的处理方式不对吗？

[szdosar]

不要执着于用迭代操作，我们来分析一下。
##itertools 是一个非常强大的库，它提供了很多用于处理迭代操作的工具。但是，对于特定的问题，直接的算法可能会更加高效。
##在我们的情境中，我们要找的是两个字符串之间的所有公共子串。使用 itertools 可能会涉及生成所有可能的子串组合，然后再进行比较，这在某些情况下可能会导致不必要的计算。
##而我们使用的滑动窗口方法是基于以下观察结果的：
##如果两个字符串在某个位置有一个公共字符，那么我们可以尝试扩展这个匹配，直到找到一个公共子串或匹配失败为止。
##通过这种方式，我们可以立即找到一个公共子串，而不需要生成和比较所有可能的子串组合。
##因此，对于这个特定的问题，滑动窗口方法可能会比使用 itertools 更加高效。但这并不意味着 itertools 不是一个有用的库。对于其他类型的问题，itertools 可能会提供更简洁、更高效的解决方案。
##以下使用滑动窗口方法
##find_common_substrings_huadong
源代码效率可大幅提高：
https://pastebin.com/raw/Qfr31L8a

[NoOneNoBody]

@blueboyggh #48
你是全部用了 #45 的代码吧？
他最后一句是用 next ，这个只返回第一个，改为 list(gg)是全部返回
如果想按长度排序（倒序），用 sorted(gg, key=len, reverse=True)

[blueboyggh]

@NoOneNoBody 谢谢，改成 list 就好了，next 是从网上抄的。

[NoOneNoBody]

@szdosar #49
滑动思路没有错，只是 window 的尺寸不定，从 min 到 length 都有，离不开每个 window 尺寸轮询
itertools.accumulate 在这里的作用就是自动生成不同 window 尺寸的切片，省了轮询的时间

如果尺寸固定，例如只找连续 4 个字符的匹配，5 个、6 个……都忽略，那用 pandas.series.shift 是对应最简单的思路
可惜 python 没有移动 window 概念，需要手写切片[start:end]

其实 @Pipecraft #12 写的利用正则贪婪匹配的思路是最精彩，虽然实际运行速度不如理想，但我还是忍不住要赞一个

我花了不少时间在这个上面，这个看上去是字符串问题，但实际是队列问题，如果能找到一个非常高效的方法的话，在 pandas 是非常有用的，大数据中快速寻找连续等值的片段用途多得很，所以我才写了个看上去跟字符串无不相干的 pandas 方案

[juny1998]

chatGPT 的回答

[juny1998]

def extract_common_substrings(str1, str2):
common_substrings = []

for i in range(len(str1)):
for j in range(i + 4, len(str1) + 1):
substring = str1[i:j]
if substring in str2 and len(substring) >= 4:
common_substrings.append(substring)

return common_substrings

# 例子
A = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
B = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。"

common_substrings = extract_common_substrings(A, B)
print(common_substrings)

[blueboyggh]

@szdosar
@NoOneNoBody

我从我的样本里取了 100 条数据，用三种方法都进行了测试，测试结果：

滑动窗口方法：13 秒完成
itertools 方法：28 秒完成
正则表达式方法：63 秒完成

其中滑动窗口的方法，取出来的样本是最全的，但是结果 list 里一些子元素有相互包含的情况，比如“中了 500 万彩票”和“了 500 万彩票”
itertools 方法的结果更加精简，但是依旧有子元素有相互包含的情况
正则表达式方法则是完全没有子元素有相互包含的情况，但是速度也最慢

以上结果可能因为本人代码小白的问题受影响，不代表三种方法的真实水平，或者有其他隐含的坑我没能力发现

[szdosar]

可以改进的，返回的子串之间有相互包含的情况。我们在添加子串到结果集之前进行检查，可以检查新找到的子串是否包含在结果集中的任何子串中，或者结果集中的任何子串是否包含在新找到的子串中。
fix 源码 https://pastebin.com/raw/6aKqeUrP

[Pipecraft]

@NoOneNoBody #52 感谢对这个正则的肯定。
正则内部是通用的算法，肯定会比针对特定问题优化的算法速度慢。
所以上面（#12 ）回复里说了“如果只是执行一次的任务，那可以怎么简单怎么来。”
如果是反复执行并且数据量很大，那不建议用正则表达式。

#12 层里的代码并不完整，#18 层里的代码更完整，只是速度更慢。
https://pastebin.com/raw/UgzrPbA7

[Pipecraft]

@blueboyggh #55 处理多条数据时，正则表达式要使用 compile 后的结果，如果每次都 compile 一次，会很慢。
即不要直接使用 #12 层的代码，使用 #18 层的代码。
当然，我相信上面的测试是这么做的。

[blueboyggh]

@Pipecraft 我的问题，18#的源码我只应用了前后对比两次的逻辑，其他的没用，估计影响了结果，一会儿我修改一下再测试一下试试

[NoOneNoBody]

呵呵，发现自己有点钻牛角尖了，不追求 yield 和去叠加就没必要再轮询一次，可以少好多行代码

而且 itertools.accumulate 是先生成后比较，概率上无效的肯定更多，比起滑动跳过无效的，工作量更多
嗯，重练一遍

[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 条数据，可以考虑多个机器同时跑然后汇总，毕竟都是可以独立运算的。