NFA转化DFA
NFA既然和DFA等价，那么，它们之间就存在对应关系，DFA到NFA的转化是自明的：没有空转移，把返回的单个state编程仅包含一个state的集合，就是一个形式上的NFA。但是，NFA到DFA的转化就不是那么简单了，实际上，在计算理论中，它属于ExpSpace问题，是一类比NP问题更难的问题。
本网站仅单台服务器: 2核2G 99￥包年，集成兼容 MySQL 的 MyTopling 高压缩高性能数据库 |
|
本网站仅单台服务器: MyTopling 2核2G 99￥包年当搜索词中有错别字时，搜索引擎会尝试纠错通过相似拼音纠错搜索引擎把这些字还原成拼音，用一个拼音相同的已知的搜索词代替。 这是一种众所周知的纠错策略，但是，当输错的字是多音字，特别是有多个这样的错误输入时，所有的搜索引擎都尽量绕开这个问题，或者仅使用最常用的那些音去纠错。 因为要考虑所有可能的拼音组合，在极端情况下会导致指数爆炸！ 例如某互联网大厂的实现(枚举多音字全排列)。 基于自动机的算法可以完美解决这个指数爆炸问题
这个算法也可以用来解决用户输入预测(智能提示)功能用户只输入Query开头部分，就自动提示出整个Query，例如用户输入举头望，就提示出举头望明月。就像现在各种搜索引擎做的那样。 基于编辑距离的纠错在已知的搜索词中寻找编辑距离与用户 Query 最小的词，使用我的算法也可以高效解决（还没做演示页面） 创建 DFA Key 与 搜索 DFA Key 的 耗时 包含了 收集网页展示需要的信息，耗时占比90%以上！ |
|
DFA的实现
在工业界，DFA的有效实现一直是一个问题，龙书中提到了一种使用四个数组的通用DFA实现，在汉字分词算法中经常用到double array作为Trie的一种实现。四数组的是通用DFA的实现，双数组的仅能用于实现Trie。并且它们的创建速度慢，难以理解，内存占用也比较多，状态id的值域范围稀疏。
自动机的一些算法和应用
几个月前实现了一个自动相关的算法，在一个比较乐观的测试中，将一个2.3G的url集合压缩到了27M，同时，key查找的时间复杂度是O(strlen(key))。当然，还有其它一些自动机相关的算法的优化实现，比如Aho-Corasick多模匹配。 继续阅读
避免应用程序抢夺焦点窗口
最近老碰到当前窗口被抢焦点，却不知道是哪个程序抢了焦点，找到了这一篇文章： 继续阅读
实现了一个压缩算法，在数据高度压缩的前提下，还可以快速查找 key
最近写了一个算法，可用于 (key,value) 存储，key 当然是 string 类型。
用一个 2.3G 的 url 集合做测试，如果不计 value 占用的空间，key 集合的存储空间可以被压缩70倍！压缩后整个数据结构仅占31M内存！压缩率比 bzip2 还要高。 继续阅读
原地排序与链表翻转
有个长度为 n 的 (key,val) 数组 a，其中 key 是 int 类型，并且其值在 [0, n) 之间（前闭后开，包括 0 不包括 n），该数组按 key 是乱序的，但没有重复 key。
题目要求：对 a 原地按 key 排序，可以使用常数个临时变量，不允许使用其它额外空间，时间复杂度必须是O(n) 继续阅读
C++ 中让对象的拷贝成为 显式 的
C++中对象的拷贝一般使用拷贝构造函数，从而对象的拷贝大多是隐式的，使用拷贝构造函数的隐式拷贝很方便，但是编译器无法识别不必要的拷贝，虽然我们人类可以识别这些不必要的拷贝，比如在写函数原型时，忘了加&，就会引发一个这样的非必要拷贝。 继续阅读
C++11: 使用 lambda 创建模板类 的 对象
C++ 中 lambda 可以直接传递给模板函数如 std::sort, 但无法传给模板类如 std::map，但是，使用一点小技巧，可以使用 lambda 创建模板类的对象，省了很多麻烦的 coding。这里给出一个示例： 继续阅读