まえがき
PDFやExcelやWord、PowerPointなどの中身の文書も含めてキーワード検索を行うソフトウェア「探三郎」を開発して公開しています。ここでは全文検索ソフトを作成するに当たっての仕組み、アルゴリズム、そしてサンプルソースを紹介していきたいと思います。
近年は、あらゆる資料・文書・図書が電子化され、電子ファイルがパソコンやファイルサーバーの中に多く保管されるようになりました。保管するファイルの種類も数も年々、増加していく傾向にあります。こうなってくると目的のファイルをどこに保管していたのか、どのようなフォルダ名、ファイル名にしていたのか、わからなくなる事が多いのではないでしょうか。このような時に、全文検索ソフトを使って、キーワードで目的のファイルを探索する事ができれば、探していたファイルを素早く見つける事ができます。
全文検索の全体フロー
全文検索の実装には、大きく分けて次のようなフローになります。
(インディクスの作成)
① 対象のファイルの一覧を作成
② 各対象ファイルからテキスト情報を摘出
③ ファイルパス、ファイル名と取り出したテキスト情報を元にインディクスを作成
(検索)
④ 検索キーワードを元にインディクスを探索して、ヒットしたファイルの一覧を作成
⑤ ヒットしたファイルをヒット数、ファイル名、更新日付、ファイルサイズなどでソートして表示
インディクスを持たずに、検索の都度、実在のファイルからテキスト情報を読込んで探索するタイプの検索ソフトもありますが、PDFやOffice文書ではテキスト抽出に時間が掛かり、ファイル数が多くなると、結果が表示されるまで時間が掛かり、実用に耐えられなくなります。事前に検索に最適化したインディクスを作成する事で、断然に早く検索できます。対象のファイルの更新が頻繁ではない場合、ファイルの更新が検索結果に即座に反映する必要がない場合は、インディクス方式が最適です。インディクスは、１日に1回、１週間に１回、数時間に１回など定期的に更新すれば、ある程度、最新の状態を検索できます。
検索ソフトは、C言語で作成しています。検索には、どうしても時間が掛かってしまいます。PythonやPHPなどのインタプリタ方式の言語より、コンパイルして高速に動作する言語を選択しています。
次章からは、各機能の詳細について記載していきます。
①対象のファイルの一覧を作成
インディクスを作成するにあたり、検索対象とするファイルのリストを作成します。利用者が検索したいフォルダ、ファイルタイプは、ある程度、限定されていると思われます。資料のフォルダの中のPDFファイルだけ検索したいとか、見積りフォルダのExcelだけなど、必要なファイルに絞り込んで、インディクスを作成します。
②各対象ファイルからテキスト情報を摘出
ファイルの中身も含めた全文検索を行うには、ファイルの中のテキスト情報を抽出する必要があります。テキストファイルの場合、ファイルをそのままオープンして、ファイルの中身の情報を読み込むだけで済みます。HTMLファイルの場合は、同じくファイルをオープンして読み込みますが、<HTML> <B> などのタグがあるので、タグ情報を除去する事で、テキスト情報だけ抽出できます。Word,Excel,PowerPointなどのOffice文書の場合、.xlsxや.docxなどの拡張子のファイルは、ZIP形式で圧縮したファイルになっています。例えば、sample.xlsxをsample.xls.zip などに拡張子を変更すると、ZIP解凍する事ができます。解凍されたxmlファイルを読み込んで、タグを除去すればテキスト情報を抽出する事ができます。但し、xmlファイルの中には、属性情報なども混在しており、文書に記述されている内容を復元するには、xmlのフォーマットを解読する必要があり難解です。
PDFファイルの場合、PDFのフォーマットが公開されています。フォーマットに従って解析してテキスト情報を抽出すれば良いのですが、こちらもバージョンもいくつかあり、フォント情報などもあり、記載されている文書を復元するのは難解です。
そこで、各ファイルタイプのファイルから、テキスト情報を抽出する外部ツールを利用します。xdoc2txt が精度もよく、多くのファイル形式に対応しています。
xdoc2txtを使って、検索対象となる各ファイルに対して、一つ一つ、テキスト情報を取り出していきます。
cd c:¥test¥xdoc2txt¥
xdoc2txt.exe -s "c:¥temp¥sample1.xlsx" > "c:¥test¥doc¥sample1.txt"
ここで文字コードはSHIFT-JISで統一しています。UTF8でも構いません。すべてで文字コードを統一する事が必要です。更に、各ファイルから取り出したテキスト情報には、スペース、改行、制御文字などの情報が含まれています。スペースや改行は、テキスト情報を冗長化させるので、スペース、改行、制御文字は、除去します。
③ ファイルパス、ファイル名と取り出したテキスト情報を元にインディクスを作成
取出しテキスト情報を整理して、インディクスを作成します。
インディクスは、いろいろな持ち方があるかと思いますが、ここではサンプルとして次の形式を示します。
indexi.dat
インディクス対象のファイルの一覧をcsv形式で保存
1. ファイルパス名
2. m0: index.datの開始位置
3. m1: index.datのファイルパスの長さ
4. m2: index.datのファイルの中のテキスト情報の長さ
index.dat
検索対象のテキスト情報を保存。ファイルのパス,ファイルの中のテキストを対象ファイルの数だけ繰り返す。
int mkindex(void){
int i,m0,m1,m2,h;
char pbuff[5012],buff[5000000];
FILE *fp;
fp = fopen("indexi.dat","wt");
h = open("index.dat",O_WRONLY|O_BINARY|O_APPEND);
for(i=0;i<flist->Count;i++){
strcpy(pbuff,flist->Strings[i].c_str());
m1 = strlen(pbuff);
// テキスト情報を抽出する関数
m2=gfil(flist->Strings[i],buff);
write(h,pbuff,m1);
write(h,buff,m2);
fprintf(fp,"%s,%d,%d,%d\n",flist->Strings[i].c_str(),file_date,file_size,m0,m1,m2);
m0=m0+m1+m2;
}
fclose(fp);
close(h);
return 1;
}
indexi.dat
c:\電報\年賀001.txt,0,19,160
c:\電報\年賀002.txt,179,19,144
c:\電報\年賀003.txt,323,19,1,128
index.dat
c:\電報\年賀001.txt新年明けましておめでとうございます。 旧年中はいろいろとお世話になり、ありがとうございました。本年 もよろしくご指導、ご鞭撻のほどよろしくお願い申しあげます。c:\電報\年賀002.txt新年明けましておめでとうございます。 日頃のご愛顧を厚く御礼申しあげますとともに、今年一年が最良の 年でありますよう、心よりお祈りいたします。c:\電報\年賀003.txt明けましておめでとうございます。 はやばやのお年賀状、うれしく拝見いたしました。 遅ればせながら、新年のご挨拶を申しあげます。
④ 検索キーワードを元にインディクスを探索して、ヒットしたファイルの一覧を作成
入力されたキーワードを含む文書を探索します。
search(char *keyword)は、キーワードに対して、インディクス化したファイルの情報を１つ１つ読み出して、
キーワードがヒットするかを探索します。
gbmMatch(char *text, char *pattern,int len)は、search(char *keyword)から呼び出される関数で、textの中にpatternの文字が含まれている回数(ヒット数)を返します。ファイルパスと、ファイルの中の文字情報のヒット数をカウントしています。
0x81-0x9f,0xe0-0xefの文字の場合、処理を別けていますがこれは、SHIFT-JISで日本語文字の２バイトの場合の処理になります。
int search(char *keyword){
int m0,m1,m2,h;
char spath[5012],bu[5012],pbuff[5012],buff[5000000];
FILE *fp;
fp = fopen("indexi.dat","rt");
h = open("index.dat",O_RDONLY|O_BINARY);
while(fgets(bu, N, fp) != NULL) {
get_csv(bu,spath,m0,m1,m2);
lseek(h,m0,SEEK_SET);
m1 = read(handle,pbuff,m1);
m2 = read(handle,buff,m2);
nml = gbmMatch(pbuff,keyword,m1) + gbmMatch(buff,keyword,m2);
if(nml>0){
printf("%d : %s", nml,spath);
}
}
}
int gbmMatch(char *text, char *pattern,int len)
{
int i,j,patlen,n;
bool flg;
patlen = strlen(pattern);
n = 0;
for(i=0;i<=len-patlen;i++){
for(j=0,flg=true;j<patlen;j++){
if(text[i+j]!=pattern[j]){
flg=false;
break;
}
}
if(flg){
n++;
i=i+patlen-1;
}else if((((unsigned char)text[i]>=(unsigned char)0x81)&&((unsigned char)text[i]<=(unsigned char)0x9f))||
(((unsigned char)text[i]>=(unsigned char)0xe0)&&((unsigned char)text[i]<=(unsigned char)0xef))){
i++;
}
}
return n;
}
⑤ ヒットしたファイルをヒット数、ファイル名、更新日付、ファイルサイズなどでソートして表示
上記のソースのサンプルでは、ヒットしたファイルをprintfで出力しているが、実際にはいったん配列に格納して、ヒット数、ファイル名、更新日付もしくはファイルサイズの順にソートして、画面に表示するのが良いでしょう。更には、ヒットした文書の前後を表示して、キーワードに合致した部分を着色表示するなどすれば、探していた目的の文書かどうかを判定しやすくなるかと思います。
追加機能
上記で、全文検索ソフトの主要機能は実装できます。更に実用的な検索ソフトとする為には、次のような機能も必要となります。
・全角半角、大文字小文字、カタカナかな文字を区別しないで検索機能
・AND、OR検索機能
・インディクスの指定時間での自動更新機能
・バックグランドでのインディクス更新
また、サンプルコードにあるgbmMatchを使った検索方法では、1万ファイルぐらいの検索でしたら問題ありませんが、検索対象のファイル数が、数万件以上になってくると、検索に時間が掛かってしまいます。
最後に
今回、ここで紹介した全文検索ソフトのロジックは、探三郎の機能の基本的な部分を取り出して記載しています。
探三郎は、フリーで公開してますので、どなたでも御利用頂けます。探三郎では、上記の追加機能も含めて検索が行えるようにしております。
更に、探三郎では、gbmMatchでの検索に加えて、SENNAを使った検索も併用しており、10万件を超えるファイルに対しても１秒以内に検索結果が出るようになっています。
是非、ダウンロードしてお試しください。
また、探三郎は、すべてのソースファイルを有償で提供しております。ソースファイルの提供を希望される場合は、作者まで御連絡ください。