【每日一题】Python 编程题：检测大模型输出的「复读机」退化（附参考答案）

hogwarts · 2026 年11 月 5 日 09:44

题目：长文本生成（摘要、文案、Agent 长回复）最容易出现的线上退化就是「复读机」——同一段话循环输出。现给你一批模型输出 texts，实现函数 eval_repetition，对每条文本做退化统计并给出 badcase 清单（字符级处理，中文按字切）：

rep_rate：n-gram 重复率 =（n-gram 总数 − 去重后的 n-gram 个数）/ n-gram 总数，保留 4 位小数
max_dup_len：最长重复子串的长度（允许重叠，如 "aaaa" 的最长重复子串是 "aaa"，长度为 3）；无任何重复则为 0
bad_index / bad_count：rep_rate >= threshold 的样本下标列表与数量
avg_rate：全量平均重复率（4 位小数）；worst：重复率最高的样本下标（并列取下标最小者）

约束：① n < 1 抛 ValueError；② 空串或长度不足 n 时 rep_rate 记 0.0，不许抛异常；③ texts 为空列表时返回 avg_rate=0.0、worst=-1、bad_index=[]；④ 不准调用 sklearn / nltk 等第三方库。

代码框架：

def eval_repetition(texts: list[str], n: int = 4, threshold: float = 0.3) -> dict:
    """批量检测大模型输出的重复退化（复读机）。

    Args:
        texts:     模型输出文本列表
        n:         n-gram 的 n，默认 4（字符级）
        threshold: 判定 badcase 的重复率阈值，rep_rate >= threshold 即为 badcase
    Returns:
        {
            "avg_rate": 平均重复率(4位小数),
            "worst": 重复率最高样本的下标(并列取最小下标),
            "bad_count": badcase 数量,
            "bad_index": badcase 下标列表,
            "details": [{"index": i, "rep_rate": x, "max_dup_len": y}, ...]
        }
    Raises:
        ValueError: n < 1
    """
    pass

自测断言：

texts = [
    "非常好非常好非常好非常好非常好",                              # 循环复读
    "这个方案不行这个方案不行这个方案不行这个方案不行",                # 循环复读
    "系统将于每周二凌晨 02:00 进行例行维护，预计持续 30 分钟。",        # 正常
    "这款产品的整体表现非常出色，在多个维度上都有明显提升，值得推荐。",  # 正常
]
r = eval_repetition(texts, n=4, threshold=0.3)
assert [(d["rep_rate"], d["max_dup_len"]) for d in r["details"]] == [
    (0.75, 12), (0.7143, 18), (0.0, 2), (0.0, 1)]
assert r["avg_rate"] == 0.3661 and r["worst"] == 0
assert r["bad_count"] == 2 and r["bad_index"] == [0, 1]
assert eval_repetition([""], n=4)["details"][0]["rep_rate"] == 0.0     # 空串不能崩
assert eval_repetition(["ab"], n=4)["details"][0]["max_dup_len"] == 0  # 长度不足且无重复
assert eval_repetition([], n=4)["worst"] == -1
try:
    eval_repetition(["abc"], n=0)
    raise AssertionError("should raise")
except ValueError:
    pass

难度：中级
题型：笔试（编程题）

hogwarts · 2026 年11 月 5 日 09:45

参考答案/答题要点：

思路一（直观解：集合去重 + 逐长度试探，O(n²)）。n-gram 重复率一行集合就搞定；最长重复子串用「长度从 1 递增试探」，一旦某个长度找不到重复就提前退出——因为若长度 L+1 存在重复，其长度为 L 的前缀必然也重复，单调性保证了 break 的正确性。

