Python实现：基于双查找表低开销标记文本中重叠实体匹配位置

核心需求对齐 #

• 仅在单词边界上做匹配，不需要识别单词内部的子串，从根源减少无效计算
• 支持长短嵌套实体的全量标记（如示例中Barrack和Barrack Obama同时在位置0命中时，需要分别记录）
• 输出为三元组格式(实体文本, 起始字符位置, 所属查找表标签)，完全匹配示例输出要求
• 规避原有实现“逐实体先扫文本查存在性、再二次扫找全位置”的双轮冗余遍历开销

方案一：单词级Trie实现（全嵌套匹配支持） #

这个方案适配所有需要全量标记嵌套实体的场景，单次扫描文本即可完成所有匹配，无重复遍历开销
下面是极简的Pythonic风格Trie实现，不需要依赖第三方库：

import re

class WordLevelTrie:
    def __init__(self):
        self.root = {}
        self.entity_labels = {}  # key: 拆成元组的实体单词序列, value: 所属表标签

    def add_entity(self, entity: str, label: str):
        # 把实体拆成单词元组存入Trie，比如"United States"转为("United", "States")
        word_seq = tuple(entity.split())
        node = self.root
        for word in word_seq:
            node = node.setdefault(word, {})
        self.entity_labels[word_seq] = label

    def match_text(self, text: str):
        results = []
        # 预提取所有单词的原始字符位置，天然对齐单词边界
        word_spans = [(m.group(), m.start()) for m in re.finditer(r"\w+", text)]
        word_count = len(word_spans)

        # 以每个单词为起点，顺着Trie向后匹配
        for start_idx in range(word_count):
            current_node = self.root
            start_pos = word_spans[start_idx][1]
            # 从当前起点向后遍历所有可能的单词组合
            for offset in range(word_count - start_idx):
                current_word = word_spans[start_idx + offset][0]
                if current_word not in current_node:
                    break
                current_node = current_node[current_word]
                # 匹配到实体结尾就记录
                matched_seq = tuple(word for word, _ in word_spans[start_idx : start_idx + offset + 1])
                if matched_seq in self.entity_labels:
                    results.append(
                        (" ".join(matched_seq), start_pos, self.entity_labels[matched_seq])
                    )
        return results

示例使用方式 #

# 初始化Trie并录入实体
trie = WordLevelTrie()
lookupA = ["Barrack", "Barrack Obama"]
lookupB = ["United", "United States", "president"]
for ent in lookupA:
    trie.add_entity(ent, "A")
for ent in lookupB:
    trie.add_entity(ent, "B")

# 匹配目标文本
test_text = "Barrack Obama was president of the United States"
print(trie.match_text(test_text))

输出效果 #

和目标输出完全一致：
[("Barrack", 0, "A"), ("Barrack Obama", 0, "A"), ("president", 18, "B"), ("United", 35, "B"), ("United States", 35, "B")]

方案二：预编译正则实现（最长匹配优先场景） #

如果你不需要标记嵌套的短实体，只需要保留最长匹配结果，这个方案是速度最快、代码最简洁的选择，底层是C实现的正则引擎，性能优于纯Python实现的Trie

import re

def build_matcher(lookupA: list, lookupB: list):
    entity_map = {}
    entity_map.update({ent: "A" for ent in lookupA})
    entity_map.update({ent: "B" for ent in lookupB})
    # 按实体长度从长到短排序，保证长实体的正则优先级更高
    sorted_ents = sorted(entity_map.keys(), key=lambda x: -len(x))
    # 生成带单词边界的预编译正则
    pattern = re.compile(r"\b(" + "|".join(re.escape(ent) for ent in sorted_ents) + r")\b")
    return pattern, entity_map

def match_text(text: str, pattern, entity_map):
    return [
        (m.group(), m.start(), entity_map[m.group()])
        for m in pattern.finditer(text)
    ]

注意：这个方案的正则引擎会在匹配后跳过已消费的字符，无法同时记录存在包含关系的长短实体（比如会优先匹配Barrack Obama，不会额外记录同位置的Barrack），适合只需要最长实体标记的场景。

性能对比 #

• 原有实现的时间复杂度为O(N*M)：N为实体总数，M为文本长度，每个实体都要单独遍历一遍文本查找匹配位置
• 上述两个方案的时间复杂度为O(M + K)：M为文本长度（拆词、单次遍历的开销），K为实体总数（构建Trie/正则的预处理开销），当实体数量较多、文本长度较大时，性能优势会放大10~100倍
• 两个方案都从逻辑上规避了单词内部的子串误匹配（比如查找表有arm时，不会把farm中的arm标记为匹配）

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