{"id":2383,"date":"2017-03-20T12:00:05","date_gmt":"2017-03-20T17:00:05","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=2383"},"modified":"2017-04-05T09:39:07","modified_gmt":"2017-04-05T14:39:07","slug":"morse-code-binary-trees-and-graphs","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2017\/03\/20\/morse-code-binary-trees-and-graphs\/","title":{"rendered":"Morse Code, Binary Trees and Graphs"},"content":{"rendered":"\r\n<div class=\"content\"><!--introduction--><p>A binary tree is an elegant way to represent and process Morse code. The new MATLAB graph object provides an elegant way to manipulate binary trees.  A new app, <tt>morse_tree<\/tt>, based on this approach, is now available in version 2.40 of <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">Cleve's Laboratory<\/a>.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#980ba6ec-f9a1-4dcd-8d92-de902770f768\">EXM chapter<\/a><\/li><li><a href=\"#0cd5850a-a68b-4ad6-9646-ecf04755ccf1\">Binary trees<\/a><\/li><li><a href=\"#7a59878e-dd39-47e1-8edc-1d67bace8026\">Morse code<\/a><\/li><li><a href=\"#2b5f287f-bda2-4425-a731-b03a6438a448\">Morse tree<\/a><\/li><li><a href=\"#098ae215-2d48-4d45-9069-e042373b0394\">Extensions<\/a><\/li><li><a href=\"#3a186e4b-bba6-4fd5-8985-c1c76d60465a\">morse_tree app<\/a><\/li><\/ul><\/div><h4>EXM chapter<a name=\"980ba6ec-f9a1-4dcd-8d92-de902770f768\"><\/a><\/h4><p>I have a <a href=\"https:\/\/www.mathworks.com\/content\/dam\/mathworks\/mathworks-dot-com\/moler\/exm\/chapters\/morse.pdf\">chapter on Morse Code<\/a> and binary trees in <i>Experiments with MATLAB<\/i>. Some of this blog post is taken from that chapter.  But today's implentation is much more, as I said, elegant.  In <i>EXM<\/i> I represented a binary tree as a cell array of cell arrays.  Now I am using clever indexing into a linear character string, together with the MATLAB graph object.  The resulting code is much shorter and more readable.<\/p><h4>Binary trees<a name=\"0cd5850a-a68b-4ad6-9646-ecf04755ccf1\"><\/a><\/h4><p>Here's all we have to do to get a picture of a binary tree. First we create the adjacency matrix and view its spy plot.<\/p><pre class=\"codeinput\">   n = 31;\r\n   j = 2:n;\r\n   k = floor(j\/2);\r\n   A = sparse(k,j,1,n,n);\r\n   spy(A)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/morse_blog_01.png\" alt=\"\"> <p>Then we create and plot the directed graph.  The MATLAB <tt>digraph<\/tt>  object, and its supporting <tt>plot<\/tt> method, are doing all of the work.<\/p><pre class=\"codeinput\">   G = digraph(A);\r\n   Gp = plot(G);\r\n   set(gca,<span class=\"string\">'xtick'<\/span>,[],<span class=\"string\">'ytick'<\/span>,[])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/morse_blog_02.png\" alt=\"\"> <p>This is the complete binary tree with five levels, and consequently $2^5-1$ nodes. (In defiance of nature, computer scientists put the <i>root<\/i> of a tree at the top.)<\/p><p>Follow the nodes in numerical order, from top to bottom and left to right.  You are doing a <i>breadth first traversal<\/i> of the structure. The <i>successors<\/i> of the node with index <i>j<\/i> have indices <i>2j<\/i> and <i>2j+1<\/i>. This makes old-fashioned linear indexing possible.<\/p><p>I want to save the coordinates of the nodes for use in the layout in my next plot.<\/p><pre class=\"codeinput\">   x = Gp.XData;\r\n   y = Gp.YData;\r\n<\/pre><h4>Morse code<a name=\"7a59878e-dd39-47e1-8edc-1d67bace8026\"><\/a><\/h4><p>Morse code is no longer important commercially, but it still has some avid fans among hobbyists. Morse code was invented over 150 years ago, not by Samuel F. B. Morse, but by his colleague, Alfred Vail.  It has been in widespread use ever since.  The code consists of short <i>dots<\/i>, '.', and longer <i>dashes<\/i>, '-', separated by short and long spaces. You may be familiar with the international distress signal, '... --- ...', the code for \"SOS\", abbreviating \"Save Our Ships\" or perhaps \"Save Our Souls\".  But did you notice that some modern cell phones signal '... -- ...', the code for \"SMS\", indicating activity of the \"Short Message Service\".<\/p><p>Until 2003, a license to operate an amateur radio in the US required minimal proficiency in Morse code.  When I was in junior high school, I learned Morse code to get my ham license, and I've never forgotten it.<\/p><p>According to Wikipedia, in 2004, the International Telecommunication Union formally added a code for the ubiquitous email character, @, to the international Morse code standard.  This was the first addition since World War I.<\/p><h4>Morse tree<a name=\"2b5f287f-bda2-4425-a731-b03a6438a448\"><\/a><\/h4><p>I could provide a table showing that '.-' is the code for A, '-...' the code for B, and so on.  But I'm not going to do that, and my MATLAB program does not have such a table.  As far as I am concerned, Morse code is <i>defined<\/i> by a MATLAB statement containing the 26 upper case letters of the English language, an asterisk, and four blanks.<\/p><pre class=\"codeinput\">    morse = <span class=\"string\">'*ETIANMSURWDKGOHVF L PJBXCYZQ  '<\/span>;\r\n<\/pre><p>The asterisk at the start serves as the root of the tree. The four blanks will correspond to four missing nodes in the bottom level of the tree.  So the binary tree is not going to be complete. The automatic layout in  the <tt>graph\/plot<\/tt> method does not draw a perfect tree.  This is why I saved the node coordinates from the plot of the full tree. Let's remove the rows and columns of these potentially unlabeled nodes from the adjacency matrix, and the coordinates.<\/p><pre class=\"codeinput\">    m = find(morse == <span class=\"string\">' '<\/span>);\r\n    A(:,m) = [];\r\n    A(m,:) = [];\r\n    x(m) = [];\r\n    y(m) = [];\r\n<\/pre><p>Convert the character array into a cell array of individual chars.<\/p><pre class=\"codeinput\">    nodes = num2cell(morse);\r\n    nodes(m) = <span class=\"string\">''<\/span>;\r\n<\/pre><p>Create the directed graph with these node labels.<\/p><pre class=\"codeinput\">    G = digraph(A,nodes);\r\n<\/pre><p>Plot the graph, using the layout saved from the full tree.<\/p><pre class=\"codeinput\">    plot(G,<span class=\"string\">'xdata'<\/span>,x,<span class=\"string\">'ydata'<\/span>,y, <span class=\"keyword\">...<\/span>\r\n        <span class=\"string\">'showarrows'<\/span>,<span class=\"string\">'off'<\/span>);\r\n    set(gca,<span class=\"string\">'xtick'<\/span>,[],<span class=\"string\">'ytick'<\/span>,[])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/morse_blog_03.png\" alt=\"\"> <p>If you follow the links downward and emit a <i>dot<\/i> when you go left and a <i>dash<\/i> when you go right, you have Morse code.  For example start at the root, go left once, then right once.  You will reach A and will have generated '.-', the code for A.<\/p><p>Morse code is already present in the defining character vector <tt>morse<\/tt>, even before we create and plot a graph. The character with index <tt>5<\/tt> is <tt>A<\/tt>.  The characters with indices <tt>2*5<\/tt> and <tt>2*5+1<\/tt> are <tt>R<\/tt> and <tt>W<\/tt>.<\/p><pre class=\"codeinput\">    j = 5;\r\n    morse(j)\r\n    morse(2*j:2*j+1)\r\n<\/pre><pre class=\"codeoutput\">ans =\r\n    'A'\r\nans =\r\n    'RW'\r\n<\/pre><p>Consequently, the Morse code for R and W is '.-.' and '.--'. This works everywhere in the first half of <tt>morse<\/tt>. The characters in the second half don't (yet) have successors.<\/p><h4>Extensions<a name=\"098ae215-2d48-4d45-9069-e042373b0394\"><\/a><\/h4><p>Morse code can be extended by replacing the blanks in the basic tree with characters that are not in the 26 letter English alphabet and adding two more levels to the tree.  Several different extensions have been in use at different times and different regions of the world. The <a href=\"https:\/\/en.wikipedia.org\/wiki\/Morse_code\">Wikipedia page<\/a> for Morse code includes a binary tree with some commonly used extensions. The fifth level includes the 10 decimal digits, several non-Latin chacters, and a few punctuation marks.  The sixth level includes several punctuation marks.<\/p><h4>morse_tree app<a name=\"3a186e4b-bba6-4fd5-8985-c1c76d60465a\"><\/a><\/h4><p>Here is a screen shot from the new app, <tt>morse_tree<\/tt>, that is available in version 2.40 of <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">Cleve's Laboratory<\/a>. Clicking  on the toggle labeled \"extend\" shows two more levels of the tree and some extensions, although not many as Wikipedia's tree. Clicking on a node in our tree highlights that node while the sound of the corresponding code is played.  This screen shot shows A highlighted.<\/p><p>Text entered in the box below the tree will be encoded and the sound played.<\/p><p>The speed of the generated code is set by the control currently labeled \"5 wpm\", for five words per minute.<\/p><pre class=\"codeinput\">   morse_tree_extended\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/morse_blog_04.png\" alt=\"\"> <p>Here's a snap quiz: What is Morse code for the @ sign? Download <tt>morse_tree<\/tt> to check your answer.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_947b15a050fb4f9d902c4b56fe419943() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='947b15a050fb4f9d902c4b56fe419943 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 947b15a050fb4f9d902c4b56fe419943';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2017 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_947b15a050fb4f9d902c4b56fe419943()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2017a<br><\/p><\/div><!--\r\n947b15a050fb4f9d902c4b56fe419943 ##### SOURCE BEGIN #####\r\n%% Morse Code, Binary Trees and Graphs\r\n% A binary tree is an elegant way to represent and process Morse code.\r\n% The new MATLAB graph object provides an elegant way to manipulate\r\n% binary trees.  A new app, |morse_tree|, based on this approach, is now\r\n% available in version 2.40 of\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\r\n% Cleve's Laboratory>.\r\n\r\n%% EXM chapter\r\n% I have a\r\n% <https:\/\/www.mathworks.com\/content\/dam\/mathworks\/mathworks-dot-com\/moler\/exm\/chapters\/morse.pdf\r\n% chapter on Morse Code> and binary trees in _Experiments with MATLAB_.\r\n% Some of this blog post is taken from that chapter.  But today's\r\n% implentation is much more, as I said, elegant.  In _EXM_ I represented\r\n% a binary tree as a cell array of cell arrays.  Now I am using clever\r\n% indexing into a linear character string, together with the MATLAB graph\r\n% object.  The resulting code is much shorter and more readable.\r\n\r\n%% Binary trees\r\n% Here's all we have to do to get a picture of a binary tree.\r\n% First we create the adjacency matrix and view its spy plot.\r\n\r\n   n = 31;\r\n   j = 2:n;\r\n   k = floor(j\/2);\r\n   A = sparse(k,j,1,n,n);\r\n   spy(A)\r\n   \r\n%%\r\n% Then we create and plot the directed graph.  The MATLAB |digraph|\r\n%  object, and its supporting |plot| method, are doing all of the work.\r\n\r\n   G = digraph(A);\r\n   Gp = plot(G);\r\n   set(gca,'xtick',[],'ytick',[])\r\n   \r\n%%\r\n% This is the complete binary tree with five levels,\r\n% and consequently $2^5-1$ nodes.\r\n% (In defiance of nature, computer scientists put the _root_ of a tree\r\n% at the top.)\r\n   \r\n%%\r\n% Follow the nodes in numerical order, from top to bottom and left\r\n% to right.  You are doing a _breadth first traversal_ of the structure.\r\n% The _successors_ of the node with index _j_ have indices _2j_ and _2j+1_.\r\n% This makes old-fashioned linear indexing possible.\r\n\r\n%%\r\n% I want to save the coordinates of the nodes for use in the layout in\r\n% my next plot.\r\n\r\n   x = Gp.XData;\r\n   y = Gp.YData;\r\n   \r\n%% Morse code\r\n% Morse code is no longer important commercially, but it still has some\r\n% avid fans among hobbyists.\r\n% Morse code was invented over 150 years ago, not by Samuel F. B. Morse, \r\n% but by his colleague, Alfred Vail.  It has been in widespread use ever \r\n% since.  The code consists of short _dots_, '.', and longer _dashes_,\r\n% '-', separated by short and long spaces.\r\n% You may be familiar with the international distress signal, \r\n% '... REPLACE_WITH_DASH_DASH- ...', the code for \"SOS\", abbreviating \"Save Our Ships\"\r\n% or perhaps \"Save Our Souls\".  But did you notice that some modern cell\r\n% phones signal '... REPLACE_WITH_DASH_DASH ...', the code for \"SMS\", indicating activity\r\n% of the \"Short Message Service\".\r\n\r\n%%\r\n% Until 2003, a license to operate an amateur radio in the US required\r\n% minimal proficiency in Morse code.  When I was in junior high school, I\r\n% learned Morse code to get my ham license, and I've never forgotten it.\r\n\r\n%%\r\n% According to Wikipedia, in 2004, the International Telecommunication\r\n% Union formally added a code for the ubiquitous email character, @,\r\n% to the international Morse code standard.  This was the first addition\r\n% since World War I.\r\n\r\n%% Morse tree\r\n% I could provide a table showing that '.-' is the code for A,\r\n% '-...' the code for B, and so on.  But I'm not going to do that,\r\n% and my MATLAB program does not have such a table.  As far as I am\r\n% concerned, Morse code is _defined_ by a MATLAB statement containing\r\n% the 26 upper case letters of the English language, an asterisk, and\r\n% four blanks.\r\n    \r\n    morse = '*ETIANMSURWDKGOHVF L PJBXCYZQ  ';\r\n     \r\n%% \r\n% The asterisk at the start serves as the root of the tree.\r\n% The four blanks will correspond to four missing nodes in the bottom\r\n% level of the tree.  So the binary tree is not going to be complete.\r\n% The automatic layout in  the |graph\/plot| method does not draw a\r\n% perfect tree.  This is why I saved the node coordinates from the\r\n% plot of the full tree.\r\n% Let's remove the rows and columns of these potentially unlabeled\r\n% nodes from the adjacency matrix, and the coordinates.\r\n\r\n    m = find(morse == ' ');\r\n    A(:,m) = [];\r\n    A(m,:) = [];\r\n    x(m) = [];\r\n    y(m) = [];\r\n    \r\n%%\r\n% Convert the character array into a cell array of individual chars.\r\n\r\n    nodes = num2cell(morse);\r\n    nodes(m) = '';\r\n    \r\n%%\r\n% Create the directed graph with these node labels.\r\n\r\n    G = digraph(A,nodes);\r\n\r\n%%\r\n% Plot the graph, using the layout saved from the full tree.\r\n\r\n    plot(G,'xdata',x,'ydata',y, ...\r\n        'showarrows','off');\r\n    set(gca,'xtick',[],'ytick',[])\r\n    \r\n%%\r\n% If you follow the links downward and emit a _dot_ when you go left\r\n% and a _dash_ when you go right, you have Morse code.  For example\r\n% start at the root, go left once, then right once.  You will reach A\r\n% and will have generated '.-', the code for A.\r\n\r\n%%\r\n% Morse code is already present in the defining character vector |morse|,\r\n% even before we create and plot a graph.\r\n% The character with index |5| is |A|.  The characters with indices\r\n% |2*5| and |2*5+1| are |R| and |W|.\r\n\r\n    j = 5;\r\n    morse(j)\r\n    morse(2*j:2*j+1)\r\n    \r\n%%\r\n% Consequently, the Morse code for R and W is '.-.' and '.REPLACE_WITH_DASH_DASH'.\r\n% This works everywhere in the first half of |morse|.\r\n% The characters in the second half don't (yet) have successors.\r\n\r\n%% Extensions\r\n% Morse code can be extended by replacing the blanks in the basic tree\r\n% with characters that are not in the 26 letter English alphabet and\r\n% adding two more levels to the tree.  Several different extensions\r\n% have been in use at different times and different regions of the world.\r\n% The <https:\/\/en.wikipedia.org\/wiki\/Morse_code Wikipedia page> for\r\n% Morse code includes a binary tree with some commonly used extensions.\r\n% The fifth level includes the 10 decimal digits, several non-Latin\r\n% chacters, and a few punctuation marks.  The sixth level includes\r\n% several punctuation marks.\r\n\r\n%% morse_tree app\r\n% Here is a screen shot from the new app, |morse_tree|, that is\r\n% available in version 2.40 of\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\r\n% Cleve's Laboratory>.\r\n% Clicking  on the toggle labeled \"extend\" shows two more levels of the\r\n% tree and some extensions, although not many as Wikipedia's tree.\r\n% Clicking on a node in our tree highlights that node while the sound of\r\n% the corresponding code is played.  This screen shot shows A highlighted.\r\n\r\n%%\r\n% Text entered in the box below the tree will be encoded and the sound\r\n% played.\r\n\r\n%%\r\n% The speed of the generated code is set by the control\r\n% currently labeled \"5 wpm\", for five words per minute.  \r\n\r\n   morse_tree_extended\r\n   \r\n%%\r\n% Here's a snap quiz: What is Morse code for the @ sign?\r\n% Download |morse_tree| to check your answer.\r\n\r\n\r\n##### SOURCE END ##### 947b15a050fb4f9d902c4b56fe419943\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/morse_blog_03.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction--><p>A binary tree is an elegant way to represent and process Morse code. The new MATLAB graph object provides an elegant way to manipulate binary trees.  A new app, <tt>morse_tree<\/tt>, based on this approach, is now available in version 2.40 of <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">Cleve's Laboratory<\/a>.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2017\/03\/20\/morse-code-binary-trees-and-graphs\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":2409,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[11,5,23,4],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2383"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=2383"}],"version-history":[{"count":5,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2383\/revisions"}],"predecessor-version":[{"id":2393,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2383\/revisions\/2393"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/2409"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=2383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=2383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=2383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}