[JavaScript] Bug in Succinct Trie Implementation of Bits.js

February 02, 2016

Bits.js ([1]) 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 ([2]), 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:

[3]patch for Bits.js - fix the bug of wrong trie insertion if words not inserted in alphabetical order · siongui/go-succinct-data-structure-trie@22c54c0 · GitHub

[4]fix the bug of wrong trie insertion if words not inserted in alphabetical order · siongui/go-succinct-data-structure-trie@aff195b · GitHub

[5]make patch file

[6]How to create a patch - MoodleDocs