Skip to content
This repository has been archived by the owner. It is now read-only.
a darts class for match string with dictionary
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
nbproject
src
tests
.gitignore
.styleci.yml
LICENSE
README.md
composer.json
composer.lock
utmake.yaml

README.md

Adarts 使用说明

基于静态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给我,先谢过大家帮忙调试了!

You can’t perform that action at this time.