大文字と小文字を区別しない3進数の検索ツリー

Question

私はしばらくの間、Ternary Search Treeを使用していましたが、自動完全ドロップダウンコンボボックスを実装するデータ構造体です。 「FO」ユーザータイプは、コンボボックスのドロップダウンが

fooの 食品 サッカー

問題があり、3分探索木の使用私の現在を表示するときには、大文字と小文字が区別され、意味します。私の実装は以下の通りです。現実世界では約1 + +のために使用されていた。したがって、私はそれをかなり信頼できるものと考えています。

My Ternary Search Tree code

しかし、私は意味鈍感な3分探索木、私は「FO」と入力する場合を探しています、コンボボックスのドロップダウンは私に

FOO 食品 サッカーが表示されます

ここにTSTの重要なインターフェイスがあります。新しいケースのインセンティブ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

私の現在の三項サーチツリーが大文字と小文字を区別しない検索をサポートすることを困難にする主な要因の1つは、私の基礎となるデータ構造が1対1のマッピングです。次のテストコードを見てください：私の現在の短期的な解決策は、私は全体TernarySearchTreeをラップするTSTSearchEngineを使用しています、ということである

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は、

（1）マップに大文字のキーを提供するTernarySearchTreeで構成されています。

（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（）UPPER-CASE（ "ABC"）に変換されます。 TernarySearchTreeに挿入されます。 "ABC"はTernarySearchTreeのキーと価値の両方になります。

（2） "ABC"はmapのキーとして使用し、name0を配列リストに挿入します。

（3）name1.toString（）は大文字（ "ABC"）に変換されます。 TernarySearchTreeに挿入されます。 S1はTernarySearchTreeのキーと値の両方になります。

（4）マップのキーとして "ABC"を使用して、name1を配列リストに挿入します。

Iは、（1）TernarySearchTreeは "ABC" を返します

engine.searchAll("a"); 

にしようとします。

（2）「ABC」は地図にアクセスするためのキーとして使用されます。 Mapはname0とname1を含む配列リストを返します。

この解決方法が機能します。サンプルコードは、Sample Code for New TSTSearchEngine

を参照することができますが、これは2回の検索が必要なため、有効な解決策ではない可能性があります。私はC++の実装があることを知りますC++ Implementation of Case Insensitive Ternary Search Tree。したがって、C++コードをJavaに移植できる機会があります。

Answer 2

は私が前にTSTを使用していないが、これは、貯蔵中および検索中の両方、下またはあなたの鍵を大文字化のように単純ではないのですか？コードスニペットからは、うまくいくはずです。

Answer 3

http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html 大文字小文字の区別はありませんが、小文字と小文字を1つの16進/ dec値にマッピングするか、接頭辞を取得するときに値を確認してください。