如何加速无空格文本分词的穷举算法？Trie可行吗？

我之前也碰到过类似的性能瓶颈——原来的递归穷举之所以慢到离谱，核心问题是每次匹配前缀都要遍历整个词典：比如文本开头有几百个可能的前缀，就要查几百次全量词典，时间复杂度是O(n*m)（n是文本长度，m是词典大小），对30MB的长文本来说完全扛不住。而Trie树（前缀树）能把前缀匹配的时间直接降到O(k)（k是前缀的长度），效率提升不是一星半点。

下面给你两种落地性极强的实现方案：手动实现Trie树（不依赖第三方库），以及用Pytrie库快速搭建，再加上记忆化优化进一步提速。

一、手动实现Trie树 + 记忆化分词 #

如果不想引入第三方依赖，自己写个轻量Trie完全够用，逻辑也清晰。

1. Trie树核心结构 #

先定义Trie节点和基础操作：

class TrieNode:
    def __init__(self):
        self.children = {}  # key: 单个字符, value: TrieNode实例
        self.is_end_of_word = False  # 标记该节点是否是一个完整单词的结尾

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

    # 向Trie中插入一个词典单词
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    # 获取当前文本开头所有匹配的词典单词
    def get_all_prefix_matches(self, text):
        matches = []
        node = self.root
        current_word = ""
        for char in text:
            if char not in node.children:
                break  # 没有更长的前缀匹配了，直接终止
            current_word += char
            node = node.children[char]
            if node.is_end_of_word:
                matches.append(current_word)
        return matches

2. 带记忆化的分词实现 #

用缓存避免重复处理相同的子文本（比如长文本里重复出现的片段），这能进一步降低计算量：

from functools import lru_cache

def trie_based_segmentation(text, trie):
    @lru_cache(maxsize=None)
    def segment_helper(sub_text):
        if not sub_text:
            return [[]]  # 空文本返回空列表的列表，作为递归终止条件
        # 获取当前子文本开头所有匹配的词典单词
        prefix_matches = trie.get_all_prefix_matches(sub_text)
        results = []
        for prefix in prefix_matches:
            # 递归处理剩余文本
            remaining_segments = segment_helper(sub_text[len(prefix):])
            # 拼接当前前缀和剩余文本的分词结果
            for seg in remaining_segments:
                results.append([prefix] + seg)
        return results

    return segment_helper(text)

3. 使用示例 #

# 初始化词典和Trie
dict_words = {'the':1, 'next':2, 'thenext':3, 'day':4}
trie = Trie()
for word in dict_words.keys():
    trie.insert(word)

# 测试分词
text = "thenextday"
segments = trie_based_segmentation(text, trie)
print(segments)
# 输出: [['the', 'next', 'day'], ['thenext', 'day']]

二、用Pytrie库快速实现（更简洁） #

如果不想自己造轮子，Pytrie库已经封装了高效的前缀树实现，直接用就行。

1. 安装Pytrie #

pip install pytrie

2. Pytrie分词实现（带记忆化） #

from pytrie import StringTrie
from functools import lru_cache

def pytrie_based_segmentation(text, dict_words):
    # 用词典构建StringTrie
    trie = StringTrie(dict_words)

    @lru_cache(maxsize=None)
    def segment_helper(sub_text):
        if not sub_text:
            return [[]]
        # Pytrie的prefixes方法直接返回所有匹配的前缀单词
        prefix_matches = list(trie.prefixes(sub_text))
        results = []
        for prefix in prefix_matches:
            remaining_segments = segment_helper(sub_text[len(prefix):])
            for seg in remaining_segments:
                results.append([prefix] + seg)
        return results

    return segment_helper(text)

3. 使用示例 #

dict_words = {'the':1, 'next':2, 'thenext':3, 'day':4}
text = "thenextday"
segments = pytrie_based_segmentation(text, dict_words)
print(segments)
# 输出: [['the', 'next', 'day'], ['thenext', 'day']]

三、额外性能优化点 #

1. 迭代替代递归（可选）：如果文本特别长（超过Python默认递归深度），可以把递归改成迭代栈实现，避免栈溢出：

def iterative_segmentation(text, trie):
    stack = [(text, [])]
    results = []
    while stack:
        current_text, current_seg = stack.pop()
        if not current_text:
            results.append(current_seg)
            continue
        prefix_matches = trie.get_all_prefix_matches(current_text)
        for prefix in prefix_matches:
            stack.append((current_text[len(prefix):], current_seg + [prefix]))
    return results

2. 预处理词典：提前过滤掉词典里的冗余单词（比如如果词典里同时有the和thenext，不用额外处理，Trie会自动处理前缀关系）。

为什么这个方案比原来的快？ #

原来的递归穷举每次匹配前缀都要遍历整个词典，比如词典有10万条，每次匹配就要查10万次；而Trie只需要沿着文本字符走，最多走最长单词的长度（比如最长单词是10个字符，就走10步），直接把匹配次数从几十万降到个位数，30MB的文本处理时间应该能从48小时压缩到几分钟甚至更短。

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