 WHAT'S THIS? HEADLINESLICENSEPROJECT ARCHIVE- RSS/1- WHAT'S NEW- FEATURES- RESOURCE- DOWNLOAD+ JESSIE + HttpVirtualUsers+ NSXBASIC+ genius_othelloCONTACT US　 ・RSS/1 - 検索キーワードおよび来訪履歴による自動カテゴリ化機能つきサーチエンジン　第4工程: インデックス作成エージェントの開発このフェーズでは，検索システムの命とも言うべき，インデックス作成システムの開発を行います．第4工程 追加1: 全文検索システムの試作第1回第4工程 追加2: 全文検索システムの試作第2回第4工程 追加3: 全文検索システムの試作第3回第4工程 追加4: 全文検索システムの試作第4回 　最初になにからするべきか恥ずかしながら，検索システムなぞ全く開発した経験もなければ，知識も全くありません．「何をするべきか」というよりは，まずどのように勉強を進めるかを考えなければなりません．これを読んでいる知識人の方，アホかと思われたでしょう．同じように勉強しようと思っている方，あまりに参考にならなくてがっかりされたことでしょう．しかし，わからないことをあえて一生懸命勉強することで，シロートでもある程度はできるのだということを知ってください．と，今のところ豪語しておきます．　無知の知まず，自分が「知らない」ということを認識しなければなりません．知らないので，現在実装されている一般的な方法を，かいつまんで少し調べてみる必要があります．現代の検索システムは，大量のデータを対象としているため，索引を作成しておくことはもはや必須です．必要であれば，その他の情報も同時に事前に作成しておきます．検索時は，検索語を分析し，索引を引き，該当するデータを検出します．従って，検索時に有利なインデックスを作成する方法が，検索速度や品質向上の鍵となります．　インデックスの種類と主な特徴インデックスとは，索引語や索引語が発見された文書と位置などを記録したものです．索引語は，一般的にはある文字数で文書を切り出したもの(N-gram)か，文書を品詞分解(形態素解析)して使用できるものを収集したものの，どちらかが使われているようです．両者のメリット・デメリットをまとめます．方法 メリット デメリット N-gram ・検索もれが少ない実装が容易である・文書の言語に依存しない・真の意味での全文検索が可能である ・インデックスのサイズが肥大化する・検索語の識別に工夫が必要である・検索ノイズが発生する 形態素 ・インデックスのサイズがN-gramと比較して小さくて済む・検索語と索引語が一致する場合が多いため，被検索文書の特定が簡単である・検索ノイズが発生しにくい ・ターゲットの言語に応じた形態素の辞書と形態素解析システムが必要になる・検索精度は形態素解析システムの品質によって左右される．検索の品質を維持するために，辞書のメンテナンスが必要になる・索引語が形態素に依存するため，検索もれが発生する 最近のサーチエンジンのトレンドとしては，索引語はN-gramで作成している様子です．しかし，企業内サーチエンジンなどの限定された環境であったり，検索語を自由文形式で入力したり，意味的に関連するページを付加的に抽出するような検索システムの場合，形態素で索引語を作成する場合も多いようです．ここで，用語の解説をします．勉強したてなので，間違っている場合もあります．間違っている場合は教えてください．【N-gram】エヌグラム文書をN文字で切り出した部品．例えば「間違っている場合」という文章を例にとると，「間違」「違っ」「って」「てい」「いる」「る場」「場合」「合」がそれである．N-gramのNは，切り出す文字列の長さに応じて，2gram(bi-gram)とか3gram(tri-gram)とか表現する．言語やその構成文字の種類によって，Nをいくつにすると良いかが違う．ある研究会の調査結果によれば，漢字は2gram，ひらがなは3gram，カタカナは3または4gramで出現することが多いらしい．最後に「合」と1gramのものも例示したのは，検索語が「合」であった場合，ヒットしなくなってしまうのを防ぐためである(末尾処理といいます)．【検索もれ】ケンサクモレ文書中に該当部分が存在するにも関わらず，検索結果として抽出できない・されないこと．例えば形態素で索引語を作成している場合を例にすると，文書が「検索語句」であった場合，「検索」でヒットしても「検索語」という検索語でヒットしないこと．文書を形態素で切り出す際に「検索」「語句」としてしまった場合に，「検索語」という索引語が生成されないことによる．なお，N-gramであればヒットする．【全文検索】ゼンブンケンサク検索語が単語であるかないかに関わらず，文書中に文字列として存在するかどうかを問う検索方法．逆にキーワード検索(?)では，対象文書からキーワードを抽出して辞書化しておき，検索語とキーワードが一致した文書を抽出して検索結果とする方法．従ってこの場合，検索語はキーワードとして何らかの文書と関連づけられている必要がある．文書中の全てのN-gramをキーワードとしているものが，全文検索とも言える．【検索ノイズ】ケンサクノイズひらたく言えば，意図しない検索結果．例えば検索語が「未解析」で2gramの索引語を作成していた場合，検索語も2gramに分割されてからAND検索されるので，「未解」「解析」を含む文書を検索することになる．ここで，「問題が未解決であるため，別途時間を作ってデバッグログを解析する必要がある」との文書中，「[未解]決」「[解析]する」でAND条件が成立するため，「未解析」という検索語が含まれないにも関わらずヒットしてしまう．これを解決するには，「未解」「解析」が隣接している位置に配置されているかどうかを判定する必要があるが，N-gramのNが小さいほど隣接確認の回数が増えるため，時間がかかる．なお，Nの値が大きいほどインデックスのサイズが大きくなる．【適合率】テキゴウリツ検索ノイズの低さを示す指標．適合率が高いということは，検索者の意図に近い文書がヒットしやすいということ．【再現率】サイゲンリツ検索もれの少なさを示す指標．再現率が低いということは，即ち検索もれが多いということになる．　RSS/1bにおけるインデックスの種類2つの方法を取り上げましたが，RSS/1bでは思い切って両方を実装する予定です．なぜなら，RSS/1bは製品化や役に立つものを目指して開発しているのではなく，サーチエンジンの開発に興味のある方に資料を提供したり，ソフトウェア開発の面白さを伝えることを目指しているためです．最終的にはどちらかになるでしょうが，今は決めていません．冒頭で書きましたが，全く知識がないので，まずは勉強してからです．そういう意味で，両方実装します．　インデックスの実装全文検索の場合，一般的には「転置インデックス」と呼ばれるものが採用されています．他にもいろいろあるようですが，あまり多くは聞きません．転置インデックスは単純なもので，図示すると索引語 文書1 文書2 索引語1 あり なし 索引語2 なし あり 索引語3 あり あり のようなものです．つまり，索引語がどの文書に出現するかを表にしたものです．「文書中にどの索引語が出てくるか」という視点からの転置形になるため，転置インデックスと呼ばれているようです．上記の転置インデックスによれば，索引語1と索引語3が出てくるのは，文書1ということになります．上記の単純な転置インデックスからは，索引語が「文書に含まれているか否か」ということしかわかりません．従って，よほど単純なものでなければ，普通は「あり」「なし」以外に，索引語が文書中に出現する位置も記録しています．位置情報がなければ，文書中には存在しない，ということです．世の中に全文検索システムはかなりの数存在しますが，基本形はこれのようです．実際には索引語は恐ろしい数量になるため，索引語の情報を発見する方法(ハッシュテーブルやその他の構造)や，索引語に対してどのような情報を付加するか(出現位置や共起情報など)や，検索語をANDやORなどで複雑に組み合わせた問い合わせ文をいかに効率よく処理するかや，不必要な索引語を登録しないようにする方法について，工夫をしていくようです．※共起 = 文章中にある語が出現した際に，別の語も同時に出現すること．英語を例にすると，'q'の次には必ずと言って問題ないほどの確率で，次には'u'がくる． この関係を共起と言う．なお，'q'の後に'u'がくる共起確率はほぼ1.00と言える．例は文字についてだが，語についても同じ考え方が適用できる．「戦争」という言葉を含む文書中，「平和」という単語が含まれる確率は，どのぐらいであろうか?それを文書中における「戦争」「平和」の共起確率と言う．文書ファイルやインデックスは，基本的に非常に大きくなる傾向があります．小さい文書ファイルを大量にディスク上に配置していると，ファイルのシークだけでも非常に時間がかかってしまい，効率的ではありません．Linuxなどでinodeでファイルを管理すれば，ファイル名ベースで管理するよりはかなり高速になるのでしょうが，特別な理由がなければ，大量のファイルを管理するのは結構な負担になります．できれば，いくつかの少ない数のファイルにまとめてしまい，シークポインタを移動することで文書間を移動するほうがよいでしょう．インデックスについても同様です．文書ファイルやインデックスなどの，非常に大きなデータファイルを，ファイル構造を維持したまま(例えば常にソートされている状態に保つetc)管理するのは，容易なことではありません．この部分については，検索システムとは別の理屈が必要になりますので，それはそのうち追いかけるようにします．今回は，参考文献だけ挙げてきます．　学習の進め方いきなり本開発を行なうのはかなり無謀ですし，またいろいろ考えすぎて時間だけが経過するように思われるため，まずは簡単なサンプルを開発し，感触を確かめます．最初は，N-gramで索引を作成するタイプの全文検索プログラムを開発します．下記の項目を満たしていれば，OKとします．索引はN-gramで作成する．Nの値は2である． 被検索文書と索引は，全てUnicode(big endian)とする．全角/半角を意識しないで済むため． 被検索文書は1つあたり数KBとし，5～10ファイル程度とする． 転置インデックスを作成する． インデックスファイルは，オープンソースのJDBMを使って管理する． 検索語は複数指定することができるが，AND検索のみとする． 検索速度やインデックスのサイズは，非常識でない限り気にしないものとする． 時間があれば，検索もれを減らすアルゴリズムで実装する． 「今後どのように開発していけば良いか」という問いに対する何らかの回答を得る． 注意点は，「あまり余計なことを気にしないで開発する」ことです．「コードがオブジェクト指向的に正しいかどうか」とか，「汎用性の有無」とか，「検索方法の妥当性うんぬん」とかを気にしていると，一向に前に進まないからです．ソースがきれいだろうがきたなかろうが，どうでもいいので開発します．もっとも，あまり汚いとわかりにくいソースになるので，そのあたりはある程度の品質は保つものとします．　今回の総括今回は，検索システムの非常に基本的な部分について勉強しました．次回は今回示したサンプルのコードを公開いたします．実は既にコードの一部を書き出しているのですが，ひとまずここで区切りをつけておきたいと思います．参考文献を以下に挙げておきますので，興味のある方は立ち読みでもしてみてください．　参考文献長尾　真　編　岩波講座 ソフトウェア科学15　自然言語処理，　岩波書店，1996，　ISBN 4-00-010355-5Michael J. Fork，Bill Zoellick 著， 楠本　博之・浜名　祐一 共訳　ファイル構造，　共立出版，1998，　ISBN 4-320-02899-6小川　泰嗣　Ricoh Technical Report No.25 「N-gram索引おける複合検索条件の効率的な処理方法」　Efficient Query Evaluation Method for Complex Queries in n-gram indexing，　1999小川　泰嗣，山本　研策，真野　博子，伊東　秀夫，　「全文検索システムのための複数転置ファイルを用いた登録高速化とランキング検索」(Extended Abstract)　出典不明，発表年不明　| 最新情報 | 特徴 | システム概要 | ダウンロード | お問い合わせ |　 COPYRIGHT 2001,2002,2003,2004 - LOGICAL-PARADOX.ORG