字符串压缩：生成唯一子串标识算法性能优化求助

我需要构建两个数据集字符串标识的交叉映射，核心是把每个字符串压缩成能唯一标识它的最短子串——比如"Apples"可以压缩为"es"（无其他ID包含该子串），"Alpha"则因为"lp"和"Al"都是最短唯一子串，用逗号拼接作为压缩ID。

原代码通过生成每个字符串的所有子串，再逐一校验唯一性，但面对7000万条记录时性能完全无法满足，核心瓶颈在于：

• 生成所有子串的时间复杂度为O(n²)，长字符串的子串数量会指数级增长
• 校验子串唯一性时，暴力遍历所有其他字符串的子串集合，属于O(m*k)的低效操作（m为总记录数，k为单条字符串的子串数）

以下是针对千万级数据集的优化方案：

方向1：反向统计子串出现频率（优先推荐） #

换思路：先统计全量数据中每个子串的出现次数，再按子串长度从小到大查找目标字符串中出现次数=1的最短子串，找到后直接终止后续长度的处理。

优化代码示例 #

from collections import defaultdict

def find_minimal_unique_substrings(dataset):
    max_str_len = max(len(s) for s in dataset) if dataset else 0
    len_to_freq = {}

    # 按子串长度从小到大遍历，找到最短唯一子串就停止
    for substr_len in range(1, max_str_len + 1):
        freq_counter = defaultdict(int)
        # 第一轮：统计当前长度所有子串的出现次数
        for s in dataset:
            if len(s) < substr_len:
                continue
            for i in range(len(s) - substr_len + 1):
                substr = s[i:i+substr_len]
                freq_counter[substr] += 1
        len_to_freq[substr_len] = freq_counter

        # 第二轮：检查每个字符串是否有当前长度的唯一子串
        result = {}
        all_found = True
        for s in dataset:
            if len(s) < substr_len:
                result[s] = ""
                all_found = False
                continue
            unique_subs = []
            for i in range(len(s) - substr_len + 1):
                substr = s[i:i+substr_len]
                if freq_counter[substr] == 1:
                    unique_subs.append(substr)
            if unique_subs:
                result[s] = ",".join(set(unique_subs))
            else:
                result[s] = ""
                all_found = False
        if all_found:
            return result
    # 极端情况：所有子串都重复，返回原字符串
    return {s: s for s in dataset}

优势 #

• 按长度递增处理，找到最短唯一子串就终止，避免生成不必要的长串
• 统计子串频率的时间复杂度为O(total_characters)，远低于原算法的O(n*s²)（s为单字符串平均长度）

方向2：利用后缀自动机（Suffix Automaton） #

后缀自动机可以高效表示所有子串，且能快速统计子串出现次数，适合超大规模字符串集合：

1. 构建所有字符串的全局后缀自动机，每个状态记录对应子串的出现次数
2. 对每个字符串，通过后缀自动机快速枚举其所有子串，筛选出出现次数为1的最短子串

优势 #

• 构建时间复杂度为O(total_characters)，空间复杂度远低于存储全量子串的哈希表，适合处理亿级规模数据

方向3：替代方案（非子串压缩） #

如果不需要严格的子串格式，可采用更高效的标识方案：

• 唯一哈希值：计算字符串的SHA-256哈希，取前N位（冲突概率极低），缺点是无可读性
• 聚类压缩：对相似字符串聚类，用前缀+差异子串的方式生成短标识
• 布隆过滤器：先快速排除重复字符串，再对唯一字符串生成短标识

额外性能优化细节 #

• 用Cython或NumPy重写核心统计逻辑，Python原生循环在千万级数据下效率极低，编译型语言循环可提升几十倍速度
• 采用分治策略：将数据集分块统计子串频率，再合并结果，避免内存溢出
• 优先处理短字符串，因为短字符串的最短唯一子串长度通常更小，可提前完成计算

内容的提问来源于stack exchange，提问作者Cem Ozd