避免临时对象的字符串加法

阅读更多关于《避免临时对象的字符串加法》

之前我有一篇文章《 C++中让对象的拷贝成为 显式 的》,使用类似的技巧,可以避免字符串加法中的临时对象,也许是因为惰性,这个想法一直没有诉诸实现,今天有空把它写了出来。 继续阅读

gold_hash_idx 完成了

阅读更多关于《gold_hash_idx 完成了》

用在 onfly minimal acyclic DFA construction 上,速度提高了大约28%,内存对每个State节约了4个字节。

以后有空再努力一下,把 gold_hash_idx 再深入泛化一步,做成可以更方便地用于 multi_index 。

gold_hash_map abstract++

阅读更多关于《gold_hash_map abstract++》

目前的gold_hash_map 实现中,index和data是耦合在一起的。
今天在思考 onfly MinADFA 的进一步优化时,想到了一点:在MinADFA_onfly 中,equivalence_register是一个gold_hash_tab, 继续阅读

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的值域范围稀疏。

继续阅读

Context 终于进 boost 了

阅读更多关于《Context 终于进 boost 了》

Version  1.51.0

New Libraries: Context 继续阅读

自动机的一些算法和应用

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

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

自动机的思维导图

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

避免应用程序抢夺焦点窗口

阅读更多关于《避免应用程序抢夺焦点窗口》

最近老碰到当前窗口被抢焦点,却不知道是哪个程序抢了焦点,找到了这一篇文章: 继续阅读