存档在 2012年12月

采用可跳跃Trie树进行地理位置的多模匹配识别

2012年12月22日

最近需要对地名进行多模匹配,看了一下现在的多模匹配算法,主要有两种使用Trie树的方法,均是建树较慢,但是查找速度很快的算法。
两种思路:

1、类似于KMP算法,匹配失败后进行跳转的Trie树。

2、采用双表的trie树进行实现,需要查找的字符串长度较为一致,没有特别长的。查找效率较高。
我使用了第一种,失败后跳转到其他节点的方法。
基本思路:
1、建立Trie树,这里使用单个字节作为节点,每个节点最多有256个孩子
Struct SkipTrieNode {
SkipTrieNode* child[256];
SkipTrieNode* skip_fail;
}
截取选区_001
2、采用BFS遍历Trie树,为每个节点计算skip fail节点

  • 首先root节点的skip fail节点为NULL,则root下的孩子节点的skip fail节点均为root,如图所示的1、2、3、4号节点到root的跳转的skip fail线
  • 然后遍历1号节点,1号节点的孩子有B,同时1号节点的skip fail节点(0号节点)也有孩子为B的节点,则将1号节点的skip fail指向0号节点的孩子B即2号节点
  • 当遍历到6号节点,首先6号节点的skip fail节点是2号,6号节点有孩子B,但是2号节点没有孩子B,则继续查找6号节点的skip fail节点的skip fail 节点即root节点,发现root节点有B孩子,于是9号节点的skip fail也指向2号节点。
  • 同理可得遍历到11号节点是,指向7号节点

截取选区_003

 

代码如下:

 

单读单写无锁队列与单写多读无锁队列

2012年12月1日

无锁(lock-free)数据结构 http://blog.csdn.net/absurd/article/details/3662318

原书《系统程序员成长计划》下载 http://ishare.iask.sina.com.cn/f/21387663.html

单读单写无锁队列源码可以看facebook 开源的folly的 ProducerConsumerQueue.h