<p>Did anyone considered formally the computational complexity of Morse-like codes from an information theory point of view?</p>
<ul>
<li>Morse Code
<ul>
<li>was optimized but designed before the advent of information theory,</li>
<li>difers from traditional prefix free codes in that all character codes end by one space (it's one way to say it, the other would be that codes are not prefix free and that they are separated by spaces in the output), and in addition</li>
<li>has 3 output characters, of variable costs (lengths): short dots, long dashes and spaces.</li>
</ul>
</li>
<li>Optimal Prefix Free Code(s)
<ul>
<li>are well understood in information theory for uniform weights of output characters, and</li>
<li>only approximated (PTAS) for non-uniform weights of output characters.</li>
</ul>
</li>
<li>I am considering the following questions:
<ol>
<li>Ignoring the variable cost of output characters (i.e. assuming that dots, dashes and spaces cost the same), what is the computational cost of computing an &quot;optimal&quot; Morse-Type Code?</li>
<li>Taking into account the variable cost of output characters, can one approximate in good time an &quot;optimal&quot; Morse-Type Code as we do for Prefix Free Codes?</li>
</ol>
</li>
</ul>
<p>I thought that at least the first question would have been covered already (the worst case and adaptive optimal algorithms are similar to that for optimal prefix free codes), but could not find a reference for it (even just the worst case for <span class="math-container">$n$</span> fixed), other than the three following ones:</p>
<ol>
<li><p>one reddit page    <a href="https://www.reddit.com/r/compsci/comments/1mkx3p/huffman_encoding_vs_morse_code;" rel="nofollow noreferrer">https://www.reddit.com/r/compsci/comments/1mkx3p/huffman_encoding_vs_morse_code;</a></p>
</li>
<li><p>one econometrics page <a href="http://deeconometrist.nl/optimizing-morse-code/" rel="nofollow noreferrer">http://deeconometrist.nl/optimizing-morse-code/</a> (which mentions scientists but does not give references) from 2019;</p>
</li>
<li><p>a more theoretical one from 2015 <a href="https://eclecticlight.co/2015/10/22/reinventing-morse-code-using-modern-theory/" rel="nofollow noreferrer">https://eclecticlight.co/2015/10/22/reinventing-morse-code-using-modern-theory/</a> (which proposes to integrate Lempel Ziv with Morse-like codes)</p>
</li>
</ol>

CC BY-SA 4.0
2020-10-27T11:38:10.213Z
I don't understand this question. What non-trivial computation are you asking about? If you can just use any sequence as a code for an input symbol and you don't have to worry about how they're separated, then just enumerate those sequences in order of their cost, and assign your input symbols to them in frequency order.
Zsbán Ambrus
CC BY-SA 4.0
2020-10-27T16:41:40.430Z
@ZsbánAmbrus  1) Designing a Morse-Like code (or even an optimal prefix free code!) implies designing which sequences you use, from a potentially infinite set. 2) The complexity of "in order of their cost" is $O(n\lg n)$, when one can sometime compute the optimal prefix free codes of an unsorted set of weights in less time than that [Shameless Self Plug: Optimal Prefix Free Codes with Partial Sorting. Algorithms 13(1): 12 (2020)].  (I am not sure if I understood your question correctly.)
J.y B.y
CC BY-SA 4.0
2020-11-02T01:52:16.657Z
Which sequences do you use? You use the cheapest ones, which it's easy to calculate since putting one sequence in the code doesn't affect whether you can put other sequences in it. So for Morse code, assign the most frequent letter to the single dot: . Assign the two next most frequent letters to the two codewords of length 2: .. and _ Assign the three next most frequent letters to the three codewords of length 3: ._ and _. and ... Then keep on going.
Peter Shor 
CC BY-SA 4.0
2020-11-03T11:58:13.997Z
Oh! Thanks! (A bit ashamed that I did not see it myself 8o| )   [Was the traditional Morse code designed this way, and is it still optimal with nowadays letter frequencies?]
J.y B.y
CC BY-SA 4.0
2020-11-10T02:13:14.507Z
@Jeremy: the traditional Morse code was indeed designed more or less that way. It's not optimal, but it's close. They got the letter frequencies by going to a printer and.counting the numbers of each letter in the printers' bins. And these didn't quite give the true squence of letter frequencies. And then after their initial design of Morse code, they changed a few of the codewords for various reasons.
Peter Shor 
<information>
Computational cost of Optimal Morse-Like codes?
J.y B.y
# Computational cost of Optimal Morse-Like codes?

