algorithm - “... WHERE word like 'ab%' order by relevace”的自定义搜索索引算法

Question

我有一个字符串和整数对数组。我想搜索字符串并按照它们对应的 int 值的顺序列出它们。

class WordClass
{
 public string Word;
 public int Relevance;
}
WordClass words[];

我想为此实现一个索引算法，但不知道使用什么算法。

在 SQL 中，它会是这样的：

SELECT word FROM table WHERE word like 'ab%' order by relevance

我已经创建了一棵 AVL 树，但我意识到一棵 AVL 树并不真正适合此目的。

该算法应该非常快。

谢谢

Answer 1

如果您想查找所有以前缀开头的单词，Trie (http://en.wikipedia.org/wiki/Trie) 是一个很好的数据结构。您可以获取所有单词，然后按相关性对其进行排序。

但是，如果您只想选择前 k 个最高相关的单词，这将不是很有效。