まさ@ブログ書き込み中

まさ@ブログ書き込み中

まさの旅、英語、プログラミング、プライベートについて、色々記録しています。

『大規模サービス技術入門』の中盤をまとめる(1)

 

こんばんは。まさです。

 

『大規模サービス技術入門』の中盤(第6回〜第10回)を読み終えたので、まとめて生きたいと思います。

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)

 

 

 

ただしPerlで実装していく章に関してはさらっと読み飛ばしましたので、実装ではなく概念や知識に関する点についてだけまとめていきます。

 

 

 データ圧縮

このまえの本書の序盤のまとめからもわかるとおり、I/Oの高速化のためにデータ圧縮をすることは大切なことです。

 

本書の第6回では圧縮プログラミングについて学びました。実際には課題が与えられて、それをPerlで実装していくものでしたが僕はPerlをやっていないので読み飛ばしました。

 

よって、ここでは知識についてさらっとまとめておきます。

 

整数を圧縮する

課題は整数列が記録されたCSV(Comma Spearated Values)形式のファイルをバイナリに変換してコンパクトに持つというものでした。

 

本書で使われていた整数列を圧縮するアルゴリズムとしてVB Code(Variable Byte Code, 可変長バイト符号)が紹介されていました。

 

これは、簡単に言うと10進数を2進数として持つ際により効率的に符号化するためのコードです。

 

例えば、数値の5と130を固定長バイナリ符号として符号化すると、以下のようになります。

(固定長バイナリ符号)

5の場合

00000000 00000000 00000000 00000101

 

130の場合

00000000 00000000 00000000 10000010 

 

固定長バイナリ符号は文字通り「固定長」なので、どれだけ小さな数字でも32ビット(4バイト)ありますが、ぶっちゃけ下位1バイト以外は冗長です。

 

VB Codeでは最小限のバイトで情報を表現します。

VB Code)

5の場合

10000101

 

130の場合

00000001 10000010

 

 5の場合を見てみると、頭に1がついてますね。これは「この整数のビット列はこのバイトで終わり」ということを表しているんだそうです。このようなフラグ(continuation ビットと呼ばれるようです)のおかげで、バイト数が固定されていなくても数を表現できるそうな。

 

ちなみに(2進数で言う)130の方は1バイト目の最後の「1」(下位7ビット)が128を表していて、2バイト目の最後の「10」(下位7ビット)が2を表しているので、128+20=130と復号できます。

 

VB Codeの場合各バイト8ビットの先頭1ビットはフラグなので、整数を表現する箇所には7ビットしか使えません。よって今回の例で言うと、1バイト目では0~127までを表し、2バイト目では128×(1~127)を表すわけですね。

 

整数「列」を圧縮する場合はもう一工夫する

先ほどは「5」と「130」など、1つの整数を圧縮する方法についてお話しましたが、整数列を圧縮する際にはどうすればいいでしょうか。

 

本書ではソート済み整数を「ギャップ」で持つことを紹介しています。

例えば、以下のような整数列があったとします。

 

[3, 10, 2, 5]

 

これを昇順にソートすると

 

[2, 3, 5, 10]

 

となります。先頭から差分を取っていくとさらにその数は小さくなりますね。

 

一つ前の要素との差を取る

[2, 1, 2, 5]

 

差分を取っているため、あとで復元したいなら先頭から足していけばいいだけです。

 

一つ前の要素を足して復元する

[2, 2+1, 2+1+2, 2+1+2+5]

→[2, 3, 5, 10]

 

その上でVB Codeで符号化する際には、より小さな数字である方がバイト数を食わないわけですからこのように値と値のギャップを取っていけばいいのですね。

 

整数列の圧縮はモールス信号と同じ原理

「圧縮の基礎」として補足されていた話をまとめておきます。

圧縮の一番根底にある理論は「記号の確率分布から、頻出記号に短い、そうでない記号には長い符号語を与える」というものだそうな。

 

そしてそれはなんとあのモールス信号も同じらしいです。

 

 モールス信号ではeとかtとか、英語で頻出する記号に対してはトンとかツーとか短く伝わって、zとかqとかあまり出てこない記号はツーツートントンなど長い符号、信号が割り当てられています。

 

へえ〜〜〜!ってなりますよね笑

 

 

アルゴリズム

ここでいうアルゴリズムは「明確に定義された計算問題に対して、定義された計算手続きを行うもの」とされていますが、それの学ぶ意義は

  • 計算機の資源は有限
  • エンジニアとしての「共通言語」
  • アルゴリズムを知っておくことで、新しい問題にも対処できる(かも)

とまとめられていました。実用面で言えば計算機の資源は有限だから、効率的な計算方法(アルゴリズム)を使った方がいいってことですな。

 

アルゴリズムの評価

どのアルゴリズムが優れているかを評価するさいにはオーダー表記(O)を使うことが一般的らしいです。

 

オーダー表記とは、対象とするアルゴリズムが入力サイズnのときこのぐらいの計算量がかかるよっていうのを表記するもの。

 

nのサイズに関わらず一定の計算量がかかる場合はO(1)、

線形探索(要素を先頭から探す方法)はO(n)、

データを二分して目当てのデータを見つける二分探索はO(log n)です。

 

O(1)<O(log n)<O(n)<O(n log n)・・・と順に計算量が増えていくそうな。

 

キーワードリンクアルゴリズム

本書には、はてなダイアリーキーワードリンクを実装する際のアルゴリズムについて触れられている箇所がありました。

 

キーワードリンクとは、ブログを書くと一部のキーワードにリンクが自動で貼られるあの機能です。このブログの本文にもリンクが貼られているのではないでしょうか。

 

はてなブログキーワードリンクを実装するとなった際に僕がすぐに思いつくのは正規表現によるパターンマッチングですが、それはアルゴリズムでいうと線形探索なので、O(n)で非効率です。

 

そこではてなではTrie(トライ木)を使ったマッチングの実装をしているそうです。

Trieは探索対象のデータの共通接頭辞をまとめた木構造になるという特徴があります。

 

f:id:masaincebu:20170912213114p:plain

 

また、AC法というTrie構造のパターンマッチを高速化させる手法をはてなでは採用しているみたいで、具体的にはマッチが途中で進んだが失敗した場合に一度先頭に戻るのではなく、Trieにさらに追加したデータ構造を使うのです。

f:id:masaincebu:20170912213153p:plain

 

 

以上で、中盤のまとめ1を終わります。

ではまた。