Fall unempfindlicher ternärer Suchbaum

Question

Ich hatte benutzt Ternärer Suchbaum Für eine Weile als Datenstruktur zur Implementierung eines automatischen kompletten Dropdown -Kombinationsfelds. Dies bedeutet, wenn der Benutzer "FO" typisiert ist, wird das Dropdown -Kombinationsfeld angezeigt

Foo Food Football

Das Problem ist, dass mein Strom, der von ternärer Suchbaum verwendet wird, Fall empfindlich ist. Meine Implementierung ist wie folgt. Es wurde von realer Welt für ungefähr 1 ++ genutzt. Daher betrachte ich es als ziemlich zuverlässig.

Mein ternärer Suchbaumcode

Ich suche jedoch nach einem unempfindlichen ternären Suchbaum, was bedeutet, wenn ich "fo" tippe, wird mir das Dropdown -Kombinationsfeld angezeigt

Foo Food Football

Hier sind eine wichtige Schnittstelle für TST, wo ich hoffe, dass der neue Case INSENTIVE TST auch eine ähnliche Schnittstelle hat.

    /** 
 * 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;
}

Ein Beispiel für die Nutzung ist wie folgt. TstSearchEngine verwendet Ternarysearchtree als Kern Rückgrat.

Beispiel Verwendung des ternären Suchbaums

// 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

Einer der Schlüsselfaktoren, der meinen aktuellen ternären Suchbaum schwierig macht, die Fall-Insensitive zu unterstützen, ist, dass meine zugrunde liegende Datenstruktur eins zu eins ist. Bitte sehen Sie sich den folgenden Testcode an:

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
}

Was meine aktuelle kurzfristige Lösung ist, dass ich TstSearchEngine verwende, um den gesamten Ternarysearchtree abzuschließen. TstSearchEngine besteht aus

(1) eine ternarysearchtree, die den Taste oberer Fall zur Verfügung stellt.

(2) Eine Karten Sie mit String-to-Arraylist.

Hier ist, was passiert, wenn ich auftritt:

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

(1) name0.toString () wird in obere Fälle ("ABC") konvertiert. Es wird in Ternarysearchtree eingefügt. "ABC" ist sowohl der Schlüssel als auch für Ternarysearchtree.

(2) "ABC" verwendet als Schlüssel für die Karte, um Namen0 in eine Array -Liste einzufügen.

(3) name1.toString () wird in obere Fälle ("ABC") konvertiert. Es wird in Ternarysearchtree eingefügt. S1 ist sowohl der Schlüssel als auch für Ternarysearchtree.

(4) "ABC" verwendet als Schlüssel für die Karte, um Name1 in eine Array -Liste einzufügen.

Wenn ich versuche,

engine.searchAll("a");

(1) Ternarysearchtree wird "ABC" zurückgegeben.

(2) "ABC" wird als Schlüssel zum Zugriff auf Karte verwendet. Die Karte gibt eine Array -Liste zurück, die Name0 und Name1 enthält.

Diese Lösung funktioniert. Der Beispielcode kann genannt werden Beispielcode für neue tstSearchEngine

Dies ist jedoch möglicherweise keine wirksame Lösung, da zwei Suchpassungen erforderlich sind. Ich finde heraus, dass es eine Implementierung in C ++ gibt C ++ Implementierung des unempfindlichen ternären Suchbaums von Fall. Daher besteht die Möglichkeit, dass C ++ Code auf Java portiert werden kann.

Answer 2

Ich habe noch keinen TST verwendet, aber ist das nicht so einfach wie unter oder obere Taste, sowohl während des Speichers als auch während der Suche? Von Ihrem Code -Snippet sieht es so aus, als ob das funktionieren sollte.

Answer 3

Ich habe einen ternären Suchbaum implementiert, Sie können einen Blick darauf werfen http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.htmlNach unempfindlichem Fall haben Sie entweder kleine und korrigiert einem Hex/DEC -Wert oder beim Erhalten des Präfixes den Wert.