< 返回版块

分享一个我写的radix tree，大家多指正

xcaptain 发表于 2019-03-31 10:56

radix tree是用来快速匹配字符串的一种数据结构，在很多比较快的web路由中都有应用，如chi。最初本来是想照着chi用rust实现一个自己的路由的但是chi的代码太复杂了所以我先从头开始写了这个简单版本，后续再添加更复杂的功能如正则匹配

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=04b70b7eb0e9e8aef7dedc72d07db44b

评论区

写评论
作者 xcaptain 2019-04-05 21:58

又修改了一下目前已经能支持包含正则表达式的匹配了，代码见 https://github.com/xcaptain/rust-algorithms/blob/master/data-structures/src/tree/radix_tree.rs

实现了类似

let mut t = TreeNode::new();
t.insert("/books/{[0-9]+}/comments/");
assert!(t.contains("/books/12/comments/"));

这样的功能之后距离一个可用的路由匹配算法就不远了

Mike Tang 2019-03-31 12:30

棒棒哒

1 共 2 条评论, 1 页