tst

Rust中的三分搜索树集合，与std::collections相似的API。

三分搜索树是一种类似于前缀树（有时称为前缀树）的类型，其中节点以类似于二叉搜索树的方式排列，但最多有三个子节点，而不是二叉树的两个限制。与其他前缀树一样，三分搜索树可以作为关联映射结构使用，具有增量字符串搜索的能力。然而，与标准前缀树相比，三分搜索树在速度上有所牺牲，但更节省空间。三分搜索树常见应用包括拼写检查和自动完成。TSTMap和TSTSet结构用于类似映射和集合的使用。

文档可在http://billyevans.github.io/tst/tst找到

它具有特殊方法

• wildcard_iter/wildcard_iter_mut - 通过通配符获取迭代器
• prefix_iter/prefix_iter_mut - 通过前缀获取迭代器
• longest_prefix - 获取最长前缀

用法

将以下内容添加到您的 Cargo.toml

[dependencies]
tst = "0.10.*"

快速开始

#[macro_use]
extern crate tst;
use tst::TSTMap;

let m = tstmap! {
    "first" =>  1,
    "second" => 2,
    "firstthird" => 3,
    "firstsecond" => 12,
    "xirst" => -13,
};

// iterate
for (key, value) in m.iter() {
    println!("{}: {}", key, value);
}
assert_eq!(Some(&1), m.get("first"));
assert_eq!(5, m.len());

// calculating longest prefix
assert_eq!("firstsecond", m.longest_prefix("firstsecondthird"));

// get values with common prefix
for (key, value) in m.prefix_iter("first") {
    println!("{}: {}", key, value);
}

// get sum by wildcard iterator
assert_eq!(-12, m.wildcard_iter(".irst").fold(0, |sum, (_, val)| sum + val));

使用通配符迭代键

#[macro_use]
extern crate tst;
use tst::TSTMap;

let m = tstmap! {
    "ac" => 1,
    "bd" => 2,
    "cc" => 3,
};

for (k, v) in m.wildcard_iter(".c") {
    println!("{} -> {}", k, v);
}

使用公共前缀迭代键

#[macro_use]
extern crate tst;
use tst::TSTMap;

let m = tstmap! {
    "abc" => 1,
    "abcd" => 1,
    "abce" => 1,
    "abca" => 1,
    "zxd" => 1,
    "add" => 1,
    "abcdef" => 1,
};

for (key, value) in m.prefix_iter("abc") {
    println!("{}: {}", key, value);
}

在树中搜索最长前缀

#[macro_use]
extern crate tst;
use tst::TSTMap;

let m = tstmap! {
    "abc" => 1,
    "abcd" => 1,
    "abce" => 1,
    "abca" => 1,
    "zxd" => 1,
    "add" => 1,
    "abcdef" => 1,
};

assert_eq!("abcd", m.longest_prefix("abcde"));

实现细节

https://en.wikipedia.org/wiki/Ternary_search_tree

许可证

TST在MIT许可证的条款下分发。

有关详细信息，请参阅LICENSE-MIT和COPYRIGHT。