今晚在家有点闲，便想点是来做。想来想去，决定写一下最近”研究“的中文分词技术。

  中文分词方法发展至今，具体来说，方法已经有多种，什么正向最大匹配、逆向最大匹配、双向最大匹配这些纯机械切词，也有基于统计模型的n元分词、HMM分词等等。

   目前个人”研究“到了n元分词，就来说说n元分词中的重要数据结构或者说基础，切分词图。当然，研究到这发现什么正向最大匹配或者逆向最大匹配等，完成可以看成是n元分词在某种条件限制下的特例，也是我想说说切分词图的原因。

   首先，上一张切分词图吧，该词图的句子是“有意见分歧”。

1.切分词图

    看到词图，大家或许会想，如何生成词图，词图的意义是什么呢，词图用什么样的数据结构存储和实现呢，下面将道来。

      （1）生成词图：

对于一个长度为n的句子，可以有n+1个节点，将句子所有的单字分开。如果我们把其中两个节点连上，我们会神奇的发现，这条边可以代表一个词（当然，可能这条表实际上并不是词，不过这没关系）。如上图，将节点1和3连起来，记做1->3，则该边便可以代表词“意见”。

根据词典，将一个句子中的所有可能词识别出来。同时，对于未知的（词不在词典中时）我们认为一个单字代表一个词，这样，我们很容易生成切分词图了（如图1）。

（2）词图的意义

词图的意义一句话概括即是包括所有可能的切分方案，后续可采用一些算法，求得最可能的切分方案。（注：当我们认为每条边的概率一样时，也就是边是词的概率一样时，切分词图求最可能切分方案则退化到最大匹配分词算法，也即是分出词最少的分词方案）。

图1，我们有两条路径（对应着两种切分方案）如下：

路径1：0－1－3－5   对应切分方案S1：有/  意见/  分歧/

路径2：0－2－3－5   对应切分方案S2：有意/  见/  分歧/

至于如何确定这两个方案那个更佳呢，我们可以通过n元模型去求得（常用1元模型或者2元模型），这不再该篇的考虑范畴内，不再细述。

（3）词图的实现

可以很容易想到，词图可以通过邻接表去实现。对，没错，邻接表可以实现词图。以下给出一些示例：

定义节点：

public class CnToken{

   public String termText;//词

   public int start;//词的开始位置

   public int end;//词的结束位置

   public int freq;//词在语料库中出现的频率

   public CnToken(int vertexFrom, intvertexTo, String word) {

       start = vertexFrom;

       end = vertexTo;

       termText = word;

   }

}

邻接表表示的切分词图由一个链表表示的数组组成，实现一个单向链表：

publicclass TokenLinkedList implements Iterable<TokenInf> {

  public static class Node {

       public TokenInf item;

       public Node next;

       Node(TokenInf item) {

            this.item = item;

            next = null;

       }

}

private Node head;

   public TokenLinkedList() {

       head = null;

   }

   public void put(TokenInf item) {

       Node n = new Node(item);

       n.next = head;

       head = n;

}

   public Node getHead() {

       return head;

}

   public Iterator<TokenInf> iterator(){//迭代器

       return new LinkIterator(head);

   }

   private class LinkIterator implementsIterator<TokenInf> {

       Node itr;

       public LinkIterator(Node begin) {

            itr = begin;

       }

       public boolean hasNext() {

           return itr != null;

       }

       public TokenInf next() {

            if (itr == null) {

                throw newNoSuchElementException();

            }

            Node cur = itr;

            itr = itr.next;

            return cur.item;

       }

       public void remove() {

            throw new UnsupportedOperationException();

       }

   }

   public String toString() {

       StringBuilder buf = newStringBuilder();

       Node cur = head;

       while (pCur != null) {

            buf.append(cur.item.toString());

            buf.append('t');

            cur = cur.next;

       }

       return buf.toString();

   }

}