55
$\begingroup$

Are all Morse code strings uniquely decipherable? Without the spaces,

......-...-..---.-----.-..-..-..

could be Hello World but perhaps the first letter is a 5 -- in fact it looks very unlikely an arbitrary sequence of dots and dashes should have a unique translation.

One might possibly use the Kraft inequality but that only applies to prefix codes.

Morse code with spaces is prefix code in which messages can always be uniquely decoded. Once we remove the spaces this is no longer true.


In the case I am right, and all Morse code message can't be uniquely decoded, is there a way to list all the possible messages? Here are some related exercise I found on codegolf.SE

$\endgroup$
  • 7
    $\begingroup$ You seem to have answered your own question already? $\endgroup$ – Raphael Dec 9 '14 at 17:34
  • 7
    $\begingroup$ "Morse code without spaces" is not morse code. The spaces are part of the specification because without them the code is not decipherable. $\endgroup$ – Stephen Kennedy Dec 9 '14 at 20:11
  • 1
    $\begingroup$ @StephenKennedy That's already in the question. Did you read it completely? $\endgroup$ – Raphael Dec 9 '14 at 22:14
  • 3
    $\begingroup$ Perl script to list possible messages for a code. Didn't realize this was a purely theoretical community. :) $\endgroup$ – Squeezy Dec 9 '14 at 22:42
  • 1
    $\begingroup$ Are you really sure your accepted answer qualifies as an answer at all, or even as a hint to anything? I mean it is obvious that ET=A ... which proves that Spielberg was right: ET is an Alien. $\endgroup$ – babou Dec 11 '14 at 23:52
93
$\begingroup$

The following are both plausible messages, but have a completely different meaning:

SOS HELP      = ...---...  .... . .-.. .--.        => ...---.........-...--.
I AM HIS DATE = ..  .- --  .... .. ...  -.. .- - . => ...---.........-...--.
$\endgroup$
  • 6
    $\begingroup$ Cute but it's already been established that Morse without spaces is ambiguous so I don't really think this is worth much more than a comment. $\endgroup$ – David Richerby Dec 9 '14 at 21:07
  • 38
    $\begingroup$ The OP seems to be asking whether one series of dots and dashes without spaces could be interpreted as two "real" messages as opposed to arbitrary sequences of T and E. The first SOS! Help! is composed of two interjections and the second I am his date is a grammatical and sensible English sentence so both are valid messages. This answers the question succinctly by providing an example. $\endgroup$ – CJ Dennis Dec 10 '14 at 3:28
  • 2
    $\begingroup$ @CJDennis The question doesn't say that at all. It asks if there Morse strings are uniquely decipherable and if there's a way of listing all the strings that code to a given sequence if dots and dashes. It says nothing at all about the strings having to have meaning in English. $\endgroup$ – David Richerby Dec 11 '14 at 17:10
  • 2
    $\begingroup$ there is both a specific (counter)example and a general way to study the problem and both are relevant to good answer(s). see eg proofs/refutations by lakatos $\endgroup$ – vzn Dec 11 '14 at 19:02
  • 3
    $\begingroup$ "What does it say, ensign?" I AM HIS DATE "So Amelia decided to elope with old Noonan, hmmm. We should probably keep this to ourselves." $\endgroup$ – dotancohen Dec 12 '14 at 9:22
36
$\begingroup$

Quoting David Richerby from the comments:

Since ⋅ represents E and − represents T, any Morse message without spaces can be interpreted as a string in $\{E,T\}^*$

Further, since A, I, M, and N are represented by the four possible combinations of two morse characters (⋅-, ⋅⋅, --, -⋅, respectively), any message without spaces can also be interpreted as a string in $\{A,I,M,N\}^*\{E,T\}?$. Note that for any Morse message of length > 1, this is distinct from David's interpretation. Thus, the only messages with unique interpretations are those of length 1 (and, I suppose, 0, if that counts as a message) - that is, ⋅, representing E, and -, representing T.

