递归词树插入失败 - 读取对象属性失败

Question

好的，所以我正在制作一个wordTree。就像任何树一样，但包含 28 个分支“”和“-”。

我将它设置为节点作为一个名为 word 的道具，这是到达该节点的字符串路径。和 def，它要么是 null 要么是一个定义。

class wordNode{
    constructor(wordString,def){
        this.word = wordString;
        this.def= def;
        this.A=null;
        this.B=null;
        this.C=null;
        this.D=null;
        this.E=null;
        this.F=null;
        this.G=null;
        this.H=null;
        this.I=null;
        this.J=null;
        this.K=null;
        this.L=null;
        this.M=null;
        this.N=null;
        this.O=null;
        this.P=null;
        this.Q=null;
        this.R=null;
        this.S=null;
        this.T=null;
        this.U=null;
        this.V=null;
        this.W=null;
        this.X=null;
        this.Y=null;
        this.Z=null;
        this["-"]=null;
        this[" "]=null;
    }
}

是wordNode的样子...很简单...

然而，插入以我不理解的方式失败了。文字正在发生变化。

原始 => 不需要的更改

EQUIVALUE = >ELUIVALUE

油腻感 = >油腻感

SPERMATOOEN = >SAIRMATOOEN

?

class WORDTREE{
 constructor(dictionaryArray){
        this.root = new wordNode("",null);
        dictionaryArray.forEach(entry=>{
            console.log(entry.word,"WORD");
            this.insert(entry);
        });
    }
    insert(wordObject){
        const wordStringArray = wordObject.word.split("");
        const targetLetter = wordStringArray[0];
        this.__insert(targetLetter, wordStringArray, this.root, wordObject,"");
    }
    __insert(letter,array, ref, word){
        const wordString =array.join("");
        const nextArray = wordString.split("");
        const nextLetter = array[0];
        nextArray.shift();
        if(ref[letter]==null){
            console.log(ref.word+nextLetter, ref.word, nextLetter, "a = b+c here?");
            ref[letter]=new wordNode(ref.word+nextLetter, (ref.word+nextLetter)==word.word?word.def:null);
        }
        const nextRef = ref[letter];
        if(nextArray.length>0){
            this.__insert(nextLetter,nextArray,nextRef,word);
        }
        else{
            console.log(nextRef.word);
            console.log("inserted at?");
            console.log(nextRef);
        }
        
    }
}

我从中生成的 dictionaryArrayObject 的结构类似于

[{word:"",def:""},{...}...]

我认为 ref[letter] = new wordNode() 在特定条件下会失败？

Answer 1

经过一些测试，@raina77ow 是正确的，在它是根的情况下，引用没有被正确处理。以下是更正后的插入函数。

   insert(word){
       const wordArray = word.word.split("").map(x=>x.toUpperCase());
       
        this.__insert(word,wordArray,this.root);
   }
   __insert(wordObject,charArray,refNode){
       if(charArray.length>0){
            const nextRef = refNode[charArray[0]]|| new WordNode(refNode.word+charArray[0], null);
            !refNode[charArray[0]]?refNode[charArray[0]]=nextRef:null;
            charArray.shift();
            this.__insert(wordObject,charArray,nextRef);
        }
        else
            {
            refNode.__setDef(wordObject.definition);
        }  
   }

Answer 2

我想知道使用更简单的数据结构是否会更好。我们可以拥有相同的基本 trie 结构，仅包括实际使用的字母，并在叶节点处使用特殊值来保存定义。像这样：

const dict = [
  {word: 'foo', def: 'foo def'},
  {word: 'fob', def: 'fob def'},
  {word: 'foolish', def: 'foolish def'},
  {word: 'bard', def: 'bard def'},
  {word: 'barstool', def: 'barstool def'},
  {word: 'bar', def: 'bar def'}
]

const tree = wordTree (dict)

//=> 
// {
//     b: {a: {r: {
//         $: 'bar def',
//         d: {$: 'bard def'},
//         s: {t: {o: {o: {l: {$: 'barstool def'}}}}}
//     }}},
//     f: {o: {
//             b: {$: 'fob def'},
//             o: {
//                 $: 'foo def',
//                 l: {i: {s: {h: {$: 'foolish def'}}}
//             }
//     }}
// }

我们可以使用相当标准的递归技术来构建它，使用普通对象作为我们的数据，使用相关字母的键，以及代表定义的键 '$'。

