Bits.js () implements a succinct trie for fast lookup of words in a
large dictionary and does not take much space at the same time. It works great
if the words are inserted in the trie in alphabetical order. When I ported the
code from JavaScript to Go (), I found that if the words are not sorted are
then inserted into the trie in alphabetical order, the resulting trie is wrong.
The following is my patch for Bits.js:
diff --git a/reference/Bits.js b/reference/Bits.js
index d5a3934..129bcd2 100644
--- a/reference/Bits.js
+++ b/reference/Bits.js
@@ -453,6 +453,18 @@ Trie.prototype = {
var node = this.cache[ this.cache.length - 1 ];
for( i = commonPrefix; i < word.length; i++ ) {
+ // fix the bug if words not inserted in alphabetical order
+ var isLetterExist = false;
+ for ( var j = 0; j < node.children.length; j++ ) {
+ if (node.children[j].letter == word[i]) {
+ this.cache.push(node.children[j]);
+ node = node.children[j];
+ isLetterExist = true;
+ break;
+ }
+ }
+ if (isLetterExist) { continue; }
+
var next = new TrieNode( word[i] );
this.nodeCount++;
node.children.push( next );
References: