中文分词逆向最大匹配法项目实践
Tag 中文分词, 逆向最大匹配法, on by view 5749

最近在自己的项目中实现了中文分词,项目是pinyin-php,是一个用C语言完成的原生php扩展。 其主要作用是将中文汉字翻译成汉语拼音,其中用到中文分词主要是为了识别多音字,因为多音字一般是在特定词语环境中出现的。 因此系统需要识别汉字词语,也就是说要实现简单的分词,当然分词准确率越高的话多音字识别率也会越高。

pinyin-php中实现中文分词达到识别多音字的目的,这一想法在pinyin-php上一版本开发的时候就已经想到了。只是自己从来都没有实践过,而且据别人说,中文分词用C语言实现起来比较麻烦,反倒是脚本语言实现起来比较方便。我多方查阅资料后知道现有中文分词方法有如下几种

  1. 字符匹配

  2. 理解法

  3. 统计法

其中字符匹配是基于字典的字符串匹配,理解法是在字符串匹配的同时还对句子进行语义分析,统计法是基于大量的语料库来实现的。其中字符匹配法最为简单,后两者首先是算法比较复杂,是我目前尚未接触到的方法,其次他们均要基于大量的语料库进行数据分析,这对于我以及pinyin-php这个项目来说是不现实的。不过对于搜索引擎这种大型的系统来说是可以实现的。因此,我采用字符匹配法。字符匹配又有如下四种方式

  1. 正向最大匹配法(由左到右的方向);

  2. 逆向最大匹配法(由右到左的方向);

  3. 最少切分(使每一句中切出的词数最小);

  4. 双向最大匹配法(进行由左到右、由右到左两次扫描);

上面四种字符匹配方法要算『双向最大匹配法』最为准确,由于汉语的特性,『逆向最大匹配法』比『正向最大匹配法』要更精确。

pinyin-php采用的便是『逆向最大匹配法』。下面看个分词实例

硕士研究生产

正向最大匹配法的结果会是『硕士研究生 / 产』,而逆向最大匹配法利用逆向扫描,可得到正确的分词结果『硕士 / 研究 / 生产』。

项目中有一个字词库,其实是我自己实现的一个hashtable,系统初始化的时候从字词库中读取汉字和词语以及其对应的汉语拼音。

key,value
一,yī
丁,dīng
七,qī
万,wàn
丈,zhàng
三,sān
上,shàng
下,xià
……
阿Q,āQ
阿爸,ābà
阿鼻,ābí
阿呆,ādāi
阿弟,ādì
阿爹,ādiē
阿斗,ādǒu
阿飞,āfēi
阿哥,āgē
……

假设hashtable中的key的最大长度为10个汉字,那么有一段文字,我首先从尾部开始截取10个汉字,放入buffer{10}中然后在hashtable中查buffer[1~10],查到后就截取后续的10个汉字,未查到的话继续查字符串buffer[2~10],未查到继续查buffer[3~10],直到buffer[10],例如若是在buffer[4~10]的时候查到了,则将buffer[1~3]退回段落的原处。匹配到的词直接总hashtable中读取其拼音如此便翻译出来了,若是查找不到则直接保持为原来的字符不变。

分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。

paragraph								buffer					segments
分词就是将连续的字序列按照一定的规范重新		组合成词序列的过程。
分词就是将连续的字序列按照一定的规范重		新组合成词序列的过程		/。
分词就是将连续的字序列按照一定的规			范重新组合成词序列的		/过程。
分词就是将连续的字序列按照一定的				规范重新组合成词序列		/的/过程。
分词就是将连续的字序列按照一				定的规范重新组合成词		/序列/的/过程。
分词就是将连续的字序						列按照一定的规范重新		/组/合成词/序列/的/过程。
分词就是将连续的							字序列按照一定的规范		/重新/组/合成词/序列/的/过程。

如果想了解我是如何编码实现的,欢迎参阅我的项目pinyin-php(https://github.com/duguying/pinyin-php)。


texlive中文书签乱码
Tag texlive, pdf, 中文, 书签, 乱码, on by view 8178

一个纠结了两天的问题,我之前在ctex环境下的latex项目迁移到texlive环境出现的问题。我之前的项目是gbk编码的,用ctex环境编译,因此,也只能够支持windows环境,故而,我将其转移到了texlive环境编写,字符集也由原来的gbk变为了utf8,这时出现问题了,起初解决书签乱码的方法是在编译过程中将生成的bachelor.out文件的编码由原来的gbk转为unicode,使用的是一个命令行工具gbk2uni.exe,可是现在全部变为utf8格式了out文件也不再是gbk,原来的转换方法无效了,后来也试着吧utf8格式的out文件转为unicode格式,可是还是无效,纠结很久,解决方法如下。

原文档头部如下

\documentclass{article}    
\usepackage{amsmath,amssymb}    
\usepackage{latexsym}    
\usepackage{CJK}    
\usepackage{listings,xcolor}    
\usepackage{graphicx}    
\usepackage{titlesec}    
\usepackage[dvipdfm,    
            pdfstartview=FitH,    
            CJKbookmarks=true,    
            bookmarksnumbered=true,    
            bookmarksopen=true,    
            colorlinks=true, %注释掉此项则交叉引用为彩色边框(将colorlinks和pdfborder同时注释掉)    
            %pdfborder=001,   %注释掉此项则交叉引用为彩色边框    
            citecolor=magenta,% magenta , cyan    
            linkcolor=blue,    
            linktocpage=true,    
            ]{hyperref}       % hyperref 宏包通常要求放在导言区的最后!!!    
\usepackage{titletoc}

修改为

\documentclass{ctexartutf8}
\usepackage{amsmath,amssymb}
\usepackage{latexsym}
\usepackage{CJKutf8}
\usepackage{listings,xcolor}
\usepackage{graphicx}
\usepackage{titlesec}

\usepackage[unicode,dvipdfm,
            pdfstartview=FitH,
            colorlinks=true, %注释掉此项则交叉引用为彩色边框(将colorlinks和pdfborder同时注释掉)
            %pdfborder=001,   %注释掉此项则交叉引用为彩色边框
            citecolor=magenta,% magenta , cyan
            linkcolor=blue,
            linktocpage=true,
            ]{hyperref}       % hyperref 宏包通常要求放在导言区的最后!!!
\usepackage{titletoc}

其中主要是将CJK包改为CJKutf8,另外原来需要开启CJKbookmark=true这些都不要了,当然\documentclass需要改为支持CJKutf8的格式,比如ctexartutf8等。

这个问题的的确确困扰了我至少两天的时间,最终还是在google上搜索错误信息! Argument of \HyPsd@GetTwoBytes has an extra }.找到一封邮件(http://lists.ffii.org/pipermail/cjk/2007-February/001832.html),这才恍然大悟。