前回は、データサイズ、I/O高速化との関係を意識する 圧縮プログラミングについてまとめた。ここでは、理論・研究の実践投入であるアルゴリズムの実用化について解説する。
１ アルゴリズムと評価
データの規模と計算量の違い
データが大きくなればなるほど、アルゴリズムやデータ構造の選択が速度に響く。例えば線形探索（リニアサーチ）がn件に対してn回の探索が必要なのに対し、二分探索（バイナリサーチ）はn件に対してlog n回の探索で完了することができる。ここでは、大規模データにおけるアルゴリズムの選択の重要さをと、アルゴリズムを製品に展開するまでの経緯を理解することを目的とする。
アルゴリズムとは
アルゴリズム（algorithm）とは、ある値または値の集合を入力（input）し、ある値または値の集合を出力（output）する、明確に定義された（well-defined）計算手続きである（『アルゴリズムイントロダクション』）。広義には処理（ドメインロジック）のフローという意味で用いられることが多い。今回取り扱うのは狭義のアルゴリズムについてである。
アルゴリズムを学ぶ意義
- 計算機の資源は有限
- エンジニアとしての「共通言語」
- アルゴリズムを知っておくことで新しい問題にも対処しやすい
アルゴリズムの評価
- オーダー表記：対象とするアルゴリズムが入力のサイズnのときにかかる計算量を表記する記法
- 計算量：時間計算量（実行時間、ステップ数）、空間計算量（メモリ使用量）
ティッシュを何回折りたためるか
O(log n)とO(n)の違いは「ティッシュを何回折りたためるか」で感覚としてつかみやすい。1枚のティッシュを半分ずつ折りたたんでいくと、7回までしか折りたためない。これはティッシュの厚みに依存しており、仮に最初の厚みを1mmとすると、1→2→4→8→16→32…と増えていく。これはO(2のn乗)の計算量と同じであり、相当大きいといえる。一方で指数の逆である対数的にしか増加しないO(log n)は、わずかな計算量で問題を解決できると直感的に理解できるだろう。
アルゴリズムとデータ構造
データ構造には配列、木構造、ヒープなどがあるが、アルゴリズムでよく使う操作に合わせて選ぶ必要がある。例えばRDBMSのインデックスの実装には、B+木という木構造がよく使われている（分散を考慮したMySQLの運用 DBのスケールアウト戦略参照）。
計算量と定数項
計算量のオーダー表記では定数項を無視する。定数項とは、そのアルゴリズムの実装中、入力サイズには依存しないが実装しなければならない処理の類いである。例えば関数呼び出しや関数から値を返すための処理、一次変数の確保、そしてif文で分岐させることなどである。実装にあたっては最初から最適化を行うのは誤った方針であり、計測の実施が重要である。
アルゴリズム活用の実際
はてなブックマークFirefox拡張の検索機能における試行錯誤があった。それは過去にユーザ本人がブックマークしたデータをインクリメンタル検索できる機能の実装において行われた。初めはSuffix Array（主にテキストデータなどを高速に検索するためのデータ構造）を用いていた。しかし、前処理に時間がかかるため、Firefox拡張が内部で持っているSQLiteにSQLでlikeによる部分一致検索を投げる（線形探索）ことにした。その後計測や見積を取ると、何の問題もなく探索ができたということがあった。
サードパーティの実装の活用
定番のアルゴリズムは、第三者が利用しやすいように実装が公開されていることも多い。例えば、PerlにおけるCPANには圧縮アルゴリズムの実装が多数ある。必要としている箇所だけを実装することで、工数も抑えられて費用対効果が高いということも起こる。
実例を見て実感を深める
以下に特定の機能に絞ったより具体的な実例を述べていく。
２ はてなダイアリーのキーワードリンク
キーワードリンクとは
キーワードリンクはブログサービスのはてなダイアリーにある機能のこと。入力された全文に対して27万語（2009年8月時点）のキーワード辞書とマッチングをして必要箇所をリンクに置き換えるというものである。
当初の実装
当初は、辞書中に含まれる全単語をOR条件でつなげる正規表現を作って使っていた。
問題発生
キーワード辞書が大規模化してくるにつれ、以下の2点で時間がかかってきた。
- 正規表現をコンパイルする処理
- 正規表現でパターンマッチする処理
パターンマッチによるキーワードリンクの問題点
キーワードリンクに計算時間がかかる問題の原因は正規表現のアルゴリズムにある。Perlなど実用的な言語の実装の多くはNFA（Nondeterministic Finite Automata）が利用されている。この処理はキーワードの個数に比例して計算量がかかるという問題点がある。
正規表現からTrieへマッチング実装切替
パターンマッチに伴う計算量の問題を解決するために、正規表現ベースの手法からTrie（トライ木）を使ったマッチングの実装に切替を行った。Trieは木構造の一種であるデータ構造である。探索対象のデータの共通接頭辞をまとめた木構造になるのが特徴で、文字列の集合を木構造に効率よく格納することができる。
AC法
AC法（Aho-Corasick法）は前述のTrie構造によるパターンマッチをさらに高速化させる手法である。辞書中からパターンマッチングを行うオートマトンを構築し、入力テキストに対して線形な計算時間を実現できる。辞書サイズに計算量が依存しない高速な手法である。
Regexp::Listへの置き換え
Regexp::Listは小飼弾氏が開発したPerlの正規表現ライブラリで、Trieベースの正規表現を生成するものである。例えば、gw/foobar fooxar foozap fooza/という正規表現は、foo(?:[bx]ar|zap?)という正規表現に変換される。共通の接頭辞や接尾辞がまとめられているので、この正規表現でパターンマッチを行った場合、ORで全単語をつなげた場合に比べて試行回数を大幅に削減できる。
キーワードリンク実装、変遷と考察
このようにキーワードリンクの実装は、巨大な正規表現→AC法→Regexp::Listと変遷してきた。この過程でわかったことは、当初シンプルな実装だったため実装が簡単かつ柔軟に行えていた点、一方データが大きくなることで本質的な解決策が必要であった点などがある。
３ はてなブックマークの記事カテゴライズ
記事カテゴライズとは
記事カテゴライズとは、新着の記事をその記事の内容に基づき自動で分類を行い、ユーザにカテゴリ分けして見せるという機能である。このカテゴリ判定にはベイジアンフィルタというしくみを使っている。ベイジアンフィルタはテキスト文書などを入力に受け取り、そこにナイーブベイズ（Naive Bayes）と呼ばれるアルゴリズムを適用して確率的にその文書がどのカテゴリに属するかを判定するプログラムである。特徴は未知の文書のカテゴリ判定を行うにあたって、過去の分類済みデータの統計情報からその判定を行うところである。
機械学習と大規模データ
多くの機械学習タスクは、ベイジアンフィルタのように正解データを必要とする。大規模データはスケーラビリティの観点からは運営者の悩みの種だが、一方で研究開発の分野では大変有用なデータなのである。
- はてなブックマークの関連エントリー：ある記事によく似た別の関連情報をユーザに提示する機能。ユーザの手によって入力された「タグ」という分類用のテキストを入力に、記事推薦アルゴリズムを使って実現している
大規模データとWebサービス
「The Google Way of Science」という元Wired magazineのKevin Kelly氏のコラムでは、「大量のデータと応用数学が他のあらゆる道具に取って代わる」という趣旨でGoogleの取り組みを考察している。例えば「Googleはこのパターンが来たらこの言葉に変換せよという機械学習のしくみに大量のデータを流し込んで翻訳エンジンを作ったのだが、誰も中国語ができないのに中国語翻訳プログラムを作ってしまった」という逸話も紹介されている。他にも例えばGoogle検索の「もしかして」機能は、過去にユーザが検索したクエリログを正解データに「こう間違えたときはこう検索し直している」という学習を行って正解データを提示しているのである。
ベイジアンフィルタのしくみ
ベイジアンフィルタの核はナイーブベイズというアルゴリズムで、ベイズの定理という公式をベースにしている。ベイズの定理はP(B|A)=P(A|B) P(B)/P(A)という確率公式が成り立つことを示す。この式はP(B|A)、つまり事象Aが起こった後で事象Bが起こる確率を直接求めるのが難しいときに役に立つ。ベイズの定理で変形すると、P(B|A)を求めるところだったのがP(A|B)、P(B)、P(A)がわかればよいということになる。P(A)は他の値との比較などで無視できることが多いので、結果としてP(A|B)とP(B)がわかればよいということに帰着する。このように、アルゴリズムのしくみまで分解すると、意外とその実装は簡単であることがわかる。
アルゴリズムが実用化されるまで
以下にはてなブックマークでの実例をリストにまとめる。
- 分類エンジンはC++で開発、サーバ化
- このサーバと通信して結果を取得するPerlクライアントを書き、Webアプリケーションから呼び出す
- 学習データを定期的にバックアップできるよう、C++のエンジンにデータのダンプ/ロード機能を追加
- 学習データ1000件を人手で用意
- まともな精度が出ているかをトラックするための統計のしくみを作成。グラフ化しながら精度をチューニング
- 冗長化を考慮し、スタンバイ側のシステムを構築。自動切替は工数がかかるため、バックアップからロードできる程度に妥協
- Webアプリケーション側にユーザインタフェースを用意
守りの姿勢、攻めの姿勢
同じアルゴリズムでも守りと攻めの双方の役割があることがわかる。例えばソートや探索、圧縮を高速に行うといったものは守りにあたり、機械学習やパターン認識などは積極的にデータを活かす意味で攻めといえる。
参考：スペルミス修正機能の作り方
はてなブックマークの検索機能にはスペルミス修正機能を搭載している。その実装は以下の5つ。
- 正解データにははてなキーワードを辞書として使う。27万語の正解辞書
- ユーザが入力した検索クエリと辞書中の語句の編集距離を取って”誤り度”を定量
- 一定の誤り度を基準に辞書中にある単語群を正解候補として取得
- 3.の正解候補をはてなブックマークの記事での単語の利用頻度を基準に正解っぽさで並べ替え
- 最も利用頻度の高い単語を正解であるとみなし、利用者に提示
最後に
速度を気にしたプログラムを書く場合、アルゴリズム・データ構造の選択は重要である。また「はてなダイアリーのキーワードリンク」「はてなブックマークの記事カテゴライズ」の2つの実装から、アルゴリズムが実際に適用された経緯や変遷、実サービスの一部でアルゴリズムがどのように活かされているのかなどを具体的に紹介した。
次回は、応用への道筋であるはてなキーワードリンクの実装について解説する。
 |
[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB DB PRESS plusシリーズ) |
