基于静态Darts实现了AC自动机的字符串匹配类库，支持UTF-8编码，目前在项目中用于敏感词功能。
该库只支持PHP7及以上版本，之前版本因为有C扩展实现了类似功能，也不需要这个。
因为并不精通算法，实现上更偏向于业务代码风格，较多地利用了php数组双向链表的特性。算法实现上若有不对，或是有更好的优化方案，请狠狠给个merge request！
| 功能描述 | 实现版本 |
|---|---|
| 修正在双数组模式下导入同路径词条引发的问题 | 1.6 |
| 调整部分方法及属性命名 | 1.5 |
搜索时增加$limit和$skip参数 |
1.4 |
| 增加批量查找功能，可一次获取所有命中词 | 1.3 |
| 修正查找失败时的指针偏移bug | 1.3 |
在此库已稳定将近9个月后居然在工作中发现了重要BUG，运营在字典中添加了一个单个字的词条后，居然查找不到这个词。
经过排查，发现这是压缩为Double Array后的正常现象。双数组结构可以获取更高的执行效率，同时也让算法实现的功能更为单一：拿一个字典与匹配字串进行碰撞，判断字串是否有包含字典中的词条。
因此，经过双数组压缩过后的字典中的每个节点，是不能同时为过路节点又为末节点的。
也就是说，如果往字典中添加小猪和小猪狗这两个词条，执的结果是无法检查到小猪这个词条的。
经过取舍，为了保证该库和算法的设计本意，对字典的构建算法做了更改，当同时添加上述两个词条时，只有小猪会被加入。因为后者已经包含前者，所以并不会对“是否包含字典中的词条”这一检查目的造成影响。
- 变更
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结果是犯规
这里有几个要点需要理解：
- limit限制的数字，是指查找起始点，而非结束点。所以这里limit=1会从第一个字"违"查起，但只要能一直匹配到成功，不会在“违”字结束匹配。
- 传入的数字是UTF-8字符数，不是字节数。
- skip和limit均不支持负数。
稍稍改进一下上面的代码：
$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给我，先谢过大家帮忙调试了！