javascript 使用 trie 自动完成
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5023141/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Autocomplete using a trie
提问by qw3n
I am working on an autocompletion script and was thinking about using a trie. My problem is I want everything that matches to be returned. So for example I type in the letter rI want all entries starting with rto be returned. Then all entries starting with reetc. Is this feasible with a trie and how would it work. Also, if there is a better way I am open to suggestions. The reason I ask is it seems like it would be complicated and a whole lot of processing to return all of the nodes off of say the rbranch.
我正在编写一个自动完成脚本，并正在考虑使用特里树。我的问题是我希望返回匹配的所有内容。因此，例如，我输入字母r我希望所有以开头的条目r都被返回。然后所有以reetc开头的条目。这是否可行，以及它如何工作。另外，如果有更好的方法，我愿意接受建议。我问的原因是它似乎很复杂，而且要从r分支中返回所有节点，需要进行大量处理。
And yes I may be reinventing the wheel, but I would like to learn how it works.
是的，我可能正在重新发明轮子，但我想了解它是如何工作的。
回答by kemiller2002
You can absolutely do it using a trie. Here is some code I threw together that can point you in the right direction:
你绝对可以使用特里来做到这一点。这是我拼凑的一些代码，可以为您指明正确的方向：
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;
};
Usage
用法
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)
I'm not saying this is anywhere near the best or most efficient way, but it should at least get you pointed in the right direction.
我并不是说这是最好或最有效的方法，但它至少应该让你指向正确的方向。
Here is a jsfiddle showing it working: https://jsfiddle.net/es6xp8h9/
这是一个显示它工作的 jsfiddle：https://jsfiddle.net/es6xp8h9/
回答by dfb
Regarding the time to discover items at a root note, if you're doing this for an autocomplete, it's likely you won't be returning too many results per 'match'. If you wanted to trade off space for speed, you could store references to the 'top n' items at each of the nodes. This, of course, would require more time on update
关于在根注释中发现项目的时间，如果您这样做是为了自动完成，则每个“匹配”可能不会返回太多结果。如果您想以空间换取速度，您可以在每个节点上存储对“前 n”项的引用。当然，这需要更多时间进行更新
