什么数据结构最适合对字符串集合进行快速查找和提高内存效率？

Question

在我的程序中，我有一个巨大的字符串列表（不重复），它们与一个词交叉。我想检查这个词是否有效——它的有效性是基于它在列表中的存在。我正在运行检查许多不同的词，所以速度是我最关心的问题，还有列表存储的内存效率。

所以我的问题是，什么数据结构最适合字符串集合的快速查找和内存效率？

我目前正在使用 BTreeSet，因为它是有序的，我认为它可以加快搜索速度。此外，由于单词可能非常相似（“apple”和“app”），我假设基于树的数据结构通过 Vec 存储它们的内存效率更高。

Answer 1

如果您需要精确匹配，那么您应该使用 HashSet。它应该比 BTreeSet.

更快更有效

但是如果您需要更复杂的search/match功能，例如按公共前缀搜索、区分大小写和不区分大小写的搜索、大量带有大公共前缀的单词等，那么 hashmap 将不会是很合身。

在这种情况下，您可以使用 trie，也称为 prefix tree。它逐个字符地存储单词，从而“压缩”公共前缀，如果您搜索许多以公共前缀开头的单词，这也提供了显着的加速。

一个非常基本的实现只是散列映射的包装器：

struct Node {
    ptr: HashMap<u8, Node>,

    // you can also use a boolean to mark the end of word, but then you would need additional code to rebuild it from the bytes 
    word: Option<String>,
}

您可以通过递归地将下一个单词字符添加到树中或使用更高效的迭代方法来将单词添加到树中：

   pub fn insert(&mut self, word: String) {
        let w = word.as_bytes();

        let mut node = self;
        for ch in w.iter().copied() {
            node = node.ptr.entry(ch).or_default()
        }

        // attach the word
        node.word = Some(word);
    }

基本搜索也很简单：

    fn find(&self, word: String) -> Option<String> {
        let word = word.as_bytes()
        let mut node = self;

        for ch in word.iter() {
            match node.ptr.get(ch) {
                Some(link) => node = link,
                None => return None,
            }
        }

        node.word.clone()
    }

但是如果你想利用“同时”搜索任何带前缀的单词，你应该利用像这样的递归结构 leetcode problem

还有一些实施注意事项：

使用更快的散列函数，因为我们只对单个字节进行散列，而 Rust 中的默认散列函数非常慢
您可以在找到 trie 之后“soft-remove”个节点，以加快后续搜索。

您可以在提供的 github link

中找到此类示例

什么数据结构最适合对字符串集合进行快速查找和提高内存效率？

What is the data structure best fit for fast lookup and memory efficiency on a collection of Strings?

string

algorithm

optimization

rust

data-structures