performance - significado - Construir trie mas rapido

trie significado

Question

Estoy creando una aplicación móvil que necesita miles de búsquedas rápidas de cadenas y comprobaciones de prefijos. Para acelerar esto, hice un Trie de mi lista de palabras, que tiene aproximadamente 180,000 palabras.

Todo está bien, pero el único problema es que la construcción de este enorme trie (tiene alrededor de 400,000 nodos) toma aproximadamente 10 segundos actualmente en mi teléfono, lo que es realmente lento.

Aquí está el código que construye el trie.

public SimpleTrie makeTrie(String file) throws Exception {
String line;
SimpleTrie trie = new SimpleTrie();
BufferedReader br = new BufferedReader(new FileReader(file));
while( (line = br.readLine()) != null) {
trie.insert(line);
}
br.close();
return trie;
}

El método de insert que se ejecuta en O(length of key)

public void insert(String key) {
TrieNode crawler = root;
for(int level=0 ; level < key.length() ; level++) {
int index = key.charAt(level) - ''A'';
if(crawler.children[index] == null) {
crawler.children[index] = getNode();
}
crawler = crawler.children[index];
}
crawler.valid = true;
}

Estoy buscando métodos intuitivos para construir el trie más rápido. ¿Tal vez construyo el trie solo una vez en mi computadora portátil, lo guardo de alguna manera en el disco y lo cargue desde un archivo en el teléfono? Pero no sé cómo implementar esto.

¿O hay otras estructuras de datos de prefijos que tardarán menos tiempo en construirse pero que tengan una complejidad de tiempo de búsqueda similar?

Cualquier sugerencia es apreciada. Gracias por adelantado.

EDITAR

Alguien sugirió usar la serialización de Java. Lo intenté, pero fue muy lento con este código:

