モールス信号はデータ圧縮の元祖？（386号）

2024年の記事もこの386号が最後となります。
一年間のご愛読をありがとうございました。
また、来年もよろしくご愛読のほどをお願いいたします。

さて、前回(385号)のランレングス法の話を書いている時に知ったのですが、高校の情報Iの教科書にはランレグス法の記載があるようです。
情報Iというのは、必須の教科ですので、イマドキの高校生はごく普通にランレングス法を習っているということになります。すごい時代になったものです。

また、その発展形としてのハフマン法の記載まであるようで、改めて教科書という書籍のレベルの高さに驚きました。

別に教科書に対抗しようというわけではありませんが、それならハフマン法の話を書いてみようじゃないか、というのが今回（と次号）のお題になります。

モールス信号

モールス信号という言葉は知ってるよという方が多いと思います。
名前を知らずとも、トン、ツーと言えばわかる方もおられるかもしれません。
電波や光を使って船から信号を送る様子は、映画などでよく使われますよね。アレです。

モールス信号の発明者はサミュエル＝モールス（Samuel Morse）で、1840年代のことのようですから、もう200年近くも前の話です。
まだラジオが影も形もない時代です。その時代に文字情報を素早く遠地に伝えられるのは画期的なことだったのでしょう。

さて、このモールス信号のトン、ツーの音はアルファベットの各文字に割り当てられています。これ自体が世界初の文字コードのようですが、とても興味深い内容なのです。

一部を抜粋します。なお、表中の「・」が短音（トン）、「－」が長音（ツー）を示します。

　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つ）、そうでない文字は長く（最長で4つ）なっているように見えます。

この点をもう少し調べてみましょう。

なぜＥが「・」なのか？

英語ではアルファベットの使用率にかなりの偏りがあることが知られています。
例えば、母音（A,E,I,O,U）はよく使われますが、子音の一部（J,Q,Xなど）は使用頻度がグッと落ちます。
特に良く使われる文字はE,T,A,O,Iといったあたりです。中でもＥの使用率は高く10％を越えるそうです。

さて、モールス信号の表を「・」と「－」の個数をかぞえてみます。
例えば、Ａなら「・－」ですから、2個という風にです。
その結果は次のようになります。

　1個　E T
　2個　A I M N
　3個　D G K O R S U W
　4個　B C F H J L P Q V X Y Z

これを見ると、英語でよく使われる文字ほど少ない数で表現されていることがわかります。
モールス信号が発明された時点では自動機械なんてありませんから、キーパンチャー（繰作者）が手作業で信号を送ります。
作業者の負担を減らす方法として、よく使う文字は入力しやすくしたのだと思われます。

その結果、一番使うＥは一番短かい「・」が割り当てられたのでしょう。

モールス信号の送出時間

次は少し視点を変え、各文字の送出時間に目を向けてみます。

最初の表を送信時間に着目して、書き換えます。

モールス信号では信号を送出する時のルールが決まっていて、「・」を送出する時間を1単位とすると、「－」を送出するのは3単位の時間で送出することになっています。

また、文字の最後には小休止として、3単位の無音時間を置くことになっています。
（余談）小休止の必要性
これは、文字の混同を避けるためです。
例えば「－・・－」というパターンを受信した場合を考えます。
これが1文字と考えればX（エックス）ですが、ひょっとすると「－」「・」「・」「－」の４文字（TEET）かもしれませんし、「－・」「・」「－」の３文字（NET)や、「－」「・－」「－」（TAT）かもしれません。
このように信号の羅列だと複数の意味に解釈できてしまいます。そのため、モールス信号では小休止の時間を定めて、そこで文字の区切りであることを示すことになっています。
（余談終わり）

ここでは1単位を0.1秒、つまり「・」の送信に0.1秒、「－」の送信に0.3秒、小休止に0.3秒かかるものとして計算してみます。
この計算結果を送信時間の短かい順に並べ直すとこうなります。

　0.4秒　E
　0.6秒　S T
　0.7秒　A H N
　0.8秒　D R U
　0.9秒　B F I L M V
　1.0秒　G K W
　1.1秒　C P X Z
　1.2秒　O
　1.3秒　J Q Y

Eの0.4秒が飛び抜けて短かく、JやQはEのその3倍以上の1.3秒を必要とします。
全体として見た時には正規分布のグラフのように、まん中が膨らんでいる点も興味深いですね。

モールス信号による効果

さて、その工夫の効果を確認してみましょう。
いくつか適当な単語を選んで送信に要する時間を見てみます。
まずはよく使われる、E,A,Tあたりがたくさん出てくる単語です。

　TEA＝1.7秒　（0.6＋0.4＋0.7）
　REST＝2.4秒　（0.8＋0.4＋0.6＋0.6）
　ERASE＝2.9秒　（0.4＋0.8＋0.7＋0.6＋0.4）
　STREET＝3.4秒　（0.6＋0.6＋0.8＋0.4＋0.4＋0.6）
　STUDENT＝4.5秒　（0.6＋0.6＋0.8＋0.8＋0.4＋0.7＋0.6）

前章の表を見ますと、最頻値（最も多くの文字が出てくる秒数）は0.9秒でした。
ということは、送出時間の平均的な期待値は次のようになります。
　3文字：0.9×3＝2.7秒
　4文字：0.9×4＝3.6秒
　5文字：0.9×5＝4.5秒
　6文字：0.9×6＝5.4秒
　7文字：0.9×7＝6.3秒

両者を比較すると、モールス信号の優秀さがわかります。

この優れたモールス信号ですが、C,J,P,Yといった時間のかかる文字が多い単語だと状況がかわります。

