Árvore de pesquisa ternária insensível ao caso

Question

Eu estava usando Árvore de pesquisa ternária Por um tempo, como a estrutura de dados para implementar uma caixa de combinação suspensa completa. O que significa que, quando o tipo de usuário "fo", a caixa de combinação suspensa será exibida

Foo Food Food Football

O problema é que minha árvore atual de pesquisa ternária é sensível ao maiúsculas de minúsculas. Minha implementação é a seguinte. Foi usado pelo mundo real por cerca de 1 ++ YEAs. Por isso, considero isso bastante confiável.

Meu código de árvore de pesquisa ternária

No entanto, estou procurando uma árvore de busca ternária insensível ao caso, o que significa que, quando eu digito "fo", a caixa combinada suspensa me mostrará

Foo Food Food Football

Aqui estão alguma interface -chave para o TST, onde espero que o novo TST Insentimento de Caso também possa ter uma interface semelhante.

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

Um exemplo de uso é o seguinte. O TSTSearchEngine está usando o TnoSearchTree como o backbone do núcleo.

Exemplo de uso da árvore de pesquisa ternária

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

Um dos principais fatores que dificultam a minha pesquisa atual de pesquisa ternária de pesquisa de caso de suporte de caso é que minha estrutura de dados subjacente é um mapeamento individual. Veja o seguinte código de teste:

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
}

Qual é a minha solução atual de curto prazo, estou usando o TSTSearchEngine para encerrar todo o ternário. TSTSearchEngine é composto por

(1) Um ternário, fornecendo a chave de caso superior para mapear.

(2) um mapa de string para arraylist.

Aqui está o que acontece quando eu me apresento:

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

(1) name0.toString () será convertido em casos superiores ("ABC"). Será inserido no ternário que pesquisou. "ABC" será essencial e o valor para o ternário que pesquisasse.

(2) "ABC" usará como chave para mapa, para inserir o nome 0 em uma lista de matrizes.

(3) name1.toString () será convertido em casos superiores ("ABC"). Será inserido no ternário que pesquisou. O S1 será chave e valor para o ternário que pesquisasse.

(4) "ABC" usará como chave para mapa, para inserir o nome1 em uma lista de matrizes.

Quando eu tento

engine.searchAll("a");

(1) TernoSearchTree retornará "ABC".

(2) "ABC" será usado como a chave para acessar o mapa. O mapa retornará uma lista de matrizes, que contém o nome 0 e o nome1.

Esta solução funciona. O código de amostra pode ser referido Código de exemplo para novo TSTSearchEngine

No entanto, essa pode não ser uma solução eficaz, pois requer dois passe de pesquisa. Eu descobri que lá é uma implementação em C ++ Implementação de C ++ da árvore de pesquisa ternária insensível. Portanto, existe uma oportunidade de que o código C ++ possa ser transportado para o Java.

Answer 2

Eu não usei um TST antes, mas isso não é tão simples quanto menor ou em maiúsculas das teclas, tanto durante o armazenamento quanto durante a pesquisa? Do seu snippet de código, parece que isso deve funcionar.

Answer 3

Eu implementei uma árvore de pesquisa ternária, você pode dar uma olhada http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternário.htmlAté o caso insensível, você mapeia pequeno e limita com um valor hexadecimal/DEC ou ao obter prefixo, verifique o valor.