javascripttriepatricia-trie

what is the easy way to make suffix from this js code?


Note the code below shows the array in the console, not in the snippet output

var nodes = ["maria", "mary", "marks", "michael"];

function insert_word(split_nodes) {
  var rest = [];
  for (var i = 0; i < split_nodes.length; i++) {
    //console.log(current);
    var word = split_nodes[i];
    var letters = word.split("");
    var current = rest;
    console.log(current);
    for (var j = 0; j < letters.length; j++) {
      var character = letters[j];
      var position = current[character];
      if (position == null) {
        current = current[character] = j == letters.length - 1 ? 0 : {};
      } else {
        current = current[character];
      }
    }
  }
}
insert_word(nodes);

Above outputs this

M :{a : {r :{i :{a :0},
    k :0,   
    y :
    },
},
    i :{c :{h :{a :{e :{l :0}}}}}}}

but I want to output this :

M :{ar:{ia:0,
    k :0,   
    y :0
    },
 ichael :0
}

can anyone help me to find out this output from my code? how could i make suffeix from this code?


Solution

  • This solution take a sightly changed object structure for the end indicator with a property isWord, because the original structure does not reflect entries like 'marc' and 'marcus', because if only 'marc' is uses, a zero at the end of the tree denotes the end of the word, but it does not allowes to add a substring, because the property is a primitive and not an object.

    Basically this solution creates first a comlete tree with single letters and then joins all properties which have only one children object.

    function join(tree) {
        Object.keys(tree).forEach(key => {
            var object = tree[key],
                subKeys = Object.keys(object),
                joinedKey = key,
                found = false;    
    
            if (key === 'isWord') {
                return;
            }
            while (subKeys.length === 1 && subKeys[0] !== 'isWord') {
                joinedKey += subKeys[0];
                object = object[subKeys[0]];
                subKeys = Object.keys(object);
                found = true;
            }
            if (found) {
                delete tree[key];
                tree[joinedKey] = object;
            }
            join(tree[joinedKey]);
        });
    }
    
    var node = ["maria", "mary", "marks", "michael"],
        tree = {};
    
    node.forEach(string => [...string].reduce((t, c) => t[c] = t[c] || {}, tree).isWord = true);
    console.log(tree);
    
    join(tree);
    console.log(tree);
    .as-console-wrapper { max-height: 100% !important; top: 0; }


    A recursive single pass approach with a function for inserting a word into a tree which updates the nodes.

    It works by

    function insertWord(tree, string) {
        var keys = Object.keys(tree),
            updated = keys.some(function (k) {
                var i = 0;
    
                if (string.startsWith(k)) {
                    insertWord(tree[k], string.slice(k.length));
                    return true;
                }
                while (k[i] === string[i] && i < k.length) {
                    i++;
                }
                if (i) {
                    tree[k.slice(0, i)] = { [k.slice(i)]: tree[k], [string.slice(i)]: 0 };
                    delete tree[k];
                    return true;
                }
            });
    
        if (!updated) {            
            tree[string] = 0;
        }
    }
    
    var words = ["maria", "mary", "marks", "michael"],
        tree = {};
    
    words.forEach(insertWord.bind(null, tree));
    console.log(tree);
    
    insertWord(tree, 'mara');
    console.log(tree);
    .as-console-wrapper { max-height: 100% !important; top: 0; }