赵走x博客
网站访问量:151506
首页
书籍
软件
工具
古诗词
搜索
登录
16、算法部分源码解析
15、系统总体流程与词典结构
14、中文分词
13、词汇与分词技术
12、三个平面中的语义研究
11、汉语的发展
10、字形的流变
9、六书及其他
8、文字符号的起源
7、整合语义角色标注模块
6、整合句法解析模块
5、整合命名实体识别模块
4、整合词性标注模块
3、整合中文分词模块
2、现代自然语言系统简介
1、中文语言的机器处理:历史回顾
15、系统总体流程与词典结构
资源编号:76151
NLP汉语自然语言处理原理与实践
自然语言处理
热度:92
ICTCLAS汉语分词系统是由张华平博士于2002年设计开发的一套中文分词系统。迄今为止,ICTCLAS都是自然语言处理领域国人设计的人工智能类算法中最成功、应用最广泛的成果。该算法具有原理简单,易于实现,便于使用,以及对于大规模分词,效率高、精度准等优势。除此之外,该算法使用的模型具有资源占用低、便于增量扩展等特点。
# 1、 概述 ICTCLAS汉语分词系统是由张华平博士于2002年设计开发的一套中文分词系统。迄今为止,ICTCLAS都是自然语言处理领域国人设计的人工智能类算法中最成功、应用最广泛的成果。该算法具有原理简单,易于实现,便于使用,以及对于大规模分词,效率高、精度准等优势。除此之外,该算法使用的模型具有资源占用低、便于增量扩展等特点。 在自然语言处理领域,一个成功的算法就意味着一个新时代的到来。首先,该算法一经问世就取得了业界的广泛关注,并斩获诸多奖项,获2002年国内973评测综合第一名;在2003年国际SIGHAN分词大赛中获得综合评比第一名;2010年获得了钱伟长中文信息处理科学技术奖一等奖。目前,据笔者所知,各大知名的网络公司都以该算法作为分词系统的核心算法。该算法使中文自然语言处理终于从词法分析时代跨入了句法分析时代。 ICTCLAS的商业版经过张博士倾力十余年的精心打造,内核升级10余次,已经成为精度最高、速度最快的中文分词系统。该系统还提供一个基于30万个常用词的免费版,可从http://ictclas.nlpir.org/ 下载。该网站也称为自然语言处理与信息检索共享平台,分词器名称调整为NLPIR汉语分词系统,并逐年升级。现在的NLPIR汉语分词系统(又称为ICTCLAS 2013),主要功能包括中文分词、词性标注、命名实体识别、用户词典功能,以及支持GBK编码、UTF8编码、BIG5编码,还新增微博分词、新词发现与关键词提取等功能,是国内最著名的分词系统之一。 为了促进大家的研究学习,ICTCLAS发布一个免费开源版称为FreeICTCLAS,均使用C++开发语言。目前,能够找到的FreeICTCLAS原始版本应该有两套:一套是基于Windows操作系统的;另一套是移植到Linux操作系统下的版本。读者可以从http://www.threedweb.cn/thread-162-1-1.html 下载Linux版本的;也可以从CSDN上找到基于Windows版本的。张华平博士在设计这个分词系统时还是研究生,因此代码具有很强的实验性,两套版本的核心源码都完全相同,仅支持GBK编码,不支持UTF-8或其他编码。目前两个版本都免费提供,以供大家学习。 笔者本来计划以此版本作为算法讲解的源码,但综合考虑到代码的易读性、实现的成熟度、编码支持及跨平台等诸多因素,决定选取较为清晰的ICTCLAS的重写版本来讲解。目的是有助于读者能够更清晰、深刻地了解算法的本质。目前,很多朋友用其他语言重写了ICTCLAS,包括使用Java语言的ICTCLAS4J,孙健的Ansj(新版本算法为CRF)及C#的SharpIctclas等。其中,比较全面的是HanLP,网址:http://hanlp.linrunsoft.com/ 。选取这个Java框架的原因不仅是其对ICTCLAS的算法还原得比较好,另外,它还是一个非常丰富的NLP算法库,除N-最短路径算法之外,还实现了HMM的Viterbi算法、最大熵算法直至CRF算法等。同时,该算法库还提供了丰富的语料资源,供用户使用。有关更多细节读者可以下载源码学习。 # 2、 中文分词流程 从本节开始,将详细介绍ICTCLAS分词算法原理,以及简单介绍系统的基本构成。这里使用的是HanLP分词模块,操作系统是Linux/Windows,开发工具是Ecplise mar 64位IDE。源代码可以从http://hanlp.linrunsoft.com/release/hanlp-1.2.8-sources.jar 下载,词典文件的下载地址:http://pan.baidu.com/s/1ntRkylN 。 ICTCLAS的算法思想来源于HMM。Java版本的重构在功能和逻辑上与C++版本基本相同。HanLP的实现做了如下修改。 ❑ 使用双数组Tire树读取和检索词典,提高性能。 ❑ 使用提供了更丰富的命名实体识别库:人名、译名、日本人名、地名、组织机构名等。 ❑ 搜索引擎系统的支持等——超出本节内容,讲解中未涉及。 ❑ 细分阶段使用了最短路径法。 当然,系统也加入了词性标注的功能。词性标注不是本章的重点,我们留到以后讲解。为了完整地了解分词的过程我们将其分为如下两部分。第一部分是整体流程及一些重要的数据结构的讲解;第二部分是关于流程每个节点的具体实现和代码注释,以及各阶段的执行结果。 图3.1所示为HanLP整体的运行流程,也是全套文档的线索结构。在逐步了解文档内容之前,先对此流程图进行简要的介绍。  图3.1 HanLP整体的运行流程 * (1)在第一个环节,系统读取待分词的字符串。输入的可以是一个句子也可以是一个篇章,如果是篇章则系统会首先进行句子切分,然后调用多线程,对每个切分的子句进行分词。 * (2)根据输入的配置信息,导入相应的词典。 常用的词典可到专门的网址下载。下载地址:http://pan.baidu.com/s/1ntRkylN 。词典一共624.5MB,全部词典种类比较多,还包括若干语言模型。本算法所需的词典位于“data/dictionary/”目录下。 包括CoreNatureDictionary(一元语言模型词典)、CoreNatureDictionary.ngram(二元语言模型词典)、person/nr.tr, nrf, nrj(人名识别词典—中国人名、译名、日本人名)、place/ns. tr(地名识别词典)、organization/nt.tr(组织机构名词典),它们的文件都有文本格式的版本,具体结构在3.2.3节中进行分析。 * (3)进入粗分阶段。 ❑ 首先对句子进行字符级切分,即将输入的句子切分为单个UTF-8编码的字符数组(函数toCharArray()),包括单个中文字符、单个英文字符、其他单个字符等。 ❑ 一元切分。查询核心词典,将字符切分的结果与词典词最大匹配,匹配的结果,包括词形、词性、词频等信息形成一元词网,之后对一元词网进行原子切分,即按模式合并英文和数字的字符构成原子词。 ❑ 二元切分。用一元分词的结果(二维数组)查询二元词典,与二元词典进行最大匹配,匹配的结果为一个Graph,形成一个词图。 ❑ NShort算法计算。将查出的每个结果按平滑算法计算二元分词的词频数得到词图中每个节点的权值(概率的倒数),应用NShort算法累加词图中每个节点构成的所有路径,权值最小(概率最大)的那条路径对应的词图节点就是初分的结果。 ❑ 对粗分结果执行后处理应用规则,识别时间类专有名词。 * (4)进入未登录词识别阶段,使用隐马尔科夫链语言模型。 * (5)将命名实体识别后的分词结果加入词图中,对词图再次进行分词(Dijkstra最短路径法)。该阶段为细分阶段。 ❑ 根据人名识别词典,将粗分的结果与之匹配,Viterbi算法识别外国的人名。 ❑ 根据地名识别词典,将粗分的结果与之匹配,Viterbi算法识别地名。 ❑ 根据组织机构名词典,将粗分的结果与之匹配,Dijkstra算法识别组织机构名。 * (6)使用词性标注模型,Viterbi算法,对分词结果进行词性标注;该部分将在第4章介绍。 * (7)转换路径为分词结果,并输出分词的结果。 如图3.1所示,整个流程的主程序位于NShortSegment类的segSentence方法内。它处于句子切分阶段之后。此函数给出了整个分词流程的总过程,其代码如下。 ``` @Override public List
segSentence(char[] sentence) { WordNet wordNetOptimum = new WordNet(sentence); // 最优词网 WordNet wordNetAll = new WordNet(sentence); // 1. 粗分阶段 List
> coarseResult = BiSegment(sentence, 2, wordNetOptimum, wordNetAll); boolean NERexists = false; for (List
vertexList : coarseResult) { if (HanLP.Config.DEBUG) { System.out.println("粗分结果" + convert(vertexList, false)); } // 2. 实体命名识别阶段 if (config.ner) { wordNetOptimum.addAll(vertexList); int preSize = wordNetOptimum.size(); if (config.nameRecognize) { PersonRecognition.Recognition(vertexList, wordNetOptimum, wordNetAll); } if (config.translatedNameRecognize) { TranslatedPersonRecognition.Recognition(vertexList, wordNetOptimum, wordNetAll); } if (config.japaneseNameRecognize) { JapanesePersonRecognition.Recognition(vertexList, wordNetOptimum, wordNetAll); } if (config.placeRecognize) { PlaceRecognition.Recognition(vertexList, wordNetOptimum, wordNetAll); } if (config.organizationRecognize) { // 层叠隐马模型——生成输出作为下一级隐马输入 vertexList = Dijkstra.compute(GenerateBiGraph(wordNetOptimum)); wordNetOptimum.addAll(vertexList); OrganizationRecognition.Recognition(vertexList, wordNetOptimum, wordNetAll); } if (! NERexists && preSize ! = wordNetOptimum.size()) { NERexists = true; } } } // 3. 细分阶段 List
vertexList = coarseResult.get(0); if (NERexists) { Graph graph = GenerateBiGraph(wordNetOptimum); vertexList = Dijkstra.compute(graph); if (HanLP.Config.DEBUG) { System.out.printf("细分词网:\n%s\n", wordNetOptimum); System.out.printf("细分词图:%s\n", graph.printByTo()); } } // 数字识别 if (config.numberQuantifierRecognize) { mergeNumberQuantifier(vertexList, wordNetAll, config); } // 如果是索引模式则全切分 if (config.indexMode) { return decorateResultForIndexMode(vertexList, wordNetAll); } // 4. 词性标准阶段 if (config.speechTagging) { speechTagging(vertexList); } return convert(vertexList, config.offset); } ``` 上述代码为整个中文分词、命名实体识别、词性标注的全过程。 # 3、 分词词典结构 在进入源码分析之前,首先应该了解一下整个项目所用的词典。词典是中文分词重要的外部资源。无论是标准的中文分词还是命名实体识别都离不开词典提供的词汇和语言模型资源。 系统共有7个不同的词典(包括语言模型)放置于Data目录下。HanLP词典结构如表3.2所示。 表3.2 HanLP词典结构 | 词典文件 | 说明 | | ------------ | ------------ | | CoreNatureDictionary | 一元语言模型词典 | | CoreNatureDictionary.ngram | 二元语言模型词典 | | person/nr. txt.trie.dat person/nr. txt.value.dat | 人名识别词典—中国人名 | | person/nrf. txt.trie.dat person/nrf. txt.value.dat | 人名识别词典—译名 | | person/nrj. txt.trie.dat person/nrj. txt.value.dat | 人名识别词典—日本人名 | | place/ns. txt.trie.dat place/ns. txt.value.dat | 地名识别词典 | | organization /nt. txt.trie.dat organization /nt. txt.value.dat | 组织机构名词典 | * (1)一元语言模型词典也被称为核心词典,文件名为CoreNatureDictionary,系统提供了一个文本版本和一个二进制版本的文件。打开文本版本的文件,截取词典的片段内容如下。 ``` 跳梁小丑 nz 16 跳棋 n 1 跳楼 v 136 跳楼价 nz 6 跳楼秀 nz 1 跳槽 vi 71 vn 55 跳水 vn 137 跳水教练 nnd 1 ``` 一元语言模型词典的第一列是词,第二列是该词的第一词性,第三列是对应该词性的词频;如果存在第四列,则是对应该词的第二词性,第五列是对应第二词性的词频;之后以此类推。 CoreNatureDictionary是算法的核心词典,其他各个词典都从此词典衍生而来。而且,一元语言模型词典的大小代表了系统的规模,即这个词典越大,所包含的词汇就越多,能够正确分词的语料范围就越大。一般可用的、最小规模的中文分词器,其核心词典的规模不能少于30万词。 * (2)二元语言模型词典的文件名为CoreNatureDictionary.ngram,系统提供了一个文本版本和一个二进制版本的文件。打开文本版本的文件,截取词典的片段内容如下。 ``` 像@跳梁小丑 24 像@跳舞 4 像@踢 18 像@踢皮球 2 像@踩着 2 像@身上 2 像@身份证 6 像@身边 2 像@身高 2 像@躺在 10 ``` 二元语言模型词典的结构与一元语言模型词典的结构不同,第一列表示两个相邻词,用@进行分隔。例如,“像@跳梁小丑”表示前一个词是“像”,后一个词是“跳梁小丑”,它们用“@”连接起来。第二列是该相邻词(共现词)在语料库中出现的概率,如上例为24次。二元语言模型词典本质上构建出一个二维的矩阵,而且是一个方阵。矩阵的行和列就是一元词表的长度。第一列的前一个词相当于矩阵的行索引,后一个词相当于矩阵的列索引,取值为矩阵词频(“Frequency”)。因此,这个矩阵非零元素的数量充分展示了词汇的搭配信息。因为这个矩阵比较大,所以以一维列表的方式显示出来。 如果把一元语言模型词典和二元语言模型词典合在一起看,它们也可看作一个图(Graph)。其中,图的顶点为一元语言模型词典中的词;二元语言模型词典的每个相邻词为连接两个顶点的一条边,词频为边的权值。它们共同构成了Graph这个完整的数据结构(参见类com.hankcs.hanlp.seg. common.Graph)。整个NShort算法就是对这个图计算最大概率的过程。 # 4、 命名实体的词典结构 人名、译名、地名、组织机构名的识别词典均由两个文件构成,后缀名分别为trie.dat和value.dat。下面仅以人名识别词典为例,简单讲解命名实体识别一元词典和二元词典的数据结构。后缀名为trie.dat的词典是一元词典,人名词典的截图如下。 ``` 郎 B 228 D 22 E 12 K 4 C 1 L 1 郏 B 4 郑 B 3505 C 21 E 20 D 5 郑国 X 84 Z 4 郑大 X 20 郑州 L 2 K 1 X 1 郑州市 K 1 郑重 L 6 ``` 此词典的数据结构与CoreNatureDictionary词典相同,第一列为词汇,第二列为第一个元模式标签,第三列为第一个元模式标签的词频;第四列为第二个元模式标签,第五列为第二个元模式标签的词频;之后依此类推。元模式位于package com.hankcs.hanlp. corpus.tag包的枚举列表NR中。表3.3给出了人名识别模式的元模式标签的含义。 表3.3 元模式标签 | 元模式 | 含义 | 示例 | | ------------ | ------------ | ------------ | | B | 姓氏 | 【张】华平先生 | | C | 名1 | 张【华】平先生 | | D | 名2 | 张华【平】先生 | | E | 单名 | 张【浩】 | | F | 人名前缀 | 【老】刘,【小】李 | | G | 人名后缀 | 王【总】,吴【妈】 | | K | 人名的上文 | 又【来到】于洪洋的家 | | L | 人名的下文 | 新华社记者黄文【摄】 | | M | 两个中国人名之间的成分 | 编剧邵钧林【和】稽道青说 | | U | 人名的上文和姓成词 | 这里【有关】天培的壮烈 | | V | 三字人名的末字和下文成词 | 龚学平等领导,邓颖【超生】前 | | X | 姓与双名的首字成词 | 【王国】维 | | Y | 姓与单名成词 | 【高峰】、【汪洋】 | | Z | 双名本身成词 | 张【朝阳】 | | A | 以下之外其他的角色 | — | | S | 句子的开头 | — | 表3.3列出了构成人名词性匹配的元模式,所有的人名模式都是由这些元模式经过排列组合而构成的。 当使用原子字符串查询trie.dat时,就返回了相应的元模式及对应此元模式的概率信息,如“王”、“菲”这两个连续的原子词,查询trie.dat词典,可以得到相应的一个元模式:“B”、“E”。这样就构成了隐马尔科夫链的转移概率矩阵。后缀名为value.dat的词典是二元词典。表3.4所示为人名识别词典的二元词典截图,该词典在目录下有txt格式的文本文件。 表3.4 人名识别词典的二元词典截图   表3.4中,第一行和第一列就是标签的序号。具体内容对照表3.3。它们构成一个15×15的方阵。方阵的每个元素表示以第一个原子词的标签为序号和以第二个原子词的标签为序号组合构成中国人名的词频(概率)。对于各类人名,系统还提供了各类组合模式串。组织机构的模式串共有36种。这些元模式构成的人名模式保存在com.hankcs.hanlp. dictionary.nr的枚举NRPattern中。由元模式构成的人名模式如表3.5所示。 表3.5 由元模式构成的人名模式 | 名字模式编码 | 含义 | | ------------ | ------------ | | BBCD | 姓+姓+名1+名2 | | BBE | 姓+姓+单名 | |BBZ | 姓+姓+双名成词 | | BCD | 姓+名1+名2 | | BEE | 姓+单名+单名 | | BE | 姓+单名 | | BC | 姓+名1 | | BEC | 姓+单名+名1 | | BG | 姓+后缀 | | DG | 名2+后缀 | | EG | 单名+后缀 | | BXD | 姓+姓双名首字成词+双名末字 | | BZ | 姓+双名本身成词 | | EE | 单名+单名 | | FE | 前缀+单名 | | FC | 前缀+名1 | | FB | 前缀+姓氏 | | FG | 前缀+后缀 | | Y | 姓与单名成词 | | XD | 姓与双名的首字成词+名2 | 表3.5中,第一列是由模式元构成的模式规则;第二列是模式规则的含义。从元模式到人名模式需要使用一个parsePattern函数进行解析,该函数位于com.hankcs.hanlp. dictionary.nr. PersonDictionary类中。有兴趣的读者可以做进一步的研究。 其他列表命名实体标签同样位于package com.hankcs.hanlp.corpus.tag包的枚举列表NT、NS、Nature中。有关翻译人名识别词典和地名识别词典等数据结构基本与人名识别词典都有类似的模式标签,感兴趣的读者可以自己打开相应的文件进行研究,自行解析一下相关文件,受篇幅所限这里不再赘述。 # 5、 词典的存储结构 HanLP在分词过程中使用了多本词典,这些词典均在调用时才加载到内存中,其都属于即插即用型。这样做的好处在于,对于那些在算法中可选的功能和词典,没有必要都导入内存、占用空间。根据配置的不同可以选择导入不同的词典。 本节以核心词典为例,简要讲解核心词典的加载过程及存储结构。核心词典的加载是在构造CoreDictionary对象时完成的。但是,加载过程有点特殊,是通过静态代码段自动完成的。静态代码段调用了load方法负责加载词典文件到内存。代码片段如下。 ``` private static boolean load(String path) { logger.info("核心词典开始加载:" + path); if (loadDat(path)) return true; // 加载二进制缓存词典 TreeMap
map = new TreeMap
(); //红黑树 BufferedReader br = null; try { br = new BufferedReader(new InputStreamReader(new FileInputStream (path), "UTF-8")); String line; int MAX_FREQUENCY = 0; long start = System.currentTimeMillis(); while ((line = br.readLine()) ! = null) { String param[] = line.split("\\s"); int natureCount = (param.length - 1) / 2; CoreDictionary.Attribute attribute = new CoreDictionary.Attribute (natureCount); for (int i = 0; i < natureCount; ++i) { attribute.nature[i] = Enum.valueOf(Nature.class, param[1 + 2 * i]); // 词性 attribute.frequency[i] = Integer.parseInt(param[2 + 2 * i]); // 词频 attribute.totalFrequency += attribute.frequency[i]; // 总词频 } map.put(param[0], attribute); MAX_FREQUENCY += attribute.totalFrequency; } br.close(); trie.build(map); …… ``` 加载过程一共经历了如下三步。 (1)查找是否存在缓存词典(二进制形式),如果存在就从缓存直接加载。 (2)如果不存在,就加载词典的文本形式。 (3)最后将文本形式的词典生成新的二进制(缓存)形式。 考察一下文本形式词典的加载过程,即可了解HanLP的词典存储结构。首先将其保存在TreeMap
容器中,它的底层数据结构是一棵红黑树。因为在构造时,红黑树总是处于平衡状态,所以构建之后不需要调优。关于红黑树的细节,将在数据结构中讲解。TreeMap
加载的内容包括4部分:String在这里是指词的字符串形式,attribute.nature是词性信息(可以是多个), attribute.frequency是不同词性下的词频信息,attribute.totalFrequency是总词频。 trie.build(map)一句调用了DoubleArrayTrie类的build方法,构建出一棵双数组trie树,代码如下。 ``` /** * 方便地构造一棵双数组trie树 * @param keyValueMap 升序键值对map * @return 构造结果 */ public int build(TreeMap
keyValueMap) { assert keyValueMap ! = null; Set
> entrySet = keyValueMap.entrySet(); //去重 return build(entrySet); // 这里调用了真正的构建方法 } ``` 中等规模数据的存储和查询常用的数据结构是HashTable,也称作散列表。Java中的HashMap就是一种格式的散列表。散列表的基本原理是在表项的存储位置与其索引键(查询索引)之间建立一个对应函数关系,这个函数称为哈希函数,通过哈希函数计算得到每个索引键与表项的存储位置相对应的关系。这样,当输入查询键时,哈希表可以近似地得到随机访问的查询效率。这种数据结构因为对键的约束不高(不要求一定是整型数值),一直以来都是中等规模存储和查询的重要数据结构。 随着数据量的增大,对于大规模的数据存储(百万单位以上),哈希表的不足逐渐暴露出来。大规模数据对内存空间占用高,Hash表因为需要哈希函数来计算地址映射,这必然会导致一些数据空间的损失(空桶),中小规模数据的情况下不明显,可以忽略不计。随着数据规模的增加,这种空间浪费会成倍地增加,导致有效存储空间的比例显著下降。 为此引入了一种新的词典结构Trie树,它也是搜索树的一种,其本质是一个确定有限状态自动机(DFA),每个节点代表自动机的一个状态,根据变量不同,进行状态转移,当到达结束状态或无法转移时,完成一次查询操作。考虑构造如下词表。 ``` 一举 一举一动 一举成名 一举成名天下知 万能 万能胶 ``` 这里提供一个节点的数据类型,然后通过这个节点来构造上述例子中的一棵Tire树:Node{code=0, depth=0, left=0, right=6}, code是字母的码表值,depth是树深度,left和right表示这个节点在词典中的索引范围。 如图3.2所示,黄色节点为空字符,代表从根节点到此节点的路径上的所有节点构成一个词。用Trie树搜索一个检索键的时间与键自身长度有关,最快的是O(1),即在第一层即可判断是否搜索到,最坏的情况是O(n), n为Trie树的层数。  图3.2 Tri树结构 而双数组Trie(Double-Array Trie)结构就是将Tire树用两个整型数组来表示,目的是为了设计一种Trie结构的压缩形式,这个思想最初是由日本人Jun-Ichi Aoe于1989年提出的。仅用两个线性数组来表示Trie树,该结构有效结合了数字搜索树(Digital Search Tree)检索时间高效的特点和链式表示的Trie空间结构紧凑的特点。其本质是一个确定有限状态自动机(DFA)。DFA的每个节点代表自动机的一个状态,根据变量的不同,进行状态转移,当到达结束状态或无法转移时,完成一次查询操作。在双数组所有键中包含的字符之间的联系都是通过简单的数学加法运算表示,不仅提高了检索速度,而且省去了链式结构中使用的大量指针,节省了存储空间。 本文限于篇幅不做具体讲解,有关双数组Trie树的更多细节内容,读者可以参照源码了解。