アルゴリズム 入門

アルゴリズムとは、何かの目的を達成するための手段のことで、コンピュータの世界では「一定の処理手順」のことを指します。昔からさまざまな分野でアルゴリズムが開発され、今でもより良いやり方を探求し、効率よく物事を処理しようと研究は続けられています。

ここでは、プログラミングをしていたら一度は触れるであろう分野のアルゴリズムをご紹介します。

検索アルゴリズム

目的のデータを探し出す時のアルゴリズムです。データベースのインデックスには、この後紹介するBツリー検索がよく使われています。

線形検索

最初から順番に検索します。データが n 個ある場合、最大検索回数は n 回、平均で (n+1) / 2 回となります。よって、データが多くなればなるほど、検索にも時間がかかります。

二分検索

データを昇順(もしくは降順)で保存し、真ん中にあるデータの値をみて、目的のデータが左右どちらにあるのかを判定し、それをずっと繰り返します。データが n 個ある場合、最大検索回数は n を半分にできる回数 + 1 なので、 2のべき乗 が n を初めて超えるまでが最大回数となります。

ex. 10個 ➔ 2*2*2*2 ここで初めて超えるので、最大4回
ex. 100個 ➔ 2*2*2*2*2*2*2 ここで初めて超えるので、最大7回
ex. 1000個 ➔ 2*2*2*2*2*2*2*2*2*2 ここで初めて超えるので、最大10回

線形検索よりも検索回数がはるかに少なくて済みます。

二分木(にぶんぎ)検索

子ノードを最大2個まで持つ木構造でデータを保存し、ルートノードから検索します。「子ノードの左側は親ノードの値より小さい、右側は大きい」というルールで並べます。

◯ をノード、一番上のノードをルートノード、子ノードを持たない末端のノードをリーフノード、ノードをつなぐ線をエッジといいます。

検索回数は木の高さによるので、あまり木が高くならないように保存すると効率的です。すべての末端ノードの高さが同じか、高さの差が1以内のツリーを平衡木といい、検索効率が一番良い構造となります。

Bツリー検索

親ノードが3つ以上の子ノードを持ち、さらに各ノードがデータを複数持つ平衡木です。ノードの配置ルールは基本的に二分木検索と同じですが、子ノードが複数のデータを持っているために少し複雑になっているので、例を交えて説明します。

ex. 親ノードが子ノードを3個持ち、さらに各ノードがデータを4個持つツリーで、数字を1から順に追加していく

値が追加された時に、木の高さが平衡木になるようにノードを組み替えていく、という処理をずっと続けます。データを保持する数は4つなので、1から追加していって4までは1つのノードに収まり、5でノードから溢れてしまいます。そこで、5を含めたノードの中央値「3」を親ノードに移動し、左側に3未満の値が入るノード、右側に3を超える値が入る子ノードを作成します。続けて値を追加していくと、今度は8で右側のノードが溢れてしまうので、また同じように中央値「6」を親ノードに移動させます。親ノードの値が2つになると、子ノードのキーの条件が、「x < 3」、「3 < x < 6」、「6 < x」 というように変わります。

こうすることで、値が追加されても平衡木を保つことができます。最大検索回数は木の高さになります。この例で言うと、16までは木の高さが2なので、検索回数は最大2回です。ノードに格納するデータ数が多ければ多いほど、検索回数も少なくなります。

Bツリーはデータベースのインデックスなどにも採用されているので、開発時に目にすることも多いかもしれません。

ソートアルゴリズム

データを並び替える時のアルゴリズムです。プログラミングでよく出てくるsort関数は、一般的に最も高速だといわれているクイックソートを使っています。

バブルソート

左からスタートして隣り合うデータの大小を比較していき、逆だったら交換する、というのを繰り返します。

ex. 「231」を昇順に並び替える

1回目の比較
「2」と「3」 => 2 < 3 なので何もしない => 231

2回目の比較
「3」と「1」 => 1の方が小さいので1と3を交換 => 213

一番右までいったので、ここで一番右の値が「3」であることが確定し、次は3を除いた残りの数字だけで比較します。

3回目の比較
「2」と「1」 => 1の方が小さいので2と1を交換 => 123

ここで終了です。比較回数はデータがn個の場合 (n-1) + (n-2) … となり、ここでは「2 + 1」で 3回、交換回数は今回は2回でしたが、最大回数は比較回数と同じになります。よって、データ数が増えれば増えるほど、交換回数・比較回数もどんどん増えてしまうので、あまり効率の良い手順ではありません。

