¿Cómo crear un índice de prefijo simple en Java?

Question

Tengo un gran conjunto de direcciones URL y quiero implementar una autocompletación. No me gusta la complejidad del enfoque ingenuo, ya que es lineal con el tamaño del conjunto:

for(String url: urls) if(url.startsWith(input) {doSomething();} 

Ahora sé que en un hash Conjunto, la función "contiene()" obras en "O (1) "pero no hay" containsPrefix() ". ¿Hay una manera simple sin usar una gran biblioteca como Lucene o codificarla yo mismo? No tendría problemas para hacerlo, pero parece excesivo para un problema tan simple, así que quiero saber si existe una solución simple existente :-)

De mis clases de informática recuerdo un árbol que consta de fragmentos de cuerdas pero Olvidé cómo se llamaba. Funcionó así:

[car, care, carrot,carrotville]-> 

car 
| 
-/ 
-e 
-rrot 
    | 
    ----ville 

P.S .: Como llamar en los métodos que devuelve todas las cadenas que una cadena es el prefijo de? Al igual que si a es el prefijo de b, ¿qué es b a a?

Answer 1

Si usted necesita encontrar de manera eficiente prefijos de cadenas, utilice un Trie, una estructura de datos diseñada precisamente para ese propósito:

un trie, o árbol de prefijo, es una estructura de datos de árbol ordenado que se utiliza para almacenar una matriz asociativa donde las claves son generalmente cadenas. A diferencia de un árbol de búsqueda binario, ningún nodo en el árbol almacena la clave asociada con ese nodo; en cambio, su posición en el árbol define la clave con la que está asociado. Todos los descendientes de un nodo tienen un prefijo común de la cadena asociada con ese nodo, y la raíz se asocia con la cadena vacía

dos enlaces con sampleimplementations. Hace

Answer 2

Hace tiempo puse una sencilla aplicación Trie aquí:

http://code.google.com/p/triebag/source/browse/trunk/src/triebag/tries/SimpleTrie.java

Sin embargo esto no es un trie compacta, por lo que crea un nodo por carácter, creando una compacta es un poco más complicado.

Answer 3

algo Una gran alternativa es una ternary search tree (más eficiente de la memoria) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree

aquí es un trie en Java http://algs4.cs.princeton.edu/52trie/TrieST.java.html

Answer 4

java.util.regex.Pattern aplicación con la expresión regular puede manejar de manera eficiente prefijos:

StringBuilder buffer = new StringBuilder(); 
for (String prefix : prefixes) { 
    if (buffer.length() > 0) 
     buffer.append("|"); 
    buffer.append(prefix); 
} 
Pattern prefixPattern = Pattern.compile("^(" + buffer + ")"); 

puede probar todos los prefijos:

boolean containsPrefix = prefixPattern.matcher(stringToTest).find(); 

Nota: para simplificar, las cadenas de prefijos no se escapan. Caracteres Regexp [,], \, *,?, $, ^, (,), {,} Y | debe estar precedido por \.