1

I was looking for better autocomplete alghoritm and i found out about trie. I have implemented basic trie 

  var trie = {};
    for( var i = 0 ; i < words.length ; i++){
        var tmp_word = words[i];
      var tmp_arr      = tmp_word.split("");
      var current      = trie;

      for( var j = 0; j < tmp_arr.length; j++){
         var letter = tmp_arr[j];
         var pos    = current [ letter ];
         if( pos == null ){
              current [ letter ] = j === tmp_arr.length - 1 ? 0 : {};
              current =current [ letter ];
         }
         else if ( pos === 0 ) {
                current [ letter ] = { $: 0 };
                current  =current [ letter ]
         }
         else{
                 current  = current [ letter ];
         }

      }      
    }

which will take words from array and create key from every letter. For example if array is

var words = [ "Hello" , "world" ,"Helis" ]

it will create this

{
  "H": {
    "e": {
      "l": {
        "l": {
          "o": 0
        },
        "i": {
          "o": {
            "s": 0
          }
        }
      }
    }
  },
  "w": {
    "o": {
      "r": {
        "l": {
          "d": 0
        }
      }
    }
  }
}

What i am struggling with is find a word to complete. E.g if i input "He" it should return Hello and Helios , what is best way how to do it? The only thing that come into my mind is brute force loop which would be really ineffective and slow. Is there any more effective way than brute force?

Darlyn
  • 4,715
  • 12
  • 40
  • 90
  • what happen, if **he** is a word in your trie. i suggest to use an own property for that, like `isword` and the value `true`. for iterating i would go for brute, because javascript is fast enough for hash tables. – Nina Scholz May 17 '16 at 13:44
  • maybe you have a look to http://stackoverflow.com/a/32781195/1447675 – Nina Scholz May 17 '16 at 14:20

1 Answers1

0

You can try https://github.com/pujansrt/trie-js

var trie = new Trie();
trie.insert('ant');
trie.insert('and');
trie.insert('antique');
console.log(trie.autoComplete('ant')); //['ant','antique']
Pujan
  • 3,154
  • 3
  • 38
  • 52