Tech Ideas

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

用 DAT 重实现 CppJieba 中文分词算法,降低 99% 内存消耗


一,问题背景

中文分词应用比较广泛的开源算法,是 jieba 结巴分词,结巴分词较高性能的实现是 C++ 版本的 CppJieba : https://github.com/yanyiwu/cppjieba

在实际使用 CppJieba 的过程中,我们发现 CppJieba 的内存占用比较高。

比如对一个 76W 词 大小 11MB 的词典 ,加载 2份 (比如为了支持平滑改动用户词典)就需要耗费 505MB内存。

这对一些多进程的后台服务,浪费大量内存,难以接受,因此这里希望削减内存耗费。

经过初步调查,确定改进方法,然后动手改造,最终把 505MB 缩减到了 4.7MB ,实现了 99% 内存降低

此处也有 issue 讨论 https://github.com/yanyiwu/cppjieba/issues/3

代码稍后可能会开源出来。

二,实现过程

二.1 查内存分布

第一步先用 jemalloc 的 memory profiler 工具查看内存耗费在哪里,

  1. 改一下 CppJieba 的 test/demo.cpp, 链接 jemalloc,编译成二进制 jieba_test
  2. 然后设置环境变量 export MALLOC_CONF="prof:true,prof_prefix:mem_prof/mem_profile_je.out,lg_prof_interval:20,lg_prof_sample:20"
  3. 然后 mkdir mem_prof, 并运行测试程序
  4. jeprof –pdf ./jieba_test mem_prof/mem_profile_je.out.xxx.heap > mem_profile.pdf

打开 mem_profile.pdf ,就可以看到内存分布了

二.2 优化方案

显而易见,内存主要耗费在: 1. Trie.hpp 中的 Trie 树构建 2. KeywordExtractor.hpp 加载 idf 词典文件。

因此方案:

1. Double Array Trie 代替 cppjieba::Trie

引入 Double Array Trie (简称 DAT ,https://github.com/s-yata/darts-clone) , 代替 Trie.hpp 中的简单内存 Trie,并把 darts 生成的 DAT 保存到文件中,在启动时,如果已经有和词典对应的 DAT ,直接 mmap() attach 上去,即可启动。

经过实测发现,75万词词典,dart-clone 生成的 DAT 文件,大小只有 24MB,而且可以 mmap 挂载,多进程共享。

2. KeywordExtractor

KeywordExtractor 是个不常用功能,直接改成支持传入空的 idfPath 和 stopWordPath, 此时不加载数据即可。

二.3 其他问题

1. 支持热更新,保证词典和DAT一致

这里一个问题是,词典可能热更新,那怎么知道 DAT 文件和当前词典的内容对应?

我的做法是,对 默认词典文件+自定义词典文件,用文件内容算 MD5,写入 DAT 文件头部,这样打开 DAT 文件发现 MD5 不一致,就知道 DAT文件过时了,即可重建 DAT 。

实测发现算 MD5 还是很快的,启动时间都在 1秒 左右。

2. 代码清理

另外,清理了一下代码,删掉了 Unicode.hpp 中的无用代码。 清理了 FullSegment.hpp HMMSegment.hpp MixSegment.hpp MPSegment.hpp QuerySegment.hpp 等中的重复代码。

3. 不兼容改动

  • 由于 Double Array Trie 无法支持动态插入词,删除 InsertUserWord() 方法
  • FullSegment.hpp 中 maxId 的计算有 bug,做了 fix。

整体改造后,代码量比原来减少 100 多行。

上线后效果显著。

当内存降低到 2-3MB 的水平后,这意味着 75W 词这种规模的大词典,可以用在手机环境。

比如可以在 ios 或者 Android 上做 中文/英文的切词, 这意味着可能在客户端实现体验相当良好的搜索引擎。

ios 上也有可用于中文的分词器 CFStringTokenizer ,但貌似不开源。

Comments