What is good algorithm to decode morse code strings?

Question

moorse_string[] = {".-",      //  0 = A ('A' = ASCII code 65; 'a' = ASCII code 97)
                       "-...",    //  1 = B
                       "-.-.",    //  2 = C
                       "-..",     //  3 = D
                       ".",       //  4 = E
                       "..-.",    //  5 = F
                       "--.",     //  6 = G
                       "....",    //  7 = H
                       "..",      //  8 = I
                       ".---",    //  9 = J
                       "-.-",     // 10 = K
                       ".-..",    // 11 = L
                       "--",      // 12 = M
                       "-.",      // 13 = N
                       "---",     // 14 = O
                       ".--.",    // 15 = P
                       "--.-",    // 16 = Q
                       ".-.",     // 17 = R
                       "...",     // 18 = S
                       "-",       // 19 = T
                       "..-",     // 20 = U
                       "...-",    // 21 = V
                       ".--",     // 22 = W
                       "-..-",    // 23 = X
                       "-.--",    // 24 = Y
                       "--..",    // 25 = Z
                       "-----",   // 26 = 0 (ASCII code 48)
                       ".----",   // 27 = 1
                       "..---",   // 28 = 2
                       "...--",   // 29 = 3
                       "....-",   // 30 = 4
                       ".....",   // 31 = 5
                       "-....",   // 32 = 6
                       "--...",   // 33 = 7
                       "---..",   // 33 = 8
                       "----.",   // 34 = 9
                       "--..--",  // 36 = , (ASCII code 44)
                       ".-.-.-"   // 37 = . (ASCII code 46)
                      }

Only thing I can think of is to match each string of code with the array of strings above until a match is found. I want to think of a better way to decode this without brute force. For example, if I have "..---". This is located at 28 index of the array. and My code now looks from 0 - 28 and finds a match and breaks. Please suggest better ideas thanks.

I want to handle following list of chars only:

and Morse encodings within a word are separated by a single space. Spaces between words and new lines are separated by three spaces.

Answer does not have to be code, but codes are accepted. Answer can be any valid suggestions that explain the logic wholly in words(atleast). I just want to explore different way of thinking. Any answer that is different from what I suggested will be accepted even if it is a worse algorithm. But if there is 2 answers then the more elegant one will be accepted. I am not asking for the solution but ideas. How would you approach the problem? and why? What is the logic that drives the algorithm? If you consider you way better than what I suggested then why?

Answer 1

You could build a tree where each node has a name and two children ("Dot" and "Dash").

For --., you'd:

• Look at the Dash child of the tree's root node.
• Go to its Dash child.
• Then go to that node's Dot child.
• Then take the name of the node "G".

For --.-, you'd do the same thing, but instead of taking the "G", you go to "Dash" and then find that it's "Q".

This is basically the way that people process the code and anticipate the target letter while they are listening to it; they get the --., and wait for the next sound to determine whether it is a "G", or perhaps a "Q", "Z", "7", or ",".

Answer 2

What you suggest is already a good method. It is what I would recommend. It is simple and easy to implement. That is a good thing. Generally, those qualities mean that it takes less time for the programmer to implement, and is less likely to have subtle bugs. Normally, as a first starting point, we want to optimize for reducing programmer time, even if it takes the computer a little longer, because the programmer's time is far more expensive than the computer's. Only if the resulting code is too slow do we begin to examine more sophisticated algorithms and data structures.

Here are two pithy quotes I like that capture these sentiments well:

• "Premature optimization is the root of all evil." - sometimes attributed to Donald Knuth. (See https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize, https://softwareengineering.stackexchange.com/q/80084/34181)

• "Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." - sometimes attributed to Brian Kernighan. (See http://www.linusakesson.net/programming/kernighans-lever/)

That said, if you want a fancier data structure, a trie would be appropriate. It might yield better performance (or it might not, depending on memory hierarchy and cache effects).