第2章 编码与组合
莫尔斯码（Morse Code）是由塞缪尔·莫尔斯发明的（1791-1872），在本书的其他章节中我们还将频繁地提到他。莫尔斯码其实是伴随着电报机的问世而被发明的，关于电报机，我们在后面也将做详细的探讨。正如通过研究莫尔斯码我们可以很方便地理解编码的本质一样，通过电报机来了解计算机硬件也是个不错的途径。
大多数人都会发现莫尔斯码的发送比接收更为简单。即使你并没有熟记莫尔斯码，也可以很方便地使用下面这张按字母表顺序排列的表格。
| 字母 | 摩斯密码 | 字母 | 摩斯密码 | 字母 | 摩斯密码 |
|---|---|---|---|---|---|
| A | .- | J | .--- | S | ... |
| B | -... | K | -.- | T | - |
| C | -.-. | L | .-.. | U | ..- |
| D | -.. | M | -- | V | ...- |
| E | . | N | -. | W | .-- |
| F | ..-. | O | --- | X | -..- |
| G | --. | P | .--. | Y | -.-- |
| H | .... | Q | --.- | Z | --.. |
| I | .. | R | .-. |
比起发送莫尔斯码，接收编码并进行解码要费时费力很多，因为译码者不得不根据一串由“点”、“划”组成的晦涩的编码序列来反查字母。例如，如果你接收到一串形如“划-点-划-划”的编码，那么你就必须从表的第一个字母开始逐个搜寻，直到找到与这串编码相符的字母“Y”为止。
问题就出在这里，因为我们现在只有一张提供“字母 → 莫尔斯码”的编码表，而缺少一张可以实现反向查询的“莫尔斯码 → 字母”译码表。在开始学习莫尔斯码的初级阶段，如果有这样的一个表无疑将是很方便的。但是要建立这样一张表，谈何容易。似乎这些字母对应的“点-划”序列并没有什么规律。
所以忘掉字母序列吧。或许根据编码中所包含点、划的多少来对其进行分组，是一个更好的组织这些编码的方法。例如，一个仅包含一个点或一个划的莫尔斯码只能代表两个字母：“E”或“T”。
| 摩斯密码 | 字母 |
|---|---|
. | E |
- | T |
一组含有 2 个点或划的编码组合，可以给我们呈现出4个字母——I，A，N 和 M。
| 摩斯密码 | 字母 | 摩斯密码 | 字母 |
|---|---|---|---|
.. | I | -. | N |
.- | A | -- | M |
一组含有 3 个点或划的莫尔斯码可以为我们表示更多的字母。
| 摩斯密码 | 字母 | 摩斯密码 | 字母 |
|---|---|---|---|
... | S | -.. | D |
..- | U | -.- | K |
.-. | R | --. | G |
.-- | W | --- | O |
最后（如果我们不想考虑存在数字和标点符号的莫尔斯码的情况），一串由4个点或划组成的莫尔斯码就可以表示 16 个字符。
| 摩斯密码 | 字母 | 摩斯密码 | 字母 |
|---|---|---|---|
.... | H | -... | B |
...- | V | -..- | X |
..-. | F | -.-. | C |
..-- | Ü | -.-- | Y |
.-.. | L | --.. | Z |
.-.- | Ä | --.- | Q |
.--. | P | ---. | Ö |
.--- | J | ---- | Ş |
综合以上数据来看，这四张表包含了 2+4+8+16 组码字，总共表示了 30 个字母，比拉丁字母表的26字母还要多出 4 个。所以，你会注意到最后一个表中有 4 组编码是用来表示重音字母的。
当有人给你发送莫尔斯码的时候，上述四张表可能会让你的解码工作变得轻松很多。当接收到某一代表特定字母的码字后，你就可以知道其中所包含的“点”和“划”的数目，那么你至少可以很快找到对应的表格去进行查找。每个表格都组织得很规整，全部是“点”的码字被排在左上角，而全部是“划”的则被排在右下角。
你发现这四张表格在大小上的规律了么？注意看，每个表格所包含的码字数目都是前一张的两倍。这其实很好理解：每个表格所含有的码字，可以看成是在前一张表格所包含的全部码字上再加一个“点”，或者再加一个“划”而组成的新码字。
我们可以用如下这样一个列表来总结这个有趣的规律。
| 点和划的数目 | 码字的数目 |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
在这四个表中，每张表的码字数都是前一张表码字数量的两倍，因此如果第一张表含有 2 个码字，那么第二张表则含有 2 x 2 个码字，而第三个表就有 2 x 2 x 2 个码字。下面用另一种方式呈现这个规律。
| 点和划的数目 | 码字的数目 |
|---|---|
| 1 | 2 |
| 2 | 2 × 2 |
| 3 | 2 × 2 × 2 |
| 4 | 2 × 2 × 2 × 2 |
当然，如果我们遇到了数字的自乘，就可以通过幂的方式来表示它。例如 2 x 2 x 2 x 2 就可以记作 2⁴（2 的 4 次幂）。数字 2、4、8 和 16 都是以 2 为底数的幂值，因为你可以通过使其自身乘 2 来得到它们。由此我们的总结列表也可以写成下面这种样子。
| 点和划的数目 | 码字的数目 |
|---|---|
| 1 | 2¹ |
| 2 | 2² |
| 3 | 2³ |
| 4 | 2⁴ |
现在这个表已经变得很简洁了。如果知道了码字中“点”和“划”的数目，那么以这个数目为指数的 2 的幂运算结果就是其总共可以表示的码字数。我们可以用下面这个简单的公式来概括上述表格所表示的内容：
码字的数目 = 2“点”和“划”的数目
使用 2 的幂值的形式可以表示很多码字，在下一章中，我们还将接触另外一个例子。
为了让莫尔斯码的解码过程更加简单，或许画张图会有所帮助，例如下面这张树型图。
这张图给出了所有字母及其所对应的由“点”和“划”组成的连续序列。当对一串码字进行解码时，我们需要沿着箭头从左向右进行搜寻。以“点-划-点”的码字为例来说，当你需要找出这串码字所代表的字母时，应首先从图的左边开始，选择“点”的分支；然后继续沿着箭头向右选择“划”，接着又是一个“点”。找到最后一个“点”时结果就会紧随其后出现了，没错就是字母“R”。
如果仔细想一想，你就会发现构建这样一个表对于定义莫尔斯码规范来说是很有必要的。首先，它确保了我们不会对不同的字母定义相同的码字。其次，通过这个表我们可以用尽可能短的码字来表示所有的字母，而避免产生编码长度上的浪费。
我们可以继续加长码字至 5 位或者更长，不过这可能超出页面打印边界。