字符串索引的数据结构？

我正在寻找针对范围查询和空间使用高度优化的字符串（UTF-8）索引的数据结构。谢谢！字符串索引的数据结构？

详述：我有任意长度的utf-8字符串的列表，我需要索引。我将只使用范围查询。

例如：我有字符串 - 苹果，猿，黑色，酷，黑暗。

查询会是这样的 - “获得2到倒序3元”或“获得通过‘AP’开头的字符串”

2010-10-11 Artem

你能否详细说明一下？ – casablanca 2010-10-11 05:17:08

你能详细解释一下吗？你有没有发现一个简单的'std :: set'是不可接受的慢？ – JoshD 2010-10-11 05:26:42

您的字符串是相对静态还是经常更改？ – casablanca 2010-10-11 05:30:13

既然你提到的“相对静止”，一个简单的排序数组会做你想要的一切，并在空间和时间方面进行高度优化。 “

”以desc顺序从2到3个元素获得“仅仅是查找相应的数组索引。

“获得以'ap'开头的字符串”可以通过二分查找完成。搜索将停止在或以第一个以'ap'开头的字符串之前，并且从那里开始，直到找到所有这样的字符串。

2010-10-11 05:35:31 casablanca

您是否检查Tries？

结构应该符合你的需求 - 范围和'开始'应该很容易，加上内存消耗也很好。

2010-10-11 10:28:43 Unreason

我喜欢卡萨布兰卡的答案：因为你的数据是相对静态的，排序列表应该没问题。

如果你想要更容易更新的东西，你可以使用blist.sortedlist。

你甚至可以使用ZODB的BTrees，它已经包含了许多你想要的功能（即范围搜索）。

2010-10-11 23:23:49 tzot

回答