大小寫不敏感的三元搜索樹

Question

我一直在使用Ternary Search Tree一段時間，作爲實現自動完成下拉組合框的數據結構。這意味着，當用戶鍵入「FO」，下拉組合框中將顯示

富 食品 足球

的問題是，我現在的三元搜索樹的使用是區分大小寫的。我的實現如下。它已被現實世界用於大約1 ++年。因此，我認爲這是相當可靠的。

My Ternary Search Tree code

不過，我要尋找一個區分大小寫的三元搜索樹，這意味着，當我輸入「FO」，下拉組合框中會顯示我

富 食品 足球

以下是TST的一些關鍵接口，我希望新的情況下可能會有類似的界面。

/** 
* Stores value in the TernarySearchTree. The value may be retrieved using key. 
* @param key A string that indexes the object to be stored. 
* @param value The object to be stored in the tree. 
*/  
public void put(String key, E value) { 
    getOrCreateNode(key).data = value; 
} 

/** 
* Retrieve the object indexed by key. 
* @param key A String index. 
* @return Object The object retrieved from the TernarySearchTree. 
*/ 
public E get(String key) { 
    TSTNode<E> node = getNode(key); 
    if(node==null) return null; 
    return node.data; 
} 

使用示例如下。 TSTSearchEngine使用TernarySearchTree作爲核心主幹。

Example usage of Ternary Search Tree

// There is stock named microsoft and MICROChip inside stocks ArrayList. 
TSTSearchEngine<Stock> engine = TSTSearchEngine<Stock>(stocks); 
// I wish it would return microsoft and MICROCHIP. Currently, it just return microsoft. 
List<Stock> results = engine.searchAll("micro"); 

Answer 1

使我當前的三元搜索樹難以支持不區分大小寫搜索的關鍵因素之一是，我的基礎數據結構是一對一映射。請看下面的測試代碼：

public void testPut() { 
    System.out.println("put"); 
    Name name0 = new Name("abc"); 
    Name name1 = new Name("abc"); 
    TernarySearchTree<Name> instance = new TernarySearchTree<Name>(); 
    instance.put(name0.toString(), name0); 
    instance.put(name1.toString(), name1); 
    assertEquals(2, instance.matchPrefix("a").size()); // fail here. Result is 1 
} 

什麼我目前短期的解決方案是，我使用TSTSearchEngine包裹了整個TernarySearchTree。 TSTSearchEngine包含

（1）一個TernarySearchTree，提供UPPER-CASE鍵映射。

（2）一個String-To-ArrayList映射。

下面是當我執行什麼發生：

TSTSearchEngine<Name> engine = TSTSearchEngine<Name>(); 
engine.put(name0); // name0 is new Name("Abc"); 
engine.put(name1); // name0 is new Name("aBc"); 

（1）name0.toString（）將被轉換爲大寫（ 「ABC」）。它將被插入TernarySearchTree。 「ABC」將成爲TernarySearchTree的關鍵和價值。 （2）「ABC」將用作map的關鍵字，將name0插入到數組列表中。

（3）name1.toString（）將被轉換爲UPPER-CASE（「ABC」）。它將被插入TernarySearchTree。 S1將是TernarySearchTree的關鍵和價值。

（4）「ABC」將用作map的關鍵字，以將name1插入到數組列表中。

當我嘗試

engine.searchAll("a"); 

（1）TernarySearchTree將返回 「ABC」。

（2）「ABC」將被用作訪問地圖的關鍵。 Map將返回一個數組列表，其中包含name0和name1。

此解決方案有效。示例代碼可以參考Sample Code for New TSTSearchEngine

但是，這可能不是一個有效的解決方案，因爲它需要兩次搜索傳遞。我發現在C++ C++ Implementation of Case Insensitive Ternary Search Tree中有一個實現。因此，C++代碼有可能被移植到Java上。

Answer 2

我以前沒有使用過一個TST，而不是這樣簡單低於或uppercasing你的鑰匙，無論是在存儲和查詢過程中？從你的代碼片段看起來應該可以工作。

Answer 3

我已經實現了一個三元搜索樹，你可以看看http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html 作爲案例insensative的，無論是你的小戴帽映射到一個十六進制/十進制值或同時獲得前綴，檢查值。