我正在研究自动完成脚本,正在考虑使用特里。我的问题是我希望所有匹配的东西都被退回。因此,例如,我输入字母r,希望r返回所有以开头的条目。然后所有条目均以reetc 开头。使用trie可行吗?它如何工作?另外,如果有更好的方法,我也欢迎提出建议。我问的原因是,看来要从r分支返回所有节点会很复杂并且要进行大量处理。
r
re
是的,我可能正在重新发明轮子,但是我想学习它是如何工作的。
您完全可以使用trie做到这一点。这是我整理的一些代码,可以为您指明正确的方向:
var tokenTree = function (tokenArray) { var createLetterObject = function (l) { var pChildren = []; var getMatchingWords = function (characterArr, availableWords, children) { if (characterArr.length === 0) { for (var child in children) { if ({}.hasOwnProperty.call(children, child)) { var currentChild = children[child]; var words = currentChild.getWords(characterArr); for (var pos in words) { if ({}.hasOwnProperty.call(words, pos)) { availableWords.push(words[pos]); } } if (currentChild.word) { availableWords.push(currentChild.word); } } } } else { var currentCharacter = characterArr.pop(); getMatchingWords(characterArr, availableWords, children[currentCharacter].children); } }; function doGetWords(wordPart) { var len = wordPart.length; var ar = []; var wordList = []; for (var ii = len - 1; ii >= 0; ii --) { ar.push(wordPart[ii].toUpperCase()); } getMatchingWords(ar, wordList, pChildren); return wordList; } return { letter: l, children: pChildren, parent: null, word: null, getWords: doGetWords }; }; var startingPoint = createLetterObject(); function parseWord(wordCharacterArray, parent, fullWord) { if (wordCharacterArray.length === 0) { parent.word = fullWord; return; } var currentCharacter = wordCharacterArray.pop().toUpperCase(); if (!parent.children[currentCharacter]) { parent.children[currentCharacter] = createLetterObject(currentCharacter); } parseWord(wordCharacterArray, parent.children[currentCharacter], fullWord); } for (var counter in tokenArray) { if ({}.hasOwnProperty.call(tokenArray, counter)) { var word = tokenArray[counter]; if (!word) { continue; } var ar = []; var wordLength = word.length; for (var ii = wordLength - 1; ii >= 0; ii--) { ar.push(word[ii]); } parseWord(ar, startingPoint, word); } } return startingPoint; };
var tokens = ["Token", "words", "whohaa", "mommy", "test", "wicked"]; var tree = tokenTree(tokens); var currentTokenSet = 'w'; var list = tree.getWords(currentTokenSet); // it will return words,whohaa,wicked. console.log(list)
我并不是说这是最好或最有效的方法,但这至少应该使您指出正确的方向。
这是一个显示其工作原理的jsfiddle:https ://jsfiddle.net/es6xp8h9/