Nimble Pirate Monitor

    radix-trie

    1.0.8 • Public • Published

    radix-trie

    Implementación de un radix-trie en JavaScript.

    Trie

    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 = require('radix-trie');
     
    const trie = new RadixTrie();
    trie.addWord('hola'. 1);
    trie.addWord('chao'. 'data');
    trie.addWord('chos'. { ejemplo: true});

    addMany(wordArray, data)

    Agrega todas las palabras del arreglo wordArray al trie, todas las palabras agregadas tendran data como información asociada.

    const RadixTrie = require('radix-trie');
     
    const trie = new RadixTrie();
    trie.addMany(['hola', 'chao', 'chos'], {prueba: false});

    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 = require('radix-trie');
     
    const trie = new RadixTrie();
    trie.addMany(['hola', 'chao', 'chos'], {prueba: false});
    trie.findNode('hola'); 
    //{
    //  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.addWord('test', 1);
    trie.addWord('testar', 2);
    trie.addWord('tester', 3);
     
    trie.findData('test'); // [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.addMany(['hola', 'test'], 1);
    trie.addMany(['hola', 'teresa'], 2);
    trie.addMany(['chao', 'trozo'], 3);
     
    trie.findMany(['test', 'hola']) // 1
    trie.findMany(['t']) // 1, 2 y 3
    trie.findMany(['h', 't']) // 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.addWord('hola', 1);
    trie.addWord('testar', 2);
    trie.addWord('tester', 3);
     
    trie.autocomplete('test'); // ['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.addWord('ho', 'ho');
    trie.addWord('hola', 'hola');
    trie.addWord('holo', 'holo');
     
    trie.removeWord('hola', 'hola');
    trie.findWord('hola', 'hola'); //false

    To do

    • Implementar Update.
    • Sanitizar palabras antes de guardarlas en el árbol.
    • Filtrar stop words en varios idiomas.
    • Aumentar la perfomance.

    Install

    npm i radix-trie

    DownloadsWeekly Downloads

    0

    Version

    1.0.8

    License

    MIT

    Last publish

    Collaborators

    • atralice
    • facuvelasco
    • guilleasz
    • mjlescano
    • msalomon
    • plataforma5
    • solanoepalacio