JS: Convert a list of bools to a compact string?

Question

I have a huge list of booleans in javascript, and want to encode them in the url as a parameter, but without it taking up too much space. So I was thinking, is it possible to convert the array of booleans to an array of bits, and then those bits to a string?

So for instance, if my list of booleans is:

[false, true, true, false, false, false, false, true]

then in bits it would be

[0, 1, 1, 0, 0, 0, 0, 1]

which is the binary for just the letter a (at least according to this).

Is something like this possible? And if so, how to convert back?

Answer 1

You can use map:

console.log( [false, true, true].map(item => item ? 1 : 0).join("") );

But map doesn't work well in Internet Explorer. Instead, I'd use a simple for loop:

var bools = [false, true, true];
for(var i = 0; i < bools.length; i++) bools[i] = bools[i] ? 1 : 0;
console.log(bools.join(""));

But what would be super cool is if you could make the string even shorter than just 0's and 1's. What if you could shrink multiple successive booleans of the same value into a single character? So [true, true, true, true] would just be "4" instead of "1111"? That's the idea I took and ran with when creating this code:

var trueMultiples = ['1', '2', '3', '4', '5', '6', '7', '8', '9', 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P', 'A', 'S', 'D'];
var falseMultiples = ['0', 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'z', 'm', 'n', 'b', 'p', 'x', 'c', 'v', 'F', 'G', 'H', 'J', 'K', 'L', 'Z', 'X', 'C', 'V', 'B', 'N', 'M'];

function encryptBools(bools) {
  var str = "",
    run = [];

  for (var i = 0; i < bools.length; i++) {
    if (run.length == 0 || run[run.length - 1] === bools[i]) {
      //stack up successive trues or successive falses as a "run"
      run.push(bools[i]);
    } else {
      //when the run ends, convert it to a trueMultiples or falseMultiples character
      var encryptionSet = bools[i] ? falseMultiples : trueMultiples;
      while (run.length > encryptionSet.length) {
        //if it's too long to be a single character, use multiple characters
        str += encryptionSet[encryptionSet.length - 1];
        run = run.slice(0, run.length - encryptionSet.length);
      }
      str += encryptionSet[run.length - 1];
      run = [bools[i]];
    }
  }

  if (bools.length > 0) {
    //for the last run, convert it to a trueMultiples or falseMultiples character
    var encryptionSet = run[run.length - 1] ? trueMultiples : falseMultiples;
    while (run.length > encryptionSet.length) {
      //if it's too long to be a single character, use multiple characters
      str += encryptionSet[encryptionSet.length - 1];
      run = run.slice(0, run.length - encryptionSet.length);
    }
    str += encryptionSet[run.length - 1];
  }

  return str;
}

function decryptBools(str) {
  var bools = [];

  for (var i = 0; i < str.length; i++) {
    if (trueMultiples.indexOf(str[i]) > -1) {
      for (var j = 0; j <= trueMultiples.indexOf(str[i]); j++) {
        bools.push(true);
      }
    } else if (falseMultiples.indexOf(str[i]) > -1) {
      for (var j = 0; j <= falseMultiples.indexOf(str[i]); j++) {
        bools.push(false);
      }
    }
  }

  return bools;
}

var bools = [true, false, false, false, false, false, true, true, true, true, false];
console.log("ORIGINAL:" + JSON.stringify(bools));

var encryptedBools = encryptBools(bools);
console.log("ENCRYPTED: " + encryptedBools);

var decryptedBools = decryptBools(encryptedBools);
console.log("DECRYPTED: " + JSON.stringify(decryptedBools));

trueMultiples and falseMultiples are the characters that denote how many successive bools you have of that value. For example, "3" indicates 3 consecutive trues, while "s" indicates 3 consecutive falses.

Best case scenario, you can reduce 200 bools down to a 7 character long string. Worst case scenario, 200 characters long. Expected, 100.497 characters long.

I stuck with basic alphanumeric characters, but feel free to add "-", "_", and "~" into the mix if you want. They're safe for urls.

UPDATE

Actually, it strikes me that our first step of converting booleans to 0's and 1's leaves us with something that looks like this:

[1, 1, 0, 1]

That looks strikingly similar to a binary number to me. What if we join that array together and get 1101 and then switch that over to decimal notation to display it as 13? Or even better yet, we can use a higher base, like 36 to get it to read as just d! Being able to switch the base of the number like this is an awesome way to produce a smaller result!

Now, I know what you're thinking. What if there are false's at the beginning and number ends up being something like 001? The leading 0's will get lost!! Well, don't worry. We can just set our algorithm up to always add a 1 to the beginning before we switch bases. That way, all the 0's will remain significant.

There are some limitations here. With 200+ booleans, these contrived numbers are going to be huge. Too big, in fact, for JavaScript to handle. We'll need to break it up into manageable chunks and then join those chunks together to get our result.

Side note: We could play with putting in more work to just signal how many leading zeros there are instead of forcing a leading 1 to improve our best-case scenario, but I think that could actually hurt our average-case scenario, so I didn't. Forcing a leading 1 forces all of our full chunks to always be 11 characters long, and that fact saves us the need for extra delimiters. Why mess with that?

Anyway, here's what I ended up with:

function compress(bools) {
  var sections = [], MAX_SAFE_SECTION = 52;
  for (var i = 0; i < bools.length; i++) {
    if (i % MAX_SAFE_SECTION == 0) sections.push([]);
    sections[Math.floor(i / MAX_SAFE_SECTION)][i % MAX_SAFE_SECTION] = bools[i] ? 1 : 0;
  }
  for (var i = 0; i < sections.length; i++) sections[i] = parseInt("1" + sections[i].join(""), 2).toString(36);
  return sections.join("");
}

function expand(str) {
  var sections = [];
  while (str.length > 0) str = str.replace(sections[sections.length] = str.substring(0, 11), "");
  for (var i = 0; i < sections.length; i++) sections[i] = parseInt(sections[i], 36).toString(2).substring(1);
  var bools = sections.join("").split("");
  for (var i = 0; i < bools.length; i++) bools[i] = bools[i] == "1";
  return bools;
}


var bools = [true, false, false, false, false, false, true, true, true, true, false];
console.log("ORIGINAL:" + JSON.stringify(bools));

var compressedBools = compress(bools);
console.log("COMPRESSED: " + compressedBools);

var expandedBools = expand(compressedBools);
console.log("EXPANDED: " + JSON.stringify(expandedBools));

It'll take an array of 200 booleans and cut it down to a 42 character string consistently.

That's good, but you might be asking yourself why we just went with base 36? Could we go higher? The answer is that I just went with 36 because it's the highest number built into JavaScript's parseInt function already. We can go higher if we're willing to add in custom base conversion code. There's a wonderful answer available here that offers a nice base conversion function, so I'll just copy their function and paste it in here to prove my point:

function convertBase(value, from_base, to_base) {
  var range = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_'.split('');
  var from_range = range.slice(0, from_base);
  var to_range = range.slice(0, to_base);

  var dec_value = value.split('').reverse().reduce(function(carry, digit, index) {
    if (from_range.indexOf(digit) === -1) throw new Error('Invalid digit `' + digit + '` for base ' + from_base + '.');
    return carry += from_range.indexOf(digit) * (Math.pow(from_base, index));
  }, 0);

  var new_value = '';
  while (dec_value > 0) {
    new_value = to_range[dec_value % to_base] + new_value;
    dec_value = (dec_value - (dec_value % to_base)) / to_base;
  }
  return new_value || '0';
}

function compress(bools) {
  var sections = [], MAX_SAFE_SECTION = 52;
  for (var i = 0; i < bools.length; i++) {
    if (i % MAX_SAFE_SECTION == 0) sections.push([]);
    sections[Math.floor(i / MAX_SAFE_SECTION)][i % MAX_SAFE_SECTION] = bools[i] ? 1 : 0;
  }
  for (var i = 0; i < sections.length; i++) sections[i] = convertBase("1" + sections[i].join(""), 2, 62);
  return sections.join("");
}

function expand(str) {
  var sections = [];
  while (str.length > 0) str = str.replace(sections[sections.length] = str.substring(0, 9), "");
  for (var i = 0; i < sections.length; i++) sections[i] = convertBase(sections[i], 62, 2).substring(1);
  var bools = sections.join("").split("");
  for (var i = 0; i < bools.length; i++) bools[i] = bools[i] == "1";
  return bools;
}


var bools = [true, false, false, false, false, false, true, true, true, true, false];
console.log("ORIGINAL:" + JSON.stringify(bools));

var compressedBools = compress(bools);
console.log("COMPRESSED: " + compressedBools);

var expandedBools = expand(compressedBools);
console.log("EXPANDED: " + JSON.stringify(expandedBools));

We can get up to base 62 with this custom function safely. That means we can take an array of 200 booleans and cut it down to a 35 character string consistently. If there isn't a ton of sequential repetition in your array, you might like to use this option instead. It's the algorithm I'd pick.

Answer 2

var bools = [false, true, true, false, false, false, false, true]

var str = bools.map(Number).join('')              // array to string

var arr = str.split('').map(Number).map(Boolean)  // string to array

console.log( str )
console.log( arr )

Answer 3

You can convert the booleans to bytes and then encode it in base64:

function encode(booleans) {
    var bits = booleans.map(Number).join('');
    var bytes = Array.from(
        bits.matchAll(/[01]{8}/g)
    ).map(byte => parseInt(byte, 2));
    var characters = bytes.map(byte => String.fromCharCode(byte)).join('');

    return btoa(characters);
}

To decode you convert the base64 string back to bytes and then take one bit at a time:

function decode(string) {
    var bytes = atob(string).split('').map(char => char.charCodeAt(0));
    var bits = [];

    for (var i = 0; i < bytes.length; i++) {
        var byte = bytes[i];
        var temp = [];
        for (var bit = 0; bit < 8; bit++) {
            temp.unshift(byte & 1)
            byte >>= 1;
        }
        bits = bits.concat(temp)
    }

    return bits.map(Boolean)
}

This only works if the length of your booleans list is multiple of 8

Answer 4

Since you have a few hundreds of values, it's possible to just create a string of 1s and 0s, that would fit in a URL without the need of further compression.

You can simply map your boolean to numbers by using + in front of them, then turn them into strings.

example, try this in console : :

    let a = [true, true, false, true];
    console.log(a.map(x => (+x).toString())); // Array(4) [ "1", "1", "0", "1" ]
    console.log(a.map(x => (+x).toString()).join("")); // "1101"

Above would be the "serialization" of your array of booleans. (that's the proper term in this context).

The "deserialization" would be the opposite steps (split the string into characters, convert the individual characters to numbers then to booleans) :

let s = "1101";
console.log(s.split("")); // Array(4) [ "1", "1", "0", "1" ]
console.log((s.split("")).map(x => +x)); // Array(4) [ 1, 1, 0, 1 ]
console.log((s.split("")).map(x => !!(+x))); // Array(4) [ true, true, false, true ]

(I left the intermediary steps so you can see the reasoning, but only the last line of each snippet is useful)

Answer 5

These functions will compress 200 booleans to a 40-character, URL-safe string, and expand them back to the original array of booleans. They should work for any length boolean array, growing by approximately one character for every six booleans:

const compressBools = (bools) =>
  String (bools .length) + '~' + 
  btoa ( bools
    .map (b => b ? '1' : '0')
    .reduce (
      ([c, ...r], b, i) => (bools .length - i) % 8 == 0 ? [[b], c, ...r] : [[...c, b], ...r],   
      [[]]
    )
    .reverse ()
    .map (a => a .join (''))
    .map (s => parseInt(s, 2))
    .map (n => String.fromCharCode(n))
    .join ('')
  )
  .replace (/\+/g, '-')
  .replace (/\//g, '_')
  .replace (/\=/g, '.')

const expandBools = (s, [len, str] = s .split ('~')) => 
  atob (str
    .replace (/\./g, '=')
    .replace (/_/g, '/')
    .replace (/\-/g, '+')
  )
  .split ('')
  .map (c => c .charCodeAt (0))
  .map (s => Number (s) .toString (2) .padStart (8, '0'))
  .flatMap (a => a .split (''))
  .slice (-len)
  .map (c => c == '1')


const arr = Array.from({length: 200}, _ => Math.random() < .5)

const compressed = compressBools (arr)
console .log (`Compressed String: "${compressed}"`)

const expanded = expandBools(compressed)
console .log (`Output matches: ${expanded.every((b, i) => b == arr[i])}`)

The three regex replacements in each are to deal with the + and / characters of the underlying base64 conversion, as well as its = padding character, replacing them with URL-safe alternatives. You could instead call encode/decodeURIComponent, but this way leads to shorter strings.

The ugly reduce in the compression is to split a long string of 0's and 1's into groups of 8, with the first one potentially shorter. This gives us bytes which we can then convert into characters.

Note that the output string starts with the count of booleans to generate. This is because we could not otherwise distinguish some leading zeros in the numbers -- which would get translated into initial falses -- from arrays which were simply shorter and didn't have such leading zeros. That number is separated from the remaining string by a tilde (~); you could easily replace this with another character if you like, but URL-safe special characters are hard to come by.

---

There is also a little game we could play if we liked with these, finding boolean arrays that lead to interesting strings. For instance:

const arr = [true, false, false, true, false, true, false, true, true, false, true, false, true, true, false, true, false, false, true, true, true, false, false, true, false, false, true, false, false, true, true, true, true, true, true, false, false, true, true, true, false, true, false, true, true, true, true, false, true, true, true, true, false, true, false, true, false, true, true, false, true, true, true, true, true, true, false, false, true, false, true, true, false, true, false, false, false, true, true, false, false, false, false, true, true, true, true, true, true, false, true, false, false, false, false, true, false, true, true, true, false, false, true, true, true, true, false, true, false, true, true, false, false, true, false, true, true, false, true, true, false, false, false, true, false, true, false, true, false, false, false, true, false, false, true, true, true, true, true, true, true, true, true, true, true, true, false, false, true, true, true, true, true, false, true, true, true, true, true, false, true, true, true, false, true, true, false, true, true, false, true, true, true, true, true, true, false, false, true, true, true, false, true, true, true, true, true, true, false, true, true]

console .log (compressBools (arr)) //~> "191~Stack_Overflow_Question_59923537"

Answer 6

I've recently made a simple library to do exactly this. It thinks of the boolean array as binary data and encodes it in Base64.

It uses these two constants. You can use a different base (Base64 for url / Base128 / ...) just by changing the characters string (and potentially adjusting bitsInChar).

// Base64 character set
const characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

// How many bits does one character represent
const bitsInChar = 6; // = Math.floor( Math.log2(characters.length) );

Encoding function

function compress(array) {

    // The output string
    let string = "";

    // Loop through the bool array (six bools at a time)
    for (let charIndex = 0; charIndex < array.length / bitsInChar; section++) {
        let number = 0;

        // Convert these six bools to a number (think of them as bits of the number) 
        for (let bit = 0; bit < bitsInChar; bit++)
            number = number * 2 + (array[charIndex*bitsInChar + bit] ? 1 : 0);

        // Convert the number to a Base64 character and add it to output
        string += characters.charAt(number);
    }

    return string;
}

Decoding function

function decompress(string) {

    // The output array
    const array = [];

    // Loop through the input string one character at a time
    for (let charIndex = 0; charIndex < string.length; charIndex++) {
        
        // Convert the Base64 char to a number 
        let number = characters.indexOf(string.charAt(charIndex));

        // Convert the number to six bools (think of them as bits of the number) 
        // And assign them to the right places in the array
        for (let bit = bitsInChar - 1; bit >= 0; bit--) {
            array[charIndex*bitsInChar + bit] = !!(number % 2)
            number = Math.floor(number / 2);
        }
    }

    return array;
}

There's one catch: After a compressing-decompressing cycle the new array's length will be rounded up to the nearest multiple of 6 (or some different number, depending on your chosen base) with additional falses being added to the end of the array. It didn't matter in my case, but if you need the exact same array you'll have to store the original length as well.