【情報Ⅰ#86】ランレングス法・ハフマン法のやり方をわかりやすく解説！｜情報１の授業動画【高校・共通テスト対策】データ・ファイルの圧縮
【情報Ⅰ#86】ランレングス法・ハフマン法のやり方をわかりやすく解説！｜情報１の授業動画【高校・共通テスト対策】データ・ファイルの圧縮
- 前回は、データの圧縮について説明しました。 デジタルデータの余分な情報を減らして、全体の情報量を小さくすることを圧縮と言い、それを戻すことを展開や解凍、伸張と呼びます。 また、データを圧縮した後に、圧縮前のデータに戻すことができる圧縮を「可逆圧縮」と言うのに対し、圧縮前のデータに戻すことができない圧縮を「非可逆圧縮」と言うことも説明しました。 そして、画像や音声、動画では様々な圧縮の方式があり、用途によって使い分けられているので、その種類や特徴の違いなどをおさえておきましょう。ということもお話しましたね。 今回は、可逆圧縮の具体的な方法である、ランレングス法とハフマン法について学んでいきます。
①ランレングス法
- 値が連続して出現するデータにおいて、連続するデータをまとめる圧縮の方法を「ランレングス法」と言います。
- うーん。そう言われてもよく分からない。
- では、具体的に例をあげましょう。
「すもももももももものうち」という文章があります。この内、「も」の文字は何個ありますか？ - えー、数えるの大変！うーんと・・・8個？
- そうですね。この文章を「すも8のうち」とするのが、ランレングス法となります。 連続する同一の文字の連なり（run）の長さ（length）を示す数字に置き換えることから、ランレングス法という名前がつきました。 ただ、私達がよく使う文章で、すももの文章のように同じ文字が何度も連続して出るのは稀です。 このランレングス法の威力が発揮されるのが、隣合う色が同じになることが多い画像です。 今回は、過去にITパスポートで出題された問題を例にあげて、考えてみましょう。 詳しくは動画をご覧ください。
②ハフマン法
- ランレングス法は連続するデータをまとめてしまう圧縮の方法のため、画像の圧縮には適していますが、連続データが出現しづらい文字の圧縮にはあまり向いていません。 ただ、文字に関しては、連続して続く文字はあまりないものの、よく使う文字とあまり使わない文字はあります。 例えば、存在する全ての英単語において、最も使われているアルファベットは「E」が13%と飛び抜けて多く、最も出現率が低いのは「Z」で0.1%程度と言われています。 このように頻出する「E」などのコードを短くすることで、効率的に圧縮する方法を「ハフマン法」と言います。 こちらは、1952年にデビッド・ハフマンによって開発された圧縮法のため、その開発者の名前を取って「ハフマン法」と呼ばれています。
- ぼくなら、「誰からも愛される可愛さとかっこよさを兼ね備えた唯一無二のぐらみん法」とかにするのになぁ・・・
- 例えば、INTELLIGENCEという単語を文字コード化してみましょう。 今回は、大文字のみを文字コード化するため、26種類を2進数で割り当てますから、1文字あたり5bit必要となります。 この理由が分からない方は、「文字のデジタル表現」のIT領域展開を見て復習しましょう。ハフマン法の特徴は、同じ情報が連続していなくてもデータを圧縮できるということでしょう。
③モールス信号
- このハフマン法を応用した例として、モールス信号があげられます。 モールス信号は、1832年にアメリカのサミュエル・モールスによって考案された、電鍵を用いて「トン」という短点と「ツー」という長点の組み合わせでアルファベットを表す通信方式です。 遠距離でも連絡可能な通信技術の元祖とも言われ、海難事故などでは｢モールス信号｣があったお陰で救われた命も数多くあります。 有名なタイタニック号が、1912年に氷山と衝突した時の遭難信号SOSも、モールス通信により無線で行われていました。 モールス信号の場合、このように各アルファベットに短点と長点の組み合わせがあり、構成されています。
- なんだかこの表、2進数みたいだね。
- はい。そのとおりです。デジタルでは0と1で表現しているのを、トンとツーという音で表現しています。 例えば、有名なSOSのモールス通信は、Sのトントントン、Oのツーツーツー、Sのトントントンを組み合わせるので、このような信号になります。 この表においても、頻出するEやTの文字は1つの音で表現され、逆にほとんど使われないXやZなどは4つの音で表現されています。
では、ここで問題です。
「－・・－－・－－－－・・」は何を表しているでしょうか？ - はい！XYZ！
- そうですね、それも正解です。 最初の4つ「－・・－」がX、次の4つ「－・－－」がY、最後の4つ「－－・・」がZを表しているので、これはXYZだろうと思った方もいると思います。 一方で、3つずつ区切ると 、「－・・」がD、「－－・」がG、「－－－」がO、そして最後もDなので、「DGOD」だろうと思った方もいますよね。
つまり、ハフマン法は可変長になるので、どこで区切れば良いか分からず、何通りもの解釈ができてしまう場合があるのです。 そこで、区切りを明確にするために、モールス信号では、短点3つ分の無音を区切りとして入れています。 つまり、今回の場合、－・・－ －・－－ －－・・のように4つずつ無音で区切られている場合には、XYZとなりますし、－・・ －－・ －－－ －・・のように3つずつ無音で区切られている場合は、DGODとなります。 - なるほど！
まとめ
- 値が連続して出現するデータにおいて、連続するデータをまとめてしまう圧縮の方法をランレングス法と言う。
- データの出現頻度に着目した圧縮方法をハフマン法と言う。
- ハフマン法では、可変長のコードとなるため、モールス信号の無音の様に区切りを示すルールが必要となる。
