はてなブックマーク

PHP で SuffixArray による結構速い全文検索というのをつくってみようと思い立ち実装してみました。 SuffixArray を実装することによって単純に検索した場合 O(n) の計算量を O(logn) に減らすことが出来ます。またこの方法は漏れなく検索することができ、なおかつインデックスサイズも少ないという他方法（転置インデックス等）に対しても利点があります。 準備として文書集合をつっこんでインデックス集合を作成します。 実行として単語とインデックスをつっこんで、ヒット確認します。 usort 時に変数の渡す方法が PHP では普通の方法で提供されていないため 開発用メモ » Blog Archive » php：関数に変数をバインドしたい を利用させてもらいました。ありがとうございます。 <?php require_once('binder.php'); function

計算機科学を少しずつ勉強しています。今まで、何も考えずに、遊びで言語を実装したり、オペレーションシステムの簡単なものを実装したりということはやっていましたが、体系的に物事を理解するのもいいですよね。 まず最初に、どういった分野があるのかということを俯瞰的に知ることが大切です。私は、最近発行された東京大学の理学部情報科学科学科紹介がいいなと思いました。分野ごとの説明だけでなく、第一人者の教授によるイントロダクション・計算機に関する現在・未来が経験者の話を交えて紹介されていて、楽しかったです。東大生っていいな・すごいな。 http://www.is.s.u-tokyo.ac.jp/pamph/ 次に教科書を調べましょう。自力で学ぶ場合は id:taorleo さんの「Leo's Chronicle: ぜひ押さえておきたいコンピューターサイエンスの教科書」が参考になりそうです。 http://l

前回に引き続き検索エンジンについて勉強中です。今回は少し PHP だと気軽に出来るかもしれない、出来ないかもしれないサイトの情報収集ツールつまるところのクローラを構築してみました。 Google や Yahoo などの検索エンジンは、いくら検索アルゴリズムを良くして、ランキングの精度をあげても、収集したサイトの情報あってこそで、元の情報が少なかったり、精度が悪いと、良い情報を提示することは出来ません。そんなわけでサイト情報を頑張って収集するクローラが必要です。 流れとしては 1. 起点のサイトを決めて、そこからリンクを再帰的に巡り情報を収集する 2. 収集したサイトから本文を抽出する となります。 まず 2. のフェーズは、検索を行った際に、広告情報などでヒットされては困る（精度が悪くなる）ので、必要になってきます。 サイボウズラボの nakatani さんが実装されたものを PHP に移

Google の検索エンジンがページのランク付けのために PageRank という指標を使っているというのは聞いたことがあるかと思います。 今日はそのアルゴリズムを PHP で軽めに実装してみました。 ちなみに PHP で実装しても何もいいことがないので、やめたほうがいいでしょう。 まず PageRank というのは簡単に説明すると、 Google が考案したページのランク付けアルゴリズムでページへリンクがそのサイトの評価だという視点でランク付けを行うために作られたものです。 詳細については Google の秘密 - PageRank 徹底解説 を参考にしてみて下さい。 その内部アルゴリムですが、おおざっぱにいえば下の箇条書きにあるよう生成された確率行列の、最大固有値（確率行列はだいたいの場合において1）の固有ベクトルをべき乗法で求めることになります。 なぜ確率行列の主固有ベクトルを求める