Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
1
$ hexo new "My New Post"
More info: Writing
1
$ hexo server
More info: Server
1
$ hexo generate
More info: Generating
1
$ hexo deploy
More info: Deployment
项目中需要使用前缀树匹配，对此进行了简单的调研和整理。
前缀树（trie），顾名思义，一般用来匹配和查找字符串的前缀。trie的键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。 trie实际上是一种DFA。输入字符串根据当前的输入的字符决定是否向下，以及去往哪个子节点。
trie树实现:一般的链表指针方式，三数组实现，双数组实现，HAT，burst trie等。
链表指针方式
HAT以及Burst trie
三数组实现
双数组实现
综上，双数组trie（Double Array trie，简称为DATrie）的实现有明显的优势，以下只讨论DATrie的细节。
数组表示trie树的状态转移，父节点跳转到子节点转化为父状态跳转到子状态
利用两个数组base, check表示状态的转移
对于状态S接收到字符c后转移到状态T
$$ S\xrightarrow{c} T $$
满足
1
2check[base[S] + c] = S
base[S] + c = T
状态更新的伪码如下
1
2
3
4
5
6
7T := base[S] + c;
if check[T] = S then
next state := T
else
fail
endif
初始状态
对于索引0，check[0]=-3代表根节点, base[0]表示偏移基地址为1，其他元素为-1表示为空
输入前缀ab
输入a
base[0]+a，由状态0跳转到状态2. check[2]为-1，说明为空，更新为父状态0；base[2]更新为跳转过来的base, 即base[0]的值1
输入b
base[2]+b，由状态2跳转到状态3，check[3]为-1，说明为空，更新为父状态2；由于字符串结束，将base[3]更新为-2，代表叶节点。
输入前缀ad
输入a
图中base和check的状态不会变化。 根据base[0]+a，从状态0跳转到2。 check[2]不为空，但check[2]的值0与其父状态S=0相等，则无需更新，进入状态2，等待输入下一个字符。这个过程相当于一个查询过程
输入d
base[2]+d，由状态2跳转到状态5，check[5]为-1，说明为空，更新为父状态2；由于字符串结束，将base[5]更新为-2，代表叶节点。
DATrie不可避免会出现冲突
输入c
状态由0跳转到状态4，check[4]空闲，将check[4]赋值为0，base[4]赋值为1.
输入a, 发生冲突
根据base[4]+4 状态从4跳转到2， 但是check[2]非空，并且check[2]=0不等于父状态4，此时发生冲突
解决冲突
挪动以4为父状态状态转移，查找对应base，check的连续的空闲空间以放入状态。这里只有最新的输入a带来的状态转移以4为父状态。base[6], check[6]有空闲。
修改base[4], 使其能够根据输入跳转到空闲空间，即base[4] = 6 - a = 5.
重新插入a. 如下图
由于业务中需要用到java，找到了一个已有java代码实现地址：https://github.com/digitalstain/DoubleArrayTrie, 但存在一些问题
根据论文An Efficient Implementation of Trie Structures， 针对上述DATrie算法还能一个tail的改进，即每个前缀的最后的结尾单独存储在一个数组里，由base里存储的值指向该tail。
例如， a 和 abcd作为前缀输入后，bcd作为一个单独的tail另外存放到一个字符串数组里。
速度 减少了base， check的状态数，以及冲突的概率，提高了插入的速度。在本地做了一个简单测试，随机插入长度1-100的随机串10w条，no tail的算法需120秒，而tail的算法只需19秒。 查询速度没有太大差别。
内存 状态数的减少的开销大于存储tail的开销，节省了内存。对于10w条线上URL，匹配12456条前缀，内存消耗9M，而no tail的大约16M
删除 能很方便的实现删除，只需将tail删除即可。
基于上述，重新实现了一个java版的前缀匹配在团队内使用。
最近由于需要Erlang与C交互，采用了linkin driver的方式。利用port_control以及driver_entry中的control回调，调用C函数。在传递复杂的数据结构，序列化和反序列化数据时遇到了一些问题，与大家分享一下。先简单介绍一下eralng driver。 首先，Erlang与外部程序交互的方式主要有两种：
另外，还有一种NIF方式，暂时没有考虑。这里我采用了linkin driver的方式。
Erlang调用driver也有两种方式：
为了方便encode和decode比较复杂的数据结构，采用ei这个库来序列化和反序列化参数。 首先，open一个port, 采用binary方式：
1
2
3
4
5
6
7
8case erl_ddll:load_driver(".", SharedLib) of
ok -> ok;
{error, alread_loaded} -> ok;
Ret ->
error_logger:error_msg("Could not load driver ~p~n", [Ret]),
exit({error, could_not_load_driver})
end,
Port = open_port({spawn, SharedLib}, [binary]).
打开port之后，就能直接用port_control来调用driver里面的函数了
1
2Resp=erlang:port_control(Port, Cmd, term_to_binary(Msg)),
io:format("recv ctl data ~p~n",[binary_to_term(Resp)]).
Port即先前打开的Port， Cmd是一个int，你可以对你的函数编号，1代表调用sum，2代表调用twice。。。最后Msg即参数，注意需要传入binary（或者字符串），返回结果Resp也是binary（或者字符串）。
对应C程序这里，需要定义一个回调函数port_ctl, 并把它添加到driver_entry里面注册，如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36ErlDrvEntry example_driver_entry = {
NULL,
example_drv_start, //driver启动时回调函数
example_drv_stop, //driver停止时回调函数
NULL,
NULL,
NULL,
"example1_drv", //driver名称
NULL,
NULL,
port_ctl, //在这里注册
NULL,
NULL,
NULL,
NULL,
NULL,
NULL
};
DRIVER_INIT(example1_drv)
{
return &example_driver_entry;
}
static ErlDrvData example_drv_start(ErlDrvPort port, char* buff)
{
example_data * d = (example_data*) driver_alloc(sizeof(example_data));
d->port = port;
set_port_control_flags(port, PORT_CONTROL_FLAG_BINARY);
return (ErlDrvData)d;
}
static void example_drv_stop(ErlDrvData handle)
{
driver_free((char*) handle);
}
Erlang调用port_control 会使得driver调用刚刚注册的port_ctl回调函数。 下面是最重要的port_ctl函数. cmd即port_control的Cmd， buf和len为接受到的函数参数数据的buffer和长度， rbuf是返回值buffer。 这里假设port_control传入Msg的参数是将一个tuple {a,b}序列化后的结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47static int port_ctl(ErlDrvData handle, unsigned int cmd, char* buf, int len,
char** rbuf, int rsize)
{
ei_x_buff x;
if(1 == cmd) { //1号命令，调用 sum(a,b)
char *p;
int i;
int arity = 0;
int version = 0;
long a, b;
int index = 0;
int res = 0;
ei_decode_version(buf, &index, &version); //必须有
ei_decode_tuple_header(buf, &index, &arity); //decode出tuple头，
//得到tuple的长度arity,这里为2
ei_decode_long(buf, &index, &a); //tuple第一个元素
ei_decode_long(buf, &index, &b); //tuple第二个元素
res = sum(a, b); //这里调用目标函数，这里是一个简单的求和
//encode返回数据阶段
ei_x_new_with_version(&x);
ei_x_encode_long(&x, res);
if(x.index > rsize){
ErlDrvBinary *ptr = driver_alloc_binary(x.index);
if(NULL == ptr)
erl_exit(1,"Out of virtual memory in malloc (%s)", __FILE__);
memcpy(ptr->orig_bytes, x.buff, x.index);
*rbuf = (char *)ptr;
} else
memcpy(*rbuf, x.buff, x.index);
ei_x_free(&x);
return x.index;
} else
if(2 == cmd) {...... }
return -1; //返回<0会导致elang：port_control抛出badarg异常
}
注意，ei_decode_version(buf, &index, &version);必须有，我在开始没有这一行时，总是无法decode成功。 后来经过阅读erlang源代码发现，传入的数据是这样序列化的：
序列化的数据都会有生成个magic number作为version， 放在第一个字节。比如一个tuple {1,2}， 假设他的version为131， tuple类型用’i'表示， 1,2属于ERL_SMALL_INTEGER_EXT，用‘a’表示该类型，则序列化后如下：
1
131 i 2 a 1 a 2
对应的131为version， i代表是一个tuple，2代表长度为2， 后面是tuple的内容，第一个a代表是一个小整数，1是这个整数的值；接着第二个a代表第二个元素为小整数，2代表这个整数值为2. 所以，必须先把version 131 decode出来，然后调用ei_decode_tuple接着解析131之后的数据才能正常。 这里，ei_decode_xxx函数中 index这个参数随着decode的调用，会指向下一个需要decode的位置。
另外，example_drv_start回调函数中set_port_control_flags(port, PORT_CONTROL_FLAG_BINARY);也必须有。
如果没有这一行, port_control返回值Reply不会是binary，而是一个list，[131, $i, 2, $a, 1, $a, 2], 这个list无法用binary_to_term还原，而且自己处理也比较麻烦。
相反，如果设置后，则会返回一个binary 《131，$i, 2, $a, 1, $a, 2》，这个格式可以用binary_to_term转化为term。相应的，如果设置PORT_CONTROL_FLAG_BINARY， 当返回缓冲区大小不够时，一定要用driver_alloc_binary来为*rbuf分配缓冲区。
如果觉得binary与term转化比较麻烦，可以考虑用erlang:port_call函数， c程序不变，只是erlang程序不需要term_to_binary以及binary_to_term.