 WHAT'S THIS? HEADLINESLICENSEPROJECT ARCHIVE- RSS/1- WHAT'S NEW- FEATURES- RESOURCE- DOWNLOAD+ JESSIE + HttpVirtualUsers+ NSXBASIC+ genius_othelloCONTACT US　 ・RSS/1 - 検索キーワードおよび来訪履歴による自動カテゴリ化機能つきサーチエンジン　第4工程 追加1: 全文検索システムの試作第1回前のページで書きましたとおり，全文検索システムの試作を行います．　全文検索システム fts 1.0最初からRSS/1bに組み込む本格的な全文検索システムを開発するのはやめにして，ひとまず勉強のために簡単な全文検索システムを開発することにしました．2003/11/22～2003/12/1の期間に夏休みを確保しましたので，その間に開発をしました．前のページの内容を全て実装したわけではありませんが，ある程度のものができたので，ひとまず公開することにいたします．仕事が忙しいので，次のバージョンアップ予定は未定です．以下，fts 1.0の実装内容です．2-gramで索引語/検索語を切り出すN-gramによるインデックス作成を行なう． インデックスファイルはJDBMで管理する． 文書ファイルはUnicodeとする．索引語および検索語は，ひとまずShift_JISとする． 全文検索を行なう 被検索文書は1つあたり数KBとし，5～10ファイル程度とする． 転置インデックスを作成する． 検索ノイズを減らす努力はしている． 実装しきれなかったことで，問題のある部分もあります．検索語の長さは指定されないが，検索語は1つのみとする．空白などで区切って複数指定することはできない． インデックスファイルの作成に非常に時間がかかる．また，サイズも非常識に大きい． 検索語は1文字以上でなければならない． 　インストールなど下記のリンクから，必要なファイルをダウンロードしてください．2003-12-08 fts-1.0.lzh (lh5形式)この試作プログラムは，JDBMとJUnitを必要とします．これらのアーカイブは，各サイトから入手してください．JDBMJUnitJDBMは0.12を想定しています．その他のバージョンをご利用いただくには，ソースコードアーカイブ内のbuild.xmlの，jdbm-x.xx.jarのxの部分を修正してください．JUnitは，CLASSPATHの通った位置に配置してください．可能ならば，${JAVA_HOME}/jre/lib/extに配置しておくと，話が早いです．インストールするには，次の手順を実施してください．(1) ソースコードアーカイブを入手する．(2) 適当なディレクトリに展開する(以下，${FTS_HOME}と呼びます)．(3) JDBMを入手し，jdbm-0.12.jarを${FTS_HOME}/extへ配置する．jdbmのバージョンにより，jarアーカイブのファイル名が違うことが予想されます．(4) junitをダウンロードする．ダウンロードしたjarアーカイブに対して，CLASSPATHを通す．(5) cd ${FTS_HOME}して，antと入力する．インデックスの作成は，次の手順で実施してください．(1) 被検索文書をUnicode Big-endian(BOMあり)のテキストファイルで${FTS_HOME}/dbに保存する．ファイル名は，1から順番に番号でつける．拡張子はつけないものとする．(2) ${FTS_HOME}において，ant index と入力する．索引語レポートを作成するには，次の手順を実施してください．(1) ${FTS_HOME}に，fts.idx.dbおよびfts.idx.lgが存在することを確認する．(2) ${FTS_HOME}において，ant keyword > terms.txt と入力する．terms.txtはテキストファイルです．　検索プログラムの使い方ftsは，${FTS_HOME}にcdした後，ant ftsと入力することで起動します．検索結果はウィンドウ上部のテキストエリアに，検索する文字列はウィンドウ下部のテキストフィールドに入力します．検索する文字列を入力して[ENTER]を叩くと，検索結果が表示されます．検索結果は，該当した文書の数量と，文書No. 出現位置(Unicode BigEndianでカウントした，文書の先頭からの文字位置)が表示されます．　プログラムの話このサイトは，ソフトウェアを開発して公開することが目的のサイトではないので，ソフトウェアの中身の話をしなければなりません．今回，書かせていただく内容は，JDBMを使ってみての感想 org.logical_paradox.consoleパッケージと使い方 fts 1.0の仕組み 今後の開発方針 です．　JDBMを使ってみての感想今回，転置インデックスの管理モジュールとして，JDBMを使用しました．JDBMは，Javaで書かれたデータファイルの管理ライブラリです(恐らく)．JDBMは未だ開発途中ですので，今後いろいろと問題が解決されてゆくでしょう．0.12で気が付いた点をいくつか挙げてみたいと思います．・使いやすいJDBMで意識する必要のあるクラスは，JDBMRecordManagerと，JDBMHashtable，JDBMEnumerationのみです．他にもいくつかクラスが定義されていますが，APIのDOCにもないように，使う必要は全くありませんので無視していて問題ありません．JDBMRecordManagerは，JDBMのデータファイルを管理するクラスです．JDBMHashtableは，名前からもわかりますが，データファイルをHashtableとして扱うためのクラスです．ただし，JDBMHashtableはHashtableをextendsしていません．JDBMEnumerationは，Enumerationと同じで，JDBMHashtableにアクセスする際に使用します．ただし，JDBMEnumerationはEnumerationとは関係ありません．JDBMは，本格的に使うには問題があると思いますが，永続ストレージに対するHashtableだと考えれば，非常に使いやすいと思います．この「使いやすい」というのは意外と重要で，汎用性を持たせまくったあげくにどうやって使えばよいのか全くわからないライブラリなども(javaxなどのパッケージでも，いくつかありますが)ありますので，それらに比べれば遥かに良心的です．・でかいJDBMはファイルに対してオブジェクトをそのまま保存しています．ソースコードをのぞいたわけではないのでわかりませんが，生成されたファイルをざっと見てみたところ，classファイルのようなものが保存されているようです．例えば文字列を保存するにして，普通にバイトデータを保存するのではなく，クラスファイルのような形で保存されるので，サイズが肥大化します．あまり大量のデータ保存には向いていないのかもしれません．セッション情報の一時的な保存処理とか，アプリケーションの設定の保存程度に使用したほうが良さそうです．・データの削除ができないJDBMRecordManagerを通して，ハッシュテーブルをファイルに作成することができますが，それの削除に対応していません．一度作成されたデータは，ずっと残っています．削除するには，ファイル自体を削除しなければなりません．この部分，sourceforge.netのjdbmのメーリングリストにもありましたが，まだ作ってないとのことです．将来的には実装される可能性があります．　なお，JDBMでキーの一致/不一致判定はVectorクラスのindexOf()で識別しています．従って，キーとするオブジェクトにStringなどの既存のものを使わない場合，boolean equals(Object)メソッドをオーバーライドして実装する必要があるかもしれません．fts 1.0では，キーにInvertedIndexKeyクラスを使っているため，基底クラスのKeyクラスで，boolean equals(Object)メソッドをオーバーライドしています．　org.logical_paradox.consoleパッケージと使い方毎回毎回，swingで画面を作るのが面倒になってきたので，使いまわしのきくような簡易GUIパッケージを作成しました．ソースアーカイブ内の，${FTS_HOME}/ext/simpleconsole.jarです．アプリケーション固有の部分と，画面を分離してあります．画面は，上図のもので固定です．コントロールの配置変更や追加・削除は全くできません．画面の自由度を極限まで抑えて，使いやすさを追求しています．簡単な実験には非常に有用なパッケージになると思います．使い方を説明する時間がないので簡単な解説しておきますが，org.logical_paradox.console.ApplicationPackクラスのサブクラスを作成し，各種メソッドを実装します．次に，org.logical_paradox.console.SimpleConsoleWndのコンストラクタに，ApplicationPackのサブクラスを渡して，initApplication()を呼び出せばOKです．使い方につきましては，FullTextSearchApplicationPack.javaとFullTextSearch.javaを参照してください．　fts 1.0の仕組みまず転置インデックスを作成していますが，索引キーはInvertedIndexKey，索引キーの出現する文書番号と文書上の位置データとして，KeywordLocationクラスの配列を，jdbmを介してファイルに保存しています．InvertedIndexKey(索引キー)でhashtableを検索すると，その索引キーが出現する文書と位置の情報が，KeywordLocationクラスの配列として取得できるということです．検索処理自体は非常にシンプルで，次の方法で行なっています．(1) 検索語を2-gramに分解し，索引語とします．(2) 全ての索引語について，jdbm経由で検索します．全ての索引語がヒットしなければ，入力された検索語が存在しないことになるので，1つでもヒットしない索引語(JDBMHashtable.get()でnullが返ってきたなど)があれば，検索に失敗したことにします．(3) 全ての索引語が出現する文書番号を取得する．(4) 全ての索引語が連続して出現するかどうかを調べる．連続していれば，検索にヒットしたものとする．なお，索引語は(1)で分解された際の順番で配置されている必要がある．(5) 最終的にヒットした索引語群のうち，(1)で分解された最初の索引語の情報を，検索結果情報(位置など)として表示する．(3)と(4)のフェーズを分けているのは，なるべく余計な処理をしないようにするためです．とはいえ，fts 1.0のソースですと，特に効果はありません．今後アルゴリズムやデータ形式を改善していく際に，余計な検査やディスクアクセスを減らすのに効果があります．(2)の段階では，次のような感じでデータが抽出されます．(例) 検索語として「サーチエンジン」を入力した場合※文書1:102 = 文書番号1の先頭からのオフセット(文字数単位)102番KeywordLocation[0] = KEY: サー 文書1:102 文書1: 503 文書3: 3321KeywordLocation[1] = KEY: ーチ 文書1:103 文書1: 504 文書3: 3321KeywordLocation[2] = KEY: チエ 文書1:103 文書2: 339 文書3: 3321 文書3: 3430KeywordLocation[3] = KEY: エン ...KeywordLocation[4] = KEY: ンジ ...　:　:この状態では，「サー」「ーチ」「チエ」「エン」「ンジ」「ジン」が隣接している位置を調べるのが非常に面倒なため，(4)の最初でデータ構造を変更しています(SearchCore.parseKeyLocations())．変更後のデータ構造は，次の通りです．Hashtable[文書No.] = {Hashtable[先頭からのオフセット] = 索引キー,Hashtable[先頭からのオフセット] = 索引キー,:}例えば，文書番号1の「サー」のオフセットが102の場合，Hashtable[0][102] = 「サー」になっているはずです．そこで，if(　Hashtable[0][102] == "サー" && Hashtable[0][103] == "ーチ" && Hashtable[0][104] == "チエ" &&　Hashtable[0][105] == "エン"  && Hashtable[0][106] == "ンジ" && Hashtable[0][107] == "ジン") {　// 連続していた} else {　// 連続していなかった}という判定をします．別に意識したわけではありませんが，この方法は，日立のBibliotheca2 TextSearchが採用しているアルゴリズムに近いのかもしれません．先方の詳しい内容を見てないのでわかりませんが．まさかいくらなんでも，僕ごとき「ど」シロートにでも考え付くような方法ではないと思いますが..この方法の問題点は，全てオンメモリでやっている点です．今はよいのですが，KeywordLocation[]のサイズが巨大になった時に，メモリに載りませんので少し工夫する必要があります．しかし今は勉強のため，このままにします．　今後の開発方針さて非常に簡単な試作コードを書いてみて，いくつか思いましたので備忘録としての意味も兼ねまして，まとめます．・何かの共通のインターフェースを作っておいて，実装はRSS/1bとは別に行なう開発するには少し試行錯誤が必要であるため，ひとまずRSS/1bのことは忘れて，単体で動作する全文検索エンジンを開発するようにします．インターフェースと実装を分離しておくことで，RSS/1bからも使用できるようにします．こうしておいて，RSS/1bは無視して開発に集中します．また，インターフェースを実装することで，既存の全文検索エンジンをRSS/1bに組み込むことを可能にする予定です．・ストレージエンジンの部分も個別に実装する今回jdbmを使ってみましたが，どうもこのままだとRSS/1bの仕様には耐えません．従って，ストレージエンジンも独自に開発する予定です．単にjdbmだとダメとかいうのではなくて，自分で書いたほうが面白いだろうな，というのがその理由です．この，「面白いから」という理由が非常に重要です．昨今の趣味プログラマは実利ばかりに走って，おのれが楽しむことを忘れているような気がします．ストレージエンジンの部分も，RSS/1bおよび上記の全文検索エンジンとは個別に開発する予定です．もっとも，全文検索エンジン用のストレージエンジンにするつもりなので，RDBみたいな汎用性は予定していません．イメージ的には，RSS/1bに全文検索エンジンとストレージエンジンを組み込んで走らせる，という感じではないかと思います．全文検索エンジンは単体でも動作しますし，ストレージエンジンについても同様，という感じです．RSS/1bのシステムは，趣味で開発をしている人が楽しめるようにしたいので，自由にいろいろ組み込んだりコードを入れてみたりして，遊べるものにしていきたいです．　第4工程: インデックス作成エージェントの開発　| 最新情報 | 特徴 | システム概要 | ダウンロード | お問い合わせ |　 COPYRIGHT 2001,2002,2003,2004 - LOGICAL-PARADOX.ORG