以下是纯函数，用于从 {word, def} 个元素 (wordTree) 的数组创建树，通过向现有树中插入一个词来创建新树 (insertWord), 列出树中的所有单词 (listWords), 或者获取列表中单词的定义, 如果不包含则返回 undefined (getWord).

const wordTree = (words) => 
  words .reduce (insertWord, {}) 

const insertWord = (tree, {def, word: [letter, ...letters]}) => 
  letter
    ? {...tree, [letter]: insertWord (tree [letter] || {}, {def, word: letters})}
    : {...tree, $: def}

const listWords = (tree, prefix = '', {$, ...children} = tree) =>
  [
    ... ($ ? [prefix] : []), 
    ... Object .keys (children) .sort () .flatMap (c => listWords (tree [c], prefix + c))
  ]

const getWord = (tree, [letter, ...letters]) =>
  letter
    ? letter in tree && getWord (tree [letter], letters)
  : '$' in tree 
    ? tree ['$'] 
  : undefined

const dict = [
  {word: 'foo', def: 'foo def'},
  {word: 'fob', def: 'fob def'},
  {word: 'foolish', def: 'foolish def'},
  {word: 'bard', def: 'bard def'},
  {word: 'barstool', def: 'barstool def'},
  {word: 'bar', def: 'bar def'}
]

const tree = wordTree (dict)
console .log (getWord (tree, 'barstool'))
console .log (listWords (tree))
console .log (tree)

.as-console-wrapper {max-height: 100% !important; top: 0}

如果我们也想要一个 deleteWord 函数，一个简单的原始版本可能就足够了，使用一个帮助程序来克隆一个删除特定键的对象：

const omitKey = (key, obj) =>
  Object .fromEntries (Object .entries (obj) .filter (([k, v]) => k !== key))

const deleteWord = (tree, [letter, ...letters]) =>
  letter
    ? letter in tree ? {...tree, [letter]: deleteWord (tree [letter], letters)} : tree
    : omitKey ('$', tree)

这会留下一些碎屑。它可能没有害处，但是如果我们从上面的列表中删除 'foolish'，生成的结构将包括 l: {i: {s: {h: {}}}，现在不需要了：

// ...
    f: {o: {
            b: {$: 'fob def'},
            o: {
                $: 'foo def',
                l: {i: {s: {h: {}}}
            }
    }}
// ...

据我所知，它没有害处，但感觉不太干净。另一方面，这确实很好地清理了所有内容，但可能会以显着的性能成本为代价：

const deleteWord = (tree, targetWord) =>
  wordTree (
    listWords (tree)
      .filter (word => word !== targetWord)
      .map (word => ({word, def: getWord (tree, word)}))
  )

我相信只要稍加思考，我们就能写出更优雅的东西。

无论如何，这只是一个建议的替代方案。我发现它比您的 constructor-based、pre-allocated 版本简单得多。但是，一如既往，YMMV.

更新

那个 delete 困扰着我。我不得不想出更好的办法。我喜欢这个版本：

const deleteWord = (tree, [letter, ...letters], child) => 
  letter 
    ? (child = deleteWord (tree [letter], letters)) && 
      Object .keys (child) .length == 0
        ? omitKey (letter, tree)
        : {...tree, [letter]: child}
    : omitKey ('$', tree)

我可能有点迷恋 expression-only 编码，如果那个版本因为奇怪的 && 而不清楚（也可以用逗号表达式来完成）并重写child 参数，那么我们可以选择这个等效参数：

const deleteWord = (tree, [letter, ...letters]) => {
  if (!letter) {
    return omitKey ('$', tree)
  }
  const child = deleteWord (tree [letter], letters)
  return Object .keys (child) .length == 0
    ? omitKey (letter, tree)
    : {...tree, [letter]: child}
}

无论哪种方式，这对我来说都是正确的特征。它会自行清理，不会吹走整棵树来完成它的工作。

虽然我在这里，但我对 wordTree 工厂功能非常满意。它优雅且性能合理，但我只想指出一个更符合代码其余部分的替代方案：

const wordTree = ([word, ...words], tree = {}) =>
  word
    ? wordTree (words, insertWord (tree, word))
    : tree

我实际上不会推荐这个。除非并且直到 tail-call 优化成为常态，否则这将运行迅速变成 recursion-depth 问题。但很高兴看到它与其余的递归代码一起出现。

递归词树插入失败 - 读取对象属性失败

recursive word tree insertion fails -reading object properties is failing

javascript

recursion

tree

insertion

更新