algorithm - 在排名(排序)列表上执行前缀搜索的有效方法？

Question

我有一个很大的列表，其中包含一些按概率排序的元素:

data class Element(val value: String, val probability: Float)

val sortedElements = listOf(
    Element("dddcccdd", 0.7f),
    Element("aaaabb", 0.2f),
    Element("bbddee", 0.1f)
)

现在我需要在此列表上执行前缀搜索，以查找以一个前缀开头的项目，然后以下一个前缀开头，依此类推(元素仍然需要按概率排序)

val filteredElements1 = sortedElements
                                  .filter { it.value.startsWith("aa") }

val filteredElements2 = sortedElements
                                  .filter { it.value.startsWith("bb") }

通过某个前缀过滤的元素的每个“请求”都需要 O(n) 时间，这在大型列表的情况下太慢了。

如果我不关心元素的顺序(它们的概率)，我可以按字典顺序对元素进行排序并执行二分搜索:排序需要 O(n*log n) 时间，每个请求 -- O(log n) 时间。

有什么方法可以加快这些操作的执行速度，同时又不丢失元素的排序(概率)？也许有某种特殊的数据结构适合这个任务？

Answer 1

您可以阅读有关 Trie 数据结构的更多信息 https://en.wikipedia.org/wiki/Trie 这对您的用例来说可能非常有用。

Leetcode对此有另一个非常详细的解释，你可以在这里找到https://leetcode.com/articles/implement-trie-prefix-tree/

希望这有帮助