Arbre de recherche ternaire insensible à la casse

Question

J'utilise l'arbre de recherche ternaire depuis un certain temps, en tant que structure de données à implémenter. une liste déroulante complète automatique. Ce qui signifie que lorsque l'utilisateur saisit "fo", la liste déroulante affiche

foo aliments football

Le problème est que mon arbre de recherche ternaire utilisé actuellement est sensible à la casse. Ma mise en œuvre est la suivante. Il avait été utilisé par le monde réel pendant environ 1 ++ ans. Par conséquent, je le considère comme très fiable.

Code de mon arbre de recherche ternaire

Cependant, je recherche un arbre de recherche ternaire, insensible à la casse, ce qui signifie que lorsque je tape "fo", la liste déroulante me montre

foO Aliments fooTBall

Voici une interface clé pour TST. J'espère que le nouveau TST insensible à la casse aura également une interface similaire.

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

Voici un exemple d'utilisation. TSTSearchEngine utilise TernarySearchTree comme cœur de réseau.

Exemple d'utilisation de l'arbre de recherche ternaire

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

L’un des facteurs clés qui rend l’arbre de recherche ternaire actuel difficile à prendre en charge, est que la structure de données sous-jacente est un mappage un à un. Veuillez regarder le code de test suivant:

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
}

Ce que ma solution actuelle à court terme est que j'utilise TSTSearchEngine pour résumer l’ensemble de TernarySearchTree. TSTSearchEngine est composé de

(1) Un arbre TernarySearch, fournissant la clé UPPER-CASE pour mapper.

(2) Une carte String-To-ArrayList.

Voici ce qui se passe lorsque j'exécute:

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

(1) name0.toString () sera converti en UPPER-CASE ("ABC"). Il sera inséré dans TernarySearchTree. " ABC " sera à la fois la clé et la valeur de TernarySearchTree.

(2) "ABC" utilisera comme clé pour mapper, pour insérer name0 dans une liste de tableaux.

(3) name1.toString () sera converti en UPPER-CASE ("ABC"). Il sera inséré dans TernarySearchTree. S1 sera à la fois la clé et la valeur de TernarySearchTree.

(4) "ABC" utilisera comme clé pour mapper, pour insérer name1 dans une liste de tableaux.

Quand j'essaie de

engine.searchAll("a");

(1) TernarySearchTree retournera "ABC".

(2) "ABC" sera utilisé comme clé pour accéder à la carte. Map retournera une liste de tableaux contenant nom0 et nom1.

Cette solution fonctionne. L'exemple de code peut être appelé Exemple de code pour le nouveau moteur TSTSearch

Toutefois, cette solution peut ne pas être efficace, car elle nécessite deux passes de recherche. Je découvre qu'il existe une implémentation en C ++ Mise en œuvre de l'affaire par C ++ Arbre de recherche ternaire insensible . Par conséquent, le code C ++ peut être transféré vers Java.

Answer 2

Je n'ai jamais utilisé de TST auparavant, mais n'est-ce pas aussi simple que de baisser ou de mettre en majuscule vos clés, à la fois pendant le stockage et pendant la recherche? D'après votre extrait de code, il semble que cela devrait fonctionner.

Answer 3

J'ai mis en place un arbre de recherche ternaire, vous pouvez consulter http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html En cas d'insensibilité à la casse, vous mappez small et majuscules sur une valeur hexadécimale / déc, ou vérifiez le préfixe en vérifiant la valeur.