Hacker News Reader

Comment by saagarjha | Hacker News Reader

No, Morse Code is not a prefix code.

“Prefix code” is sufficient for the problem to be well-defined, but I don’t think it is necessary.

For a trivial counterexample, consider an alphabet of

   .-
   ..-
   ...-

(And yes, it isn’t uniquely solvable in the case or Morse code, as shown by the counter example A = ET)

That's a prefix code, they're defined by no code word being a prefix of another (so if you put them in a trie the code words only appear on leaves).

A trivial example is the reverse:

  _.
  _..
  _...

Which can be decoded by, at worst, reversing the string first.

(Sorry if I've misunderstood your example)

No, you didn’t.

Telegraph operators could do this in their heads in realtime!

They inserted spaces though, between characters and words. In this problem, all spaces are removed.

We also have to do that to decode speech. You can simulate the way people do it with a hidden Markov model.