Tech Ideas

C++,Linux,Algorithm,Crypto,Lisp,etc

GB 规模语料上的高性能新词发现算法


分词是中文搜索的重要环节,目前分词算法已经比较成熟,分词错误的主要是由于未登录词。

因此发现业务领域语料库中的新词,减少未登录词,对改善搜索引擎的用户体验有重要意义。

新词发现的一种常用算法,是 matrix67 大神 2012 年提出的 《互联网时代的社会语言学:基于SNS的文本数据挖掘》 https://www.matrix67.com/blog/archives/5044

其主要思路,是统计语料中出现的所有 ngram 子字符串的凝固度,自由度,信息熵。

算法中需要统计所有 ngram 子字符串的 左熵右熵,实现该算法时,一般以子字符串为 key,用哈希表来存。

但随着语料库变大时,内存消耗变大,

比如之前的 python 版本实现,对 200MB 的语料,就需要约 30G 内存来存哈希表,

导致单机内存不足无法运行,而且对这样规模的语料库,算法需要跑一两天才能出结果。

这里我应用一些工程实现方面的技巧, 把用哈希表统计左熵右熵的计算,拆分成多个子哈希表,分批计算,并利用多核并行,大幅度优化了算法的性能。

最终实现了 GB 大小语料上的新词发现,并把运行时间缩减到了 30 分钟左右 。

https://github.com/hankcs/HanLP/wiki/%E6%96%B0%E8%AF%8D%E8%AF%86%E5%88%AB

Comments