从零实现中文分词算法：FMM/RMM核心原理与Python实战

中文分词是自然语言处理的基础环节，直接影响后续的词性标注、语义分析等任务效果。许多开发者习惯直接调用现成的分词工具，却对背后的算法原理一知半解。本文将带您用Python从零实现三种经典分词算法，并通过"在野生动物园玩"等实例深入解析实现细节。

1. 中文分词基础与算法选择

中文与英文不同，词与词之间没有天然分隔符。例如"野生动物园"可以切分为"野生/动物园"或"野生动物/园"，这给计算机处理带来了挑战。目前主流的分词算法可分为三类：

• 基于词典的方法 ：依赖预设词典进行匹配（如FMM/RMM）
• 基于统计的方法 ：利用语料库统计信息（如N-gram、HMM）
• 混合方法 ：结合词典与统计优势（如Jieba）

# 示例词典结构
word_dict = {
    "野生动物园": 1,
    "野生": 1, 
    "动物园": 1,
    "动物": 1,
    "在野": 1,
    "生动": 1
}

提示：词典质量直接影响分词效果，建议优先使用专业领域词典

2. 正向最大匹配(FMM)算法实现

FMM算法采用"贪心"策略，每次尽可能匹配最长的词典词。其核心流程为：

1. 初始化最大词长max_len
2. 从文本起始位置开始扫描
3. 取当前起始位置+max_len的子串进行词典匹配
4. 若匹配失败则缩短子串长度继续尝试
5. 匹配成功则记录分词结果并移动起始位置

def FMM(dict, sentence):
    max_len = max(len(word) for word in dict)
    result = []
    start = 0
    
    while start < len(sentence):
        end = min(start + max_len, len(sentence))
        word = sentence[start:end]
        
        while len(word) > 1 and word not in dict:
            word = word[:-1]  # 缩短匹配长度
        
        result.append(word)
        start += len(word)
    
    return result

常见问题处理：

• 索引越界 ：需限制end不超过句子长度
• 单字处理 ：当子串长度为1时强制切分
• 词典设计 ：包含专业术语能提升准确率

3. 逆向最大匹配(RMM)算法优化

RMM从句子末尾开始扫描，特别适合处理中文中的偏正结构。实践表明，RMM在多数场景下准确率高于FMM。

def RMM(dict, sentence):
    max_len = max(len(word) for word in dict)
    result = []
    end = len(sentence)
    
    while end > 0:
        start = max(0, end - max_len)
        word = sentence[start:end]
        
        while len(word) > 1 and word not in dict:
            word = word[1:]  # 调整匹配起始位置
        
        result.insert(0, word)  # 逆向插入结果
        end -= len(word)
    
    return result

性能对比实验：

测试句子	FMM结果	RMM结果
"在野生动物园玩"	['在野', '生动', '物', '园', '玩']	['在', '野生动物园', '玩']
"研究生命起源"	['研究生', '命', '起源']	['研究', '生命', '起源']

4. 双向最大匹配(BM)策略实现

BM算法综合FMM和RMM结果，按照以下规则选择最优解：

1. 优先选择分词数量少的结果
2. 数量相同时选择单字较少的结果
3. 仍相同则按业务需求选择

def BM(dict, sentence):
    fmm_res = FMM(dict, sentence)
    rmm_res = RMM(dict, sentence)
    
    if len(fmm_res) != len(rmm_res):
        return fmm_res if len(fmm_res) < len(rmm_res) else rmm_res
    else:
        fmm_single = sum(1 for word in fmm_res if len(word)==1)
        rmm_single = sum(1 for word in rmm_res if len(word)==1)
        return fmm_res if fmm_single < rmm_single else rmm_res

实际项目中，可以进一步优化：

# 性能优化版FMM
def optimized_FMM(dict, sentence):
    max_len = max(len(word) for word in dict)
    word_set = set(dict)  # 使用集合加速查找
    result = []
    start = 0
    
    while start < len(sentence):
        for length in range(min(max_len, len(sentence)-start), 0, -1):
            word = sentence[start:start+length]
            if word in word_set or length == 1:
                result.append(word)
                start += length
                break
    
    return result

5. 工程实践与扩展思考

在实际应用中，还需要考虑以下问题：

词典优化方案 ：

• 动态加载词典
• 热更新机制
• 多级词典结构

性能瓶颈突破 ：

• 使用Trie树加速查找
• 并行化处理长文本
• 内存映射大词典

# 简单的Trie树实现
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class TrieDict:
    def __init__(self):
        self.root = TrieNode()
        self.max_len = 0
    
    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_word = True
        self.max_len = max(self.max_len, len(word))

对于更复杂的场景，可以考虑：

• 结合统计方法处理未登录词
• 引入机器学习模型优化歧义消解
• 设计领域自适应机制