　JOY=3.8秒　（1.3＋1.2＋1.3）
　ZOOM=4.4秒　（1.1＋1.2＋1.2＋0.9）
　HAPPY＝4.9秒　（0.7＋0.7＋1.1＋1.1＋1.3）
　PEOPLE＝5.1秒　（1.1＋0.4＋1.2＋1.1＋0.9＋0.4）
　POLYGON＝6.2秒　（1.1＋1.2＋0.9＋1.3＋1.0＋1.2＋0.7)

これも上の期待値と比べると、かなり悪い数字となっていることがわかります。

ここでわかる点は２つあります。
一つは、どの文字をどのシンボルに割り当てるかが非常に重要であるという点、もう一つはどんなに優秀な組み合わせを考えても、非効率になるパターンは必ず出てくるということです。

送出時間の短縮とデータ圧縮は同じ考え方

さて、ここまで長々とモールス信号のお話を続けてきました。
ここまでではハフマン法はおろか、データ圧縮の「デ」の字も出てきませんでした。

ですが、ここまでのお話を理解いただくことが、ハフマン法を含むデータ圧縮を理解するのに非常に重要なのです。

ポイントは上にも書いた2点。

　1. どのデータパターンをどのシンボルに割り当てるかが重要
　2. あらゆるデータに最適化したシンボル定義は不可能

この両者は相反しているんですね。パターンとシンボルの表を決めるのは大切と書いておきながら、どんな表を決めたって非効率なパターンは必ず存在するというのですから。

こんなのを解消する方法なんてあるのでしょうか？

パターン辞書という考え方

上記のモールス信号は通信のためのルールですので、勝手にパターンとシンボルの表を変えるわけにはいきません。通信相手はその変更を知らなければ理解しようがありませから。

ですが、データ圧縮に限っていえば、特定の圧縮データを元に戻せればいいわけですから、ユニバーサルなパターンとシンボルの表でなくてもいいはずです。
圧縮対象のデータに特化した、パターンとシンボルの表をデータ圧縮の度に作ればいいのです。

つまり、圧縮したいデータの内容を精査して、専用のパターンとシンボルの表を作り、圧縮ファイルの中にデータと共に収納するのです。
このパターンとシンボルの表のことを一般に「辞書（dictionary)」と呼びます。

いくつか例を挙げましょう。

パターンＡ：　ABC-ABC-ABC-ABC-ABC-（ABC-を5回繰り返し）
圧縮データ：
　（辞書部）1:ABC-
　（データ部）11111

パターンＢ：　ABCD-ABC-ABCD-ABC-ABC-（ABCD-が2回とABC-が3回含まれる）
圧縮データ：
　（辞書部）1:ABCD-,2:ABC-
　（データ部）12122

パターンＣ：　AB-ABCD-ABCD-ABC
圧縮データ：
　（辞書部）1:AB,2:-ABC,3:D
　（データ部）123232

この方式なら、固定のパターンとシンボルの表を用意しなくてもOKですので、汎用性があります。

このように辞書を作りながらデータ圧縮を行う方式のことを辞書方式（Dictionary Coder）と呼びます。
次回に解説するハフマン法も辞書方式の一つです。

とはいえ、巨大なデータの全てを調べて辞書を作るのは大変な労力が要ります。
どこで区切るのが最適（最も圧縮率が高い）かを知るには、試行錯誤が必要だからです。
例えば、上のパターンCは次のように分解することもできます。

パターンＣ２：　AB-ABCD-ABCD-ABC　（パターンCと同じ）
圧縮データ：
　（辞書部）1:AB-,2:ABCD-,3:ABC
　（データ部）1223

パターンCとパターンC2のどちらが効率が良いかは、辞書部やデータ部をどんな構造にするかによります。
文字数ベースで考えると、パターンCでは辞書部は15文字と小さいがデータ部が6文字と大きい（合計で21文字）、パターンC2は辞書部は19文字と大きいが、データ部は4文字と小さい（合計で23文字）となります。
元データが16文字ですので、（文字数ベースで考えると）どちらの圧縮データも落第です。現実の圧縮ソフトでは辞書を作る時にビット単位で分析しますので、文字単位で考えるよりもずっと高い効率での圧縮が可能となります。
巨大なデータだとこの試行錯誤が大変なことになりそうだというのは想像できると思います。

なので、圧縮ソフトといえど、試行の必要な組み合わせは爆発的に増えすぎてしまい、最適解まで至ることは難しいのです。

ちなみに、辞書部も圧縮データの一部ですので、辞書部が大きくなりすぎると、圧縮の効果が薄れたり、むしろ辞書の分だけデータが増えたりすることもありえます。

辞書部とデータ部のバランスを取るという点もデータ圧縮の難しさと言えます。

まとめ

今回はモールス信号の話から、データの出現頻度によって、シンボルの決め方を工夫すれば、送信時間を縮めることができるというお話をしました。

その考え方はそのままデータ圧縮でも利用できます。
現代の多くのデータ圧縮法で採用されている辞書方式がそれです。

辞書方式では元データを走査して多く登場するパターンを検出し、それを辞書に登録することで、同じパターンの繰り返しをせずに済むようにします。

次回解説するハフマン法は、この方式をさらに進め、理論的には究極の圧縮率を目指せる方式（符号化）です。

今回は、モールス信号がデータ圧縮技術の視点から見ても優秀な方式であることをお話しました。
次回もお楽しみに。

（この記事は2024年12月に執筆しました）

このNoteは私が主宰するメルマガ「がんばりすぎないセキュリティ」からの転載です。
誰もが気になるセキュリティに関連するトピックを毎週月曜日の早朝に配信しています。
無料ですので、是非ご登録ください。
https://www.mag2.com/m/0001678731.html
弊社の窓口（ info@egao-it.com ) にメールをお送りいただいてもOKです。