gpt4 book ai didi

javascript - 使用 trie 自动完成

转载 作者:可可西里 更新时间:2023-11-01 02:36:41 25 4
gpt4 key购买 nike

我正在编写一个自动完成脚本,并且正在考虑使用 trie。我的问题是我想要返回匹配的所有内容。因此,例如,我输入字母 r 我希望返回所有以 r 开头的条目。然后是所有以 re 等开头的条目。这对 trie 来说是否可行,它是如何工作的。另外,如果有更好的方法,我愿意接受建议。我问的原因是,返回 r 分支的所有节点似乎很复杂,需要大量处理。

是的,我可能正在重新发明轮子,但我想了解它是如何工作的。

最佳答案

您完全可以使用 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/

关于javascript - 使用 trie 自动完成,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5023141/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com