title: How can I analyze or improve my niece's simple compression algorithm that is based on Morse code?
body: <p>My 8 year old niece had a lesson on Morse code in school yesterday, and her assignment was to convert various phrases to Morse code. One of the phrases included her age, and instead of writing <strong><code>---..</code></strong>, she wrote <strong><code>3-2.</code></strong> because (in her words), &quot;it's less writing that way.&quot; This rudimentary &quot;compression algorithm&quot; sparked my curiosity, so I wrote a bit of code to implement it.</p>
  <p>However, we made a few changes along the way. I pointed out to her that if you wrote just <strong><code>.....-----</code></strong>, there isn't any way to tell if the writer meant <code>50</code> or <code>eeeeettttt</code>. In reality, there is a pause in between each letter of each word and every word so this isn't a problem, but our scheme didn't have that. I pulled out some graph paper and suggested padding the Morse code for each symbol with another symbol to facilitate coding and remove ambiguity from the scheme. My nice suggested using <code>+</code> because &quot;no one ever writes those in sentences.&quot; (Ouch, I recently graduated with a math degree, but fair enough.)</p>
  <p>Since some of us <em>do</em> write with <code>+</code>, and we all use hyphens and periods/dots, which would conflict with our standard definition of Morse code, these symbols are replaced with <code>p</code>, <code>h</code>, and <code>d</code>, respectively. Of course, this brings us to the problem of what to do with symbols that aren't defined in our extended Morse code. My niece wanted to simply ignore them, so that's what we did. For the sake of case sensitive preservation of the textual message, upper case letters aren't lower cased in the code; they're just carried through as is and padded with <code>+</code>.</p>
  <h3>Summary of the algorithm:</h3>
  <ol>
  <li>Morse codes are right-padded to 5 characters with <code>+</code></li>
  <li>We extended Morse code to substitute <code>p</code> for <code>+</code>, <code>d</code> for <code>.</code>, and <code>h</code> for <code>-</code>.</li>
  <li>Symbols that aren't defined in our &quot;extended&quot; Morse code are passed through intact.</li>
  <li>Runs of symbols are replaced with  unless only one consecutive character occurs, in which case the number is omitted.</li>
  </ol>
  <h3>Potential pitfalls:</h3>
  <ol>
  <li>My padding scheme probably reduces the effectiveness of the compression.</li>
  <li>Compression might be improved by using blocks larger than 5 characters</li>
  <li>If either my niece or I knew anything about compression algorithms, we could probably use  that makes them successful.</li>
  <li>This obviously isn't suitable for production, but since there are numerous efficient compression algorithms for such purposes, I'm ignoring that problem for the time being.</li>
  <li>???</li>
  </ol>
  <h3>Example:</h3>
  <p>In our algorithm, &quot;Hello, World&quot; translates to</p>
  <pre><code>H++++.++++.-..+.-..+---++,+++++++++W++++---++.-.++.-..+-..++
  </code></pre>
  <p>and compresses to</p>
  <pre><code>H4+.4+.-2.+.-2.+3-2+,9+W4+3-2+.-.2+.-2.+-2.2+
  </code></pre>
  <p>Here is the Python code I threw together:</p>
  <pre><code>#!/usr/bin/python3
  
  import itertools
  import string
  
  class MorseString(str):
      def __init__(self, string):
          # or, pad values during iteration but this seems neater
          self._char_morse_map = {&quot;a&quot;:&quot;.-+++&quot;, &quot;b&quot;:&quot;-...+&quot;, &quot;c&quot;:&quot;-.-.+&quot;, &quot;d&quot;:&quot;-..++&quot;, \
                                  &quot;e&quot;:&quot;.++++&quot;, &quot;f&quot;:&quot;..-.+&quot;, &quot;g&quot;:&quot;--.++&quot;, &quot;h&quot;:&quot;....+&quot;, \
                                  &quot;i&quot;:&quot;..+++&quot;, &quot;j&quot;:&quot;.---+&quot;, &quot;k&quot;:&quot;-.-++&quot;, &quot;l&quot;:&quot;.-..+&quot;, \
                                  &quot;m&quot;:&quot;--+++&quot;, &quot;n&quot;:&quot;-.+++&quot;, &quot;o&quot;:&quot;---++&quot;, &quot;p&quot;:&quot;.--.+&quot;, \
                                  &quot;q&quot;:&quot;--.-+&quot;, &quot;r&quot;:&quot;.-.++&quot;, &quot;s&quot;:&quot;...++&quot;, &quot;t&quot;:&quot;-++++&quot;, \
                                  &quot;u&quot;:&quot;..-++&quot;, &quot;v&quot;:&quot;...-+&quot;, &quot;w&quot;:&quot;.--++&quot;, &quot;x&quot;:&quot;-..-+&quot;, \
                                  &quot;y&quot;:&quot;-.--+&quot;, &quot;z&quot;:&quot;--..+&quot;, &quot;1&quot;:&quot;.----&quot;, &quot;2&quot;:&quot;..---&quot;, \
                                  &quot;3&quot;:&quot;...--&quot;, &quot;4&quot;:&quot;....-&quot;, &quot;5&quot;:&quot;.....&quot;, &quot;6&quot;:&quot;-....&quot;, \
                                  &quot;7&quot;:&quot;--...&quot;, &quot;8&quot;:&quot;---..&quot;, &quot;9&quot;:&quot;----.&quot;, &quot;0&quot;:&quot;-----&quot;,
                                  &quot; &quot;:&quot;+++++&quot;, &quot;.&quot;:&quot;d++++&quot;, &quot;+&quot;:&quot;p++++&quot;, &quot;-&quot;:&quot;h++++&quot;}
          
          self._morse_char_map = dict()
          for letter, code in self._char_morse_map.items():
              self._morse_char_map[code] = letter
  
          self._string = string
  
          # convert the string to &quot;Morse code&quot;. Could also use c.lower()
          self._morse_string = &quot;&quot;.join([self._char_morse_map.get(c, c.ljust(5, &quot;+&quot;)) for c in self._string])
  
      def compress(self):
          def grouper(n, k):
              return str(n) + k if n &gt; 1 else k
  
          # could just use lambda
          return &quot;&quot;.join([grouper(len(list(g)), k) for k, g in itertools.groupby(self._morse_string)])
  
      def decompress(self):
          i = 0
          start = 0
          chars = list()
          sc = self.compress()
          while i &lt; len(sc):
              curr = sc[i]
              i += 1
              if not(curr in string.digits):
                  num = 1 if start + 1 == i else int(sc[start:i-1])
                  chars.append(&quot;&quot;.join(curr * num))
                  start = i
  
          code = &quot;&quot;.join(chars)
          chars = list()
  
          for i in range(0, len(code), 5):
              piece = &quot;&quot;.join(code[i:i+5])
              chars.append(self._morse_char_map.get(piece, piece[0]))
              
          return &quot;&quot;.join(chars)
  
  
  def main():
      s0 = &quot;Hello, World&quot;
      ms0 = MorseString(s0)
      print(ms0._morse_string)
      print(ms0.compress())
      assert(s0 == ms0.decompress())
      
      s1 = &quot;Hello  2 world.&quot;
      ms1 = MorseString(s1)
      assert(s1 == ms1.decompress())
  
      s2 = &quot;The quick brown fox jumped over the lazy dog.&quot;
      ms2 = MorseString(s2)
      assert(s2 == ms2.decompress())
  
      s3 = &quot;abc  -.+&quot;
      ms3 = MorseString(s3)
      ms3
      assert(s3 == ms3.decompress())
  
  if __name__ == &quot;__main__&quot;:
      main()
  </code></pre>
  <p>What are some simple methods that would a) improve our algorithm, and b) be relatively easy to explain to my 8-year old niece? While the last point is clearly subjective, I'm nevertheless trying to indulge her curiosity as much as possible.</p>
  <p>I welcome any improvements to the code as well since it's not structured terribly well (I'm fairly certain it's structured quite poorly, actually, but it's quick and dirty), although that's strictly for my benefit since I haven't gotten my niece to use Python (YET).</p>
  <h3>Update</h3>
  <p>Here is an updated version of the code, which attempts to incorporate both user1884905's modifications to the algorithm and Karl's improvements to the code itself.</p>
  <pre><code>import itertools
  import string
  
  _char_morse_map = {&quot;a&quot;:&quot;.-&quot;, &quot;b&quot;:&quot;-...&quot;, &quot;c&quot;:&quot;-.-.&quot;, &quot;d&quot;:&quot;-..&quot;, \
                     &quot;e&quot;:&quot;.&quot;, &quot;f&quot;:&quot;..-.&quot;, &quot;g&quot;:&quot;--.&quot;, &quot;h&quot;:&quot;....&quot;, \
                     &quot;i&quot;:&quot;..&quot;, &quot;j&quot;:&quot;.---&quot;, &quot;k&quot;:&quot;-.-&quot;, &quot;l&quot;:&quot;.-..&quot;, \
                     &quot;m&quot;:&quot;--&quot;, &quot;n&quot;:&quot;-.&quot;, &quot;o&quot;:&quot;---&quot;, &quot;p&quot;:&quot;.--.&quot;, \
                     &quot;q&quot;:&quot;--.-&quot;, &quot;r&quot;:&quot;.-.&quot;, &quot;s&quot;:&quot;...&quot;, &quot;t&quot;:&quot;-&quot;, \
                     &quot;u&quot;:&quot;..-&quot;, &quot;v&quot;:&quot;...-&quot;, &quot;w&quot;:&quot;.--&quot;, &quot;x&quot;:&quot;-..-&quot;, \
                     &quot;y&quot;:&quot;-.--&quot;, &quot;z&quot;:&quot;--..&quot;, &quot;1&quot;:&quot;.----&quot;, &quot;2&quot;:&quot;..---&quot;, \
                     &quot;3&quot;:&quot;...--&quot;, &quot;4&quot;:&quot;....-&quot;, &quot;5&quot;:&quot;.....&quot;, &quot;6&quot;:&quot;-....&quot;, \
                     &quot;7&quot;:&quot;--...&quot;, &quot;8&quot;:&quot;---..&quot;, &quot;9&quot;:&quot;----.&quot;, &quot;0&quot;:&quot;-----&quot;,
                     &quot; &quot;:&quot;&quot;, &quot;.&quot;:&quot;d&quot;, &quot;+&quot;:&quot;p&quot;, &quot;-&quot;:&quot;h&quot;}
  
  _morse_char_map = {
      code: letter
      for letter, code in _char_morse_map.items()
  }
  
  
  def encode(s):
      return &quot;&quot;.join(_char_morse_map.get(c, c) + &quot;+&quot; for c in s)
  
  def decode(encoded):
      return &quot;&quot;.join(decode_gen(encoded))
  
  def decode_gen(encoded):
      word = &quot;&quot;
      for c in encoded:
          if c != &quot;+&quot;:
              word += c
          else:
              yield _morse_char_map.get(word, word) if word != &quot;&quot; else &quot; &quot;
              word = &quot;&quot;
  
  def compress(s):
      def grouper(n, k):
          return str(n) + k if n &gt; 1 else k
  
      return &quot;&quot;.join(grouper(len(list(g)), k) for k, g in itertools.groupby(s))
  
  def decompress(compressed):
      return &quot;&quot;.join(decompress_gen(compressed))
  
  def decompress_gen(compressed):
      digits = &quot;&quot;
      for c in compressed:
          if c in string.digits:
              digits += c
          else:
              number = int(digits) if digits else 1
              yield &quot;&quot;.join(c * number)
              digits = &quot;&quot;
  </code></pre>