Caso de búsqueda ternario insensible

Question

Había estado usando Árbol de búsqueda ternaria por un tiempo, como la estructura de datos a implementar un cuadro de combo desplegable automático completo. Lo que significa que cuando el usuario escriba " fo " ;, se mostrará el cuadro combinado desplegable

foo comida futbol

El problema es que mi actual uso de Ternary Search Tree distingue entre mayúsculas y minúsculas. Mi implementación es la siguiente. Había sido usado por el mundo real por alrededor de 1 ++ yeas. Por lo tanto, lo considero bastante confiable.

Mi código de búsqueda ternaria

Sin embargo, estoy buscando un Árbol de búsqueda ternario que no distinga mayúsculas y minúsculas, lo que significa que cuando escribo " fo " ;, el cuadro desplegable desplegable me mostrará

foO Comida fooTBall

Aquí hay algunas interfaces clave para TST, donde espero que la nueva TST insensible a los casos también tenga una interfaz similar.

    /** 
 * 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 ejemplo de uso es el siguiente. TSTSearchEngine está utilizando TernarySearchTree como la red troncal central.

Ejemplo de uso del árbol de búsqueda ternario

// 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 de los factores clave que hace que mi actual árbol de búsqueda ternaria sea difícil de admitir es la búsqueda que no distingue entre mayúsculas y minúsculas es que mi estructura de datos subyacente es la asignación de uno a uno. Por favor mire el siguiente código de prueba:

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
}

Lo que mi solución actual a corto plazo es que estoy usando TSTSearchEngine para resumir todo el TernarySearchTree. TSTSearchEngine se compone de

(1) Un TernarySearchTree, que proporciona una clave de MAYÚSCULAS para el mapa.

(2) Un mapa String-To-ArrayList.

Esto es lo que sucede cuando realizo:

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

(1) name0.toString () se convertirá en MAYÚSCULAS (" ABC "). Se insertará en TernarySearchTree. " ABC " será clave y valor para TernarySearchTree.

(2) " ABC " se utilizará como clave para el mapa, para insertar name0 en una lista de matriz.

(3) name1.toString () se convertirá a MAYÚSCULAS (" ABC "). Se insertará en TernarySearchTree. S1 será clave y valor para TernarySearchTree.

(4) " ABC " se usará como clave para el mapa, para insertar nombre1 en una lista de matriz.

Cuando trato de

engine.searchAll("a");

(1) TernarySearchTree devolverá " ABC " ;.

(2) " ABC " Se utilizará como la clave para acceder al mapa. El mapa devolverá una lista de matriz, que contiene nombre0 y nombre1.

Esta solución funciona. El código de ejemplo se puede consultar en Código de ejemplo para el nuevo motor TSTSearchEngine

Sin embargo, esto puede no ser una solución efectiva, ya que requiere dos pasadas de búsqueda. Descubrí que hay una implementación en C ++ C ++ Implementación del caso Árbol de búsqueda ternario insensible . Por lo tanto, existe la oportunidad de que el código C ++ se pueda portar a Java.

Answer 2

No he usado un TST antes, pero ¿no es esto tan simple como bajar o subir las llaves, tanto durante el almacenamiento como durante la búsqueda? Desde el fragmento de código parece que debería funcionar.

Answer 3

He implementado un árbol de búsqueda ternario, puede echar un vistazo a http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html En el caso de no tener en cuenta las mayúsculas y minúsculas, asigne valores pequeños y mayúsculas a un valor de hex / dec, o al obtener un prefijo, verifique el valor.