分词技术也算得上半个人工智能,学术界一直以来都在不断进行相关研究。相对而言,英文分词的性能和准确度还是比中文要高得多。一直以来也没真正关心过这个问题,但是昨晚在微信群里有个人问了下关键词屏蔽的问题。于是大家就讨论开来了。

网上关于中文分词的文章很多,但是无外乎分为两类:

  1. 学院派,各种概念,各种文献,一看就知道文章很牛逼,但是读完了,你还是稀里糊涂,什么都没懂。
  2. 意识流。寥寥数语,轻描淡写,一般只给出一个概念,如分词的话,抛出一个trietree,然后让你自己去想。一般这类人,要么是大牛,不屑于细说,要么是菜鸟,自己也说不清楚。

下面本人就以自己的理解,来说说中文分词。

在我的理解里,分词一般分两类。

  1. 基于语义分析的分词方法。这个方法就比较高大上了,需要结合上下文识别生词、自动消除歧义。这个方法一般属于科学范畴,工程实现太过复杂了。所以这里不作分析。
  2. 词典对照的分词方法。这种方法比较常见,世面上的分词方法都是采用这个。下面就说说这个词典对照的分词方法。

对于一段文本,如

 

首先要立足一个字,然后逐渐向后映射,再去字典里对照看有没有这个词,如果有,就把他挑出来,上面这段话,如果扫描到我,则用依次拿“我”,“我是”,“我是中”,“我是中国”,“我是中国人”去字典里对照,如果词典里有这个词,就挑出来。需要说明的是,中文词是没有长度限制的(理论上),所以立足一个字后,要一直往后扫描,一直扫描到句子结束或碰到符号为止。上次跟群里一个朋友争论的焦点也在这,市面上绝大多数的算法,都是限定了扫描范围,一般三四个字,不会无限扫描下去,中文词一般也就两三个字,成语才四字,所以这样其实在大多数情况下也是可行的,只是按道理讲,缺乏了一定的准确性。

 上述所讲,乃是原文扫描,分词还有一个重要的东西,那就是词典。中文跟英语不一样,英语的词是最小单元,根据空格拆分,压根就不需要什么词典。

汉语是以字为基本的书写单位,词语之间并没有明显的区分标记。我们需要把每个词一一拿去词典比照,判断这几个字的组合是不是一个词。一说到字典,很多人就想到了trietree,因为很多数据结构的教材是翻译的英文资料,很多课本的demo也都是构造一篇英文的文章的trietree,原因无他,简单而已。我们知道,英语也就26个字母,构造一个指针数组(注意:是指针数组,不是数组指针),然后每个数组元素是指向下个节点的指针,这样就可以串起来了。这样看起来,似乎解决方案很完美,很多人面试,一提到这类问题,trie tree脱口而出,根本就不思考。那么,trie tree真有那么完美吗?

trie tree是一种树状链表,是hash表的变种,典型应用是用于统计和排序大量字符串。他是一种前缀树,减少了前缀的重复占用空间,故而省空间。以上都是教科书里写的,自然也没有啥问题,但是我在前面就说了,教科书都是讲英文字符串处理的,自然是没错,但是中文也是这样吗?中文常见的字有3000多个,加上繁体字,超5000没问题,如果平均一个词3字,每字3字节,那么一共是5000*5000*5000*3,这是一个很大的数字,很明显,中文的trietree明显不省空间,原因是汉字太多了,基本前缀复用率很低。反倒不如直接hash或多层hash,我们按10W词计算,每个词算3字,大约空间也只有100000*3*3,这远比前面的方案省空间,而且hash的查找效率只跟层级有关,查找效率不比trietree低。当然hash也有弊端,因为hash的每个父节点和字节点是单向联通的,只能点查找,故并不适合统计,如果要统计,二叉树层级太深,查询效率不高,故而用b树或b+树较为合适。