Daachorse 是一个使用Aho-Corasick 算法进行快速多重模式匹配的 crate ,在输入文本的长度上以线性时间运行。对于时间和内存效率,模式匹配自动机是使用紧凑的双数组数据结构实现的。该数据结构不仅支持恒定时间的状态到状态遍历,而且在只有 12 个字节的紧凑空间中表示每个状态。 例如,与Rust 中最流行的 Aho-Corasick 实现的 aho-corasick crate的NFA相比, 当使用675K 模式。
2022-06-11 18:06:28 3.44MB rust 算法
Trie树是搜索树的一种,来自英文单词"Retrieval"的简写,可以建立有效的数据检索组织结构,是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态。在词典中这种状态包括"词前缀","已成词"等。 双数组Trie(Double-ArrayTrie)是trie树的一个简单而有效的实现,由两个整数数组构成,一个是base[],另一个是check[]。设数组下标为i,如果base[i],check[i]均为0,表示该位置为空。如果base[i]为负值,表示该状态为词语。Check[i]表示该状态的前一状态,t=base[i]+a,check[t]=i
1
主要介绍了Java中实现双数组Trie树实例,双数组Trie就是一种优化了空间的Trie树,本文给出了实现代码、测试代码和测试结果,需要的朋友可以参考下
2021-11-13 21:03:35 68KB Java 双数组 Trie树
1