Here's some JavaScript that will tell you all possible interpretations of a string of . and -. Strings of up to length 22 run in under a second, but anything higher than that starts getting pretty slow - I wouldn't, for example, try to decode HELLO WORLD with it. You can pop open a JavaScript console in your browser, paste this in, and then call, for example, decode('......-...-..---'). (In this example, entry #2446 is the intended string "HELLO".)

var decode = function(code) {
  var cache = {
    '0': ['']
  };
  for(var start = 0;start < code.length;start++) {
    for(var len = 1;len < 6;len++) {
      if(start + len > code.length) continue;
      if(!cache[start + len]) cache[start + len] = [];
      var curCode = code.slice(start, start + len);
      if(dict[curCode]) {
        for(var i_start = 0;i_start < cache[start].length;i_start++) {
          cache[start + len].push(cache[start][i_start] + dict[curCode]);
        }
      }
    }
  }
  return cache[code.length];
};

var dict = {
  '.-': 'A',
  '-...': 'B',
  '-.-.': 'C',
  '-..': 'D',
  '.': 'E',
  '..-.': 'F',
  '--.': 'G',
  '....': 'H',
  '..': 'I',
  '.---': 'J',
  '-.-': 'K',
  '.-..': 'L',
  '--': 'M',
  '-.': 'N',
  '---': 'O',
  '.--.': 'P',
  '--.-': 'Q',
  '.-.': 'R',
  '...': 'S',
  '-': 'T',
  '..-': 'U',
  '...-': 'V',
  '.--': 'W',
  '-..-': 'X',
  '-.--': 'Y',
  '--..': 'Z',
  '.----': '1',
  '..---': '2',
  '...--': '3',
  '....-': '4',
  '.....': '5',
  '-....': '6',
  '--...': '7',
  '---..': '8',
  '----.': '9',
  '-----': '0'
};

The code to prune it to only strings of real words is a bit longer, so I put it here. It runs under node.js and expects a file at /usr/share/dict/words-2500. The dictionary I'm using can be found here. It is not naive - it prunes as it goes, so it runs much faster on larger inputs.

The dictionary consists of a top-2500 words list I found on the internet somewhere, minus some 1-, 2-, and 3- letter combinations that I deemed not words. This algorithm is sensitive to having too many short words to choose from, and slows down drastically if you allow, say, every individual letter as a word (I'm looking at you, /usr/share/dict/words).

The algorithm finishes by sorting based on the number of words, so the "interesting" ones will hopefully be at the top. This works great on HELLO WORLD, running in under a second and returning the expected phrase as the first hit. From this I also learned that DATA SCIENTIST (the only other phrase I tried) morse codes the same as NEW REAL INDIA.

Edit: I searched for more interesting ones for a few minutes. The words SPACES and SWITCH are morsagrams. So far they're the longest single-word pair I've found.

$\endgroup$
  • 3
    $\begingroup$ Have you just invented the word morsagram ? I like it very much, but a web-search provided a single link - to this site. $\endgroup$ – BmyGuest Dec 11 '14 at 10:48
  • $\begingroup$ I have also taken the liberty to turn this interesting question into an open challenge on Puzzling.SE with some reference back to this posting here. $\endgroup$ – BmyGuest Dec 11 '14 at 11:17
  • $\begingroup$ @BmyGuest Yeah, that's a completely made-up word. I kinda like it, though. $\endgroup$ – Aaron Dufour Dec 11 '14 at 15:46
17
$\begingroup$

It is enough to observe that certain short combinations of letters give ambiguous decodings. A single ambiguous sequence suffices, but I can see the following:

ATE ~ P
EA ~ IT
MO ~ OM

etc. As David Richerby notes in the comments, any letter is equivalent to a string of Es and Ts, which makes Morse Code ambiguous as a way of encoding arbitrary sequences of letters; the above combinations show that this is true even of plausible letter combinations in English (for instance, MEAT ~ MITT). Perhaps an interesting coding exercise would be to find all strings of five or fewer letters which could be mistaken for something else, restricting to letter combinations that may actually be found in English text (using one or more words), grouped by equivalence class.

Using your original example, it also happens to be the case that

HELLO WORLD ~ HAS TEAM NO MAID TOE

and while the right-hand side is perhaps unrealistic even as a partial message, it is certainly a sequence of English words, and one that could be found in less than 15 minutes without computer assistance. This could be taken as evidence that many phrases in English could be misparsed as a different (possibly nonsensical) sequence of English words.

$\endgroup$
  • $\begingroup$ MT vs TM is a very short example. $\endgroup$ – Raphael Dec 9 '14 at 17:35
  • 2
    $\begingroup$ @Raphael MT == TM == O All three are the same sequence. That makes it very difficult to translate. $\endgroup$ – Red_Shadow Dec 9 '14 at 19:23
10
$\begingroup$

Morse Code is actually a ternary code, not a binary code, so the spaces are necessary. If spaces were not there, a lot of ambiguity would result, not so much with the entire message, but with individual letters.

For example, 2 dots is an I, but 3 dots is an S. If you are transcribing and you hear two dots, do you immediately write "I" or do you wait until you hear another dot (or dash)?

The answer is that each value is space separated so they are grouped together. When operators key messages in Morse, they make a pause of the same length as a dash after each letter code sequence to indicate the end of the sequence.

Even if you wrote an AI program to look at a full sentence at a time and figure out what was the logical interpretation of the message, there would still be many slight ambiguities and misspellings that would

$\endgroup$
  • 2
    $\begingroup$ Your last sentence seems to have been truncated. $\endgroup$ – David Richerby Dec 11 '14 at 19:40
  • 2
    $\begingroup$ @DavidRicherby Yes, that is because I tried to make post using Morse Code with no spaces. $\endgroup$ – Tyler Durden Dec 11 '14 at 19:46
4
$\begingroup$

a few notes not covered in other (good) answers but which dont generally research prior knowledge and cite any stuff (to me an intrinsic part of computer science).

  • this general theory of CS falls into the category of text segmentation and also "word splitting"/ "disambiguation" although there the theory is a bit different, its about splitting sequences of symbols into words (with variable letters), etc, where the symbols are units. here the strings are split into letters where letters have variable length, but the theory is analogous although not exactly 1-1. ie mapping between sentences-into-words, variable-word-letter-lengths, and sentences-into-words, variable-word/letter-lengths.

  • as others have pointed out this can be studied empirically. and someone did that from one angle (there are multiple ways to study this) and "published" the results on a web page with a big directory/ table of results.

    I found 25,787 ambiguous Morse code words. This is made of 10,330 distinct Morse strings. The highest frequency ambiguous Morse word has 13 possible donor words. The results are grouped below in tables based on the frequency of words that share the same Morse representation.

  • wow, "context matters"... a nearly identical question "translating morse code without spaces" on stackoverflow from 3yrs ago currently has 0 votes.

$\endgroup$
2
$\begingroup$

In general there are exponentially many possible decodings, but if you really want you can list them all. You can also list them in a succinct way, that is, give a succinct representation for all of them. Since this is nothing more than a programming exercise, I challenge you to do it yourself.

That said, the fact that there is ambiguity does not preclude the ability to decipher the message, or at least large parts of the message. Assuming a probabilistic model for the text represented by the Morse code – for definiteness, we can assume that it's English and use statistical properties of English – it may be possible to essentially decode the message, though some local ambiguities may be unavoidable. The reason is that most decodings correspond to non-sense plaintext. The way to do it is to extend the dynamic programming algorithm from the previous paragraph to estimate the likelihood of each decoding, and then choose the maximum likelihood decoding. This approach has more chance to succeed as the message gets longer.

$\endgroup$
  • $\begingroup$ Doesn't the Viterbi algorithm do something similar to what you described? Quantifying the exponential growth of the number of decodings, is that an appropriate question for here, or cstheory.SE? $\endgroup$ – john mangual Dec 9 '14 at 22:04
  • 1
    $\begingroup$ That's right, the idea is to use dynamic programming. Estimating the exponential growth probably fits here better than cstheory. $\endgroup$ – Yuval Filmus Dec 10 '14 at 6:27
  • $\begingroup$ actually, this is very similar to what is done to identify words in speech processing. The result is what is called a word lattice, that is a condensed representation of all the word sequences that could match the sound sequence analyzed. $\endgroup$ – babou Dec 11 '14 at 20:50
1
$\begingroup$

How to define/recognize/generate the language of all possible decodings.

Clearly, without spaces, the morse code is no longer uniquely decipherable.

It is however possible to give in a condensed form all the possible ways to decode it. This is actually similar to what is done in speech processing: from a unique stream of sounds (or of phonems), you have to find all the ways it can be decomposed in a sequence of words. The algorithms for doing this produce what is called a word lattice. You will find an example in the "lexical ambiguity" section of this answer.

In the case of binary Morse code (no spaces), you have only dots and dashes, but the problem is the same.

The way you can get all translations is as follow.

First you build Generalized Sequential Machine (GSM) $T$ that decodes the a Morse sentence. This is easily achieved by building a trie that recognizes Morse code. When a code is recognized, the corresponding letter/digit is output, and there is (non deterministically) an empty transition back to the root of the trie. But at the same time, the code word may be continued into a longer one (non-deterministically).

Then you take your Morse sequence $w$ of $n$ dashes and dots, and you read it as a linear finite state automaton $W$ with $n+1$ states (the positions between the dashes and dots, from $0$ to $n$) that generates this unique sentence, i.e. the singleton language $L=\{w\}=\mathcal L(W)$. What you want is the language of all translations $T(L)$. You know from general theorems that, since L is finite, hence regular, and since regular languages are closed under GSM mappings, that the language $T(L)$ is regular. So what you really want is a FSA that recognizes (or generates) that language.

For that purpose, you can simply apply a standard cross-product construction, similar to the one used for the intersection of two regular languages, to the two finites states devices $T$ and $W$. The transition are chosen so that you mimic both the transducer $T$ and the FSA $W$. You easily get a FSA that defines the regular language of all translations.

The details are easily worked out. But ask if you need more.

$\endgroup$
0
$\begingroup$

Some pseudo-code for a solver that will give all possible interpretations. This is based on a few quick thoughts, so additional input would be welcome. Method accepts two inputs one of the text so far translated, and the second of morse code.

MorseSolver (string textSoFar, string codeRemaining)
{
    if(codeRemaining length == 0) output textSoFar
    else
    {
        codeLength = length of code remaining
        read 1 through (min of 5 or codeLength) characters from codeRemaining
        for each set of characters
        {
            call an IsMorseCode method that checks if the characters 
              input are valid morse code
            if they are valid add the translated character to textSoFar 
              and remove the characters from codeRemaining, then call 
              the MorseSolver again with the new strings)
        }

}

This will output all the possible combinations of letters and numbers without any spaces between "words". If you wanted to prove the ambiguity, this would certainly do it. If you wanted to get some meaningful messages out, then try looking for code meant to translate hashtags into readable language.

Using the above, I wrote a program in C# which does the above. I stopped it from running at 22 million possibilities for the above string that can translate to hello world. The Morse Code equivalent of "Hello" resulted in 20,569 possible results. I also did not include the numbers. That would be higher if I allowed them.

$\endgroup$
  • $\begingroup$ The output of such an algorithm would be a proof that any individual string is ambiguous but it wouldn't prove that all strings are ambiguous. $\endgroup$ – David Richerby Dec 9 '14 at 20:29
  • $\begingroup$ @DavidRicherby All strings of length > 1 are ambiguous. That has been proven elsewhere on this page. I was attempting to answer the second part of the question, and provide a means to extrapolate all possible solutions from a string. $\endgroup$ – Red_Shadow Dec 9 '14 at 20:58
  • $\begingroup$ Just out of curiosity, would you share your C# program? My Perl version comes up with 19796 possible solutions for the "HELLO" equivalent. Most probably I forgot to output some cases though... $\endgroup$ – Squeezy Dec 9 '14 at 22:32
  • 1
    $\begingroup$ Real source code is offtopic here; please publish it elsewhere (pastebin, Gist, ...) and only link to it. $\endgroup$ – Raphael Dec 11 '14 at 16:33

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