Динамическое присвоение свойств объекту JavaScript (trie)

Question

Я пытаюсь реализовать вариацию trie в JavaScript. В принципе, это эффективный объект хранения данных, в котором символы в ключах не повторяются. Другими словами, если у меня есть ключи «Абэ» и «ANN,» только один экземпляр разделяемого буквы «а» должно появиться:

{ 
    a: { 
     b: { 
      e: { 
       0: 'lincoln' 
      } 
     }, 
     n: { 
      n: { 
       0: 'mcgee' 
      } 
     } 
    } 
} 

Вот желаемая реализация и несколько примеров использования:

function Trie() { 
    // The top level of the trie. 
    var root = {}; 

    return { 
     write: function (key, value) { 
     }, 
     read: function (key) { 
     } 
    }; 
} 

// Sample usage 
var trie = new Trie(); 

trie.write('abe', 'lincoln'); 
trie.write('ann', 'mcgee'); 

trie.read('abe'); // returns 'lincoln' 
trie.read('ann'); // returns 'mcgee' 

Я столкнулся с блокатором относительно метода write. Учитывая строковый ключ, такой как «abe», мне нужно присвоить свойство root['a']['b']['e']. Я не могу найти способ присвоить значение объекту нескольким слоям, если число ключей и значения ключей неизвестны.

Единственное решение, которое приходит на ум, я думаю, плохое: поместив путь к значению в строку и используя eval. Например: eval("root['a']['b']['e'] = 'lincoln'");

Есть ли лучшее решение для динамического присвоения значений? (Я понимаю, что это немного сложной проблемы, так что я рад уточнить путем предоставления дополнительной информации.)

Answer 1

очень наивный подход (с учетом требований, хотя я хотел бы написать другую реализацию)

заданная строка ключей и указатель на корень и значение для назначения;

function write(root,path,value){ 
    var a = path.split(''); // 'abc'->['a','b','c'] 
    var pointer = root; 
    var i=0; 
    while(i<a.length-1){ 
     if(pointer[a[i]] == undefined){ 
      pointer[a[i]]={}; 
     } 
     pointer = pointer[a[i]]; 
     i++; 
    } 
    pointer[a[i]]=value; 
    return root; 
} 

EDIT: Я предполагаю, что все ключи существуют на соответствующем объекте. Я добавил условие if, если некоторые ключи не определены.

EDIT: 2 сплит исправлен, исправление немного ошибка прямо сейчас;)

EDIT: 3 должен работать.

usage : write({},'abc',1) // yields {a:{b:{c:1}}} 

Answer 2

То, что вы ищете, представляет собой двойной массив trie. вы можете сделать поиск GitHub для этого, но две основные библиотеки перечислили:

• doublearray, из документации:

вар DoubleArray = требуется (»./ doublearray.js');

вар слова = [

{k: 'а', V: 1},

{к: 'ABC', v: 2},

];

var trie = doublearray.builder(). Build (слова);

trie.contain ('a'); // -> true

trie.поиск ('ABC'); // -> 2

• или datrie