 WHAT'S THIS? HEADLINESLICENSEPROJECT ARCHIVE- RSS/1- WHAT'S NEW- FEATURES- RESOURCE- DOWNLOAD+ JESSIE + HttpVirtualUsers+ NSXBASIC+ genius_othelloCONTACT US　 ・RSS/1 - 検索キーワードおよび来訪履歴による自動カテゴリ化機能つきサーチエンジン　第4工程 追加4: 全文検索システムの試作第4回fts 1.3を開発しましたので，公開いたします．　全文検索システム fts 1.3v1.2からかなり長いこと時間が経過しましたが，試作4号が完成しましたので公開いたします．fts 1.3は，全文検索システムとしては1.2と全く同じ機能/同じ精度を持ちます．唯一違う点は，ストレージ関連のライブラリをJDBMからlpcommon-btree他に移行したことで，インデックス生成の高速化を実現したことです．正直なところ，ストレージ関連ライブラリの開発をしこしことずっとやっていました．　インストールなどソースコードを下記のリンクから取得して，fts 1.0と同じ要領でインストールしてください．2004-07-07 fts-1.3.zip (zip形式)このアーカイブには，必要なライブラリ一式と，ビルドファイルであるbuild.xmlが含まれています．ビルド方法は1.0から変更ありませんので，わからない場合は以前の記事を参考にしてください．　ストレージ関連のライブラリについてJDBMがあまりにも遅いので，自分でストレージ関連のライブラリを開発していました．開発したライブラリは，次の3つです．lpcommon-core.jar (コアライブラリ) lpcommon-btree.jar (b-tree構造を実現するライブラリ) lpcommon-vrm.jar (可変長レコードファイルを扱うライブラリ) それぞれのソースコードは，下記のリンクから取得してください．2004-07-07 lpcommon-core-1.0.zip2004-07-07 lpcommon-btree-1.0.zip2004-07-07 lpcommon-vrm-1.0.zipビルド方法は，ソースコードを展開したディレクトリに移動し，コマンドプロンプト(ないしはシェル)よりantとするだけです．jarファイルが生成されます．　インデックスの管理方法についてfts 1.3より，独自で開発したb-tree構造を管理するためのライブラリでインデックスを管理するようにしました．lpcommon-btreeがそれです．ftsのインデックスは，(1)索引語そのものの情報 (2)索引語がどの文書のどの位置に出現するかを記録した転置情報 の2つで構成されていますが，lpcommon-btreeで管理するインデックス(fts.idx)は，このうちの前者のほうです．fts.idxに記録されるデータは全て固定長で，索引語の文字列そのものと，その索引語の転置情報(fts.idx.dat)のバイト変位です．実際の転置情報はfts.idx.dat(可変長レコードファイル)に配置されるため，転置情報への先頭からのバイト変位も記録するようにしています．転置情報については，可変長レコードファイルとして，lpcommon-vrmで管理しています．転置情報として記録されるデータは，JDBM版で生成していた転置情報と全く同一です．つまり，"[文書番号]位置情報"の配列です．　lpcommon-btreeについてlpcommon-btreeは，b-tree関連のライブラリです．b-treeはRDBMS他で一般的に採用されているデータ構造です．普通のツリー構造(2分木など)は一番上の階層から下へ向かって木が生長する仕組みになっていますが，b-treeの場合は一番下の階層から作成され，要素が追加されると上へ向かって成長する仕組みになっています．従って，どのようなデータがどのような順番で与えられたとしても，木は常に完全平衡になります．b-treeに関する詳しい説明については，インターネットで検索をするか，あるいは参考文献をあったてください．lpcommon-btreeで提供する機能は，b-treeにてデータを管理するための仕組みです．実際にファイルに格納するデータ構造などは，別途自分で定義する必要があります．ftsの場合，BtreeKeyクラスを拡張してFTSBtreeKeyクラスを定義しています．このクラスは，(1) 索引語の文字列表現 (2) 索引語に対応する転置情報のバイト変位 を管理しています．現在lpcommon-btreeでは，データの挿入と検索ができますが，更新と削除は実装していません．lpcommon-btreeに関する詳しい資料が欲しい場合は，こちらから要望をあげてください．時間がとれるようでしたら，今後解説を記述する機会があると思います．　lpcommon-vrmについてlpcommon-vrmは，可変長レコードのファイルを管理するライブラリです．lpcommon-btreeで扱うファイルは固定長レコードのため，レコード番号が分かればデータの格納されているバイト変位と，データのサイズがわかりますが，転置情報のデータサイズは常に不定であるため，可変長レコードのファイルとして管理する必要があります．lpcommon-vrmを使用する場合，任意のデータ型に対応する(1)RecordFactoryクラス (2)Recordクラス の2つを実装します．ftsの場合，KeywordLocationArrayFactoryクラスと，KeywordLocationArrayクラスがそれぞれに該当します。Recordクラスにはファイルに格納/復元したいオブジェクトを格納ますが，オブジェクトは必ずByteStreamの派生クラスでなければなりません．ByteStreamはlpcommon-coreで提供されているインターフェースで，バイト列への変換をサポートしています．ftsの場合，索引語の位置情報クラスKeywordLocationクラスがByteStreamインターフェースを実装しています．KeywordLocationArrayクラス(Record)のデータ型であるKeywordLocationArrayByteStreamクラスですが，これはKeywordLocationを配列として管理するクラスです．このクラスは，ArrayListByteStreamクラスのサブクラスとしています．バイト列変換可能な配列を使用する場合，ArrayListByteStreamクラスを派生させて，データ用のクラスを作成します．lpcommon-vrmの詳しい使い方は，別途解説する予定です．　lpcommon-btreeと，lpcommon-vrmについてですが，基本的にはデータ型とデータを生成するためのファクトリクラスを実装するだけで，b-treeあるいは可変長レコードファイルを扱える，という点がポイントです．　ライブラリ入れ替えの効果JDBMからlpcommon-btreeへライブラリの変更をした結果，どのような効果があったのかをまとめます．テスト環境は以下のとおりです．Windows2000AdvancedServer / Pentium4-1600MHz / 1.0GB memory / 7200rpm HDD 60GB　 fts 1.2(JDBM) fts 1.3(lpcommon-btree) 生成されるインデックスのサイズ(合計KB) 5065 6553 文書ファイル7件の処理時間(秒) 1285 120 fts 1.2よりfts 1.3のほうが若干サイズが大きいのは，可変長レコードファイルで断片化が発生しているのと，インデックスファイルのおけるページサイズ(次数16)の関係だと思われます．このあたりは，最適化処理をすると若干改善されると思われます．ページサイズや次数という語がわからない場合，b-treeの参考文献をあってください．　今後の予定多少インデックス作成速度が遅いですが，ひとまず耐えられる程度のものができたと考えています．fts自体の大きな問題として，N-gramのnの値より短い文字列が検索でヒットしない，というものがあります．これについては，もう少しいろいろ調べないとわかりません．調べていますが，そのあたりの処理に関する記述がどこにも見当たらない状況です．検索速度自体を高速化したい場合，主にインデックスファイルの構造を最適化する必要があるでしょう．サマリー作成処理については，研究の余地が尽きない分野でしょう．あまり時間をかけるつもりはありませんが，もう少しサマリー作成アルゴリズムだけを分離できる形に，ソースコードを改変するかもしれません．別の話をしますと，lpcommon-btreeのライブラリを使用する場合，b-tree構造に対する挿入と検索処理は排他ロックされますので，これが原因で並列化の効果を薄くしています．インデックス作成を分散化する場合，この部分を改善しなければなりません．また，検索処理などでb-tree構造を直接ドライブしていますが，この部分に何かもっと実装を意識しなくてすむインターフェースを入れる予定です．今後は全部並行して進めますが，(1) 各種インターフェースの整備(2) ftsのソースコード改善(3) lpcommon-btree/lpcommon-vrmのリファクタリング(4) RSS/1bで使用するindexerの作成(5) RSS/1bの探索システムとの連動(6) 全文検索用のwebアプリケーション作成の順番にならって設計・製造を進めたいと思います．また，当初の計画から方針や設計が変更されていますので，このサイトの過去のコンテンツを修正する予定です．　参考文献「ファイル構造」，共立出版，ISBN4-320-02899-6(b-treeその他のファイル構造に関する解説が記載されています)　第4工程: インデックス作成エージェントの開発　| 最新情報 | 特徴 | システム概要 | ダウンロード | お問い合わせ |　 COPYRIGHT 2001,2002,2003,2004 - LOGICAL-PARADOX.ORG