如何实现字母序列的二次分组压缩？Python代码优化求助

你现在的代码已经完成了一级游程编码（Run-Length Encoding），也就是把连续重复的单个字符压缩成「字符+次数」的形式，但要实现二次分组（识别重复的压缩子串），我们需要在一级压缩的基础上，再做一层「重复子串匹配与替换」的处理。

第一步：优化一级压缩代码 #

先确保你的一级压缩能稳定输出A2B2A2B2AC，你的现有代码逻辑是对的，这里优化下可读性：

def run_length_encode(seq):
    if not seq:
        return ""
    comp = []
    current_char = seq[0]
    count = 1
    for char in seq[1:]:
        if char == current_char:
            count += 1
        else:
            comp.append(current_char)
            if count > 1:
                comp.append(str(count))
            current_char = char
            count = 1
    # 处理最后一组剩余的字符
    comp.append(current_char)
    if count > 1:
        comp.append(str(count))
    return ''.join(comp)

测试：run_length_encode("AABBAABBAC")会输出A2B2A2B2AC，和你当前的结果一致。

第二步：实现二次分组压缩 #

接下来要解决的核心问题是：在一级压缩结果中，找到重复出现的连续子串，将其替换为(子串)次数的形式。这里要注意优先匹配最长的重复子串，避免短子串先匹配导致长重复单元被拆分。

比如对于A2B2A2B2AC，我们要先识别出最长的重复子串A2B2（重复2次），而不是拆成更短的子串组合。

实现这个逻辑的函数如下：

def secondary_compress(s):
    n = len(s)
    # 从最长的可能子串长度开始检查，最小长度设为2（单个字符的重复已经在一级处理过）
    for length in range(n//2, 1, -1):
        i = 0
        while i <= n - 2*length:
            substring = s[i:i+length]
            # 检查后续长度是否和当前子串完全一致
            if s[i+length:i+2*length] == substring:
                # 统计完整的重复次数
                count = 2
                j = i + 2*length
                while j + length <= n and s[j:j+length] == substring:
                    count += 1
                    j += length
                # 替换重复子串为分组格式
                s = s[:i] + f"({substring}){count}" + s[j:]
                n = len(s)  # 更新字符串长度，适配后续检查
                i = j  # 跳到替换后的位置继续处理剩余内容
            else:
                i += 1
    return s

第三步：组合两个函数 #

把一级压缩和二次压缩逻辑结合，就得到最终的压缩函数：

def compact_rep(seq):
    # 第一步：完成单个字符的连续重复压缩
    encoded = run_length_encode(seq)
    # 第二步：识别并压缩重复的子串单元
    compressed = secondary_compress(encoded)
    return compressed

测试验证：

print(compact_rep("AABBAABBAC"))  # 输出：(A2B2)2AC

补充说明 #

• 这个逻辑会优先匹配最长的重复子串，避免出现误拆分的情况（比如不会把A2B2A2B2拆成(A2)2(B2)2）
• 支持多层重复，比如A2B2A2B2A2B2会被压缩成(A2B2)3
• 无法形成重复子串的片段（比如末尾的AC）会保留原样

内容的提问来源于stack exchange，提问作者Catarina Ribeiro