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

StackOverflow https://stackoverflow.com/questions/618086

質問

実装するデータ構造として、しばらくの間 Ternary Search Tree を使用していましたオートコンプリートドロップダウンコンボボックス。つまり、ユーザーが「fo」と入力すると、ドロップダウンコンボボックスが表示されます

foo フード サッカー

問題は、現在使用されているTernary Search Treeで大文字と小文字が区別されることです。私の実装は次のとおりです。現実世界では約1 ++年前から使用されていました。したがって、非常に信頼できると考えています。

My Ternary Search Treeコード

ただし、大文字と小文字を区別しないTernary Search Treeを探しています。つまり、「fo」と入力すると、ドロップダウンコンボボックスに表示されます

foO フード fooTBall

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をコアバックボーンとして使用しています。

三項検索ツリーの使用例 

// 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");
役に立ちましたか？

解決

現在のTernary Search Treeで大文字と小文字を区別しない検索をサポートするのが難しい主な要因の1つは、基礎となるデータ構造が1対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。

（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（）は、大文字（＆quot; ABC＆quot;）に変換されます。 TernarySearchTreeに挿入されます。 ＆quot; ABC＆quot; TernarySearchTreeのキーと値の両方になります。

（2）＆quot; ABC＆quot; name0を配列リストに挿入するために、mapのキーとして使用します。

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

（4）＆quot; ABC＆quot; name1を配列リストに挿入するために、mapのキーとして使用します。

しようとするとき

engine.searchAll("a");

（1）TernarySearchTreeは「ABC」を返します。

（2）＆quot; ABC＆quot;マップにアクセスするためのキーとして使用されます。マップは、name0とname1を含む配列リストを返します。

このソリューションは機能します。サンプルコードは新しいTSTSearchEngineのサンプルコード

ただし、これは2つの検索パスを必要とするため、効果的なソリューションではない場合があります。 C ++に実装があることがわかりましたケースのC ++実装インセンシティブな三項検索ツリー。したがって、C ++コードをJavaに移植できる可能性があります。

他のヒント

以前にTSTを使用したことはありませんが、これは、保管中と検索中の両方で、キーを低くしたり、大文字にしたりするほど単純ではありませんか？コードスニペットから、それが機能するように見えます。

Ternary検索ツリーを実装しました。 http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html 大文字と小文字を区別しないように、smallとcapsを1つの16進数値または12進数値にマッピングするか、プレフィックスを取得しながら値を確認します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top