3
\$\begingroup\$

My application state is represented by a string of numbers and I'm trying to encode the string so that it is as small as possible (ie. fewest number of characters). An example string would be: 133223333302302040

I realized that most of these strings consist of number pairs containing 0, 1, 2, 3 (4 and 5 also exist but are rare). I decided to replace the most common number pairs with letters, shortening my encoded string by ~50%

I have a function that returns the mapping:

function getValueMap(lettersFirst = false) {
  const map = {
    '00': 'a',
    '01': 'b',
    '02': 'c',
    '03': 'd',
    '10': 'e',
    '11': 'f',
    '12': 'g',
    '13': 'h',
    '20': 'i',
    '21': 'j',
    '22': 'k',
    '23': 'l',
    '30': 'm',
    '31': 'n',
    '32': 'o',
    '33': 'p'
  };

  if (lettersFirst) {
    return Object.fromEntries(Object.entries(map).map(([k, v]) => [v, k]));
  } else {
    return map;
  }
}

To encode, I iterate through every pair of input numbers, check if it is in the map, and if so, add the letter to the encoded output. For odd length inputs I simply remove the last digit, dont encode it, and simply append the number to the output string untouched:

encode(text) {
  const map = getValueMap();
  let values;
  let suffix = '';

  if (text.length % 2 !== 0) {
    suffix = text.charAt(text.length - 1);
    values = text.slice(0, -1);
  } else {
    values = text;
  }

  let encoded = '';
  for (let i = 0; i <= text.length - 2; i += 2) {
    if (map[values[i] + values[i + 1]]) {
      encoded += map[values[i] + values[i + 1]];
    } else {
      encoded += values[i] + values[i + 1];
    }
  }
  encoded += suffix;
  return encoded;
}

To decode, iterate through the string, if its a letter, add the corresponding number pair to the decoded output. If its already a number, simply add the number instead:

decode(encoded) {
  const map = getValueMap(true);
  let decoded = '';

  for (let i = 0; i < encoded.length; i++) {
    if (encoded[i].toLowerCase() !== encoded[i].toUpperCase()) {
      decoded += map[encoded[i]];
    } else {
      decoded += encoded[i];
    }
  }

  return decoded;
}

Some example inputs and outputs:

Encode:
13223233202200252044 -> hkopika25i44

Decode:
holppcmi40 -> 133223333302302040

Is there a more straightforward way to do this? My implementation feels unnecessarily obtuse. For example, do I actually need to create a map/reverse map when I could maybe rely on indexing the pair array or alphabet instead? Is there a more elegant way to iterate over pairs of numbers? Or to build up the final encoded/decoded form without appending to a string?

\$\endgroup\$
  • \$\begingroup\$ Does the string of numbers have a maximum length? \$\endgroup\$ – TheDancingCode Dec 25 '19 at 9:58
  • \$\begingroup\$ The max length will fluctuate between 20-22. Each individual number within that string cannot be greater than 5 \$\endgroup\$ – Simon Dec 25 '19 at 11:10
2
\$\begingroup\$

First a few suggestions to your design. You are effectively trying to represent list of small numbers as String, with no actual meaning (at least that's how I understood it). I'd consider:

  • Represent it for what it is - list of small numbers could be represented as byte array. That seems a lot more natural and convenient.
  • Use some simpler mapping, if it doesn't matter what kind of character is the result. If numbers really are in range between 0 and 32 and not much higher, I'd go for mapping function, that for example adds 65 (and substracts 65 in reverse). That mapping function is really simple and you don't need any kind of map. Your code would be reduced only to initial tokenization basically. 00 becomes A, 30 becomes _ according to their ASCII codes (+65).

In case you wanna keep your String representation, here are my points to your code:

getValueMap

  • Names getValueMap name and lettersFirst don't really say what much about what do they do.
  • There's no point to recalculate reverse map everytime. Flag parameters with this kind of if are typical code smell and bad practice.
  • I suggest creating 2 module variables codesToCharacters (original map) and charactersToCodes (once pre-calculated) instead.

decode

  • I'd love if this function was just mapping encoded data to decoded data based on mapping function.
  • Not sure, why is there that if. I think you are trying to check, if current character is letter or not and if so, map it, otherwise use the character. That took me a while to understand. If there was really need, I would extract that to function with propper name (like isLetter) to increase readability.
  • Anyway, why even doing that? Why not instead look into the map and if map contains key, use map value, otherwise use original character.

Function would look something like (pseudocode, not tested):

function decode(encoded) {

    return encoded.split("").map(
        c => {
            charactersToCodes.hasKey(c) ? charactersToCodes[c] : c
        }).join()

}

encode would be on same principle, only difference is, that you need to tokenize it correctly first and then map :)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your insight! Your suggested approach with map is so much more elegant \$\endgroup\$ – Simon Dec 24 '19 at 11:47
2
\$\begingroup\$

Another simple solution would be base conversion. The original string contains the characters 0 to 5, meaning it is in base 6. Every pair of characters can therefore be encoded as one base 36 character. The resulting string will contain the characters a to z and 0 to 9.

A string of length n will, after conversion, have length n/2 if n is even, or (n/2) + 1 if n is odd.

function convertBase(str, fromBase, toBase) {
  return parseInt(str, fromBase).toString(toBase);
}

function encode(str) {
  const hasEvenLength = str.length % 2 === 0;
  const chuncks = hasEvenLength ? [] : [str.substr(0, 1)];
  const startIndex = hasEvenLength ? 0 : 1;
  for (let i = startIndex; i < str.length - 1; i += 2) {
    chuncks.push(str.substr(i, 2));
  }
  return chuncks.map(chunck => convertBase(chunck, 6, 36)).join('');
}

function decode(str) {
  return str.split('').map(char => convertBase(char, 36, 6)).join('');
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.