def eval_repetition(texts, n=4, threshold=0.3):
    if n < 1:
        raise ValueError("n must be >= 1")

    def rep_rate(s):
        total = len(s) - n + 1
        if total <= 0:
            return 0.0
        grams = {s[i:i + n] for i in range(total)}
        return round((total - len(grams)) / total, 4)

    def longest_dup(s):
        best = 0
        for L in range(1, len(s)):
            seen = set()
            hit = False
            for i in range(len(s) - L + 1):
                sub = s[i:i + L]
                if sub in seen:
                    hit = True
                    break
                seen.add(sub)
            if not hit:
                break
            best = L
        return best

    details = [{"index": i, "rep_rate": rep_rate(t), "max_dup_len": longest_dup(t)}
               for i, t in enumerate(texts)]
    bad = [d["index"] for d in details if d["rep_rate"] >= threshold]
    avg = round(sum(d["rep_rate"] for d in details) / len(details), 4) if details else 0.0
    worst = max(details, key=lambda d: d["rep_rate"])["index"] if details else -1
    return {"avg_rate": avg, "worst": worst, "bad_count": len(bad),
            "bad_index": bad, "details": details}

hogwarts · 2026 年11 月 5 日 09:45

思路二（优雅解：Counter 累加重复次数 + 二分求最长重复子串）。重复率不必先去重再相减，直接 sum(v-1)，语义更贴「多出来的 n-gram 个数」；最长重复子串改成二分答案，把 O(n²) 降到 O(n log n)，长文本（模型输出动辄上千字）差距明显。

from collections import Counter


def rep_rate_v2(s, n=4):
    total = len(s) - n + 1
    if total <= 0:
        return 0.0
    c = Counter(s[i:i + n] for i in range(total))
    return round(sum(v - 1 for v in c.values()) / total, 4)


def longest_dup_v2(s):
    def has_dup(L):
        if L <= 0:
            return False
        seen = set()
        for i in range(len(s) - L + 1):
            sub = s[i:i + L]
            if sub in seen:
                return True
            seen.add(sub)
        return False

    lo, hi = 0, max(0, len(s) - 1)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if has_dup(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo


def eval_repetition_v2(texts, n=4, threshold=0.3):
    if n < 1:
        raise ValueError("n must be >= 1")
    details = [{"index": i, "rep_rate": rep_rate_v2(t, n), "max_dup_len": longest_dup_v2(t)}
               for i, t in enumerate(texts)]
    bad = [d["index"] for d in details if d["rep_rate"] >= threshold]
    avg = round(sum(d["rep_rate"] for d in details) / len(details), 4) if details else 0.0
    worst = max(range(len(details)), key=lambda i: details[i]["rep_rate"]) if details else -1
    return {"avg_rate": avg, "worst": worst, "bad_count": len(bad), "bad_index": bad,
            "details": details}

hogwarts · 2026 年11 月 5 日 09:45

思路三（加分解：后缀排序 + 相邻 LCP）。把所有后缀排序后，最长重复子串 = 相邻后缀的最长公共前缀的最大值，一行 max 出结果，面试能讲清这个结论非常加分（注意 Python 按 s[i:] 排序实际是 O(n² log n)，工程上要用 SA-IS 或滚窗哈希）。

def longest_dup_suffix(s):
    if len(s) < 2:
        return 0
    sa = sorted(range(len(s)), key=lambda i: s[i:])
    best = 0
    for a, b in zip(sa, sa[1:]):
        k = 0
        while k < min(len(s) - a, len(s) - b) and s[a + k] == s[b + k]:
            k += 1
        best = max(best, k)
    return best

hogwarts · 2026 年11 月 5 日 09:45

三种实现的输出完全一致（已用 3000 组随机中英混排样本与最朴素的两两后缀对比做对拍验证）。

采分点：

n-gram 的切法要说清楚是字符级（中文场景），总数是 len-n+1，边界 len < n 直接返回 0.0；
最长重复子串允许重叠，"aaaa" → 3 而不是 2，这里最容易写错；
长度试探能提前 break / 能二分，靠的是「短的必重复 ⇒ 长的可能不重复」这一单调性，讲得出比写出来更加分；
除零与空列表保护（avg_rate、worst、max 空序列都会炸）；
并列最高取最小下标——口径要稳定，否则回归对比时同一批数据每次给不同 worst；
指标语义：rep_rate 高≠一定差（模板类文本天然重复多），阈值要按任务类型分别定；
工程延伸：可再补 Distinct-N、Self-BLEU、循环周期检测（找出最小重复单元），并保留 badcase 原文供人工复核，不要只做门禁卡断。