简与美（1）

简与美（1）

最近在做项目的时候经常使用数学，把很多复杂的问题化简成很简单的模型，而这使得实现相当美观，为了激励自己继续钻研下去，也希望总结一些得失，我打算从今天开始陆续写一个《简与美》系列。 脑中的数学是抽象的，手中的数学是简单的。 上周做一个分词器。一个普通的分词器，对中文和英文进行自动切分，并标注词性。主要的技术就两点，词典的构造和切词模型的训练。 词典的构造要基于分词器对词典的要求。一般分词器对词典主要是查询操作，有三种查询操作，第一种是给定一个词语w，查询w是否是词；第二种是给定一个位置，查询从该位置起始的最长词；第三种是给定一个位置，查询从该位置起始的所有词语。 如果是依赖于字符串比较的词典查询算法，对于第二、三种查询，需要多次进行字符串比较，这是很耗费时间的，但是这种词典的结构一般是比较简单的。为了避免字符串比较操作，出现了逐字比较的查询算法，这种算法只需要遍历输入的句子一次，就可以完成三种查询，不需要进行字符串比较，但是这要构造非常复杂的数据结构，常用的数据结构是trie树结构。 trie树是一种有限状态自动机，每个节点代表一个状态，根据输入变量的不同，进行状态转移。对于中文句子，输入变量就是每一个汉字，每输入一个汉字，就会引发一个状态转移，可能是从一个状态到另一个状态，也可能是一个状态到它自身的转移。假设有n种状态，输入变量有m种，那么trie树的存储空间就是O（m*n)，一般n>50万，m>5000，空间占用相当庞大。而且有些时候trie树的节点分支很少，造成了空间的大量浪费（有效存储空间过小，而树结构存储空间较大）。于是，有研究者提出了用三个线性数组存储trie树结构，并在此基础上进一步改进，提出了用两个线性数组表示trie树的方法，这就是双数组trie树。 双数组trie树是两个整形数组，一个是base[]，一个是check[]，base数组中每一个元素对应trie树中的一个节点，他的值做状态转移的基值，check值相当于校验值，用于检查该状态是否存在。对于从状态s到状态t的一个转移，必须要满足如下两个条件： 1、base[s] + c = t 2、check[t] = s 其中的c是输入变量。 base[i]和check[i]均为0时表示该位置为空，base[i]为负值时表示该状态是一个可结束的状态。两个数组按照如下方法构造： 对于状态AB1、AB2、...ABn，状态A在数组中下表为i，check[i]=0，令A的base值base[i] = k，k满足条件： base[k+B1]=0,check[k+B1]=0,base[k+B2]=0,check[k+B2]=0,...base[k+Bn]=0,check[k+Bn]=0 也就是说，k的值要保证使A的直接子节点B1、B2、...Bn都能放入数组（这些位置都是空的）即可。k的值确定之后，状态AB1、AB2、...ABn在数组中的下标随即确定，分别为k+B1，k+B2，...k+Bn，同时： check[k+B1]=check[k+B2]=...=check[k+Bn]=i。 数组构造完成之后，要查找一个关键码Ab，只需要判断check[base[A]+b]是否等于A，如果是，则Ab在trie树中可以查询到，否则查询失败。 是不是很巧妙呢，其实，写代码实现出来也不过100多行，实在是太美了，还有更美的呢。 待续...