世界でもっとも強力な9のアルゴリズムを読んで

この記事は「世界でもっとも強力な9のアルゴリズム」という本を読んだ感想をただ書き留めておくだけです。

1. 検索エンジン
2. ページランク
3. 公開鍵暗号
4. 誤り訂正符号
5. パターン認識
6. データ圧縮
7. データベース
8. デジタル署名
9. 決定不可能性

検索エンジン

マッチングとランキングがある。マッチングで単語から検索するページを引き当てて、それらのページをランキングしてランクの高いものから表示していく

• マッチング
  • 単語を全て並べてその単語がどのページにあるか全て並べる
    →"cat sat"という二つの連続した単語で検索したいときにこれだと検索の効率が悪い。catを探して、その後にsatが続いているものを検索しなければならない。
  • 位置情報も乗っけると解決。ページ番号 - 単語番号　とすることでインデックスから検索可能
    　
• ランキング
  • タイトルに含まれているかどうかを確認する
    →これじゃ弱いので次の章で

ページランク

• ハイパーリンクトリック
  • 他のページから参照されていたら+1ポイントなどとしてページにランク付けをしていく
• オーソリティトリック
  • その分野において権威のある人の方を優先するというもの。権威を決めるのは難しいので、ここではたくさんの人から参照されていたらそれを+1ポイントと加算して保持しておき、そのページが参照している記事はそのページのポイントを全て加算するというものである。これにより、有名な（権威のある）記事から参照されている記事は+1ポイントではなく+100ポイント（有名な記事のポイント分）などとして加算してランク付けをする
• ランダムサーファートリック
  • ハイパーリンクトリックでは循環参照などが起こり無限にランクを加算させていく手が存在しているのでそれらを省くために、ハイパーリンクトリックとオーソリティトリックを掛け合わせたトリックを使う。このトリックでは100万回などの多数回、ある記事からその記事内にある、別の記事へのリンクへ飛び、そのページの訪れた回数をカウントするというものである。ここで重要なのは、循環参照が起こらないように、10%ほどの確率で全く別の記事へ飛ぶということである。これを複数回行うことで、オーソリティトリックのような有名な記事が参照している記事へ訪れる回数も保ちつつ、循環参照なども避けることができるというものである

公開鍵暗号

ここでは絵の具として考えている。AとBで同じ色を作りたいが他の人にはバレないように作る
絵の具はいくら混ぜても元の色を復元することができないので、実際の暗号とほぼ同じ

• まずは公開絵の具を一つ用意する
• Aが自分しか知らない色を作成し、公開絵の具と混ぜて、公にする（Aの公開絵の具）
• Bも自分しか知らない色を作成し、公開絵の具と混ぜて、公にする（Bの公開絵の具）
• AはBの公開絵の具と自分の秘密絵の具を混ぜる
• BはAの公開絵の具と自分の秘密絵の具を混ぜる
• これにより、AとBのみが同じ色の絵の具を共有することができる（AとBの共通絵の具）
• この時CがAの公開絵の具やBの公開絵の具を知ることができても、AとBの共通絵の具を知ることはできない。なぜなら、 AとBの公開絵の具を混ぜても元の公開絵の具の分が少し多くなってしまい、作成された絵の具から特定の絵の具の色を取り除くことはできないので、AとBの共通絵の具はCから知ることはできない

実際は数字で行われているが、原理としてはこれと変わらない

誤り訂正符号

数字を送って伝えたい

• 反復トリック
  • 送りまくる。桁数ごとにもっとも多いものを採用する
• 冗長性トリック
  • 5をfiveとすることで文字がfiqeなどになってもなんとなくわかるよねってやつ
• チェックサム
  • 送りたい数字の和の1桁目を最後に付属させる
  • これだと合計で10ずれた時にチェックサムと同じになるので階段チェックサムというものが生まれた
  • 4 7 2 8を送りたい時は1 * 4 + 2 * 7 + 3 * 2 + 4 * 8を計算し、その一桁目を階段チェックサムとして付随させる
  • シンプルチェックサムと階段チェックサムの両方を渡すことでより誤りを検知しやすくなる
• ピンポイントトリック
  • 4 8 3 2 1 5 7 6 9を送りたいとする。この時に正方形にそれぞれを並べてそれらの縦横のシンプルチェックサムを計算し、それを一つの数字列に直して送るというものである。

ピンポイントトリック

送信したいもの： 4 8 3 2 1 5 7 6 9

正方形にしてチェックサムを計算
4 8 3 | 5 
2 1 5 | 8
7 6 9 | 2
-------
3 5 7

送信するメッセージ: 4 8 3 5 2 1 5 8 7 6 9 2 3 5 7

これを送信することでどこか間違いが発生しても誤りの位置を特定し、縦横のチェックサムから元の数字を復元することができる。コンピュータ科学では2次元パリティとも呼ばれている

パターン認識

• 最近傍法
  • もっとも近い点が正義
• k最近傍法
  • 近くのk個見て一番多いものが正義
    これらにより、自宅の住所からその人物が献金する政党を予想したりなどができる

手書きの2 - 予想される2をすることで白地の上に黒い部分が出てくる。それが何%かによってその手書きの文字が予想される文字と一致するかを判定する方法

ニューラルネットワーク
はいなら1、いいえなら0で伝播していき、境界値を設定して、その境界値を超えていたら1でまた伝播させていく。正しくなかったら境界値を変えたり重みをつけてみる。これにさらに、信号を0,1ではなく0から1の間をとるようにする

データ圧縮

• ロスなし圧縮
  • AAAAABBCをA5B2C1で圧縮する
• ロスあり圧縮
  • データの一部を取り除く。画像を9*9のピクセルごとに区切って、そこの中で一番多い色に全ての色を統一する、的なこと

データベース

• トランザクション
  • これにより、データの一貫性が保証される。例えば、 AがBに1000円送金したい時に、Aの残高から1000円引いてBの残高を1000円増やすが、Aの残高から1000円引いた時にそのDBがクラッシュし、再起動したらAの残高が1000円少ない状態になってしまっている。
  • これにはTo-Doリストトリックを使用する（ログ先行書き込み）
  • これはDBが今からやろうとしている操作をログに保存するというものである。ログはハードディスクなどの永続記憶に保存されるので、ログ内の情報は、クラッシュして再起動しても残る
  • これにより先行書き込みログは以下のようになる

1. 送金トランザクションを開始する
2. Aの残高を5000円から4000円にする
3. Bの残高を3000円から4000円にする
4. 送金トランザクションを終了する

これにより、2の途中でDBがクラッシュしても再度全ての内容を1からやり直し、4まで終えたらこのトランザクションを終了したことを書き込めばいい
これによりアトミック性が担保される。それがさらにデータの一貫性を保証してくれる

しかしこれはDBにデータが残っていた場合の話で、データがクラッシュしてしまったらもう元には戻せない。なのでレプリケーとする必要がある。これは一つのDBでデータを管理するのではなく、同じDBを複製することで冗長性を確保し、安全性を高めようともの

• ロールバック

• 準備してコミットトリック

• 仮想テーブルトリック
  ここら辺は説明するにはちょっと長いから省略〜

デジタル署名

言ってることは基本的には理解できるけど、何やろうとしてるのかとか全体像掴めないまま進んでしまってよくわかんなかった、期間開けすぎた

決定不可能性

• 真ではないことの証明
  あんまちゃんと読めてない