大文字と小文字を区別しない3値検索ツリー
-
03-07-2019 - |
質問
実装するデータ構造として、しばらくの間 Ternary Search Tree を使用していましたオートコンプリートドロップダウンコンボボックス。つまり、ユーザーが「fo」と入力すると、ドロップダウンコンボボックスが表示されます
foo フード サッカー
問題は、現在使用されているTernary Search Treeで大文字と小文字が区別されることです。私の実装は次のとおりです。現実世界では約1 ++年前から使用されていました。したがって、非常に信頼できると考えています。
ただし、大文字と小文字を区別しない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進数値にマッピングするか、プレフィックスを取得しながら値を確認します。