V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
blueboyggh
V2EX  ›  Python

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

  •  
  •   blueboyggh · 2023-09-05 21:37:32 +08:00 · 4056 次点击
    这是一个创建于 424 天前的主题,其中的信息可能已经有所发展或是发生改变。
    要求相同部分在原字符串中是连续的,而且长度要达到 4 个字符:
    举个例子:
    A 字符串:我今天特别开心啊,因为今天是个好日子,我中了 500 万彩票。
    B 字符串:今天不是个好日子,因为邻居中了 500 万彩票,我今天不开心。
    然后从上面两个字符串中提取出“中了 500 万彩票”和“是个好日子”
    除了每个字符串挨个字符遍历,还有其他好办法吗?主要是需要比对的字符串数量是几千这个数量级。
    73 条回复    2023-09-28 09:37:24 +08:00
    cy18
        1
    cy18  
       2023-09-05 21:51:03 +08:00   ❤️ 1
    先 O(n^2)建个字典树,再做 n 次 O(n)的查询,总计 O(n^2),不知道有没有其他更快或者更简单的办法。
    blueboyggh
        2
    blueboyggh  
    OP
       2023-09-05 22:04:16 +08:00
    @cy18 虽然看不懂,但还是谢谢
    ladypxy
        3
    ladypxy  
       2023-09-05 22:05:00 +08:00
    这是要做关键词过滤/审核?
    xuanbg
        4
    xuanbg  
       2023-09-05 22:11:54 +08:00   ❤️ 1
    字符串转成字符的集合,取交集。
    cdwyd
        5
    cdwyd  
       2023-09-05 22:11:59 +08:00
    才几千个,循环完全扛得住。除非你对比的字符串长度不是你举例的长度
    cy18
        6
    cy18  
       2023-09-05 22:16:32 +08:00   ❤️ 1
    接收 O(n^3)的话,用 set 实现估计 10 行以内代码就能搞定。
    搜了下有个现成的库 https://pygtrie.readthedocs.io/en/latest/,先把第一个字符串的按照起始位置生成 n 个字符串全塞到字典树里,再用对第二个字符串用 longest_prefix 函数做 n 次查询就搞定了。
    blueboyggh
        7
    blueboyggh  
    OP
       2023-09-05 22:19:28 +08:00 via Android
    @cdwyd 确实不是举例的长度,字符串字数可能一百多字,甚至更多
    blueboyggh
        8
    blueboyggh  
    OP
       2023-09-05 22:19:45 +08:00 via Android
    @ladypxy 没必要什么都往这上面想吧
    ClericPy
        9
    ClericPy  
       2023-09-05 22:27:47 +08:00   ❤️ 1
    使用 Python 提取两个字符串中长度超过 4 个字符的公共子串. 问了俩 gpt 类的答案都是遍历.
    先抄答案实现一个试试, 性能不够再考虑 KMP 或者 trie 树优化, 还有那种带缓存的递归优化优化
    em70
        10
    em70  
       2023-09-05 22:30:23 +08:00   ❤️ 1
    最长公共子序列( 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
        11
    NoOneNoBody  
       2023-09-05 23:18:37 +08:00   ❤️ 1
    这个我写过好几个方案,基本没跳出两个思路
    这两个思路都是定位一个尾字符向前或向后组 n 个字符,然后再匹配,跟 #6 所说是一样的
    1. itertools.accumulate
    2. 是 numpy 模拟 pandas.rolling
    载入 pandas/numpy 很耗时,但如果项目本身就需要载入的话,用这个比较大量文字数据,倒是很好用
    这个用的是向量函数,没什么优化空间,但数据量很大的话,反而有有优势

    还有一个想法是 AC 自动机,主要是有些项目一早就预载了 AC 自动机的字典,匹配目标主要也是在字典范围内,没必要再去各个文字语句都拆解一遍,不过这个没有去做,因为这个暂时没有应用场景,前两个已经很快了
    Pipecraft
        12
    Pipecraft  
       2023-09-06 00:51:14 +08:00   ❤️ 8
    OP 想要的是提取所有长度大于 4 的公共子序列,而上面一些回复说的是最长公共子序列,两个是不同问题。

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

    ```python
    import re

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

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

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

    正则的贪婪匹配,比较契合 OP 这个的问题。
    blueboyggh
        13
    blueboyggh  
    OP
       2023-09-06 06:48:18 +08:00
    @Pipecraft 十分感谢,再麻烦问一下,如果长度要求不是 4 ,而是 8 ,是不是只把正则代码里的 4 改成 8 就行了?
    flyqie
        14
    flyqie  
       2023-09-06 07:17:29 +08:00 via Android
    要求相同部分在原字符串中是连续的,而且长度要达到 4 个字符

    你这个提取结果是固定的吗,还是说根据句子动态调整?
    blueboyggh
        15
    blueboyggh  
    OP
       2023-09-06 07:19:06 +08:00 via Android
    @flyqie 不太理解您的固定和动态调整的意思?
    flyqie
        16
    flyqie  
       2023-09-06 07:21:53 +08:00 via Android
    @blueboyggh #15

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

    楼上老哥代码似乎已经解决了你的问题,4 改 8 的话#号数量也得改一下。
    blueboyggh
        17
    blueboyggh  
    OP
       2023-09-06 08:04:38 +08:00 via Android
    @flyqie 我测试了一下,好像不用改#号数量也能用
    Pipecraft
        18
    Pipecraft  
       2023-09-06 08:49:14 +08:00   ❤️ 2
    @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
        19
    szdosar  
       2023-09-06 09:40:09 +08:00   ❤️ 1
    试试这个,运行结果是:['是个好日子,', '中了 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
        20
    blueboyggh  
    OP
       2023-09-06 09:42:43 +08:00   ❤️ 1
    @Pipecraft 十分感谢您!祝您中 500 万!
    blueboyggh
        21
    blueboyggh  
    OP
       2023-09-06 09:43:06 +08:00
    @szdosar 好的,我先用了楼上老哥的代码,先测试,回头再试试您的
    maocat
        22
    maocat  
       2023-09-06 09:58:22 +08:00
    这种需求以前我会安心写代码,现在我只想扔给 langchain
    ruanimal
        23
    ruanimal  
       2023-09-06 10:12:12 +08:00
    用 difflib.SequenceMatcher
    MoYi123
        24
    MoYi123  
       2023-09-06 10:13:39 +08:00
    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
        25
    qianckjuan  
       2023-09-06 10:27:18 +08:00
    不是 kmp 算法吗
    blueboyggh
        26
    blueboyggh  
    OP
       2023-09-06 11:23:27 +08:00
    @Pipecraft
    @szdosar

    我发现用二位的代码,用我题目中的例子就可以正常运行,但是用我实际需要匹配的字符串,就找不到匹配项,可是明明里面就有匹配项。哪位能加个联系方式帮帮忙...有偿也可以
    szdosar
        27
    szdosar  
       2023-09-06 11:40:37 +08:00
    你改一下 min_length=9 ,结果就是
    ['中了 500 万彩票', '中了 500 万彩']
    [Finished in 133ms]
    所以是不是这个的原因,长度问题?
    blueboyggh
        28
    blueboyggh  
    OP
       2023-09-06 11:53:21 +08:00
    @szdosar 实际我的长度需求是 8 ,我改成 8 了,也不行,我题目中这个例子是可以的,但是我实际需要用的字符串不行
    blueboyggh
        29
    blueboyggh  
    OP
       2023-09-06 12:27:10 +08:00
    @szdosar 我发现了,因为我是从 excel 表格里提取的内容,如果内容里有换行符,就会影响判断,即使换行符并不在需要提取的相同文本内,也不行,这是因为换行符会影响字符串提取吗?
    Pipecraft
        30
    Pipecraft  
       2023-09-06 13:11:27 +08:00
    @blueboyggh #29 建议删除换行符以后,提取。
    正则参数加上 multiline flag 可以匹配带换行符的字符串,
    但是有换行符可能会匹配不到一些结果。

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

    这两个字符串去掉换行符,应该可以匹配 ‘ABCD’,如果不去掉换行符,就匹配不到了。
    szdosar
        31
    szdosar  
       2023-09-06 13:46:46 +08:00
    你把要比较的内容放在两个文本文件中试试:
    '''
    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
        32
    blueboyggh  
    OP
       2023-09-06 13:55:28 +08:00
    @szdosar 主要是我需要对比的数据是上千条的 excel ,一个一个复制到文本文档,效率太低了吧
    szdosar
        33
    szdosar  
       2023-09-06 14:23:11 +08:00
    方法有不是只有一套,对吧?
    '''
    #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
        34
    blueboyggh  
    OP
       2023-09-06 15:12:24 +08:00
    @szdosar 感谢,目前正在测试之前的代码,跑了 3 个小时,跑了 1300 条数据了
    NoOneNoBody
        35
    NoOneNoBody  
       2023-09-06 16:09:23 +08:00
    @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
        36
    RuiCBai  
       2023-09-06 16:27:59 +08:00 via Android
    这不就是最长公共子数列嘛 (比最长公共子序列还简单一些)
    KAAAsS
        37
    KAAAsS  
       2023-09-06 17:05:12 +08:00
    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
        38
    szdosar  
       2023-09-06 19:07:08 +08:00 via iPhone
    https://drive.google.com/file/d/1-Kv19SR2HITSiWnzs6XzI_JqyqcjpK2w/view?usp=sharing
    - - - - - - - - - - - - - - -
    感谢指点,我也就是半桶水,上面这个链接是源码。
    RedisMasterNode
        39
    RedisMasterNode  
       2023-09-06 19:20:44 +08:00
    可以很暴力解决,如果数据量不太大

    https://pastebin.com/raw/q3wf0h23

    测试例子:
    >>> str1 = "abcdefgandhahaok"
    >>> str2 = "acsdefokokhhaha00"
    >>> find_common_substrings(str1, str2, 3)
    ['def', 'hah', 'haha', 'aha']
    RedisMasterNode
        40
    RedisMasterNode  
       2023-09-06 19:21:08 +08:00
    >>> find_common_substrings(str1, str2, 4)
    ['haha']
    RedisMasterNode
        41
    RedisMasterNode  
       2023-09-06 19:24:30 +08:00
    补充一句刚刚测试了一下大约 2000 字符的对比,其实很快很快,主要看楼主希望达到什么程度,例如最差最差接受 1 秒执行完,那是非常轻松的,如果是真的有 1ms 内处理的需求再考虑其他方案就是了
    SaberJack
        42
    SaberJack  
       2023-09-06 19:35:56 +08:00
    动态规划可以解决
    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
        43
    Tstxxy  
       2023-09-06 19:44:55 +08:00
    两个字符串的公共子序列肯定包含楼主要的连续 4 个以上相同字符的序列。
    其实只需要在状态表格中加多一个字段,表示已经有连续几个字符相同了。
    以上算法的复杂度为 o(mn)
    楼主可以先了解公共子序列的算法。
    blueboyggh
        44
    blueboyggh  
    OP
       2023-09-07 09:49:40 +08:00
    https://pastebin.com/raw/irdJS0iK


    @NoOneNoBody 麻烦给看看我处理的缩进和完善的 demo 是否有问题?测试结果只能输出一个“ 万彩票”
    liuhai233
        45
    liuhai233  
       2023-09-07 11:37:07 +08:00
    szdosar
        46
    szdosar  
       2023-09-07 11:37:18 +08:00
    我处理了一下你这个代码的缩进 https://pastebin.com/raw/6mEqdaZG
    输出是:
    '''
    是个好日子,
    [Finished in 131ms]
    '''
    NoOneNoBody
        47
    NoOneNoBody  
       2023-09-07 11:37:36 +08:00
    @blueboyggh #41
    不对
    1.交换 s/ss 那行缩进多了,但不影响
    2.从 sss.reverse()开始到结束,都是在第一个 for 内部的,所以全部需要再增加缩进一层
    blueboyggh
        48
    blueboyggh  
    OP
       2023-09-07 13:55:45 +08:00
    @szdosar
    @NoOneNoBody

    对,现在输出能出第一个相同字符串“是个好日子,”了,但是“中了 500 万彩票”没有,是因为我对 yield 返回的 x 的处理方式不对吗?
    szdosar
        49
    szdosar  
       2023-09-07 14:15:29 +08:00
    不要执着于用迭代操作,我们来分析一下。
    ##itertools 是一个非常强大的库,它提供了很多用于处理迭代操作的工具。但是,对于特定的问题,直接的算法可能会更加高效。
    ##在我们的情境中,我们要找的是两个字符串之间的所有公共子串。使用 itertools 可能会涉及生成所有可能的子串组合,然后再进行比较,这在某些情况下可能会导致不必要的计算。
    ##而我们使用的滑动窗口方法是基于以下观察结果的:
    ##如果两个字符串在某个位置有一个公共字符,那么我们可以尝试扩展这个匹配,直到找到一个公共子串或匹配失败为止。
    ##通过这种方式,我们可以立即找到一个公共子串,而不需要生成和比较所有可能的子串组合。
    ##因此,对于这个特定的问题,滑动窗口方法可能会比使用 itertools 更加高效。但这并不意味着 itertools 不是一个有用的库。对于其他类型的问题,itertools 可能会提供更简洁、更高效的解决方案。
    ##以下使用滑动窗口方法
    ##find_common_substrings_huadong
    源代码效率可大幅提高:
    https://pastebin.com/raw/Qfr31L8a
    NoOneNoBody
        50
    NoOneNoBody  
       2023-09-07 14:18:27 +08:00
    @blueboyggh #48
    你是全部用了 #45 的代码吧?
    他最后一句是用 next ,这个只返回第一个,改为 list(gg)是全部返回
    如果想按长度排序(倒序),用 sorted(gg, key=len, reverse=True)
    blueboyggh
        51
    blueboyggh  
    OP
       2023-09-07 14:24:16 +08:00
    @NoOneNoBody 谢谢,改成 list 就好了,next 是从网上抄的。
    NoOneNoBody
        52
    NoOneNoBody  
       2023-09-07 14:50:13 +08:00
    @szdosar #49
    滑动思路没有错,只是 window 的尺寸不定,从 min 到 length 都有,离不开每个 window 尺寸轮询
    itertools.accumulate 在这里的作用就是自动生成不同 window 尺寸的切片,省了轮询的时间

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

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

    我花了不少时间在这个上面,这个看上去是字符串问题,但实际是队列问题,如果能找到一个非常高效的方法的话,在 pandas 是非常有用的,大数据中快速寻找连续等值的片段用途多得很,所以我才写了个看上去跟字符串无不相干的 pandas 方案
    juny1998
        53
    juny1998  
       2023-09-07 15:18:57 +08:00
    chatGPT 的回答
    juny1998
        54
    juny1998  
       2023-09-07 15:19:09 +08:00
    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
        55
    blueboyggh  
    OP
       2023-09-07 15:19:42 +08:00
    @szdosar
    @NoOneNoBody

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

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

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

    以上结果可能因为本人代码小白的问题受影响,不代表三种方法的真实水平,或者有其他隐含的坑我没能力发现
    szdosar
        56
    szdosar  
       2023-09-07 15:31:21 +08:00   ❤️ 1
    可以改进的,返回的子串之间有相互包含的情况。我们在添加子串到结果集之前进行检查,可以检查新找到的子串是否包含在结果集中的任何子串中,或者结果集中的任何子串是否包含在新找到的子串中。
    fix 源码 https://pastebin.com/raw/6aKqeUrP
    Pipecraft
        57
    Pipecraft  
       2023-09-07 15:32:38 +08:00
    @NoOneNoBody #52 感谢对这个正则的肯定。
    正则内部是通用的算法,肯定会比针对特定问题优化的算法速度慢。
    所以上面(#12 )回复里说了“如果只是执行一次的任务,那可以怎么简单怎么来。”
    如果是反复执行并且数据量很大,那不建议用正则表达式。

    #12 层里的代码并不完整,#18 层里的代码更完整,只是速度更慢。
    https://pastebin.com/raw/UgzrPbA7
    Pipecraft
        58
    Pipecraft  
       2023-09-07 15:39:25 +08:00
    @blueboyggh #55 处理多条数据时,正则表达式要使用 compile 后的结果,如果每次都 compile 一次,会很慢。
    即不要直接使用 #12 层的代码,使用 #18 层的代码。
    当然,我相信上面的测试是这么做的。
    blueboyggh
        59
    blueboyggh  
    OP
       2023-09-07 16:18:38 +08:00
    @Pipecraft 我的问题,18#的源码我只应用了前后对比两次的逻辑,其他的没用,估计影响了结果,一会儿我修改一下再测试一下试试
    NoOneNoBody
        60
    NoOneNoBody  
       2023-09-07 16:33:17 +08:00   ❤️ 1
    呵呵,发现自己有点钻牛角尖了,不追求 yield 和去叠加就没必要再轮询一次,可以少好多行代码

    而且 itertools.accumulate 是先生成后比较,概率上无效的肯定更多,比起滑动跳过无效的,工作量更多
    嗯,重练一遍
    blueboyggh
        61
    blueboyggh  
    OP
       2023-09-07 16:58:57 +08:00
    @NoOneNoBody 期待新代码共享
    blueboyggh
        62
    blueboyggh  
    OP
       2023-09-07 17:00:00 +08:00
    @Pipecraft 使用 18#的代码后,测试 100 条数据时间从 63 秒变成 59 秒,好像变化不多,是不是我的问题?
    blueboyggh
        63
    blueboyggh  
    OP
       2023-09-07 17:04:55 +08:00
    @szdosar 感谢,测试使用新代码,结果里没有相互包含的子元素了
    NoOneNoBody
        64
    NoOneNoBody  
       2023-09-07 17:20:07 +08:00
    @blueboyggh #63
    就此题来说,@szdosar #49 帖的代码足够好了,你是用这个测出最短时间的吧?
    我现在只是翻翻 more_itertools 有没有可用的东西,如果没有,也就不会写出更高效率的了

    https://stackoverflow.com/questions/66668405/python-sliding-windows-of-a-list
    这里有个关于 moving window (移动窗口)的例子,感觉也差不多
    blueboyggh
        65
    blueboyggh  
    OP
       2023-09-07 17:38:53 +08:00
    @NoOneNoBody 好的,确实是#49 的时间最短,感谢
    NoOneNoBody
        66
    NoOneNoBody  
       2023-09-07 18:22:28 +08:00
    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
        67
    Pipecraft  
       2023-09-07 18:46:16 +08:00
    @blueboyggh #62 差不多会那样,毕竟相比匹配用的时间,compile 表达式的时间没有多少。
    NoOneNoBody
        68
    NoOneNoBody  
       2023-09-07 21:29:10 +08:00
    @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
        69
    NoOneNoBody  
       2023-09-07 21:46:30 +08:00
    @NoOneNoBody #68
    秀逗了,长度 len 可以用这个,但匹配不能用这个,逻辑不对

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

    算了,今天到此为止,脑子都打结了,去娱乐一下
    cy18
        70
    cy18  
       2023-09-08 12:55:45 +08:00
    用 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
        71
    blueboyggh  
    OP
       2023-09-26 08:23:43 +08:00
    @Pipecraft
    @NoOneNoBody

    由于现在数据量上升到了将近 10w 条,现在跑完一遍数据需要二十多个小时,这个滑动窗口的方法,还有什么能优化的地方吗?比如上多线程啥的?
    NoOneNoBody
        72
    NoOneNoBody  
       2023-09-26 11:19:30 +08:00
    @blueboyggh #71
    10w 条的话
    1. 向量化函数
    2. 一些机器学习方向的包,#70 那个不知道是不是,这种包都是需要花时间建模,然后应用很快
    3. 多进程并发,多线程因为 GIL 没用

    前两个需要学习成本,但学会就很有用,可以用到其他工作,不仅是字符串,尤其是大批量的数值计算
    并发的话比较快上手,因为单例函数已经存在,建进程池而已,花点时间比较一下其他并发包的 performance ,有不少比原生更快的
    Pipecraft
        73
    Pipecraft  
       2023-09-28 09:37:24 +08:00
    @blueboyggh #71 可以保存跑过的数据的结果,下次不再计算这个部分,只计算增量的部分。

    但是,如果每天都有新的 10 w 条数据,可以考虑多个机器同时跑然后汇总,毕竟都是可以独立运算的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   921 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 21:27 · PVG 05:27 · LAX 14:27 · JFK 17:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.