有多个初始状态的 DFA

阅读更多关于《有多个初始状态的 DFA》

最近做了一项工作:允许一个 DFA 有多个起始状态(可以称作根: root)。引入这个概念有很多好处,主要体现在 DFA Union 中,这个操作通过 NFA 到 DFA 的转化来完成,算法思想很简单: 继续阅读

多正则表达式匹配(Multiple Regular Expression Matching)

阅读更多关于《多正则表达式匹配(Multiple Regular Expression Matching)》

目前 febird 中的自动机库已支持正则表达式,并且,支持的是多正则表达式匹配: 继续阅读

把自动机用作 Key-Value 存储

阅读更多关于《把自动机用作 Key-Value 存储》

这篇文档只关心 有穷状态自动机 ,不讲具体的算法,对自动机只讲一些基本概念。主要描述 怎样使用自动机工具创建 KV 数据库,怎样使用自动机 API 访问 KV 数据库…… 继续阅读

字符串匹配中的图论

阅读更多关于《字符串匹配中的图论》

有一个字符串由多个变量拼接而成: “$x1$x2$x3$x4$x5$x6…” ,这个列表可以一直延伸到 $x10000,而每个变量都至少有一种可能的取值,为了简化问题,每个变量不会再引用别的变量。问题是:给定一个字符串T,判断这个字符串是否能由上面这个 “$x1$x2$x3$x4$x5$x6…” 生成。

继续阅读

Trie, Hash, MinADFA

阅读更多关于《Trie, Hash, MinADFA》

Trie的搜索复杂度是 O(length(strkey)),Hash表,计算Hash的复杂度也是O(length(strkey)),但是,仔细分析一下: 继续阅读

NFA转化DFA

阅读更多关于《NFA转化DFA》

NFA既然和DFA等价,那么,它们之间就存在对应关系,DFA到NFA的转化是自明的:没有空转移,把返回的单个state编程仅包含一个state的集合,就是一个形式上的NFA。但是,NFA到DFA的转化就不是那么简单了,实际上,在计算理论中,它属于ExpSpace问题,是一类比NP问题更难的问题。

继续阅读

DFA的实现

阅读更多关于《DFA的实现》

在工业界,DFA的有效实现一直是一个问题,龙书中提到了一种使用四个数组的通用DFA实现,在汉字分词算法中经常用到double array作为Trie的一种实现。四数组的是通用DFA的实现,双数组的仅能用于实现Trie。并且它们的创建速度慢,难以理解,内存占用也比较多,状态id的值域范围稀疏。

继续阅读

自动机的一些算法和应用

阅读更多关于《自动机的一些算法和应用》

几个月前实现了一个自动相关的算法,在一个比较乐观的测试中,将一个2.3G的url集合压缩到了27M,同时,key查找的时间复杂度是O(strlen(key))。当然,还有其它一些自动机相关的算法的优化实现,比如Aho-Corasick多模匹配。 继续阅读

自动机的思维导图

阅读更多关于《自动机的思维导图》
自动机有很多用途,不光是编译器会用到,众所周知的还有正则表达式。其他,简单的如字符串搜索,存储等,复杂点的如模型验证,定理证明…… 继续阅读

实现了一个压缩算法,在数据高度压缩的前提下,还可以快速查找 key

阅读更多关于《实现了一个压缩算法,在数据高度压缩的前提下,还可以快速查找 key》

最近写了一个算法,可用于 (key,value) 存储,key 当然是 string 类型。

用一个 2.3G 的 url 集合做测试,如果不计 value 占用的空间,key 集合的存储空间可以被压缩70倍!压缩后整个数据结构仅占31M内存!压缩率比 bzip2 还要高。 继续阅读