javascript - 如何用 JavaScript 构建一棵基数树？

Question

受到 iOS7 iMessage 的下一个单词预测的启发，我决定尝试编写一个脚本，该脚本将根据用户输入来学习哪些单词/字母最有可能想要完成用户当前的单词，或者哪些单词可能会完成接下来很可能是需要的。

为此，我将使用与 Radix Tree 非常相似的数据结构。 (又名帕特里夏·特里)。

以此用户输入为例:

I like icecream

由此，我的目标是生成以下数据结构:

var speakData = {
    "I": { //the key
        value: "I", //the stored value for this unit of the combination
        count: 1, //the number of times that this combination has occured
        followables: { // the next level of the tree; all combinations 
                       // that might follow this one
            " ": {
                value: " ",
                count: 1,
                followables: {
                    "l": {
                        value: "l",
                        count: 1,
                        followables: {
                            "i": {
                                value: "i",
                                count: 1,
                                followables: {
                                    "k": {
                                        value: "k",
                                        count: 1,
                                        followables: {
                                            "e": {
                                                value: "e",
                                                count: 1,
                                                followables: {
                                                    // and so on 
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

这本质上是一个基数树，带有一些额外的信息，使我能够权衡用户接下来可能想要输入的已学习可能性的概率。

从上述极其有限的数据集中，当用户键入“I”时，我们最好的(也是唯一的)猜测是下一个字符将是“”。

现在我已经解释了我的目标和方法，这是我的问题:

如何根据任何给定的用户输入构建此数据结构？

function learn(message, brain){
    for(var i = 0; i < message.length; i++){
        brain[message[i]] = {};
        brain[message[i]].value = message[i];
        brain[message[i]].count++;
        brain[message[i]].followables = 
    }
}

据我所知，但我不确定如何递归地在正确的位置插入下一个值。

Answer 1

只需创建一个简单的递归函数，如下所示:

function learn(message, brain){
  if(message.length == 0) return {}; // or do something else
  var ch = message[0]; // get the first character
  if(!brain[ch]) { // create new node when not exists
    brain[ch] = {value:ch,count:1,followables:{}};
  } else { // increment count when exist
    brain[ch].count += 1;
  }
  var substr = message.substring(1); // remove first character
  if(substr) { // do it for the remaining substring
    brain[ch].followables = learn(substr,brain[ch].followables)
  }
  return brain;
}

当然你也可以让它迭代，而不是递归。

// test code:
var brain = {};
brain = learn('test',brain);
brain = learn('testing',brain);
brain = learn('tes',brain);
brain = learn('yay',brain);
console.log(JSON.stringify(brain, null, 2));

会输出类似这样的内容:

{
  "t": {
    "value": "t",
    "count": 3,
    "followables": {
      "e": {
        "value": "e",
        "count": 3,
        "followables": {
          "s": {
            "value": "s",
            "count": 3,
            "followables": {
              "t": {
                "value": "t",
                "count": 2,
                "followables": {
                  "i": {
                    "value": "i",
                    "count": 1,
                    "followables": {
                      "n": {
                        "value": "n",
                        "count": 1,
                        "followables": {
                          "g": {
                            "value": "g",
                            "count": 1,
                            "followables": {}
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  },
  "y": {
    "value": "y",
    "count": 1,
    "followables": {
      "a": {
        "value": "a",
        "count": 1,
        "followables": {
          "y": {
            "value": "y",
            "count": 1,
            "followables": {}
          }
        }
      }
    }
  }
}