public void serializeTrie(SimpleTrie trie, String file) {
try {
ObjectOutput out = new ObjectOutputStream(new BufferedOutputStream(new FileOutputStream(file)));
out.writeObject(trie);
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public SimpleTrie deserializeTrie(String file) {
try {
ObjectInput in = new ObjectInputStream(new BufferedInputStream(new FileInputStream(file)));
SimpleTrie trie = (SimpleTrie)in.readObject();
in.close();
return trie;
} catch (IOException | ClassNotFoundException e) {
e.printStackTrace();
return null;
}
}

¿Se puede hacer este código anterior más rápido?

Mi trie: http://pastebin.com/QkFisi09

Lista de palabras: http://www.isc.ro/lists/twl06.zip

El IDE de Android se utiliza para ejecutar el código: http://play.google.com/store/apps/details?id=com.jimmychen.app.sand

Answer 1

¿Es el espacio ineficiente o el tiempo ineficiente? Si está haciendo una prueba simple, entonces el espacio puede ser parte del problema cuando se trata de un dispositivo móvil. Echa un vistazo a los intentos de patricia / radix, especialmente si lo estás utilizando como una herramienta de búsqueda de prefijo.

Trie: http://en.wikipedia.org/wiki/Trie

Patricia / Radix trie: http://en.wikipedia.org/wiki/Radix_tree

No mencionó un idioma, pero aquí hay dos implementaciones de intentos de prefijo en Java.

Trie regular: http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/Trie.java

Patricia / Radix (espacio-eficiente) trie: http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java

Answer 2

Aquí hay un formato razonablemente compacto para almacenar un archivo en disco. Lo especificaré por su (eficiente) algoritmo de deserialización. Inicialice una pila cuyo contenido inicial sea el nodo raíz del trie. Lea los caracteres uno por uno e interprételos de la siguiente manera. El significado de una letra AZ es "asignar un nuevo nodo, convertirlo en un hijo de la parte superior actual de la pila, y empujar el nodo recién asignado en la pila". La letra indica en qué posición se encuentra el niño. El significado de un espacio es "establecer el indicador válido del nodo en la parte superior de la pila en verdadero". El significado de un retroceso (/ b) es "abrir la pila".

Por ejemplo, la entrada

TREE /b/bIE /b/b/bOO /b/b/b

da la lista de palabras

TREE
TRIE
TOO

. En su escritorio, construya el trie utilizando cualquier método y luego serialice mediante el siguiente algoritmo recursivo (pseudocódigo).

serialize(node):
if node is valid: put('' '')
for letter in A-Z:
if node has a child under letter:
put(letter)
serialize(child)
put(''/b'')

Answer 3

En lugar de un archivo simple, puede usar una base de datos como sqlite y un conjunto anidado o árbol celko para almacenar el trie y también puede construir un trie más rápido y más corto (menos nodos) con un trío de búsqueda ternaria.

Answer 4

Esta no es una bala mágica, pero probablemente pueda reducir su tiempo de ejecución haciendo una asignación de memoria grande en lugar de un montón de pequeños.

Vi un ~ 10% de aceleración en el código de prueba a continuación (C ++, no Java, lo siento) cuando usé un "grupo de nodos" en lugar de confiar en asignaciones individuales:

#include <string>
#include <fstream>
#define USE_NODE_POOL
#ifdef USE_NODE_POOL
struct Node;
Node *node_pool;
int node_pool_idx = 0;
#endif
struct Node {
void insert(const std::string &s) { insert_helper(s, 0); }
void insert_helper(const std::string &s, int idx) {
if (idx >= s.length()) return;
int char_idx = s[idx] - ''A'';
if (children[char_idx] == nullptr) {
#ifdef USE_NODE_POOL
children[char_idx] = &node_pool[node_pool_idx++];
#else
children[char_idx] = new Node();
#endif
}
children[char_idx]->insert_helper(s, idx + 1);
}
Node *children[26] = {};
};
int main() {
#ifdef USE_NODE_POOL
node_pool = new Node[400000];
#endif
Node n;
std::ifstream fin("TWL06.txt");
std::string word;
while (fin >> word) n.insert(word);
}

Answer 5

Los intentos de que se prealloate todos los niños posibles (256) tienen una gran cantidad de espacio desperdiciado. Estás haciendo llorar a tu caché. Almacenar esos punteros a los niños en una estructura de datos de tamaño variable.

Algunos intentos se optimizarán al tener un nodo para representar una cadena larga, y dividir esa cadena solo cuando sea necesario.

Answer 6

No me gusta la idea de direccionar nodos por índice en matriz, pero solo porque requiere una adición más (índice al puntero). Pero con el conjunto de nodos preasignados, quizás ahorre algo de tiempo en la asignación y la inicialización. Y también puede ahorrar mucho espacio reservando los primeros 26 índices para los nodos de hoja. Por lo tanto, no necesitará asignar e inicializar 180000 nodos de hoja.

También con índices, podrá leer la matriz de nodos preparada desde el disco en formato binario. Esto tiene que ser varias veces más rápido. Pero no estoy seguro de cómo hacer esto en tu idioma. ¿Esto es Java?

Si comprobó que su vocabulario de origen está ordenado, también puede ahorrar algo de tiempo al comparar algún prefijo de la cadena actual con el anterior. Ej. Primeros 4 caracteres. Si son iguales puedes comenzar tu

para (nivel int = 0; nivel <key.length (); nivel ++) {

bucle desde el 5 ° nivel.

Answer 7

Puede almacenar su trie como una matriz de nodos, con referencias a nodos secundarios reemplazados por índices de matriz. Tu nodo raíz sería el primer elemento. De esa manera, usted podría fácilmente almacenar / cargar su archivo desde un simple formato de texto o binario.

public class SimpleTrie {
public class TrieNode {
boolean valid;
int[] children;
}
private TrieNode[] nodes;
private int numberOfNodes;
private TrieNode getNode() {
TrieNode t = nodes[++numberOnNodes];
return t;
}
}

Answer 8

Solo construye una cadena grande [] y ordénala. Luego puedes usar la búsqueda binaria para encontrar la ubicación de una cadena. También puede hacer una consulta basada en prefijos sin mucho trabajo.

Ejemplo de búsqueda de prefijo:

Método de comparación:

private static int compare(String string, String prefix) {
if (prefix.length()>string.length()) return Integer.MIN_VALUE;
for (int i=0; i<prefix.length(); i++) {
char s = string.charAt(i);
char p = prefix.charAt(i);
if (s!=p) {
if (p<s) {
// prefix is before string
return -1;
}
// prefix is after string
return 1;
}
}
return 0;
}

Encuentra una ocurrencia del prefijo en la matriz y devuelve su ubicación (MIN o MAX no se encuentran)

private static int recursiveFind(String[] strings, String prefix, int start, int end) {
if (start == end) {
String lastValue = strings[start]; // start==end
if (compare(lastValue,prefix)==0)
return start; // start==end
return Integer.MAX_VALUE;
}
int low = start;
int high = end + 1; // zero indexed, so add one.
int middle = low + ((high - low) / 2);
String middleValue = strings[middle];
int comp = compare(middleValue,prefix);
if (comp == Integer.MIN_VALUE) return comp;
if (comp==0)
return middle;
if (comp>0)
return recursiveFind(strings, prefix, middle + 1, end);
return recursiveFind(strings, prefix, start, middle - 1);
}

Obtiene una matriz de cadena y un prefijo, imprime las apariciones del prefijo en la matriz

private static boolean testPrefix(String[] strings, String prefix) {
int i = recursiveFind(strings, prefix, 0, strings.length-1);
if (i==Integer.MAX_VALUE || i==Integer.MIN_VALUE) {
// not found
return false;
}
// Found an occurrence, now search up and down for other occurrences
int up = i+1;
int down = i;
while (down>=0) {
String string = strings[down];
if (compare(string,prefix)==0) {
System.out.println(string);
} else {
break;
}
down--;
}
while (up<strings.length) {
String string = strings[up];
if (compare(string,prefix)==0) {
System.out.println(string);
} else {
break;
}
up++;
}
return true;
}

Answer 9

Los intentos de doble matriz son muy rápidos para guardar / cargar porque todos los datos se almacenan en matrices lineales. También son muy rápidos de buscar, pero las inserciones pueden ser costosas. Apuesto a que hay una implementación de Java en alguna parte.

Además, si sus datos son estáticos (es decir, no los actualiza en el teléfono), considere DAFSA para su tarea. Es una de las estructuras de datos más eficientes para almacenar palabras (debe ser mejor que los intentos "estándar" y los intentos de radix para el tamaño y para la velocidad, mejor que los intentos sucintos para la velocidad, a menudo mejor que los intentos sucintos para el tamaño). Hay una buena implementación de C ++: dawgdic : puede usarla para compilar DAFSA desde la línea de comandos y luego usar un lector Java para la estructura de datos resultante (la implementación de ejemplo está here ).