(Asked by: username_0 on 2020-10-26)

Did anyone considered formally the computational complexity of Morse-like codes from an information theory point of view?

* Morse Code
  + was optimized but designed before the advent of information theory,
  + difers from traditional prefix free codes in that all character codes end by one space (it's one way to say it, the other would be that codes are not prefix free and that they are separated by spaces in the output), and in addition
  + has 3 output characters, of variable costs (lengths): short dots, long dashes and spaces.
* Optimal Prefix Free Code(s)
  + are well understood in information theory for uniform weights of output characters, and
  + only approximated (PTAS) for non-uniform weights of output characters.
* I am considering the following questions:
  1. Ignoring the variable cost of output characters (i.e. assuming that dots, dashes and spaces cost the same), what is the computational cost of computing an "optimal" Morse-Type Code?
  2. Taking into account the variable cost of output characters, can one approximate in good time an "optimal" Morse-Type Code as we do for Prefix Free Codes?

I thought that at least the first question would have been covered already (the worst case and adaptive optimal algorithms are similar to that for optimal prefix free codes), but could not find a reference for it (even just the worst case for $n$ fixed), other than the three following ones:

1. one reddit page <https://www.reddit.com/r/compsci/comments/1mkx3p/huffman_encoding_vs_morse_code;>
2. one econometrics page <http://deeconometrist.nl/optimizing-morse-code/> (which mentions scientists but does not give references) from 2019;
3. a more theoretical one from 2015 <https://eclecticlight.co/2015/10/22/reinventing-morse-code-using-modern-theory/> (which proposes to integrate Lempel Ziv with Morse-like codes)

**Tags:** information
> **Comments:**
> **username_1**: I don't understand this question. What non-trivial computation are you asking about? If you can just use any sequence as a code for an input symbol and you don't have to worry about how they're separated, then just enumerate those sequences in order of their cost, and assign your input symbols to them in frequency order.  
> **username_0**: @ZsbánAmbrus  1) Designing a Morse-Like code (or even an optimal prefix free code!) implies designing which sequences you use, from a potentially infinite set. 2) The complexity of "in order of their cost" is $O(n\lg n)$, when one can sometime compute the optimal prefix free codes of an unsorted set of weights in less time than that [Shameless Self Plug: Optimal Prefix Free Codes with Partial Sorting. Algorithms 13(1): 12 (2020)].  (I am not sure if I understood your question correctly.)  
> **username_2**: Which sequences do you use? You use the cheapest ones, which it's easy to calculate since putting one sequence in the code doesn't affect whether you can put other sequences in it. So for Morse code, assign the most frequent letter to the single dot: . Assign the two next most frequent letters to the two codewords of length 2: .. and _ Assign the three next most frequent letters to the three codewords of length 3: ._ and _. and ... Then keep on going.  
> **username_0**: Oh! Thanks! (A bit ashamed that I did not see it myself 8o| )   [Was the traditional Morse code designed this way, and is it still optimal with nowadays letter frequencies?]  
> **username_2**: @Jeremy: the traditional Morse code was indeed designed more or less that way. It's not optimal, but it's close. They got the letter frequencies by going to a printer and.counting the numbers of each letter in the printers' bins. And these didn't quite give the true squence of letter frequencies. And then after their initial design of Morse code, they changed a few of the codewords for various reasons.  

---

## 0 answers

