ついでなのではてなキーワードによるマークアップの実装エンジンでも書いてみる
データ準備
はてなキーワードの一覧がまず必要なので、このページから落とす。
http://developer.hatena.ne.jp/ja/documents/keyword/misc/catalog
結構でかい。10MBくらいある。キーワード数35万強。
まあ事前に落として、ローカルファイルに保存しておけばまだ早いかなと。
実用レベルの速度ではないのは後述。今回のはレンサバでも動くという利点はあるけども、とにかく遅い。
ちなみにはてなじゃなくてWikipediaがいいよという場合は、こっちにある。
http://dumps.wikimedia.org/jawiki/latest/jawiki-latest-all-titles-in-ns0.gz
こっちは圧縮済みで8MB、解凍後で28MBもある。130万ワード強。
アルゴリズム
とりあえずこんな文章だとしよう。
こんにちは、私は告原豊和と言います。ベトナムでネオニートをやっています。
ネオニートってイミフですが、要は働きたくないでござると言って会社には行かないけど、霞を食べているだけだと死んでしまうので食料代はなんらかの形で稼いでいるなんちゃってニートです。
辞書で「こんにちは」と「こんばんは」と、「ベトナム」と「ネオニート」と「ニート」が登録されているとする。
二つかな。
一個ずつ見ていく方法
「こんにちは」を「こんばんは」と「こんにちは」の候補から搾り出す手順としては、Trieではこういう形になる。
こ（二つ）→こん（二つ）→こんに（一つ、部分一致）→こんにち（一つ、部分一致）→こんにちは（一つ、完全一致）
これを素直に全部やって、「完全一致」が出た最長のタイミングでマークアップする方法がまず一つ。
でもちょっと効率悪い気もするがどうなんだろう。
実際は「こ」をとるまでは無の状態から検索、「こん」をとる際は「こ」から検索、「こんに」をとる際は「こん」から検索するので、探索コストは常に一つずつとなりほぼ最低値に近くなるはずではあるんだが、"最長かどうか"の判断に時間をとられそう。
例えば「こんにちは、僕は」というキーワードが登録されていたら、こんにちはをとった後にさらに「こんにちは、私」まで検索してヒットしなくなったことを確認して、「こんにちは」まで戻ってキーワードをとらないといけない。
多分、ネオニートってワードを見て「ネオニート」と「ニート」二つのワードをマッチさせる方法ならこの方法がベストだけど、最長一致したキーワードのみだと微妙。
とれたタイミングで即見る方法
「こ」の段階で「こんにちは」と「こんばんは」をとれば、いちいち「こん」「こんに」「こんにち」「こんにちは」に対して再検索をかける必要はないじゃろうと。
だから「こ」の段階で長い順に整列させて、「こんにちは」がヒットしたら「こんにちは」のキーワードを設定した上でヒットしたキーワード分読み飛ばせばいい。
この方法の難点はキーワード数が多い場合かと思われる。
Wikipediaで100万強、はてなキーワードで35万強だけど、普通にやっても10万以上になることは容易に想像できるので、「こ」からとれるワード数が50以上とかになると、キーワード抽出コストがばかにならない。
本来「こんにちは」と5文字たどるだけでいいのが、「こんにちは、私はプリンターが欲しいのですが、なかなか買えません」なんてキーワードがあったらこのキーワードを抽出するのに30以上も辿ってとってこないといけない。
最長一致の場合は一個ずつ見ていく方法より処理が簡潔になってよさそうだけど、全マッチさせるなら非効率的っぽいかなと。
とりあえず
両方実装してみる。
どっちのやり方でもそれなりに改善の余地のある作りだけど、全一致の場合は一個ずつ方式、最長一致の場合はとれたタイミングで即見る方式で。
実装してみた
こんな感じ。
<?php require_once('TTrieMB.class.php'); function _tkeyword_strcomp($s1, $s2) { $l1 = mb_strlen($s1); $l2 = mb_strlen($s2); if ($l1 == $l2) return 0; return ($l1 > $l2) ? -1 : 1; } class TKeyword { var $keywords = array(); function __construct() { } function load() { $this->tree = new TTrieMB(); //$this->_loadWikiKeyword(); //$this->_loadHatenaKeyword(); $this->_loadTest(); } function _loadTest() { $this->tree->add('こんにちは'); $this->tree->add('こんばんは'); $this->tree->add('こんにちは、僕は'); $this->tree->add('ニート'); $this->tree->add('ネオニート'); $this->tree->add('ベトナム'); } function _loadWikiKeyword() { $fp = fopen('jawiki-latest-all-titles-in-ns0', 'r'); if (! $fp) return FALSE; while (! feof($fp)) { $buf = fgets($fp); if ($buf) $this->tree->add($buf); } fclose($fp); return TRUE; } function _loadHatenaKeyword() { $fp = fopen('keywordlist_furigana.csv', 'r'); if (! $fp) return FALSE; while (! feof($fp)) { $buf = fgets($fp); list($furigana, $keyword) = explode("\t", $buf); if ($keyword) $this->tree->add($keyword); } fclose($fp); return TRUE; } //2012/12/14 TTrieMBが1文字ごとキーになったのを受けて微調整 function matchAll($source) { $matches = array(); $len = mb_strlen($source); for ($i=0; $i<$len; $i++) { $cnt = 1; $k = mb_substr($source, $i, $cnt); $ret = $this->tree->searchO($k); if (! $ret) continue; if ($ret->s) $matches[] = $ret->s; while (count($ret->trie) > 0) { $cnt++; $k = mb_substr($source, $i, $cnt); $ret = $ret->searchO($k, $cnt-1); if (! $ret) break; if ($ret->s) $matches[] = $ret->s; } } return $matches; } function matchLongest($source) { $matches = array(); $len = mb_strlen($source); for ($i=0; $i<$len; $i++) { $k = mb_substr($source, $i, 1); $ret = $this->tree->search($k); if ($ret === FALSE) continue; if (count($ret) > 0) { usort($ret, '_tkeyword_strcomp'); foreach ($ret as $keyword) { $l = mb_strlen($keyword); if (mb_substr($source, $i, $l) == $keyword) { $matches[] = $keyword; $i+=$l-1; break; } } } } return $matches; } } ?>
途中にある$this->_loadWikiKeyword();、$this->_loadHatenaKeyword();、$this->_loadTest();は、Wikiを読んだりはてなを読んだり、テスト用のを読んだりするため用。
この辺は好きなのを適当にコメント外して使う。
こんな感じで使う。
<?php require_once('TKeyword.class.php'); $test_str = 'こんにちは、私は告原豊和と言います。ベトナムでネオニートをやっています。 ネオニートってイミフですが、要は働きたくないでござると言って会社には行かないけど、霞を食べているだけだと死んでしまうので食料代はなんらかの形で稼いでいるなんちゃってニートです。'; $test = new TKeyword(); $t = microtime(true); $test->load(); print_r($test->matchAll($test_str)); print_r($test->matchLongest($test_str)); echo (microtime(true)-$t); ?>
※TTrieMB.class.phpは昨日の記事参照
matchAllが一個ずつ、matchLongestがとれたタイミングで即見。
ただマッチしたキーワードが返るだけなので、はてなキーワードっぽく整形するならもうちょっとやりようがあるけど。
こんなん追加する感じっすかねぇ。
<?php function matchLongestToHtml($source) { $s = array(); $len = mb_strlen($source); for ($i=0; $i<$len; $i++) { $k = mb_substr($source, $i, 1); $ret = $this->tree->search($k); if ($ret === FALSE) { $s[] = $k; continue; } if (count($ret) > 0) { usort($ret, '_tkeyword_strcomp'); $has = FALSE; foreach ($ret as $keyword) { $l = mb_strlen($keyword); if (mb_substr($source, $i, $l) == $keyword) { $matches[] = $keyword; $i+=$l-1; $s[] = '<a href="http://d.hatena.ne.jp/keyword/'. rawurlencode($keyword).'">'.$keyword.'</a>'; $has = TRUE; break; } } if (! $has) $s[] = $k; } } return implode($s); } ?>
これだと戻り値がはてなキーワードのリンク付きにはなる。Wikipediaの場合も似たような形。
全マッチの方はどういうHTML出力がいいのか謎なので省略。
問題
まず、はてなキーワードのファイルとかは、メモリが足らずに読めない事が多いだろう（笑）
30万以上のデータをTrieに移し変えたら128MBとかじゃ全然足らんのですよ。
こっちの貧弱な環境の例だと、1GBにしたら一応読める事は読めるが、今度は実行時間制限に引っかかる。set_time_limit(0)もやらないといけないのでどんどんレンタルサーバ環境から遠ざかる。
計ってみると読み込みに必要な時間は7分、必要メモリ量が700MB強。解析に必要な時間は0.02秒だった。
Wikiはマシンが死にそうなので試してないけど、3GBくらいじゃないのと。
だから、基本的にこれだけの量のデータをリクエストごとに読み込むっていうのがまず非現実的。
本当は解析用サーバを別に持たせて、そっちのサーバで常時動かしているデーモンを作らないと無理。
本来全キーワード読みなんて重たい処理は一度やれば十分で、後はキーワード追加や削除のタイミングで更新すればいいだけなのに、毎回全読みになるのはきつい。
あくまでこういう実装もあるよという話なだけで、本来はちゃんと専用サーバおいて動かさないと駄目ですよということで。
実装としての改善案
一応、改善案としては「こんにちは」と「こんばんは」の場合に、いちいち「こ」「こん」「こんに」「こんにち」「こんにちは」「こんば」「こんばん」「こんばんは」の8つを作らないで、「こん」「こんにちは」「こんばんは」の三つに省略するって形が一つ。
もう一つ、Wikiの図柄からそういうもんかと判断したけど、「こ」「こん」「こんに」「こんにち」「こんにちは」のデータ構造じゃなくて、「こ」「ん」「に」「ち」「は」で作るってのもメモリ消費量的には意味がありそう。
元々仮実装に過ぎないものだから、作りこむ予定はないんだけど、1万キーワードくらいは耐えられるかと思ったのがそうでもなさそうなので、場合によってはちょいと考える。
loadTestで2万件を適当に作るようにした場合、データ構造構築にかかるのはローカルPCで2秒強。この程度なら許容範囲に見えるけど、数字放り込むだけと意味のあるメッセージが並んでいるパターンは大分生成コストが違うからなぁ。
function _loadTest() {
for ($i=0; $i<20000; $i++)
$this->tree->add($i);
}
仕様としての改善案
「3文字未満のキーワードは許容しない」とかの制限事項をつければ「こんにちは」のデータ構造は「こんに」「こんにち」「こんにちは」の三つに絞れる。五つと三つじゃ大違いよ。
はてなキーワードの場合は「一文字キーワードは不可」、二文字〜三文字キーワードは紛らわしいのは積極的に削除って方針っぽい。
二文字以上、にすると「こん」が最初になって「こん」「こんに」「こんにち」「こんにちは」の4文字。
それとくそ長いキーワードも防止しておくとよさそう。
妥当なのは2文字以上16または32文字以下くらいではなかろうか。
まとめ
リクエストごとにしかライフサイクルが無いものでTrie実装なんてやると、1万くらいでガタが来るんじゃないのと。
1万未満の場合はそれなりに動くと思うけど、仕様による制限事項とそれに合わせたアルゴリズムの改変と、後は必要に応じて省略なり不要バイトの削除なりをするのがよさげ。
当面、俺の方は現行の作りでのmatchAllを使って進めてみる予定。
