中文分词算法之最大正向匹配算法（Python版）
最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法，分为正向和逆向，原理都是一样的。
正向最大匹配算法，故名思意，从左向右扫描寻找词的最大匹配。
首先我们可以规定一个词的最大长度，每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配，如果没有找到，就缩短长度继续寻找，直到找到或者成为单字。
实例：
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实现：
脚本接受两个参数，一个是输入文件的路径，另一个是词典的路径。
它的运行方法如下：
#!/usr/bin/env pythonimport cPickle as pickleimport syswindow_size=5def max_match_segment(line, dic): # write your code here chars = line.decode("utf8") words = [] idx = 0 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 if not matched: i = 1 words.append(chars[idx].encode("utf8")) idx += i return wordsif __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) ))实例参考自：北大詹卫东老师“中文信息处理基础”的课件 ：http://ishare.iask.sina.com.cn/f/22509596.html