CodeZine(コードジン)

特集ページ一覧

視覚的にイメージしにくいアルゴリズムを徹底的にイラストで表現するとこうなる

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2017/06/13 07:00

 近年、IT企業の社員研修ではアルゴリズムを理解することが重視されるようになってきました。しかし、文字とフローチャートだけでは仕組みをイメージしづらいのも事実。『アルゴリズム図鑑』ではアルゴリズムをまず視覚的にイメージできるように、26種類のアルゴリズムをイラストで解説。3種類のアルゴリズムを紹介します。

アルゴリズム図鑑』の元となったのは、Appleが2016年末に発表した「ベストApp10選」に選ばれたアプリ「アルゴリズム図鑑」です。

 勉強しようと思っても、文字や少数の図解だけでは仕組み・概念を理解しづらいのがアルゴリズム。アプリではイラストで表現することでその課題を解決し、大変な好評を得ました。本書は紙幅を活かして一覧での見やすさを高め、26種類のアルゴリズムを徹底的にイラストで表現しました。

 今回は本書から、データ構造の「リスト」、グラフを探索するアルゴリズムの「幅優先探索」、データを暗号化するアルゴリズムの「公開鍵暗号方式」、データを似たもの同士に分類するクラスタリングアルゴリズムの「k-means法」を紹介します。

リスト――データ構造

 アルゴリズムの仕組みを理解するのであれば、そこで扱うデータの構造について知っておく必要があります。データはメモリに蓄えられており、その際にデータの順番や位置関係などを規定したものがデータ構造です。

 データ構造の一つが「リスト」。データを一直線に並べた構造をしていて、データの追加や削除がしやすいメリットがある反面、アクセスには時間がかかるというデメリットもあります。

リスト1-1

 これはリストの概念図で、三つのデータが格納されています。各データを繋いでいるのがポインタで、メモリ上の位置を指し示します。

リスト1-2

 リストではポインタが位置関係を規定するため、メモリ上の連続した領域に格納される必要がありません。データは一般的に離れた領域に格納されています。

リスト1-3
リスト1-4

 格納場所が異なるため、各データにはポインタを順に辿らないとアクセスできません(順次アクセス、またはシーケンシャルアクセス)。RedにアクセスしたいときはBlueからアクセスし、Yellowを経る必要があります。

リスト1-5

 データを追加するときは、追加する前後のデータのポインタを指し替えるだけなので簡単です。BlueとYellowの間にGreenを追加したいときは……

リスト1-6

 BlueのポインタをGreenに、GreenのポインタをYellowに向けます。これでデータが追加されたことになります。もちろんGreenのデータはメモリ上のどこにあっても構いません。

リスト1-7

 データの削除もポインタの指し替えで行います。Yellowを削除したいなら……

リスト1-8

 GreenのポインタをRedに指し替えましょう。Yellowはどこからもアクセスできないので、消す必要もなく、その領域は別のデータに上書きされて再利用されます。

 ここで紹介したリストは最も基本的なもので、拡張されたものもあります。リストの最後尾のデータであるRedはポインタを持っていませんでしたが、Redから先頭のBlueへポインタを指せば「環状リスト(循環リスト)」ができ上がります。常に一定個の最新データを保持したいときに有用です。

 また、各データに双方向のポインタを持たせて、「双方向リスト」を作ることもできます。リストを前からでも後ろからでも辿れるので便利ですが、ポインタの数が増えることでデータ格納のための領域が多くなる欠点もあります。

リスト1-9

幅優先探索――グラフ探索

 では、ここからアルゴリズムを紹介していきましょう。最初に紹介するのはグラフを探索するアルゴリズムの「幅優先探索」です。

 そもそもコンピューターサイエンスでいうグラフとは、複数個の頂点(ノード)が辺で結ばれたものをいいます。人間関係(ソーシャルグラフ)、路線図、コンピューターネットワークなど、様々なものをグラフで表現できます。

 これらのグラフを探索するためのアルゴリズムの一つである幅優先探索は、全貌のわからないグラフにおいて、始点から辺を辿りながら頂点を探索し、指定された頂点(ゴール)に辿り着けば目的達成です。端的には、頂点を探索する際、始点に近い頂点から優先的に探索していくアルゴリズムです。

リスト2-1

 まず、始点を定めましょう。今回はAです。ゴールとしてGを設定しますが、Gがどこにあるかは最初の時点ではわかりません。

リスト2-2

 Aから辿れる頂点B、C、Dが次に進む頂点の候補です。

