科学网 › 标签 › 切分词图

标签: 切分词图

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

分词技术之全切分词图: huapei1989 2015-5-10 23:31; 今晚在家有点闲，便想点是来做。想来想去，决定写一下最近 ” 研究 “ 的中文分词技术。中文分词方法发展至今，具体来说，方法已经有多种，什么正向最大匹配、逆向最大匹配、双向最大匹配这些纯机械切词，也有基于统计模型的 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 IterableTokenInf { 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 IteratorTokenInf iterator(){// 迭代器 return new LinkIterator(head); } private class LinkIterator implementsIteratorTokenInf { 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(); } }; 个人分类: nlp|4271 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 切分词图

相关帖子

相关日志

关闭安全验证