前回は、理論・研究の実践投入であるアルゴリズムの実用化についてまとめた。ここでは、応用への道筋であるはてなキーワードリンクの実装について解説する。
１ [課題]はてなキーワードリンクを作る
AC法を使ってはてなキーワードリンクを作る
[課題]与えられた文章から、はてなキーワードとその出現位置を適切に抽出するプログラムを作成する。Trieはハッシュリファレンスなどを用いて作れば十分。1分程度の時間で動くものでよい。
はてなキーワードリンクのアルゴリズムの要件は以下の3つである。
- キーワード集合を与える
- 任意の文章を入力する
- 文章中にキーワードが見つかったらその位置と長さを返す
その手順は以下の通り（詳細略）。
- サンプルプログラム：My::AhoCorasickがアルゴリズムを実装したライブラリ
- AC法の実装：キーワード集合からTrieのデータ構造を作り、Failure Linksを作る処理を行う
- 実際の課題：AC法のキーワード集合
- 出題意図：実装手順の体験
テストを書く
テストスクリプト（t/01_ahocorasick.t）により、Perlのテストフレームワークでテストを自動化する。なお、アルゴリズムコンテストのサイトとして、Sphere Online Judge、TopCorderなどがある。
２ 回答例と考え方
回答例
リスト（/lib/My/AhoCorasick.pm）が課題の回答例である（詳細略）。この実装では、TrieはPerl組み込みのハッシュで実現している。大枠は以下の3つ。
- add_string()がTrieを構成する処理
- make_failure_links()が、Failure Linksを張る処理
- match()がオートマトンに入力を与えてキーワード抽出を行う処理
最後に
はてなキーワードリンクのアルゴリズムでは、キーワード集合を与えるなどの3つの要件を満たせれば実装が可能である。また、こういったアルゴリズムを実装する際にはテストを自動化しながら実装するとよい。キーワード集合からTrieを構成し、パターンマッチに失敗した場合に使うFailure Linksを作成するという流れを覚えておきたい。
次回は、大規模データ処理のノウハウの塊である全文検索技術について解説する。
 |
[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB DB PRESS plusシリーズ) |