リスト2-3

 候補の中から頂点を一つ選びます。選択の基準は、最も早く候補に追加されたものです(同じタイミングのときはどれでも構いません)。

リスト2-4

 今回はB、C、Dが同じタイミングで候補となったのでBを選択します。

リスト2-5

 Bに移動すると、Aが探索済みとなります。

リスト2-6

 Bから辿れるEとFを候補に追加しましょう。これで候補がC、D、E、Fとなりました。

リスト2-7

 C、D、E、Fのうち、最も早く候補になったのはCとDです。今回も左側のCを選択します。

リスト2-8

 Bから、選択したCに移動します。Bが探索済みとなります。

リスト2-9

 Cから辿れるHが新たに候補に加わります。現在の候補はD、E、F、Hです。

リスト2-10

 このように、ゴールに辿り着くか、すべての頂点を探索し終えるまで探索を繰り返します。

リスト2-11
リスト2-12
リスト2-13

 今回の例での選択順はA、B、C、D、E、F、H、I、J、K、そしてGとなりました。

 幅優先探索では文字どおり幅広く探索を行っていく特徴があります。当たり前のことですが、始点の近くにゴールがあるほうが探索が早く終了します。

 ちなみに、ここまで例として用いてきた連結して閉路のないグラフはと呼ばれています。また、始点と終点が同じ頂点である(閉路がある)グラフも同様に探索することができます。

公開鍵暗号方式――セキュリティのアルゴリズム

 次に紹介するのはセキュリティのアルゴリズム、その中でも最も有名で重要な「公開鍵暗号方式」です。

 インターネットを使ってデータをやり取りする際、安全に利用するためにセキュリティを確保しなければなりません。データを暗号化する方式は数々考案されてきては脆弱性が暴かれてきました。公開鍵暗号方式は、これまでの暗号方式が抱えていたとりわけ大きな課題、鍵配送問題を解決したのです。

 たとえデータを複雑に暗号化しても、復号する(平文に戻す)にはそれを解く鍵が必要です。その鍵は暗号化した人の手から復号したい人の手に安全に送り届けなければなりません。いったいどうすれば安全に送れるのか? 鍵を暗号化したら、さらにそれを復合するための鍵を送る必要があり……さて。

 公開鍵暗号方式はどのような仕組みで課題を解決し、安全を確保しているのでしょうか(ちなみに、公開鍵暗号方式にもいくつか種類があり、強力なRSA暗号がよく使われています)。

リスト3-1

 では、公開鍵暗号方式を利用したデータのやり取りの全体像を見ていきます。AさんがBさんにインターネット経由でデータabcを送ろうとします(Xさんがその様子を見ています)。

リスト3-2

 まず、受け手のBさんが公開鍵P(public key)と秘密鍵S(secret key)を作成します。もちろんこれらの作業を行うのはコンピューターです。

リスト3-3

 Bさんは公開鍵をAさんに送信します。のちほど説明するように、公開鍵は第三者に知られても問題ありません。

リスト3-4

 AさんはBさんから受け取った公開鍵でデータを暗号化します。

リスト3-5

 Aさんは暗号化されたデータ(暗号文)をBさんに送信し、Bさんは秘密鍵を使って復号します。これでBさんはデータabcを取得することができました。

リスト3-6

 公開鍵と暗号文はインターネットで送信されるため、悪意のある第三者Xさんに盗み見されるかもしれません。しかし、公開鍵では暗号文を復号できないので、Xさんは元のデータabcを取得できないのです。

リスト3-7

 公開鍵暗号方式には不特定多数間でのやり取りがしやすいというメリットがあります。具体的に見てみます。

リスト3-8

 公開鍵はその名のとおり、人に知られても問題ありません。一方で、秘密鍵は誰にも知られないように管理する必要があります。

リスト3-9

 さて、複数人がBさんにデータを送信したいとしましょう。

リスト3-10

 データを送信する人は、Bさんが公開している公開鍵を取得します。

リスト3-11

 そして、送信したいデータを暗号化します。

リスト3-12

 その後、暗号文をBさんに送ります。

リスト3-13

 Bさんは暗号文を自分の秘密鍵を復号します。これでBさんは元のデータを取得できました。このように、データを送信する相手ごとに鍵を用意しなくていいのがこの方式のいいところです。データの受け手だけが秘密鍵を持つので、安全性も高いのです。

リスト3-14

 公開鍵の信頼性は重要です。しかし実は、Xさんが悪巧みできる余地も理屈から言えば残されているのです。それを知るために、Bさんが公開鍵PBと秘密鍵SBを使ってデータのやり取りをする場面を見てみましょう。

