爲二進制搜索預處理一組常量字符串

Question

我有幾個字符串的排序列表（大小= K < 1000）。我需要在排序列表中查找數十億（大小= N）字符串的插入位置。該列表保持不變，並將字符串插入到子節點中。

現在的問題是：我目前使用二進制搜索，其時間成本是O（strlen * NlogK）。但是，因爲排序的列表是恆定的。我想知道在小排序列表上是否有預處理方法使搜索比logK更快？

Answer 1

一些很好的替代品包括Trie，或perfect hash table（可能爲Patricia trie或ternary search tree實現）。

編輯：要找到「插入位置」使用一個trie的非匹配字符串，首先標記每個完整的字符串與它的位置（當你最初建立trie時，你可以做到這一點）。當搜索不匹配的字符串時，您會在不匹配的字符串中的第一個索引處檢測到該字符串。

例如，假設您在包含CAN NOT和CATASTROPHE的trie中查找字符串CAR（並且沒有其他相關內容）。您會在R處檢測到這種不匹配，因爲R不在A以下。但是，應該很容易知道該位置的周圍字母是N和T.前往N然後繼續向下並向右會把你帶到不能去的地方。或者，去T，然後繼續往下走，會帶給你災難。

Answer 2

除了Chris Okasaki，我建議你計算每個樹節點（trie或patricia）在相應子樹中的樹葉數量（你可以用深度優先遍歷來做到這一點）。

爲了與你走在樹和葉子的數量之和（即預先計算），你在離開子樹被從當前位置留下了一個字符串的查詢。當你在位置停下來時，如果不與查詢字符串發生衝突，就不能繼續樹形路徑，這意味着你可以找到這個字符串的位置。指數是用總和計算的所有留下的葉子的數量。