自然语言处理之词语抽取

多日之前看到了Matrix67的《互联网时代的社会语言学:基于SNS的文本数据挖掘》,文中提到的方法是无监管的,而且无需词典就能提取词语,要素概括起来有两点:词的凝聚力,以及左右邻字的信息熵。今天把这个方法实现了一下。

对于凝聚力,我的理解是可以用词前后两部分的pointwise mutual information来描述,比如对于“博物馆”一词,考虑“博”与“物馆”之间,以及“博物”与“馆”之间的pointwise mutual information,两者取较小值作为“博物馆”这个词的凝聚力。

左右邻字的信息熵按照Matrix67原文方法计算。

计算pmi和信息熵都需要使用词频,直观的想法是先枚举词的长度$len$,之后枚举所有连在一起的长为$len$的字数组作为候选词。计算词频需要用到类似Rabin-Karp算法的string hash,或者trie,或者一些binary search tree

另一种实现方式是使用suffix array,以相同词作为前缀的后缀在suffix array中处于连续的一段,这样一遍扫描就能依次得到每个词的频度,空间占用较小。另外一个好处是共享同一个右邻字的后缀也是连续的一段,一遍扫描可以得到每个右邻字的频度。之后翻转字符串再做一次得到左邻字的信息,或者把suffix array改造成prefix array

实践

模仿BYVoid对《笑傲江湖》进行了分析。

  • 使用poppler中的pdftotext把pdf转成txt。
  • ./WordExtractor < in > out,两三秒就运行完了。
  • 人工分析 out,设置信息熵以及 pmi 的阈值。
  • 修改analysis.rb并执行ruby analysis.rb < out得到结果。

    令狐冲 自己 甚么 咱们 岳不群 倘若 说道 师父 盈盈 田伯光 林平之 仪琳 如何 武功
    剑法 岳灵珊 一个 长剑 左冷禅 任我行 如此 华山 突然 弟子 今日 他们 恒山派 向问天
    东方不败 余沧海 江湖 不知 华山派 登时 跟着 之中 笑道 出来 教主 心想 虽然 当真
    只是 心中 也不 魔教 二人 小师妹 此刻 刘正风

源代码

github gist