radix-trie
Implementación de un radix-trie en JavaScript.
El árbol comienza en la la raíz (root
), y contiene Nodos y aristas (labels
). Los labels son el máximo prefijo común de las palabras que terminan en los nodos subyacentes.
Cada palabra nueva genera un nuevo nodo al que se puede llegar a través de uno o varios labels
. En este nodo se guarda información asociada a la palabra (puede ser de cualquier tipo), y un flag que dice si es eow
(End of Word). Con cada nueva palabra, se computa el prefijo común máximo (longest common prefix), y el nuevo nodo se ubicará debajo de este nuevo label.
API
addWord(word, data)
Agrega la palabra word
al trie, y data
como información asociada a esa palabra.
const RadixTrie = ; const trie = ;trie;trie;trie;
addMany(wordArray, data)
Agrega todas las palabras del arreglo wordArray
al trie, todas las palabras agregadas tendran data
como información asociada.
const RadixTrie = ; const trie = ;trie;
findNode('word')
Devuelve el nodo al cual nos lleva seguir los labels con la palabra word
. Retorna false
si no existe tal nodo.
const RadixTrie = ; const trie = ;trie;trie; //{// word: 'hola',// data: [{prueba: false}],//}
findData(word)
Devuelve un arreglo con los datos de todos los nodos por debajo de los labels de word
:
trie;trie;trie; trie; // [1, 2, 3]
findMany(arrayOfWords)
Devuelve la intersección de los resultados de findData
para cada palabra. Sirve para buscar por varias palabras a la vez.
trie;trie;trie; trie // 1trie // 1, 2 y 3trie // 1 y 2
autocomplete(substring)
Devuelve un arreglo de palabras que comienzen con substring
. o sea que estén debajo del nodo al que se pueda llegar siguiendo los labels del substring
.
trie;trie;trie; trie; // ['testar, 'tester']
removeWord(word, data)
Borra la data
asociada a word
, y re-acomoda el árbol cuando es necesario para que mantengas las propiedades del radix-trie.
trie;trie;trie; trie;trie; //false
To do
- Implementar Update.
- Sanitizar palabras antes de guardarlas en el árbol.
- Filtrar stop words en varios idiomas.
- Aumentar la perfomance.