トライ (プレフィックス ツリーとも呼ばれます) があります。接頭辞を指定して、その接頭辞で始まる10 個の単語のリストを取得したいと考えています。
この問題のユニークな点は、与えられたプレフィックスで始まる10 個の単語だけが必要であり、すべてではないということです。これを考慮して、実行できる最適化があります。
私が知っている以下の私のコードは正常に動作します。トライの各ノードには、childrenプロパティとプロパティがありthis_is_the_end_of_a_wordます。たとえば、「hi」を挿入すると、トライは次のようになります。
.
問題: 接頭辞を指定して、その接頭辞で始まる10 個の単語のリストを取得したいと考えています。
prefix問題に対する私のアプローチは次のとおりです。の最後の文字に対応するノードに到達するまで、 の文字をたどってプレフィックス ツリーを下りますprefix。ここで、このノードで DFS を実行し、リストにあるノードを追跡する必要this_is_the_end_of_a_word === trueがあります。ただし、リストの長さが 10 になったら検索を停止し、リストを返す必要があります。
私のアプローチは健全だと思いますが、特に再帰的な DFS を使用しようとしているため、実装に問題があります。そのため、再帰呼び出し間で「グローバル」リストを渡す方法がわかりません。クロージャーを使用する必要があることはわかっていますが、JavaScript は初めてで、どうすればよいかわかりません。私がすでに試したことの例を以下に示します。
私の Trie クラス (このコードが機能することはわかっています。これは、データ構造をどのように編成したかを確認できるようにするためです。)
var Trie = function() {
var that = Object.create(Trie.prototype);
that.children = {}; //mapping: next character -> child nodes
that.this_is_the_end_of_a_word = false;
that.insertWord = function(word) {
var current_node = that;
for (var i = 0; i < word.length; i++) {
var c = word[i]
//if character is not in the trie already, add it
if (!(c in current_node.children)) {
current_node.children[c] = Trie();
}
//update current_node
current_node = current_node.children[c];
};
//after adding all the chars of the word,
//you are at the end of a word
current_node.this_is_the_end_of_a_word = true;
}
that.insertWords = function(words) {
for (var i = 0; i < words.length; i++) {
that.insertWord(words[i]);
}
}
that.contains = function(word) {
//start at the root
var current_node = that;
for (var i = 0; i < word.length; i++) {
var c = word[i];
//if the word's character isn't a child of the current_node,
//the word isn't in the trie
if (!(c in current_node.children)) {
return false;
}
//move down the trie, update current_node
current_node = current_node.children[c];
};
return current_node.this_is_the_end_of_a_word;
}
Object.freeze(that);
return that;
}
私の最初のアプローチ（多くのバグがあります）
num_words_to_go = 10;
//this global is bad practice;
//I want to put this as the argument to a closure
//so it's passed between recursive calls
that.getWords = function(start_node, prefix) {
console.log(0);
var words = [];
//if start node is a word, add it
if (start_node.this_is_the_end_of_a_word) {
words.push(start_node);
num_words_to_go--;
}
if (num_words_to_go <= 0 || !start_node.children) {
return words;
}
return start_node.children.forEach(
currentValue.getWords(
currentValue, prefix + <character for this child>));
/*I can't think of a nice way to write this without going through all of the children.
I know I don't need to, because I only need to find 10 words and get out.
This is why I was leaning towards the recursive DFS.
*/
}
2番目のアプローチ：私が見ているPythonの例も見つけました：
http://v1v3kn.tumblr.com/post/18238156967/roll-your-own-autocomplete-solution-using-tries
彼の例をJavaScriptに翻訳してみました。しかし、まだ何かがうまくいかないall_suffixes。
that.all_suffixes = function (prefix){
results = [];
if (that.this_is_the_end_of_a_word) results.push(prefix);
if (!(that.children)) return results;
if (results.length > 2) return results;
var callback = function(currentValue, i, array){
return currentValue.all_suffixes(prefix+array[i]);
}
arr = that.children.forEach(callback, that);
//[child.all_suffixes(prefix + char) for (char, child) in self.children.items()]
return concat(reduce(concat, arr), results);
}
that.autocomplete = function(prefix){
current_node = that;
for(var i = 0; i < prefix.length; i++){
var c = prefix[i];
//if there is nothing in the trie with this prefix
if (!(c in current_node.children)){
return [];
}
current_node = current_node.children[c];
}
return list(current_node.all_suffixes(prefix))
}