リスト3-15

 ここで、データを盗み見しようとするXさんも公開鍵Pxと秘密鍵Sxを作成します。

リスト3-16

 Bさんが公開鍵PBをAさんに送るとき、事件が起こります。

リスト3-17

 なんと、Xさんが公開鍵PBを自分の公開鍵Pxにすり替えてしまいました。

リスト3-18

 当然、Aさんに届くのはXさんの公開鍵Px。公開鍵自体は誰が作成したものかわからないので、Aさんは公開鍵のすり替えに気づけません。

リスト3-19

 そのため、Aさんは公開鍵Pxでデータを暗号化してしまいます。

リスト3-20

 そして、AさんがBさんに暗号文を送ろうとしたとき、Xさんが暗号文を受け取ります。

リスト3-21

 何が起きるかは明白でしょう。Xさんは秘密鍵Sxで暗号文を復号できてしまいます! Xさんはデータを盗み見ることに成功しました。

リスト3-22

 次に、XさんはBさんの公開鍵PBでデータを暗号化します。

リスト3-23

 Xさんはその暗号文をBさんに渡します。この暗号文はBさんの公開鍵PBで作成したものなので、Bさんは自分の秘密鍵PBで復号できます。Aさん同様、データを盗み見されたことに気づけません。

 このように、公開鍵をすり替えてデータを盗み見る攻撃手法を「man-in-the-middle攻撃」と呼びます。

 この攻撃は防げないのでしょうか? 解決策はあります。公開鍵の作成者を証明するための「デジタル証明書」というアルゴリズムを利用するのです。その仕組みについては、ぜひ本書で。

k-means法――クラスタリング

 最後に紹介するのは、クラスタリングのアルゴリズム「k-means法」です。

 クラスタリングとは、多数のデータを似たもの同士のグループに分類する操作のことで、それぞれのグループをクラスターと呼びます。データ間の距離を定義できれば、距離の遠近でそれぞれのデータがどれくらい似ているかを判断でき、クラスタリングすることができます。

 k-means法は基本的・代表的なもので、クラスターが事前に与える数(k個)になるようにクラスタリングするアルゴリズムです。

リスト4-1

 まず、クラスタリングを行いたいデータを用意しましょう。次に、クラスター数を決めます。今回は3とします。このイラストでは、データを点で表し、データ間の距離は2点間の直線距離を用います。

リスト4-2

 クラスターの中心点として、3点をランダムに設置します。

リスト4-3

 各データについて、3つの中心点のうち最も近い点を計算します。

リスト4-4

 各データを決定したクラスターに分類します。これで三つのクラスターができました。

リスト4-5

 各クラスターに属するデータの重心を計算し、クラスターの中心点をそこに移動させます。

リスト4-6

 最も近いクラスターの中心点を再計算し、各データをクラスターに再分類しました。

リスト4-7

 各データのクラスターへの分類と、中心点の重心への移動を中心点が収束するまで(動かなくなるまで)繰り返します。

リスト4-8

 これは3回目の繰り返しが終わったあとの状態です。

リスト4-9

 4回目の繰り返しが終わったところです。これ以上やっても中心点は移動しないので、クラスタリング完了です。

 k-measn法では操作を繰り返すと中心点が必ずどこかに収束することが証明されています。設定するクラスター数が適切でないと、有意な結果が得られないこともあるので気をつけましょう。

ビジュアライズされたアルゴリズム

 紹介した三つのアルゴリズムを既に知っていた方、あるいは全然知らなかった方も、このように仕組みをイラストでしっかり表現すれば、一気に視覚的にイメージしやすくなったのではないでしょうか。

アルゴリズム図鑑』にはほかのアルゴリズムも掲載していますので、気になる方はチェックしてみてください。

購入者限定の特典はこちら

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

Amazon SEshop その他


アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

著者:石田保輝、宮崎修一
発売日:2017年6月5日(月)
価格:2,570円(税込)

本書のポイント

・基本的な26のアルゴリズムすべてイラストで解説
・誌面がフルカラーなので、図の動きがわかりやすい
・各アルゴリズムの考え方や計算効率、問題点もフォロー
・50万人が学んだ大人気アプリを書籍化

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • 渡部 拓也(ワタナベ タクヤ)

     翔泳社マーケティング課。MarkeZine、CodeZine、EnterpriseZine、Biz/Zine、ほかにて翔泳社の本の紹介記事や著者インタビュー、たまにそれ以外も執筆しています。

All contents copyright © 2005-2020 Shoeisha Co., Ltd. All rights reserved. ver.1.5