andares/adarts

a darts class

v1.6.2 2017-08-08 19:18 UTC

README

基于静态Darts实现了AC自动机的字符串匹配类库,支持UTF-8编码,目前在项目中用于敏感词功能。

该库只支持PHP7及以上版本,之前版本因为有C扩展实现了类似功能,也不需要这个。

因为并不精通算法,实现上更偏向于业务代码风格,较多地利用了php数组双向链表的特性。算法实现上若有不对,或是有更好的优化方案,请狠狠给个merge request!

更新与路线图

功能描述 实现版本
修正在双数组模式下导入同路径词条引发的问题 1.6
调整部分方法及属性命名 1.5
搜索时增加$limit$skip参数 1.4
增加批量查找功能,可一次获取所有命中词 1.3
修正查找失败时的指针偏移bug 1.3

更新内容详述

1.6版本改动

在此库已稳定将近9个月后居然在工作中发现了重要BUG,运营在字典中添加了一个单个字的词条后,居然查找不到这个词。

经过排查,发现这是压缩为Double Array后的正常现象。双数组结构可以获取更高的执行效率,同时也让算法实现的功能更为单一:拿一个字典与匹配字串进行碰撞,判断字串是否有包含字典中的词条。

因此,经过双数组压缩过后的字典中的每个节点,是不能同时为过路节点又为末节点的。

也就是说,如果往字典中添加小猪小猪狗这两个词条,执的结果是无法检查到小猪这个词条的。

经过取舍,为了保证该库和算法的设计本意,对字典的构建算法做了更改,当同时添加上述两个词条时,只有小猪会被加入。因为后者已经包含前者,所以并不会对“是否包含字典中的词条”这一检查目的造成影响。

1.5版本改动

  • 变更getWordsByState()方法更名为getWordByState(),原方法名做兼容性留存

安装

一个简单的composer库而已:

composer require andares/adarts

序列化功能用到了msgpack,这个东西我很喜欢,推荐使用:

pecl install msgpack-2.0.1

安装完后在php.ini或是conf.d里加上extension=msgpack.so即可,线上环境莫忘重启fpm

创建字典

$dict = new \Adarts\Dictionary();
$dict->add('word1')
    ->add('word2')
    ->add('word3')
    ->add('word4')
    ->confirm();
  • add() 向字典中添加一个词条,返回$this,可像上面那样重复调用。
  • confirm() 当词条添加完后生成darts树及失败指针。

当然我知道大家实际中一般都会这么用:

<?php
use Adarts\Dictionary;

// ...这里是从mysql中读取词条列表到$collection变量的1000行代码
$collection = MySQL::get();

$dict = new Dictionary();
foreach ($collection as $word) {
    $dict->add($word);
}
$dict->confirm();

请注意,由于confirm()行为会对数据做压缩处理,因此一个新建的字典对象应只能执行一次confirm()操作,重复执行将导致报错。如果有需要重新生成字典,可以重新new一个新的字典对象进行创建。因为压缩后的darts树本身就算不上一种可逆操作,所以这个库本身并不能同时作为存放原始字典的容器使用。这个库字典设计一切目标是为了更快地搜索匹配,词库更适合放在数据库、文件系统等其他地方。

搜索匹配

字典创建完后就可以用于搜索,例如:

$result = $dict->seek('get out! asshole!')->current();
if ($result) {
    throw new \LogicException('you could not say it');
}
  • seek() 搜索一个字串,看是否有字典中匹配的词。返回一个生成器对象,所以请使用current()方法获取第一个匹配词。

在上面的例子中,我们假设asshole在字典中,那么current()方法即可得到一个不为0的整数。

事实上,$result即Darts中的叶子节点state

如果传入的字串中未包含字典中的内容,由于迭代器特性,则会返回一个null值,这点需要注意!

限制搜索范围

搜索时传入$limit参数,可限制只搜索到某个第几个字作为开头,例如:

