模糊前缀搜索

Rust 中用于模糊前缀字符串搜索和自动完成的灵活字典树实现。

文档

• API 参考文档 (docs.rs)

功能

• 基于前缀的模糊搜索（Levenshtein 距离）
• 可自定义编辑距离的模糊搜索
• 每个单词可以关联多个数据
• 为搜索结果使用 Jaro-Winkler 相似度评分
• 线程安全
• 无依赖

安装

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

[dependencies]
fuzzy_prefix_search = "0.2"

用法

以下是如何使用模糊前缀搜索的快速示例

use fuzzy_prefix_search::Trie;

fn main() {
    let mut trie = Trie::new();

    // Insert words with associated data
    trie.insert("apple", 1);
    trie.insert("application", 2);
    trie.insert("appetite", 3);

    // Perform a fuzzy search
    let results = trie.search_within_distance("appl", 1);

    for result in results {
        println!("Word: {}, Data: {:?}", result.word, result.data);
    }

    // Search with similarity scoring
    let scored_results = trie.search_within_distance_scored("aple", 2);

    for result in scored_results {
        println!("Word: {}, Data: {:?}, Score: {}", result.word, result.data, result.score);
    }
}

高级用法

自定义数据类型

字典树支持任何实现了 Clone、Default、PartialEq、Eq 和 Hash 的数据类型

#[derive(Clone, Default, PartialEq, Eq, Hash)]
struct CustomData {
    id: u32,
    value: String,
}

let mut trie = Trie::new();
trie.insert("example", CustomData { id: 1, value: "Test".to_string() });

删除数据

您可以删除特定数据值的所有出现

trie.remove_all(&2);

性能

• 插入的时间复杂度为 O(k)，其中 k 是单词的长度
• 使用具有共享前缀的树结构高效存储空间
• TODO：基准测试、优化、算法选择...

注意：为了获得比 Rc/RefCell 方法快两倍的读取性能，我们在删除时使用了 不安全 的操作。

贡献

欢迎贡献！请随意提交拉取请求。

资源

• https://phiresky.github.io/levenshtein-demo/
• https://www.geeksforgeeks.org/trie-insert-and-search/
• http://stevehanov.ca/blog/?id=114
• https://murilo.wordpress.com/2011/02/01/fast-and-easy-levenshtein-distance-using-a-trie-in-c/
• https://blog.vjeux.com/2011/c/c-fuzzy-search-with-trie.html

许可证

本项目受 MIT 或 Apache 2.0 许可证的许可 - 有关详细信息，请参阅 LICENSE 文件。