Как построить Radix Tree в JavaScript?

Question

Вдохновленный предсказанием следующего слова iOS7 iMessage, я решил попытаться написать скрипт, который на основе пользовательского ввода узнает, какие слова / буквы, скорее всего, хотят завершить текущее слово пользователя или какое слово, скорее всего, может быть желаемый следующий.

Для этого я собираюсь использовать структуру данных, очень похожую на Radix Tree (AKA a Patricia Trie).

Возьмем этот пользовательский ввод, например:

Я люблю мороженое

Исходя из этого, моя цель - создать следующую структуру данных:

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 
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

По сути, это Radix Tree с некоторой дополнительной информацией, позволяющей мне взвесить вероятность изученных возможностей, которые пользователь может захотеть набрать в следующий раз.

Из приведенного выше крайне ограниченного набора данных, когда пользователь вводит "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": {}
          }
        }
      }
    }
  }
}