algorithm - 用于快速搜索由给定字母组成的单词的数据结构

Question

给定一个随机字符串，我想在字典中找到仅由这些字母组成的每个单词。输入字符可以忽略，所以对于字符串“ccta”我们可以找到“act”或“cat”。

我应该如何实现数据结构来实现这个目标？

它可能只是一个纯文本文件，但这会很慢而且没有意思。我的想法是首先为给定的字符串构建一个频率图:

pub trait FreqMap {
    type Content;
    type Count;

    fn frequency_map(&self) -> BTreeMap<Self::Content, Self::Count>;
}

impl FreqMap for str {
    type Content = char;
    type Count = usize;

    fn frequency_map(&self) -> BTreeMap<char, usize> {
        let mut freqmap = BTreeMap::new();
        for c in self.chars() {
            *freqmap.entry(c).or_insert(0) += 1;
        }
        freqmap
    }
}

然后我会构建一些数据结构，这些数据结构可以被此类频率图“索引”。我可以将字典转换成这样的结构，搜索速度会非常快。

通过这样的频率图索引字典的最佳方法是什么？

Answer 1

对于字典部分，我想你可能会使用Trie数据结构。你可以了解更多here和一个很好的实现(虽然在 C 中)和教程 here .

它本质上是一个搜索树，可以存储字符串，或者更确切地说是字符串前缀，非常适合实现字典。

您可以先为字典中的单词构建 T​​ries。例如，对每个字母进行一次尝试，以便将所有以该字母开头的单词存储在一起。

对于搜索部分，一个解决方案(虽然效率有点低)可能是生成给定字符串的所有排列，并在创建的尝试中搜索它们。如果找到置换字符串的任何前缀的匹配项，也可以返回它。