中文分词算法--最大匹配算法

在 Fri 25 March 2016 发布于 自然语言处理 分类 • 标签为 中文分词, 最大匹配

中文分词算法分两大方向:一是机械分词算法, 一是基于统计的分词算法。本篇文章主要介绍机械分词算法中最基础的算法: 最大匹配算法(Maximum Matching, 一下简称MM算法)。 MM算法有三种: 正向最大匹配算法, 逆向最大匹配算法。双向最大匹配算法是取前面两种分词算法切分出来词, 然后根据一定的策略筛出切分效果最好的最为最终的切分结果。下面一一介绍这三种分词方法。

正向最大匹配算法和逆向最大匹配算法

最大匹配算法以字典为例子, 在目标串中取出长度为最大词长(按需任意配置)的连续词在字典中进行扫描匹配。其流程图如下:

forward_max_match_algorithm

依据此逻辑, 给出简单的python实现。对于逆向最大匹配算法, 其和正向最大匹配算法的原理一样, 只是从后向前切词。 这里的字典使用的是搜狗提供的字典, 点击下载

#!/usr/bin/env python
# encoding: utf-8
# -*- coding: UTF-8 -*-

import os
import sys 

def get_trie(filepath):
    trie = {}
    reader = open(filepath, 'r')
    for line in …

阅读全文