TreeSplitter---树形分词算法

TreeSplitter---树形分词算法2015-02-11注：思路不是原创，首先感谢思维的突发奇想者

一、说明：

目前分词的算法很多，现成的分词组件也不少，但很难找到一个我自己需要的，我只要一个分词功能，一个能理所当然完成分词工作的东西，理所当然是指词库里有什么词就能分出什么词。一些智能分词的目标是毋庸置疑的，难度也是随着智能的程度而增加，不是你我（只少不是我）随随便便走在大街上就能突发奇想出来的。一些成熟的分词方法是基于词库的，本着DRY原则以至于DRO（Don’t repeat others），君要了解请看这里或直接Google。其中的不足，思路的原作者经已说的很明白，我体会过，很可能你也体会过！这问题困扰了我好久，就在清明前放假的那天，搜索了几篇关于分词的文章，决定利用这三天好好了解一下分词的方式。看时发现，大多都是【最大匹配法】，唯独这篇已树形分词的文章让我看到了希望，它正是我需要的！本来还想遵守DRO原则，就在网上搜索源码，却一直求之不得，在这种情况下只能DIY（do it yourself）了。

二、实现：

1、建立Node类

Node表示树的一个结点，结点有值，有一个父结点多个子结点，还要知道是否是一个词尾，即从根到此是否是一个词（下文用【成词】表示），方法GetTermValue就是上溯得到其词的。

Node类[Serializable]public class Node{public char Value { get; set; }public Node Parent { get; set; }public bool End { get; set; }public Dictionary<char, Node> Children { get; set; }public static Node Empty = new Node（" ", null）;public Node（char value, Node parent）{this.Value = value;this.Parent = parent;Children = new Dictionary<char, Node>（）;}public string GetTermValue（）{List<char> chars = new List<char>（5）;Node node = this;while （node.Parent ！= null）{chars.Insert（0, node.Value）;node = node.Parent;}return new string（chars.ToArray（））;}}

2、树形词库的创建

如果能在头脑里想象出来这个树的结构，这一步就能很容易的搞定了，而关于树的结构，咱高中生一个，表述能力自知很拙，所以请看原创者的论文。关于存储，最简单的就是直接序列化了，但因为父结点要保存所有子结点，第一次生成后真是吓一跳，文本词库用的是盘古分词整理的，大概是15w词1.5M的大小，树形词库生成后大小80多M！这个时候肯定开始优化了：

1）把Node属性命名都用一个字母，测试后发现自己愚蠢了，大小只减少了1M多，序列化不会像mongodb那样存储，哈哈真是自己想多了....

2）能否改变树的存储结构？因为分词时的检索效率很重要，树加载后肯定还是要形成如Node类表示的那样，就想能不能存储成扁平结构或是让父结点引用首个子结点，首个子结点引用下个兄弟结点等等，考虑了几个，一个测试成功的都没有！书到用时方恨少呀，没研究过数据结构，所以在这个地方的思维也很局限，可能真的存在很好的方法！

3）压缩流，这个很简单，.net类库有自带，测试发现，不但简单，效果还显著，树形词库一下子减小到20多M，这个我是可以接收了！

4）非托管代码，一直对C语言有敬畏之意，虽然很多看不懂，但感觉很有趣有样子，在.net里也是一直没用unsafe式编过代码，趁此机会就试一把，只用到对字符串中的字符访问那里，改好后Ctrl+F5还真运行了！只是效果基本没变，看来用在这个地方的safe代码效率也很高的呀，所以这个基本不算优化，只是满足一下自己虚荣的心罢了！

树类型看源码，下面的创建方法是树类型里的静态方法，因为想到词库的维护，Build即表示Create和Append，Append时用到了LoadRootNode方法，接下来会给出。

创建树形词库public static void BuildDict（string[] lines, string dictPath）{var capitals = lines.Select（（line） => { return line[0]; }）.Distinct（）.ToArray（）;//第一级节点foreach （var capital in capitals）{Node rootNode = rootNode = LoadRootNode（capital, dictPath, true）;if （rootNode == null） rootNode = new Node（capital, Node.Empty）;#region 建立以rootPrefix为首字的一组节点var terms = lines.Where（（line） => { return line[0] == capital; }）;foreach （var term in terms）{int length = term.Length;if （length == 1） //首字也为一个词的情况rootNode.End = true;var parentNode = rootNode;unsafe{fixed （char* cs = term）{int i = 1;char curChar;while （（curChar = *（cs + i）） ！= char.MinValue）{Node curDictNode = null;if （parentNode.Children.Keys.Contains（curChar））{curDictNode = parentNode.Children[curChar];}else{curDictNode = new Node（curChar, parentNode）;parentNode.Children.Add（curChar, curDictNode）;}if （i == length - 1） curDictNode.End = true;parentNode = curDictNode;i++;}}}}#endregionusing （FileStream stream = new FileStream（GetDictFileName（capital, dictPath）, FileMode.Create））{using （GZipStream zip = new GZipStream（stream, System.IO.Compression.CompressionMode.Compress））{var formatter = new BinaryFormatter（）;formatter.FilterLevel = System.Runtime.Serialization.Formatters.TypeFilterLevel.Low;formatter.TypeFormat = System.Runtime.Serialization.Formatters.FormatterTypeStyle.TypesWhenNeeded;formatter.Serialize（zip, rootNode）;}}rootNode = null;}GC.Collect（）;}