放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

词图的生成

目录

当分词系统有一份词典的时候,就可以生成词图了。所谓词图,指的是句子中所有词可能构成的图。如果一个词A的下一个词可能是B的话,那么A和B之间具有一条路径E(A,B)。一个词可能有多个后续,同时也可能有多个前驱,它们构成的图我称作词图。

词图的生成

需要稀疏2维矩阵模型,以一个词的起始位置作为行,终止位置作为列,可以得到一个二维矩阵。例如:“他说的确实在理”这句话

那么如何建立节点之间的联系呢?也就是如何找到一个词A的后续B、C、D……呢?有两种已实现的方法,一种是所谓的DynamicArray法,一种是快速offset法。

DynamicArray法

最直截了当的想法当然是用二维数组模拟这个模型了,很明显,其中有不少空洞,所以在ICT系列的分词器中定义了一个蹩脚的DynamicArray结构用来储存模型,DynamicArray结构的每个节点包含一个个词的row和col,待会儿看完offset法你就会明白我什么么说DynamicArray蹩脚。

在这张图中,行和列有一个非常有意思的关系:col为 n 的列中所有词可以与row为 n 的所有行中的词进行组合。例如“的确”这个词,它的col = 5,需要和它计算平滑值的有两个,分别是row = 5的两个词:“实”和“实在”。

连接词形成边的时候,利用上面提到的关系即可。

但是在遍历和插入的时候,需要一个个比较col和row的关系,复杂度是O(N)。

快速offset

虽然模型的表示用DynamicArray没有信息的损失,但问题是,真的需要表示模型吗?

当然不,我可以将起始offset相同的词写到一行:

始##始
他
说
的/的确
确/确实
实/实在
在/在理
理
末##末

这个储存起来很简单,一个一维数组,每个元素是一个单链表。

怎么知道“的确”的下一个词是什么呢?“的确”的行号是4,长度是2,4+2=6,于是第六行的两个词“实/实在”就是“的确”的后续。就这么简单。

同时这种方法速度非常快,插入和查询的时间都是O(1)。

小结

MISS是设计的准则,不需要新定义那么复杂的数据结构。ICT作者为何定义那么复杂的DynamicArray,写了那么多曲曲折折的代码就不知道了。

Reference

http://www.cnblogs.com/zhenyulu/articles/668035.html

http://blog.csdn.net/sinboy/article/details/663123

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 词图的生成

分享到:更多 ()

评论 18

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #10

    当调用标准分词的时候,并且在用户自定义词典加入了新词。在对一个包含分词的句子进行分词时,分词系统是采用什么样的分词策略啊?我的理解时标准分词是叠层隐马尔科夫最短路,自定义词典是ac+trie。请问一下是怎么处理的啊?

    sunny2个月前 (06-08)回复
  2. #9

    2元语法词典路径,是用来模拟马尔可夫的转移概率么? 这个词典也太大了吧,有什么简便的方法可以处理么?

    尹坤2年前 (2016-02-18)回复
    • 在所有模型里算小的,HanLP有独特的压缩方法

      hankcs2年前 (2016-02-20)回复
  3. #8

    看楼主源码,为什么你自己写的最短路方法,叫Viterbi算法,我没有看出来

    letcheng2年前 (2015-12-27)回复
  4. #7

    你好

    不一致,是在句子中的offset

    不是,最短路是概率负对数图的最短路

    不清楚,它那个应该是落后的词典分词

    hankcs2年前 (2015-11-08)回复
  5. #6

    how are you thank you

    0-3 4-7 8-11 12-17 18-21 offset,
    楼主你好,请教几个问题:
    1.说和确/确实,两个term的起始位移不一致吗,不都是0吗?
    2.的确”的行号是4,长度是2,4+2=6,于是第六行的两个词“实/实在”就是“的确”的后续。这就是所谓的最短路径算法?
    3.lucene smartcn的最短路径算法就是您的第二种?

    lTHJj2年前 (2015-11-08)回复
  6. #5

    请问这么一个CoreNatureDictionary.ngram.** 的词典是如何生成,在您开源的hanlp中对应哪个代码?

    allen2年前 (2015-06-15)回复
    • 训练出来的,这里的main方法就演示了核心词典、BiGram词典、词性转移矩阵的生成。当然,你得自己准备一个分词语料库。http://t.cn/R2aIgJh

      hankcs2年前 (2015-06-28)回复
  7. #4

    标准分词就是ICTCLAS分词系统吧??

    木叶三郎2年前 (2015-04-19)回复
    • 可以这么说,基于层叠隐马模型的最短路分词

      hankcs2年前 (2015-04-19)回复
  8. #3

    这里的词图的生成就是标准分词的解释吗?

    木叶三郎2年前 (2015-04-19)回复
  9. #2

    你这里所说的:标准分词就是前向最大匹配方法吗?

    木叶三郎2年前 (2015-04-19)回复
  10. #1

    呵呵,我就是这么实现的。

    maoYe3年前 (2014-08-28)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机