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

Question

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

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

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

Мне нравится 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 
               } 
              } 
             } 
            } 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} 

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

Из вышеизложенного крайне ограниченного набора данных, когда пользователь вводит «я», наша лучшая (и единственная) догадка заключается в том, что следующий символ будет «".

Так что теперь я объяснил свою цель и метод, вот мой вопрос:

Как я могу построить эту структуру данных из любого заданного пользовательского ввода?

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": {} 
      } 
     } 
     } 
    } 
    } 
}