選択ソート

左からスタートして、右側の全データと大小を比較していき、一番小さい(または大きい)値と交換していきます。バブルソートとは逆で、左から値が確定していきます。

ex. 「231」を昇順に並び替える

1回目の比較
「2」と「3」 => 2の方が小さいので何もしない => 231

2回目の比較
「2」と「1」 => 1の方が小さいので2と1を交換 => 132

ここで一番左の値が確定しました。次は左から2番目からスタートします。

3回目の比較
「3」と「2」 => 2が一番小さいので3と2を交換 => 123

ここで終了です。比較回数は3回、交換回数は2回でした。比較回数は実はバブルソートと同じです。ただし、交換回数は選択ソートは(n-1)で済むので、選択ソートのほうが効率が良い手順となります。

クイックソート

適当な値を基準値(ピボットといいます)として、その値より小さい数値を左側、大きい数値を右側に移動します。具体的には、先頭から基準値以上の値がヒットするまで探します。ヒットしたら、今度は末尾から基準値未満の値を探して、その値が見つかった場合に、その値同士を交換していきます。交換したら、また先頭の続きから同じように検索していきます。先頭と末尾からの検索でヒットした値の位置が左右逆になったらそこでストップし、先頭からの検索で最後にヒットした位置の左側を境界としてグループを分割します。分けたグループで同じく基準値をそれぞれ選び、同様のことを繰り返します。これをグループの要素が1つになるまで繰りします。(言葉だけだとわからないと思うので、後述の図を参考にしてください。)

基準値の決め方はいくつかやり方はあるものの特に決まっていません。最初の値を採用したり、ランダムに選んだり、中央値を採用したりします。

ex. 「52413」を、「3」を基準値として昇順に並び替える

1回目の比較
「5」 => 3以上なのでストップ => 次は末尾から開始

2回目の比較
「3」 => 3以上なので何もしない => 次に進む

3回目の比較
「1」 => 3未満なのでストップ。ここで、「5」と「1」を交換 => 「12453」 => 先頭の続きに戻る

4回目の比較
「2」 => 3未満なので何もしない

5回目の比較
「4」 => 3以上なのでストップ => 次は末尾の続きから

6回目の比較
「4」 => 3以上なので何もしない

7回目の比較
「2」 => 3未満なのでストップ

ただし、ここで先頭からヒットした値が右側になったのでストップ。先頭からの検索で最後にヒットした「4」の左側でラインを切り、グループを2つに分けてそれぞれ基準値を適当に選び、同じことを繰り返します。以降の処理は図で補足します。

クイックソートは基準値によって検索効率がかなり異なってきます。効率が悪いと選択ソートと同じくらいの効率になってしまいます。

圧縮アルゴリズム

データの圧縮とは、元のデータを保持したまま容量を削減したり、元のデータを加工して容量を削減したりすることです。アルゴリズムには2種類あり、圧縮したデータを元通りに戻せるものを可逆圧縮、戻せないものを非可逆圧縮といいます。テキストファイルは元に戻せないと困るので可逆圧縮、画像や音声・動画ファイルはある程度データが損失させてサイズを落とす非可逆圧縮がよく使われています。

ランレングス符号化

可逆圧縮アルゴリズムの1つで、連続する同一の値を「値x回数」で表現し、元の情報を[文字][繰り返し回数]という形式に置き換えて全体の文字数を減らします。

ex. 111112223 => 152331

ただし、繰り返しがまったくないと逆に文字数が多くなってしまうので、同じデータが数個以上続いていたらランレングスで符号化する、というやり方が使われます。ちなみにランレングスは、「続く(run)長さ(length)」という意味です。

ハフマン符号化

コンピュータではすべてのデータを「0」と「1」の2進数で表現できるようになっており、0と1に変換されたデータを符号、符号にすることを符号化、符号化されたデータを元に戻すことを復号化といいます。ハフマン符号化は、元の文字の符号よりも短い符号で表現し直すことで圧縮しています。

仮にABCDBの文字を「000」「001」「010」「011」「100」で表現したとすると、

ABBCCDDDEEEは、

「000 001 001 010 010 011 011 011 100 100 100」の 33ビット になります。

ここで、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、全体のビット数を短くする、というのがハフマン符号化です。違う符号を割り当てるため、文字とビット列の対応表を作成します。

