How can I efficiently create a suffix using this JavaScript code?

Question

How can I efficiently create a suffix using this JavaScript code?

Take note that the code displayed below showcases the array in the console, rather than in the snippet output

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

function add_suffix(names) {
  var suffixes = [];
  for (var i = 0; i < names.length; i++) {
    //console.log(current);
    var name = names[i];
    var letters = name.split("");
    var current = suffixes;
    console.log(current);
    for (var j = 0; j < letters.length; j++) {
      var letter = letters[j];
      var pos = current[letter];
      if (pos == null) {
        current = current[letter] = j == letters.length - 1 ? 0 : {};
      } else {
        current = current[letter];
      }
    }
  }
}
add_suffix(names);

The above code produces this output:

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

However, I am aiming to achieve this specific output:

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

Is there anyone who can assist me in obtaining this desired output from my code? How can I modify it to achieve the intended result?

javascript trie patricia-trie

Answer 1

Answer №1

This approach involves modifying the object structure for the end indicator by adding a property isWord. This modification is necessary because the original structure does not account for entries like 'marc' and 'marcus'. When only 'marc' is used, a zero at the end of the tree signifies the end of the word but restricts the addition of substrings due to the property being a primitive rather than an object.

Essentially, this solution first creates a complete tree with single letters and then merges all properties that have only one child 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; }

This implementation follows a recursive single pass approach using a function to insert a word into a tree and update the nodes accordingly.

The process works by:

Comparing the given string with all keys in the object. If the string starts with the current key, a recursive call is made with the remaining part of the string and the nested part of the trie.
If the strings do not start with the same characters, it examines how many characters match between the key and the string.

If a common prefix is found, a new node is created with the shared part, the old node's content, and a new node for the remaining part of the string.

Subsequently, the old node is deleted since its content is now part of the new node, and the iteration stops by returning true for the update check.
If no updates were made, a new property is assigned to the tree with the string as the key and value set to zero.

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; }

Answer 2

This approach involves modifying the object structure for the end indicator by adding a property isWord. This modification is necessary because the original structure does not account for entries like 'marc' and 'marcus'. When only 'marc' is used, a zero at the end of the tree signifies the end of the word but restricts the addition of substrings due to the property being a primitive rather than an object.

Essentially, this solution first creates a complete tree with single letters and then merges all properties that have only one child 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; }

This implementation follows a recursive single pass approach using a function to insert a word into a tree and update the nodes accordingly.

The process works by:

Comparing the given string with all keys in the object. If the string starts with the current key, a recursive call is made with the remaining part of the string and the nested part of the trie.
If the strings do not start with the same characters, it examines how many characters match between the key and the string.

If a common prefix is found, a new node is created with the shared part, the old node's content, and a new node for the remaining part of the string.

Subsequently, the old node is deleted since its content is now part of the new node, and the iteration stops by returning true for the update check.
If no updates were made, a new property is assigned to the tree with the string as the key and value set to zero.

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; }

How can I efficiently create a suffix using this JavaScript code?

Answer №1

Similar questions

Best practices for managing an array of buttons and handling click events in ReactJs

Gatsby MDX fails to locate the desired page despite displaying the title and slug

Utilize the jQuery function as a callback argument

Currently, I am compiling a list of tasks that need to be completed, but I am encountering a dilemma that is proving difficult to resolve

Combining two kebab-case CSS classes within a React component

Updating the state on a click event triggered by a MenuItem in React using Material UI

Troubleshooting: Imported Variable in Angular 2+ Throwing Module Not Found Error

Creating a collection of interconnected strings with various combinations and mixed orders

Tips for successfully sending parameters in a Google Geocoding request

Error in Vue.js: Trying to access properties of an undefined object

Fixed position not being maintained after clicking the button

Confirmation for deletion in HTML form

What is the best way to integrate a PHP page with its own CSS and JavaScript into a Wordpress page?

Accessing the return value from an ASP.NET web service in JavaScript outside of the callback function

When dragging a new connection in jsPlumb, the existing one should be automatically removed

Retrieve the script's location from the server prior to the initialization of Angular

Combining several JSON objects into a single JSON object using JavaScript

Exploring the functionality of the readline module using a simulated command-line

Generating text upon clicking by utilizing vue apex charts dataPointIndex

Is it possible to retract a message on Discord after it has been sent?