python 中文分词算法之前向最大正向匹配算法

 Pala   2017-10-31 15:31   307 人阅读  0 条评论

最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法,分为正向和逆向,原理都是一样的。

正向最大匹配算法,故名思意,从左向右扫描寻找词的最大匹配。

首先我们可以规定一个词的最大长度,每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配,如果没有找到,就缩短长度继续寻找,直到找到或者成为单字。

实例:

S1="计算语言学课程是三个课时" ,设定最大词长MaxLen = 5 ,S2= " "

字典中含有三个词:[计算语言学]、[课程]、[课时]

(1)S2="";S1不为空,从S1左边取出候选子串W="计算语言学";

(2)查词表,“计算语言学”在词表中,将W加入到S2中,S2=“计算语言学/ ”, 并将W从S1中去掉,此时S1="课程是三个课时";

(3)S1不为空,于是从S1左边取出候选子串W="课程是三个";

(4)查词表,W不在词表中,将W最右边一个字去掉,得到W="课程是三";

(5)查词表,W不在词表中,将W最右边一个字去掉,得到W="课程是";

(6)查词表,W不在词表中,将W最右边一个字去掉,得到W="课程"

(7)查词表,W在词表中,将W加入到S2中,S2=“计算语言学/ 课程/ ”,并 将W从S1中去掉,此时S1="是三个课时";

(8)S1不为空,于是从S1左边取出候选子串W="是三个课时";

(9)查词表,W不在词表中,将W最右边一个字去掉,得到W="是三个课";

(10)查词表,W不在词表中,将W最右边一个字去掉,得到W="是三个";

(11)查词表,W不在词表中,将W最右边一个字去掉,得到W="是三"

(12)查词表,W不在词表中,将W最右边一个字去掉,得到W=“是”,这时 W是单字,将W加入到S2中,S2=“计算语言学/ 课程/ 是/ ”,并将 W从S1中去掉,此时S1="三个课时";

(13)S1不为空,从S1左边取出候选子串W="三个课时";

(14)查词表,W不在词表中,将W最右边一个字去掉,得到W="三个课";

(15)查词表,W不在词表中,将W最右边一个字去掉,得到W="三个";

(16)查词表,W不在词表中,将W最右边一个字去掉,得到W=“三”,这时 W是单字,将W加入到S2中,S2=“计算语言学/ 课程/ 是/ 三/ ”,并 将W从S1中去掉,此时S1="个课时";

(17)S1不为空,从S1左边取出候选子串W="个课时";

(18)查词表,W不在词表中,将W最右边一个字去掉,得到W="个课";

(19)查词表,W不在词表中,将W最右边一个字去掉,得到W=“个”, 这时W是单字,将W加入到S2中,S2=“计算语言学/ 课程/ 是/ 三/ 个/ ",并将W从S1中去掉,此时S1="课时";

(20)S1不为空,从S1左边取出候选子串W="课时";

(21)查词表,W在词表中,将W加入到S2中,S2=“计算语言学/ 课程/ 是/ 三/ 个/ 课时/ ",并将W从S1中去掉,此时S1=""。

(22)S1为空,输出S2作为分词结果,分词过程结束。

中文分词算法的Python实现:

脚本接受两个参数,一个是输入文件的路径,另一个是词典的路径。

它的运行方法如下:

python max-match.py <data> <dict>
#!/usr/bin/env python
import cPickle as pickle
import sys

# 词语最大长度为5
window_size=5

def max_match_segment(line, dic):
    # write your code here
    chars = line.decode("utf8")
    words = []
    idx = 0
    # 判断索引是否超过chars的长度
    while idx < len(chars):
        matched = False
        for i in xrange(window_size, 0, -1):
            cand=chars[idx:idx+i].encode("utf8")
            if cand in dic:
                words.append(cand)
                matched = True
                break
        # 判断for中是否匹配到数据
        if not matched:
            i = 1
            words.append(chars[idx].encode("utf8"))
        idx += i

    return words

if __name__=="__main__":

    try:
        fpi=open(sys.argv[1], "r")
    except:
        print >> sys.stderr, "failed to open file"
        sys.exit(1)

    try:
        dic = pickle.load(open(sys.argv[2], "r"))
    except:
        print >> sys.stderr, "failed to load dict %s" % sys.argv[2]
        sys.exit(1)
    try:
        fpo = open("out.txt","w")
    except:
        print >> sys.stderr, "failed to load out.txt"
        sys.exit(1)
    for line in fpi:
        fpo.write("\t".join( max_match_segment(line.strip(), dic) ))

当然,这只是最基础的,还可以有很多高级的优化,比如说改成Trie树版本的,控制最大词长度的等等。

实例参考自:北大詹卫东老师“中文信息处理基础”的课件 :http://ishare.iask.sina.com.cn/f/22509596.html

