多模式字符串匹配下的匹配结果去重：避免重复命中的实用处理方案

一、先聊聊这是什么场景

在咱们日常开发里，经常会遇到这样的活儿：给你一份关键词清单，让你在一大段文本里把出现的位置全找出来。比如搞网络内容安全的，要实时拦截违规词；做日志分析的，要从一堆日志里挑出关心的事件；还有电商系统的搜索建议，也得把用户输入和一堆候选商品名同时匹配。这种一次性拿多个关键词去文本里找命中位置的操作，就是所谓的多模式字符串匹配。

匹配完只是第一步，真正头疼的是结果里经常混着一堆“假重复”。比如关键词清单里既有“中华人民共和国”，又有“中华”和“人民共和国”，那么文本一开始，三个词全都命中了，位置还叠在一起。如果咱们直接把这些结果一股脑交给下游，同一条内容会被重复计数、重复报警、重复展示，看着就别扭，也会让运营同学误以为系统有问题。所以，怎么把重复命中清理干净，就成了多模式匹配方案里绕不开的一个环节。

这篇文章不聊太悬的数学原理，就讲讲怎么用顺手的方式把匹配结果去重。我会用 Python 实现几个方案，从最简单的排序到高效的工具库，一步步把问题掰开揉碎。

二、重复命中是怎么产生的

要处理重复，先要明白重复从哪来。我在实际项目里见过的情况，大概有这么几类。

2.1 关键词互相包含

“中国”和“中国人民”，文本里出现“中国人民”，那“中国”肯定也会在开头命中。两个结果一条长一条短，位置重叠。如果不做去重，一条内容会触发两次检测。

2.2 关键词之间有交叉但谁也不包含谁

比如关键词“abcd”和“cdef”，文本“abcdef”里，前一个命中 0 到 4，后一个命中 2 到 6，中间有一段重合。在某些业务里，这两个结果代表了两条不同的规则，应该都保留；但在另一类业务里，可能只关心“这段文本到底覆盖了哪些区间”，这时就需要把重叠区间合并。

2.3 同一个关键词被重复输出

即便只有一个关键词，如果匹配算法内部有多条路径会走到同一个结果，也可能会把同一个位置输出两遍。尤其是在用了自动机或者正则表达式并且打开了重叠匹配时，这种情况就更常见。

三、去重前需要想清楚的两件事

动手写代码之前，我建议先花几分钟把需求定清楚。不然代码写一半容易跑偏。

3.1 明确“重复”的定义

重复到底是指什么？是起始位置和结束位置都相同的两条记录？还是只要位置有重叠就算重复？这个定义直接决定你采用哪种去重策略。如果只去掉完全一致的记录，那用集合就行；如果想合并重叠区间，那就得排序加比较。

3.2 明确去重的优先级

位置相同时应该保留哪个关键词？是最长的那个？还是按关键词在清单里的顺序？还是看规则的优先级？不同场景有不同答案。最稳妥的办法是在去重之前给每个关键词定义一个权重，去重时按权重保留。

四、方案一：位置排序合并

这个方案特别直观：把所有的匹配结果按起点从小到大排列，如果起点一样，就把终点长的放前面。排好之后，从头扫一遍，在扫的过程中维护一个“当前已经覆盖到的最远结束位置”。只有当前这条命中能越过这个最远位置时，才把它收下，并更新最远位置。这样一来，落在已有覆盖范围内的命中就被自然过滤掉了。

下面用 Python 演示一遍。

4.1 原始匹配

# 技术栈：Python 3.9
# 先把所有关键词的所有出现位置找出来
# 这里为了演示简单，直接用字符串的 find 方法

text = "中华人民共和国成立了"

matches = []

    start = 0
    while True:
        # 从 start 位置开始找关键词
        pos = text.find(kw, start)
        if pos == -1:
            break  # 找不到了就跳过
        # 记录起点、终点（终点用开区间）、关键词
        matches.append((pos, pos + len(kw), kw))
        # 继续往后找，允许重合位置出现
        start = pos + 1

# 按起点升序排序，起点相同就让更长的排在前面
matches.sort(key=lambda x: (x[0], -x[1]))

# 打印排序后的结果
print("原始命中：")
for m in matches:
    print(m)

4.2 合并去重

# 接上面
# 目标：合并位置重叠的命中，让每条文本区间只保留一次

filtered = []
max_end = -1

