/ahocorasick

AC自动机的Python实现及其性能对比

Primary LanguagePythonMIT LicenseMIT

ahocorasick

AC自动机的Python实现及其性能对比

测试数据

数据存放在data目录中，包括PKU和AS的分词数据集、jieba词库组成，分别测试三个数据集装载耗时及匹配耗时的性能

数据集 单词数 数据大小
PKU 55303 1826448字
AS 141339 8368050 字
Jieba 584429 4050566字

性能结果

（词典装载时间，数据查询时间）

实现 PKU AS jieba
prefix_dict （0.065, 2.39） (0.211, 11.0) (0.803, 5.53)
tried_dict （0.226, 2.52） (0.748, 11.83) (2.79, 5.09)
ahocorasick_dict (0.437, 1.12) (2.81, 5.95) (49.0, 2.67)
tried_dar (9.80, 3.96) (70.15, 19.35) --

结果分析

  1. tried_dar：普通双数组实现并不适用于Python，其性能反而下降严重
  2. prefix_dict：将所有前缀都存放在一个字典中，内存和构建时间均明显下降，查找性能基本跟tried_dict一致
  3. 词典装载：tried_dict词典装载时间随词典数量增长装载时间呈现线性增长
  4. 运行性能：从性能上看，tried_dict性能约为100W c/s，ahocorasick_dict 实现约为tried_dict实现性能的1.5-2.0倍
  5. LAC、pkuseg、thulac等分词器性能低于 5W c/s，从ahocorasick_dict替换为tried_dict后性能下降低于2.5%

模块脚本

.
|____imp                          # 各个版本AC自动机的实现
| |____ahocorasick_dict.py        # 基于词典的AC自动机
| |____tried_dict.py              # 基于词典的Tried树
| |____tried_dar.py               # 基于双数组的Tried树
|____test_ac.py                   # 测试各词典AC自动机的脚本