まず、文字を頻出度順にまとめます。すると、

A: 1
B: 2
C: 2
D: 3
E: 3

です。これをハフマン木という木構造に直します。まず、左から頻出度の多い順にノードを並べます。

次に、右のノードから親ノードを作成していきます。親ノードの値は左右のノードの回数の合計値とします。

最後に、各ノードにビットを付与します。作成した親ノードのエッジの左右に「0」と「1」を割り当て、各文字のビットを、ルートノードから辿っていった時のビット列を付与します。こうすることで、各文字に一意のビット列を割り当て、かつ頻出度の多い文字に短いビット列を割り当てることができます。

この対応表を元に ABBCCDDDEEE を変換してみると、

「1111 1110 1110 110 110 10 10 10 0 0 0」の 27ビット となり、元の長さよりも 6ビット 短くなりました。

符号長の平均をとってみても、11文字中1ビット列が3回、2ビット列が3回、3ビット列が2回、4ビット列が3回なので、

1*3/11 + 2*3/11 + 3*2/11 + 4*3/11 = 2.45…

元のビットだと、11文字中3ビットが11回なので「3」となり、平均値も少なくなっているのがわかります。

JPEG圧縮

画像を非可逆圧縮するアルゴリズムです。人間の目では知覚できない部分をうまく取り除くことでデータ量を削減します。

画像は「ピクセル」という小さな四角で表現されていて、それぞれのビクセルは色情報をRBG(赤青緑)で持っています。RBGはそれぞれ「0〜255」の数値で表します。

JPEG圧縮は、まずRGBを、輝度を表す「Y」、色素を表す「Cb」「Cr」という情報に変換します。そして、人間の目では区別がつきにくい色素を削減します。次に、隣通しのピクセルの色情報を比較し、変化が大きいところをなるべく小さくします。(こちらも変化が小さいところをいじると人間の目で違いがわかってしまうようです)

こうすることでなるべく同じ色の繰り返しを増やし、ハフマン符号化などを活用して圧縮していきます。

PNG圧縮

画像を可逆圧縮するアルゴリズムです。LZ77 というアルゴリズムと、ハフマン符号化を組み合わせ方法で圧縮しています。基本的に繰り返しを利用したアルゴリズムなので、イラストなど複雑さの少ない画像ほど、PNGは効率よく圧縮できます。

MP3圧縮

音声を非可逆圧縮するアルゴリズムです。人間の耳には聞こえにくい部分をうまく取り除くことでデータ量を削減します。

音声をデジタルデータで取り込む時に、音声を1秒ごとに決まった数のデータを取り出して(=サンプリング)いきます。この数値をサンプリング周波数といい、Hz(ヘルツ)という単位で表します。ちなみに携帯電話だと「8kHz」で1秒間に8,000回、CDだと「44.1kHz」で1秒間に44,100回取り出していることになり、Hzが大きければ大きいほど元の音をデータとして正確に収集することができます。ちなみに、人間が聴くことのできる音の周波数は 20kHz くらいまでと言われていますが、音をデジタル化する時は元の周波数の2倍以上のサンプリング周波数が必要らしく、CDもそれに近い周波数となっています。

データを取り込んだ後は、音の大きさを数値化します(=量子化)。音の大きさは、携帯電話だと「8ビット」、CDだと「16ビット」で表します。これより、1秒間のデータ量は、携帯電話の場合は「8kHz × 8ビット = 64kbps」、CDの場合は「44,1kHz × 16ビット x 2(ステレオ) = 1411.2kbps」となります。(bps は bit per second)

MP3は、人間の可聴域に限界に近い 19kHz 以上の周波数をカットし、あとは人間の耳では聞き取れないくらいの小さな音や、大きい音と重なってかき消されてしまう音をカットするなどしてデータを減らしていき、最後にビットレートを下げます。上記のようにCDだと 1411.2kbps ですが、これを 128 kbps まで下げても人間の耳でははっきりと違いを区別するのは難しいようです。

MPEG圧縮

動画を非可逆圧縮するアルゴリズムです。動画では、データを圧縮することをエンコード、解凍することをデコード、エンコードとデコードを実現するアルゴリズムをコーデックと呼んでいます。さらにコーデックは映像用と音声用に分かれ、上記のMP3は音声のコーデックにあたります。

