Albero di ricerca ternaria insensibile al maiuscolo / minuscolo

Question

Ho usato Ternary Search Tree come struttura dei dati da implementare una casella combinata a discesa con completamento automatico. Ciò significa che, quando l'utente digita " fo " ;, verrà visualizzata la casella combinata a discesa

foo cibo calcio

Il problema è che il mio attuale utilizzo dell'albero della ricerca ternaria fa distinzione tra maiuscole e minuscole. La mia implementazione è la seguente. Era stato usato dal mondo reale per circa 1 ++ sì. Quindi, lo considero abbastanza affidabile.

Il mio codice dell'albero della ricerca ternaria

Tuttavia, sto cercando un albero di ricerca ternario senza distinzione tra maiuscole e minuscole, il che significa che quando scrivo "fo", la casella combinata a discesa mi mostrerà

foo Cibo CALCIO

Ecco alcune interfacce chiave per TST, in cui spero che anche il nuovo TST insensibile al caso possa avere un'interfaccia simile.

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

Un esempio di utilizzo è il seguente. TSTSearchEngine utilizza TernarySearchTree come backbone principale.

Esempio di utilizzo dell'albero di ricerca ternaria

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

Uno dei fattori chiave che rende il mio attuale albero di ricerca ternaria difficile da supportare la ricerca senza distinzione tra maiuscole e minuscole è che la mia struttura di dati sottostante è il mapping uno a uno. Si prega di guardare il seguente codice di prova:

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
}

Quale sia la mia attuale soluzione a breve termine, sto usando TSTSearchEngine per concludere l'intero TernarySearchTree. TSTSearchEngine è composto da

(1) Un TernarySearchTree, che fornisce la chiave MAIUSCOLA per mappare.
(2) Una mappa String-To-ArrayList.

Ecco cosa succede quando mi esibisco:

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

(1) name0.toString () verrà convertito in MAIUSCOLO ("ABC"). Sarà inserito in TernarySearchTree. & Quot; ABC " sarà chiave e valore per TernarySearchTree.
(2) "ABC" userà come chiave per la mappa, per inserire name0 in un elenco di array.
(3) name1.toString () verrà convertito in MAIUSCOLO ("ABC"). Sarà inserito in TernarySearchTree. S1 sarà sia chiave che valore per TernarySearchTree.
(4) "ABC" utilizzerà come chiave per la mappa, per inserire nome1 in un elenco di array.

Quando provo a

engine.searchAll("a");

(1) TernarySearchTree restituirà " ABC " ;.
(2) "ABC" verrà utilizzato come chiave per accedere alla mappa. Mappa restituirà un elenco di array, che contiene name0 e name1.

Questa soluzione funziona. È possibile fare riferimento al codice di esempio Codice di esempio per il nuovo TSTSearchEngine

Tuttavia, questa potrebbe non essere una soluzione efficace, poiché richiede due passaggi di ricerca. Scopro che esiste un'implementazione in C ++ C ++ Implementation of Case Albero di ricerca ternario insensibile . Pertanto, esiste la possibilità che il codice C ++ possa essere trasferito su Java.

Answer 2

Non ho mai usato un TST prima, ma non è così semplice come abbassare o maiuscole le tue chiavi, sia durante la memorizzazione che durante la ricerca? Dal tuo frammento di codice sembra che dovrebbe funzionare.

Answer 3

Ho implementato un albero di ricerca ternario, puoi dare un'occhiata a http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html A partire dalla distinzione tra maiuscole e minuscole, o si associa small e maiusc a un valore esadecimale / dec o mentre si ottiene il prefisso, controllare il valore.