11

私はオートコンプリートスクリプトに取り組んでおり、トライの使用を考えていました。私の問題は、一致するすべてのものを返したいということです。たとえば、文字rを入力すると、で始まるすべてのエントリrが返されます。次に、etcで始まるすべてのエントリre。これはトライで実行可能であり、どのように機能しますか。また、もっと良い方法があれば、私は提案を受け入れます。r私が尋ねる理由は、ブランチなどからすべてのノードを返すのは複雑で、多くの処理が必要になるように思われるからです。

はい、私は車輪の再発明をしているかもしれませんが、それがどのように機能するかを学びたいと思います。

4

2 に答える 2

15

あなたは絶対にトライを使ってそれをすることができます。これが私が一緒に投げたいくつかのコードで、あなたを正しい方向に向けることができます：

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/

于 2011-02-16T22:53:17.977 に答える
0

ルートノートでアイテムを検出する時間に関して、オートコンプリートでこれを実行している場合、「一致」ごとにあまり多くの結果が返されない可能性があります。スペースと速度のトレードオフが必要な場合は、各ノードの「上位n」アイテムへの参照を保存できます。もちろん、これには更新にもっと時間がかかります

于 2011-02-17T00:07:16.490 に答える