for start, end, kw in matches:
    if end <= max_end:
        # 这条命中被已保留的命中完全覆盖了，不需要
        continue
    # 这条命中扩展了覆盖范围，留下来
    filtered.append((start, end, kw))
    max_end = end

print("\n去重之后：")
for m in filtered:
    print(m)

这种方案处理包含关系特别干净。但要注意，如果两条命中只是部分交叉，而各自都有独立的扩展范围，上面的代码会把两条都保留。比如“abcd”和“cdef”，后一条的终点更远，所以都会保留。从区间覆盖的角度看，这是合理的。

五、方案二：哈希集合去重

如果说位置排序合并是“重内容”，那哈希集合去重就是“轻操作”。它不关心区间是否重叠，只负责去掉完全相同的记录。这种方案适合那些需要保留所有不同规则命中的场景。

5.1 使用三元组做去重键

# 技术栈：Python 3.9
# 将(起点, 终点, 关键词)作为去重键

raw_matches = [
    (0, 3, "中华人民共和国"),
    (0, 2, "中华"),
    (0, 3, "中华人民共和国"),  # 模拟重复输出
    (6, 9, "共和国"),
]

seen = set()
unique_matches = []

for start, end, kw in raw_matches:
    key = (start, end, kw)  # 只要这个三元组出现过，就丢弃
    if key in seen:
        continue
    seen.add(key)
    unique_matches.append((start, end, kw))

print("去重结果：")
for item in unique_matches:
    print(item)

运行后，第三条和第一条完全一样，就被去掉了。第一条和第二条、第四条位置各不相同，全部保留。这个方案最大的好处是可以随时加字段，比如把规则 ID、匹配优先级都放进去。缺点是如果原始匹配结果里有几十万条，内存占用会变大。

5.2 只按位置去重

有些业务不在乎命中哪个词，只关心某个位置有没有命中过。这时候去重键就只用起点和终点。

# 技术栈：Python 3.9
# 只根据位置去重，忽略具体是哪个关键词命中的

raw_matches = [
    (0, 2, "北京"),
    (0, 3, "北京市"),
    (0, 2, "北京市"),  # 位置重复
]

seen_pos = set()
unique_matches = []

for start, end, kw in raw_matches:
    pos_key = (start, end)
    if pos_key in seen_pos:
        continue
    seen_pos.add(pos_key)
    unique_matches.append((start, end, kw))

print("按位置去重后：")
for item in unique_matches:
    print(item)

这里第一条和第三条位置都是 (0, 2)，只保留了第一条，第二条因为终点不同，被保留下来。如果希望同一段位置只保留最长关键词，可以在往集合里加之前先按关键词长度排个序，先处理长的。

六、方案三：AC自动机加去重

6.1 为什么需要 AC自动机

前面用 find 方法是一个一个关键词挨个扫，如果关键词只有四五个，那没问题。可一旦关键词涨到几百上千个，文本又是几十万字，这种方式的耗时就会变得不可接受。这时候就需要一个叫 Aho-Corasick 的经典算法。

AC自动机可以理解为在 Trie 树的基础上加了失配指针，它在扫描文本时能同时记住所有关键词的匹配状态。文本每个字符只需要过一遍，所有命中的关键词都能被找到，所以匹配效率非常高。咱们不用自己实现这个算法，直接用 pyahocorasick 这个 Python 库就行。

先装一下库：

# 安装AC自动机库
pip install pyahocorasick

6.2 使用 AC自动机匹配并去重

# 技术栈：Python 3.9 + pyahocorasick
# 演示AC自动机返回多个匹配，再利用集合去掉重复位置

import ahocorasick

# 1. 创建自动机并添加关键词
automaton = ahocorasick.Automaton()

    # 绑定索引和关键词，方便后面看是哪个词命中
    automaton.add_word(word, (index, word))

# 2. 构建自动机
automaton.make_automaton()

# 3. 对目标文本进行匹配
text = "中华人民共和国成立了"
matches = []

# iter会返回每个命中位置的结束下标和之前绑定的数据
for end_index, (index, word) in automaton.iter(text):
    start_index = end_index - len(word) + 1
    matches.append((start_index, end_index + 1, index, word))

print("AC自动机原始命中数量：", len(matches))
for m in matches:
    print(m)

# 4. 使用集合按位置去重
unique = []
seen_keys = set()