動画は、使っている映像コーデック・音声コーデックや、作成者などのメタ情報を格納した「コンテナ」というフォーマットで構成されています。コンテナはさまざまな企業や団体によって独自に規定されていて、使われている映像コーデックと音声コーデックの組み合わせも違ったりしますが、だいたいは映像コーデックだと「H264」、音声コーデックだと「AAC」や「MP3」が多いです。

MPEG圧縮は、「MP4」というコンテナ名で、MPEG1,2,3 … というように規格がたくさんあり、規格によって使っているアルゴリズムも異なりますが、たいていはフレーム間予測というのが使われています。フレーム間予測は、フレーム間の差分を抽出し、1つ1つの画像を全部保存するのではなく、2枚目を1枚目の画像とその差分情報から生成する、という感じでデータを保存するやり方です。

暗号化アルゴリズム

暗号化とは、データを第三者が見てもわからないように変換することです。暗号化する前の情報を平文、暗号化した後の情報を暗号文、暗号文を平文に復元することを復号といいます。

コンピュータで暗号化や復号を行う際には鍵(key)という桁数の多い数値を使います。この鍵を使用することで、もし暗号化アルゴリズムがばれたとしても、鍵がないと簡単には復号できないので、鍵の管理は非常に重要になります。鍵の桁数(=鍵長)は多ければ多いほど安全になりますが、その分暗号化や復号に時間がかかるので、バランスの良さが求められます。

共通鍵暗号方式

暗号化と復号に同じ鍵を使います。データを暗号化した人は、暗号化で使用した鍵を復号する人に渡す必要がありますが、その通達手段にインターネットを使うのは極めて危険なため、ネット上ではほとんど使われていません。

代表的なアルゴリズムにはAESがよく使われていて、鍵長は 128ビット、192ビット、256ビットの中から選ぶことができます。

公開鍵暗号方式

暗号化と復号に異なる鍵を使います。鍵は両方ともデータの受信者が作成し、暗号化に使う鍵をデータの送信者に渡します。データの送信者はデータを送る時に渡された鍵を使って暗号化し、受信者は送られてきたデータをもう1つの鍵を使って復号します。送信者に渡す鍵は公開鍵と呼ばれ、誰の手に渡っても問題ありません。データを暗号化するのにしか使えないからです。一方、復号するための鍵は秘密鍵と呼ばれ、この鍵を持っていれば公開鍵によって暗号化されたデータを誰でも解読できてしまうので、受信者はこの鍵を自分以外の手に渡らないよう厳重に管理する必要があります。

代表的なアルゴリズムにはRSAがよく使われていて、以下の式によって成り立っています。

除数: 割り算の母数にあたる値。
素数: どんな値で割っても割り切れず、必ずあまりがでる値。1は除きます。
最小公倍数: 2つの数に共通する倍数の中で、最も値が小さいもの。
mod: 割り算の「あまり」のこと。 8 mod 5 は 「8 ÷ 5 のあまり」なので「3」を指す。

たとえば、「3」という公開鍵と「7」という秘密鍵を作成し、「2」という数字を、「55」の除数で暗号化してみると、

2の3乗(2*2*2) / 55 = 0 あまり 8

「8」が暗号文です。これ復号する時は、

8の7乗(8*8*8*8*8*8*8) / 55 = 38,130 あまり 2

「2」が平文となり、暗号化前の情報に戻りました。この公開鍵・秘密鍵・除数にはルールがあり、除数は2, 3, 5, 7, 11,… などの素数を2つかけた値にします。除数は、平文の値以上である必要があることに注意します。上記の除数「55」は、56以上の「あまり」が求められないので、平文が「56」以上の値の場合は使用できません。

除数の「55」は、実は素数の「5」と「11」を使って求めたものでした。そして、べき乗するのに使う公開鍵と秘密鍵の「3」と「7」という値は、下記の公式によって求めたものです。(P と Q は素数、n は1以上の任意の整数です)

公開鍵の値 x 秘密鍵の値 = 「n x (P-1 と Q-1 の最小公倍数) + 1」

上記の例では、P = 5, Q = 11 で、n に「1」をあてはめると、

「 1 x 20(4 と 10 の最小公倍数) + 1 」 = 21

になります。21を「3 x 7」に分解したそれぞれの値が、公開鍵と秘密鍵の値になっていました。 

これでアルゴリズム入門は終了です。本来はいろいろ数式が登場するのですが、入門編ということでなるべく省きました。数学が得意な方は、ぜひいろいろな書籍を当たってみて下さい。