4
汉字编码格式：UTF-8
中文处理和英文处理的一个很大不同就在于编码格式的复杂性。常见的中文编码 格式有 GB2312，GB18030，GBK，Unicode 等等。同样的中文字符，在不同的汉字 编码格式中，可能有不同的二进制表示。因此编程做字符串匹配时，通常要求统一的 编码格式。 在 linux 下可以用 file 命令查看文本文件的编码格式。经过检查，发现老师提供的 词典和语料属于不同的编码格式，直接做字符串匹配可能会有问题。 考虑到 UBUNTU 以 UTF-8 作为默认编码格式，我索性使用 enconv 命令将词典和语料都转换成 UTF-8 格式。 下面简要介绍一下 UTF-8 格式。 前 面 提 到 的 Unicode 的 学 名 是 "Universal Multiple-Octet Coded Character Set"，简称为 UCS。UCS 可以看作是"Unicode Character Set"的缩写。 UCS 只是规定如何编码，并没有规定如何传输、保存这个编码。UTF-8 是被广泛 接受的方案。UTF-8 的一个特别的好处是它与 ISO-8859-1 完全兼容。UTF 是“UCS Transformation Format”的缩写。 UTF-8 就是以 8 位为单元对 UCS 进行编码。 从 UCS-2 到 UTF-8 的编码方式如下： UCS-2 编码(16 进制) 0000 – 007F 0080 – 07FF 0800 – FFFF UTF-8 字节流(二进制) 0xxxxxxx 110xxxxx 10xxxxxx 1110xxxx 10xxxxxx 10xxxxxx
5
程序流程图
6
7
程序源代码
/* * segment.cpp ---- 中文分词程序 * * 功能：１）中文词典分词（逆向最大匹配） * ２）数字分词 * ３）西文分词 * ４）时间分词 * 用法： * ./segment ARTICAL * 范例： * ./segment 1998-01-qiefen-file.txt.utf8 * 屏幕输出： * 词典读入完毕，耗时 0.000776 s * 分词完毕，耗时 3.18 s * * 分词结果保存在 result.txt.utf8 中。 * * 注意：１）本程序只能处理 utf-8 文本，其他格式的文本请用 iconv 或 enconv 转换成 utf-8 格式。 * ２ ） 程 序 运 行 需 要 dict/CoreDict.txt.utf8，dict/number.txt.utf8，dict/unit.txt.utf8 三个文件。 * * 参考了以下文章，特此感谢！ * /maximum-matching-method-of-chinese-wordsegmentation/ * * Created on: 2010-11-30 * Author: xuweilin <usa911 at > */
北京邮电大学计算机学院 《自然语言处理导论》 中文分词实验报告
姓 名： 许伟林 学 号： 08211306 指导教师： 郑岩 日 期： 2010/12/22
1
内容目录
一、实验目的...............................................................3 二、实验环境...............................................................3 三、实验材料...............................................................3 四、实验设计...............................................................3 一、分词策略.............................................................3 词典逆向最大匹配法...................................................4 基于确定文法的分词法.................................................4 二、程序设计.............................................................4 查找算法：哈希表查找.................................................4 汉字编码格式：UTF-8...................................................5 程序流程图............................................................6 程序源代码............................................................8 五、结果和性能分析........................................................16 分词结果示例............................................................16 性能分析................................................................17 六、有待解决的问题........................................................18 七、实验总结..............................................................19
基于确定文法的分词法
基于确定文法的分词法可以进行数字、西文、时间的分词，设计思路是这样的： 1、 增加一个词典，存储中文编码（全角）的大小写拉丁字母、 中文小写数字、 阿 拉伯数字、 数字单位（百、 千、 万、 亿、 兆）、 小数点、 百分号、 除号；词类型记为[D1]； 2、 增加一个词典，存储中文编码的时间单位，包括年、 月、 日、 时、 分、 秒、 点;词 类型记为[D2]； 3、 文法的正则表达式为[D1]*[D2]？。
3
由于时间仓促，且水平有限，本程序只实现了第 2 种和第 3 种分词法，即词典逆 向最大匹配法和基于确定文法的分词法。
词典逆向最大匹配法
词典逆向最大匹配法完成分词的大部分工作，设计思路是这样的： 1、 将词典的每个词条读入内存，最长是 4 字词，最短是 1 字词； 2、 从语料中读入一段（一行）文字，保存为字符串； 3、 如果字符串长度大于 4 个中文字符，则取字符串最右边的 4 个中文字符，作 为候选词；否则取出整个字符串作为候选词； 4、 在词典中查找这个候选词，如果查找失败，则去掉这个候选词的最左字，重 复这步进行查找，直到候选词为 1 个中文字符； 5、 将候选词从字符串中取出、删除，回到第 3 步直到字符串为空； 6、 回到第 2 步直到语料已读完。
二、程序设计 查找算法：哈希表查找
除了分词结果的准确性，程序的性能也是至关重要的。由于本程序采用了词典法 来分词，执行过程需要检索大量数据，因此查找效率成为程序性能的决定性因素。 据我的了解，目前比较成熟的查找算法主要有顺序查找、 二分查找、 哈希表查找等。 顺序查找的算法复杂度为 O(n)； 二分查找的算法复杂度为 O(logn)，但需要事先排序； 哈希表查找的复杂度为 O(1)。 本程序采用效率最高的哈希表查找算法。
#include #include #include #include #include #include #include #include <iostream> <string> <fstream> <sstream> <ext/hash_map> <iomanip> <stdio.h> <time.h> // 最en("dict/number.txt.utf8"); if (!infile.is_open()) { cerr << "Unable to open input file: " << "wordlexicon" << " -- bailing out!" << endl; exit(-1); } while (getline(infile, strtmp)) // 读入词典的每一行并将其添加入哈希中 { istringstream istr(strtmp); istr >> word; //读入每行第一个词 numberhash.insert(sipair(word, 1)); //插入到哈希中 } infile.close(); infile.open("dict/unit.txt.utf8"); if (!infile.is_open()) { cerr << "Unable to open input file: " << "wordlexicon" << " -- bailing out!" << endl; exit(-1); } while (getline(infile, strtmp)) // 读入词典的每一行并将其添加入哈希中 { istringstream istr(strtmp); istr >> word; //读入每行第一个词 unithash.insert(sipair(word, 1)); //插入到哈希中 } infile.close(); } //删除语料库中已有的分词空格，由本程序重新分词 string eat_space(string s1) { int p1=0,p2=0; int count; string s2; while(p2 < s1.length()){ //删除全角空格 // if((s1[p2]-0xffffffe3)==0 && // s1[p2+1]-0xffffff80==0 && // s1[p2+2]-0xffffff80==0){//空格