如何在Python中从Trie搜索结果中筛选特定匹配？

问题根源 #

当前实现存在三个核心问题：

• 短子串误匹配：Trie的search方法会将路径上所有标记为is_end_of_word的节点都作为匹配结果返回，包括单个字符、短子串（比如完整实体中的单个字符）。
• 位置计算错误：使用text.find(match[0])获取起始位置时，会返回该子串第一次出现的位置，而非当前匹配的实际位置，导致重复子串的位置信息错误。
• 重复匹配未跳过已匹配区域：遍历文本时未跳过已匹配的字符，导致同一区域内的短子串被多次识别。

解决方案 #

1. 最长匹配优先：对每个文本起始位置，优先匹配最长的有效实体，忽略路径上的短子串匹配。
2. 记录实际匹配位置：搜索时直接记录每个匹配的起始、结束索引，避免依赖find方法导致的位置偏差。
3. 跳过已匹配区域：找到最长匹配后，将文本遍历指针跳转到匹配结束的位置，避免重复处理同一区域。

修改后的完整代码 #

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False
        self.category = None


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word, category):
        current = self.root
        for char in str(word):
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.is_end_of_word = True
        current.category = category

    def search(self, text):
        matches = []
        i = 0
        while i < len(text):
            current = self.root
            j = i
            longest_match = None
            longest_category = None
            longest_end = i
            # 寻找当前起始位置的最长匹配实体
            while j < len(text) and text[j] in current.children:
                current = current.children[text[j]]
                if current.is_end_of_word:
                    # 更新最长匹配的信息
                    longest_match = text[i:j+1]
                    longest_category = current.category
                    longest_end = j + 1
                j += 1
            # 找到有效匹配则记录，并跳过已匹配区域
            if longest_match is not None:
                matches.append((longest_match, longest_category, i, longest_end))
                i = longest_end
            else:
                # 无匹配则移动到下一个字符
                i += 1
        return matches


def build_trie(trie: Trie = None) -> Trie:
    """构建Trie数据结构。

    参数:
        trie (Trie): 传入的Trie数据结构。

    返回:
        Trie: 构建完成的Trie数据结构。

    异常:
        FileNotFoundError: 文件未找到时抛出。
        ValueError: Excel文件中无有效数据时抛出。
    """
    if trie is None:
        trie = Trie()
    try:
        categories = [
            "person",
            "organization",
            "location",
            "facility",
            "product",
            "event",
        ]
        file_names = [category + ".xlsx" for category in categories]
        entities = merge_excel_files(file_names)
        for _, row in entities.iterrows():
            trie.insert(row["word"], row["category"])
        return trie
    except Exception as e:
        LOGGER.info(msg=f"Error occurred while building the trie: {e}")
        raise


def search_entities(text: str, id: int, trie: Trie) -> dict:
    """在波斯语文本中搜索实体，并以JSON格式返回匹配结果用于命名实体识别（NER）。

    参数:
        text (str): 待搜索的文本。
        trie (Trie): 包含实体的Trie数据结构。

    返回:
        dict: 包含匹配结果的字典。

    示例:
        >>> search_entities('وزرارت ورزش و جوانان را دوست دارم.', trie)
            [
                {
                    "text": "وزرارت ورزش و جوانان را دوست دارم.",
                    "id": 5,
                    "pre": [
                        {
                            "id": 1,
                            "start": 0,
                            "end": 15,
                            "word": "وزرارت ورزش و جوانان",
                            "category": "organization"
                        }
                    ]
                }
            ]

    """
    matches = trie.search(text)
    result = [
        {
            "text": text,
            "id": id,
            "pre": [
                {
                    "id": idx + 1,
                    "start": start,
                    "end": end,
                    "word": word,
                    "category": category
                }
                for idx, (word, category, start, end) in enumerate(matches)
            ],
        }
    ]
    return result


trie = build_trie()
text = "آلبرت انیشتین در بزرگراه آزادگان به همراه پرویز معین به سوی پردیس سینمایی راگا در حال حرکت هستند."
print(search_entities(text, 2500, trie))

修改说明 #

• Trie.search方法改为while循环遍历文本，对每个起始位置优先寻找最长匹配实体，仅记录最长结果，并跳过已匹配区域。
• 搜索结果直接返回匹配的start和end索引，避免使用text.find导致的位置错误。
• search_entities直接使用返回的索引构建结果，确保位置信息准确。

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