// 假设“违法”和“犯规”两字在字典中
$limit  = 1;
$result = $dict->seek('违法犯规', $limit)->current();

// 这时$result结果只有违法

搜索时传入第二个参数$skip,可跳过几个字符开始搜索,例如:

$limit  = 1;
$skip   = 2;
$result = $dict->seek('违法犯规', $limit, $skip)->current();

// 这时$result结果是犯规

这里有几个要点需要理解:

  1. limit限制的数字,是指查找起始点,而非结束点。所以这里limit=1会从第一个字"违"查起,但只要能一直匹配到成功,不会在“违”字结束匹配。
  2. 传入的数字是UTF-8字符数,不是字节数。
  3. skip和limit均不支持负数。

根据state获取匹配词

稍稍改进一下上面的代码:

$result = $dict->seek('get out! asshole!')->current();
if ($result) {
    throw new \LogicException('you could not say ' . $dict->getWordByState($result));
}
  • getWordByState() 根据叶子节点state获取找到的匹配词,如果没意外上面取到的是asshole

查找多个命中词

foreach ($dict->seek('get out! asshole!') as $result) {
    echo "you could not say ' . $dict->getWordByState($result);
}

利用迭代器特性,foreach返回的生成器对象即可获取所有命中词条。

关于找到的位置

因为支持失败指针,所以state的转换不是线性的,当通过失败指针跳到其他词条(的某个节点)时,还没找到好的方法(有效率地)逆推到起始节点的办法。

因此seek()只能告诉你是否有找到,最多带一个找到了什么,如果需要实现知道位置的功能,可以使用找到词条另外调php方法去处理。在已经明确结果的 下,单词条的查询效率不会有什么问题。

序列化

Trie树的策略就是提前对字典做分析,在搜索的时候以最少的步数进行匹配搜索。所以每次搜索时都实时建立字典显然有违初衷,我们可以通过在输入词条列表时创建字典,并调confirm()生成分析后的Darts数据,然后对Dictionary进行序列化后保存(用你最爱的持久化方案,MySQL、mongodb、redis、memcache、leveldb等等等等)。

这样当需要搜索时,只需要读出字典对象直接搜索就行了。

Adarts使用msgpack进行字典序列化,以获得比php序列化或json更好的I/O性能。

// 这是创建$dict并添加词条并confirm()的1000行代码

$packed = serialize($dict);

// 这是把序列化后的数据持久化的1000行代码
// 嗯,也许可能长这样
redis()->set('dict', $packed);

现在我们要用了,那么:

// 可能长成这样的读出序列化数据代码
$packed = redis()->get('dict');
$dict = unserialize($packed);

$result = $dict->seek($str)->current();
// ...搜索后的1000行业务代码

精简字典对象

显然,上面的做法还没有让速度达到最快,因为了字典对象在创建的过程中会产生大量中间数据。这其中一部分是在其他一些场景(非搜索)中有用的,有一些则目前看起来没什么用处。

所以如果确认这个字典对象的序列化数据只用在搜索这一场景中(判断有无),那么可以这样打包:

$packed = serialize($dict->simplify());

这样做会只留搜索必要的数据,让序列化后的数据更小,读出和反序列化更快。

注意simplify()之后的字典对象去掉了词条states索引,这会导致getWordByState()方法不可用(总是返回空串)。所以对于有两种需求的情况来说,推荐精简与完整的字典序列化各存一份,以适用不同的场景。

感谢

感谢网上被复制了无数份的Trie PHP实现那个教程文档,虽然Trie树部分的代码完全没有参考价值,但我确实复制粘贴了原作者写的UTF-8拆分代码,并得到了指点。

还有http://www.cnblogs.com/ooon/p/4883159.html此文,参考的内容是最多的,刚看第一眼的时候其实并没有想读懂>_<

嗯,暂时就先写到这里,如果有坑请发issue给我,先谢过大家帮忙调试了!