あいまい全文検索におけるディスクアクセス数の見積もり

青木 太一 (0451001)

全文検索は，大量の電子文書から所望の部分を得るのに必要不可欠な技術である．
どれだけ大量の文書があっても，全文検索システムがなくては文書の利用価値は低い．
本研究で扱うあいまい全文検索とは，通常の全文検索と違い，
検索対象の文書中で検索語と「完全に」一致する部分だけでなく，
検索語からk文字の挿入，置換，欠落を許して一致する部分を得ることもできる検索である．
このようなあいまい検索は，文書中の誤字，脱字，表記ゆれをカバーして
検索ができるので有用である．

誤字，脱字，表記ゆれをカバーする検索は重要である．
ひとつには光学式文字読取装置(OCR)で紙媒体から変換された
電子文書の増加が上げられる．
OCRによる文書には誤認識による誤字脱字がある．
また，校正作業を経ないWebの文書や電子メールには多くの誤字脱字が含まれる．
特に新語や外国の固有名詞は，誤字脱字だけでなく，そもそも記述された
言語での表記法が定まっていない場合も多い．
例として「Levenshtein」という人名をWebで検索したとき，
正しい綴りだけでは約1/3のページをとり逃してしまうという報告がある．

一方で，近年の電子データの増加を鑑みると，あいまい全文検索システムが大容量の文書を
扱えることは重要である．もし文書サイズが検索システムのメモリに収まらない場合，
ディスクアクセスが発生する．
ディスクアクセス遅延時間は，メモリアクセス遅延時間の100倍程度長い．
このため，ディスクアクセス遅延が検索処理時間の大半を占める状況が発生しやすく，
検索速度向上のために，ディスクアクセス数を減らすことは重要である．

しかし，先行研究では文書とその索引がメモリにのることを前提としている．
ディスクアクセスの発生に注目した研究はなかった．
そのため，本研究ではメモリに収まらない大容量の文書に対するあいまい検索速度向上のため，
ディスクアクセス数に注目した．
具体的には，あいまい検索手法のデータ参照の様子からディスクアクセス数を見積った．

ディスクアクセス数を減らすためには，二つの要素がある．
一つは無駄なデータ参照をしないことである．
もう一つはデータ参照先を局所的にすることで，
ディスクキャッシュをきかせることである．

ディスクアクセス数を見積もった手法は二つである．
一つは動的計画法であり，この手法では，データ参照数は多いが，データ参照先は局所的であることがわかった．
ディスクアクセス数は，最悪時で文書長を記号数とメモリのページサイズで割ったものに比例することがわかった．

見積もりをしたもう一つの手法は動的計画法に接尾辞配列と
高さ配列という索引構造を併用するものである．
この手法では，データ参照数は少なくなるが，データ参照先は局所的でないことがわかった．
ディスクアクセス数は，平均で，記号数を許容する誤り数でべき乗したものに比例することがわかった．

本論文の見積もりは，誤り数，記号数，文書長に応じて適切なあいまい検索手法を選択する
指針となる．