Автозаполнение с помощью дерева

Question

Я работаю над сценарием автозаполнения и думал об использовании trie.Моя проблема в том, что я хочу вернуть все, что соответствует.Так, например, я набираю букву r Я хочу, чтобы все записи, начиная с r, были возвращены.Затем все записи, начинающиеся с re и т. Д. Возможно ли это с помощью дерева и как это будет работать?Кроме того, если есть лучший способ, я открыт для предложений.Причина, по которой я спрашиваю, состоит в том, что кажется сложным и требует много обработки, чтобы вернуть все узлы, скажем, из ветви r.

И да, возможно, я изобретаю колесо, нохотел бы узнать, как это работает.

Answer 1

Вы можете сделать это с помощью 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/

Answer 2

Что касается времени обнаружения элементов в корневой заметке, если вы делаете это для автозаполнения, скорее всего, вы не будете возвращать слишком много результатов за «совпадение». Если вы хотите обменять пространство на скорость, вы можете хранить ссылки на элементы 'top n' на каждом из узлов. Это, конечно, потребует больше времени на обновление