字符串索引的數據結構？

Question

我正在尋找針對範圍查詢和空間使用高度優化的字符串（UTF-8）索引的數據結構。謝謝！

詳述： 我有任意長度的utf-8字符串的列表，我需要索引。我將只使用範圍查詢。

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

查詢會是這樣的 - 「獲得2到倒序3元」或「獲得通過‘AP’開頭的字符串」

Answer 1

既然你提到的「相對靜止」，一個簡單的排序數組會做你想要的一切，並在空間和時間方面進行高度優化。 「

」以desc順序從2到3個元素獲得「僅僅是查找相應的數組索引。

「獲得以'ap'開頭的字符串」可以通過二分查找完成。搜索將停止在或以第一個以'ap'開頭的字符串之前，並且從那裏開始，直到找到所有這樣的字符串。

Answer 2

您是否檢查Tries？

結構應該符合你的需求 - 範圍和'開始'應該很容易，加上內存消耗也很好。

Answer 3

我喜歡卡薩布蘭卡的答案：因爲你的數據是相對靜態的，排序列表應該沒問題。

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

你甚至可以使用ZODB的BTrees，它已經包含了許多你想要的功能（即範圍搜索）。