for start, end, index, word in matches:
    pos_key = (start, end)
    if pos_key in seen_keys:
        continue
    seen_keys.add(pos_key)
    unique.append((start, end, index, word))

print("\n去重后的命中数量：", len(unique))
for m in unique:
    print(m)

这个例子里，AC自动机会把“中华”和“中华人民共和国”同时输出，虽然它们的起点和终点都不同，所以不会被去重。如果我们把去重键改成起点位置，那就能合并起点相同的命中，变成只保留一种。这里正好体现了“去重键决定业务语义”。

七、正则多模式匹配的坑

有的同学可能会说，我平时用正则表达式也有 | 可以匹配多个词，是不是也能用？确实，简单场景下可以用正则，但这里有几个坑要注意。

第一，正则返回的匹配并不保证把所有可能的重叠匹配都找出来。re.finditer 默认只在每个位置返回一个匹配结果，有时你期望得到多个，结果它只给你一个。第二，如果用某些支持重叠匹配的库，又会输出海量重复结果。第三，正则表达式一旦写得太复杂，比如几十个词用 | 连在一起，匹配速度会变得很慢，还容易出现回溯陷阱。所以，如果是生产环境，关键词数量又多，我更推荐直接用 AC自动机。

八、应用场景

8.1 内容安全平台

内容安全系统每天要扫描用户发的评论、文章、图片里的文字。如果多个敏感词都命中了同一段话，去重之后可以让审核人员只看一条最关键的命中，避免被重复信息淹没。比如一个帖子同时出现“赌博”和“网络赌博”，合并后只报“网络赌博”就够了。

8.2 日志审计

日志里有大量模板化的字符串。假如已知的错误码和模块名有几百个，扫描每一行日志时都会产生多个命中。通过去重，可以准确统计出这一行到底是哪几个模块相关，不会因为子串重叠而重复计数。

8.3 用户输入实时联想

输入法、搜索引擎或者表单自动补全，需要在用户输入过程中同时匹配很多备选词。如果候选词之间存在包含关系，比如用户输入“北京”，算法同时匹配到了“北京”和“北京大学”，界面上只显示一条最合适的提示会更友好。

九、技术优缺点全面对比

9.1 位置排序合并

优点是逻辑直白，写起来快，不需要额外依赖，而且它对内存友好，不需要把所有结果都存下来。缺点是对“重复”的判断比较粗，只适合按区间覆盖来去重的场景。如果两条命中只是端点相同但关键词不同，这个方法会保留一条，但那条不一定是你想要的规则。

9.2 哈希集合去重

优点是灵活，去重键可以随便定义，可读性好。缺点是要先把所有匹配结果都收集起来，内存压力比较大。另外它本身不具备区间合并能力，如果需要合并重叠，还得配合排序。

9.3 AC自动机加集合

优点是匹配性能高，关键词越多优势越明显，适合大数据量、高吞吐的在线服务。缺点是引入了第三方依赖，而且自动机的构建过程需要时间，如果关键词列表频繁变化，就得重新构建自动机，这时成本会变高。

十、注意事项

第一，明确需求里的“重复”是不是真的重复。位置相同但关键词不同，到底算不算重复？不同业务答案完全不同。写代码前要跟业务方确认清楚。

第二，在线实时匹配时，去重逻辑尽量轻量化。不要在命中回调里做排序或者做复杂的数据库查询，否则会拖慢整个请求链路。

第三，如果关键词列表很大，建议给 AC自动机增加一个缓存层。关键词列表不常变化时，就复用同一个自动机，避免每次请求都去构建。

第四，如果文本特别长，建议分块处理。把文本切成段落或句子，每块独立匹配去重，最后再把结果拼起来。这样可以避免一次性把整个超大文本加载进内存。

第五，别忽略空关键词或单字关键词。有些关键词太短，比如长度为一的汉字，它可能在整个文本里命中成千上万次，去重后依然很多。这时候可以设置一个最小匹配长度，把没有分析价值的短词过滤掉。

十一、总结

多模式匹配结果的去重，看起来是个小问题，但如果不处理，会给下游系统带来很多重复的噪声。这篇文章从三个角度聊了解决方案：位置排序合并适合区间合并场景，哈希集合去重适合保留精确不同规则的场景，AC自动机加集合则能在保证性能的同时完成去重。没有哪个方案是万能的，关键是先把业务语义想明白，再去选择最顺手的技术手段。希望这些代码和思路能在你下次写多模式匹配的时候派上用场。