从此js代码制作后缀的简单方法是什么？

Question

请注意，下面的代码显示了控制台中的数组，而不是片段输出中的数组

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

以上输出这个

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

但我想输出这个：

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

谁能帮我从我的代码中找出这个输出？我怎样才能用这段代码制作后缀？

Answer 1

此解决方案对带有属性 isWord 的结束指示器进行了轻微更改的对象结构，因为原始结构不反映 'marc' 和 'marcus' 等条目, 因为如果只使用 'marc' ，树末尾的零表示单词的末尾，但它不允许添加子字符串，因为属性是原始的而不是对象。

基本上，此解决方案首先创建一个包含单个字母的完整树，然后连接所有只有一个子对象的属性。

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

一种递归单遍方法，具有将单词插入更新节点的树的功能。

它的工作原理是

检查给定的 string 与对象的所有键，如果 string 以实际键开始，则递归调用部分字符串和嵌套部分特里树已创建。
否则，它检查键和字符串中有多少字符相同。

然后它检查计数器并创建一个具有公共部分和两个节点的新节点，旧节点内容和字符串的新节点。

由于新节点的存在，旧节点不再是必需的并被删除，并且迭代通过返回 true 以进行 update 检查而停止。
如果没有发生更新，将分配一个新的属性，其中字符串作为键，零作为值。

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

从此js代码制作后缀的简单方法是什么？

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

javascript

trie

patricia-trie