Similar Posts:

  • 基于词典的逆向最大匹配中文分词算法,更好实现中英文数字混合分词

    基于词典的逆向最大匹配中文分词算法,能实现中英文数字混合分词.比如能分出这样的词:bb霜.3室.乐phone.touch4.mp3.T恤.实际分词效果比正向分词效果好 publicclass RMM { privatestaticfinal Log log = LogFactory.getLog(RMM.class); privatestatic HashMap<String, Integer> dictionary =null; privatestaticfinalint WORD_MAX_

  • 在路上--原创中文分词算法的网络作者们

    互众信息科技官网 www.huzoom.cn 首发.作者:windfic,转载请保留作者信息. <我自己设计的中文分词算法> http://xiecc.itpub.net/post/1476/52479 由最大匹配法分词的缺陷:1.长度限制:2.效率低:3.掩盖分词歧义.而改进设计自己的中文分词算法:1.高效:2.无长度限制:3.歧义包容. 算法的突破口-词库:词库是树状结构的单字.每一次的匹配变成了树的遍历,而这种遍历的效率都是线性的. <TreeSplitter---树形分词算法&g

  • Matrix67:漫话中文分词算法

    文章转载自: 我爱自然语言处理 记得第一次了解中文分词算法是在 Google 黑板报 上看到的,当初看到那个算法时我彻底被震撼住了,想不到一个看似不可能完成的任务竟然有如此神奇巧妙的算法.最近在詹卫东老师的<中文信息处理导论>课上 再次学到中文分词算法,才知道这并不是中文分词算法研究的全部,前前后后还有很多故事可讲.在没有建立统计语言模型时,人们还在语言学的角度对自动分词进 行研究,期间诞生了很多有意思的理论. 中文分词的主要困难在于分词歧义."结婚的和尚未结婚的",应该分

  • 三种中文分词算法优劣比较(转载)

    作者:刀剑笑(Blog:http://blog.csdn.net/jyz3051) Email:jyz3051 at yahoo dot com dot cn('at'请替换成'@','dot'请替换成'.' ) 关键词:中文分词,中文分词算法,基于字符串匹配的分词,基于理解的分词,基于统计的分词 到目前为止,中文分词包括三种方法:1)基于字符串匹配的分词:2)基于理解的分词:3)基于统计的分词.到目前为止 ,还无法证明哪一种方法更准确,每种方法都有自己的利弊,有强项也有致命弱点,简单的对比见下

  • 中文分词算法的初步研究

    public String Fmm(String source) { String[] targets = new String[source.length()]; String target = ""; int MaxLen = source.length(); int temLen = MaxLen; int primarylen = 0; while (true) { if (len.containsKey(temLen)) { tem = source.substring(pr

  • 中文分词算法笔记(转载)

    转载:http://www.cnblogs.com/lvpei/archive/2010/08/04/1792409.html 中文分词基本算法主要分类 基于词典的方法.基于统计的方法.基于规则的方法.(传说中还有基于理解的-神经网络-专家系统,按下不表) 1.基于词典的方法(字符串匹配,机械分词方法) 定义:按照一定策略将待分析的汉字串与一个"大机器词典"中的词条进行匹配,若在词典中找到某个字符串,则匹配成功. 按照扫描方向的不同:正向匹配和逆向匹配 按照长度的不同:最大匹配和最小匹

  • 中文分词算法大全

    做中文搜索,关键词提取,文档分类都离不开中文分词,能用的代码包有如下 单字切分 sphinx只要把min_word_len设置为1,并配置charset_table,默认就是单字切分,lucene用StandardAnalyzer CJKAnalyzer lucene自带,两两分词,就是把 ABCD 分成 AB,BC,CD 3段 PaodingAnalyzer 开源,可以用于lucene http://code.google.com/p/paoding/ sphinx-for-chinese 基

  • 中文分词算法—— 基于词典的方法

    1.基于词典的方法(字符串匹配,机械分词方法) 定义:按照一定策略将待分析的汉字串与一个"大机器词典"中的词条进行匹配,若在词典中找到某个字符串,则匹配成功. 按照扫描方向的不同:正向匹配和逆向匹配 按照长度的不同:最大匹配和最小匹配 1.1正向最大匹配思想MM 1>从左向右取待切分汉语句的m个字符作为匹配字段,m为大机器词典中最长词条个数. 2>查找大机器词典并进行匹配.若匹配成功,则将这个匹配字段作为一个词切分出来. 若匹配不成功,则将这个匹配字段的最后一个字去掉,剩下

  • ZZ MMSEG 中文分词算法

    译者原文地址: http://leeing.org/2009/11/01/mmseg-chinese-segmentation-algorithm/ 论文原文地址: http://technology.chtsai.org/mmseg/ MMSEG :一个基于最大匹配算法的两种变体的中文单词识别系统 发表日期: 1996-04-29 更新日期: 1998-03-06 文档更新: 2000-03-12 许可: 非商业使用情况下免费 Copyright 1996-2006 Chih-Hao Tsai

  • C# 中文分词算法(实现从文章中提取关键字算法)

    using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.IO; using System.Text.RegularExpressions; namespace TKS.Framework.Common { /// <summary> /// 分词类 /// </summary> public

实例参考自:北大詹卫东老师“中文信息处理基础”的课件 :http://ishare.iask.sina.com.cn/f/22509596.html

本文地址:http://chenxm.cc/post/450.html
版权声明:本文为原创文章,版权归 Pala 所有,欢迎分享本文,转载请保留出处!

发表评论


表情

还没有留言,还不快点抢沙发?