膨大な情報の中から必要な情報を的確に見つけ出すことが情報検索であり、情報検索は情報化社会における基本的な技能の一つに位置づけられる。文書検索はテキスト文書を検索対象とする情報検索である。本研究がテキストを対象としたのは、テキストが知識を表現する上で最も主要なメディアという地位にあるからである。電子化文書の増大・検索ユーザの拡大・文書共有化の進展という最近のIT革命の進展に伴い、文書検索に対するニーズも非常に高まっている。

　文書検索の対象は自然言語で記述されたテキストである。文法・語彙等の特性は言語によって異なるため、言語ごとに相応しい文書検索モデル・実装方法も異なる。特に、検索高速化のために必要不可欠な索引において、索引の基本要素である索引単位として何を選択するかは性能および運用しやすさに大きく影響する。代表的な索引方式には単語を索引単位とする単語索引とn-gram(n文字組)を索引単位とするn-gram索引がある。単語を分かち書きせず、造語力の高い日本語においてはn-gram索引が広く利用されているが、n-gram索引には検索速度が遅いという問題がある。その理由は、ユーザから与えられる検索文字列が索引単位であるn-gramに一致するとは限らず、一致しない場合には複数のn-gramを用いて検索結果を求める必要があるからである。特に検索文字列がn-gramよりも長い場合には、検索文字列中のn-gramが全て出現する文書を特定(候補文書特定処理と呼ぶ)した上で、そのような文書においてn-gramが適切な相対位置にあって検索文字列を構成していることの確認(位置検査処理と呼ぶ)が必要であり、高速化の余地が大きい。

　本論文では、日本語文書を対象としたn-gram索引の検索処理の高速化について研究する。高速化の基本原理は、n-gram索引における検索コスト増大の主要因である位置検査処理を可能な限り省略・低減するというものである。n-gram索引における検索高速化の従来研究は、複数のnを組み合わせる、文字種に応じてnを調整する等のn-gram抽出法に集中していた。これに対し、本研究は検索処理法および索引の物理編成法の改良による高速化である点に特徴がある。

　検索処理法の改良では位置検査の削減・省略に着目した。日本語では造語力の高さから長い複合語がいくらでも生成されるため、n-gram抽出法の工夫だけではn-gram索引における検索速度低下要因の位置検査を無くすことが不可能だからである。位置検査省略による検索高速化という考え方は従来研究にも存在している。しかし、従来研究が単一検索文字列の場合のみを極めて限定的に扱っていたのに対し、本研究では以下の3点について拡張する。

(1)単一検索文字列処理において、省略するn-gramを動的に選択するように拡張

従来は候補文書特定と位置検査の両フェーズに同一のn-gram群を静的に選択していた。これに対し、本研究では両フェーズの処理特性の違いに着目して異なるn-gram群を索引内容に応じて動的に選択する。実際には、位置検査用には検索文字列を被覆するn-gram群のなかからn-gramの文書頻度の合計が最小となる組み合わせ(最小頻度パスと呼ぶ)を動的に選択し、候補文書特定には最小頻度パスにそれらの前後にある文書頻度の少ないものを加えたn-gram群を用いる選択n-gram法を提案した。選択n-gram法により、位置検査を行うべき文書数を削減するとともに位置検査自体のコストも低減し、単一検索文字列の検索処理を高速化できる。

(2)AND・OR・ANDNOTの論理演算子に拡張

従来は単一検索文字列の処理のみを高速化の対象にしており、論理演算子処理を対象とする研究はなかった。これに対し本研究では、論理演算子の処理アルゴリズムを複数の検索文字列の論理関係を考慮することで不要な位置検査を行なわないように改良し、検索を高速化する。AND，OR，ANDNOTの3種類の論理演算子について、この考えに基づく拡張省略法を提示した。さらに、演算子が入れ子になった複合条件に対しても拡張省略法が適用できることを示した。

(3)ランキング検索に拡張

ランキング検索では検索条件に対する文書スコアに応じて検索された文書を順序付けする。文書スコア計算には文書頻度・文書内頻度の2種類の頻度情報が必要であるが、両頻度を求めるたびごとに位置検査が発生するため検索コストが増大する。従来研究としてn-gramの頻度情報に基づいてスコア計算するスコア合成法が提案されているが、検索精度の低下という問題があった。これに対し、検索精度を低下させることがないように検索文字列の頻度情報に基づいてスコア計算しつつ、頻度情報を求める際に必要な位置検査を可能な限り削減する2つの高速化手法を提案した。1つ目の順序入れ替え法は、検索文字列が出現する文書を特定すると同時に文書内頻度も求めることで、従来必要であった文書頻度を単独で求める処理を省略する。もう1つの頻度推定法は、検索文字列を構成するn-gramの頻度情報から文書頻度および文書内頻度を近似的に求めることで位置検査を省略する。これら2つの高速化手法は組み合わせ可能であり、相乗効果が期待できる。なお、推定頻度は必ずしも正しい値にならないため、頻度推定法によるランキング結果は基本方式のものと同一とは限らないが、検索精度への影響は極めて小さいと考えられる。

　n-gram索引のファイル形式としては、n-gramの各文書における出現位置を格納可能である転置ファイルが一般的である。本研究では、位置検査省略による検索高速化手法向けの転置ファイルの物理編成法も提案する。単語索引用転置ファイルの物理編成法は従来から研究されており、その一部はn-gram索引に対しても有効である。本研究では、n-gram索引では検索処理が候補文書特定と位置検査の2つのフェーズから構成され、文書内出現位置は位置検査でしか用いられないという処理特性に着目した物理編成法を提案する。具体的には、n-gramの出現情報を、文書IDとそれ以外の文書内頻度・出現位置情報に分離して配置するとともに、出現情報を圧縮する際にブロック化する。以上の工夫により、ページアクセスおよび検索時の伸長処理を大幅に削減することが可能となる。

　提案高速化手法の評価実験を行った。単一文字列と論理演算子については新聞記事8年分、85万文書(テキスト量748MB)を用いて評価した。ランキング検索については論文要旨33万文書(テキスト量267MB)から成るテストコレクションNTCIR-1を用いて評価した。以下の表は評価結果のまとめである。

　この表は、全データの読み込みを伴うCOLD、条件評価フェーズにおけるデータ読み込みのみのWARM、データ読み込みを伴わないHOTの3つ場合について、従来手法に対する提案手法の検索速度の向上率を示している。ランキング検索については、高速化効果が最大であった順序入れ替え法と頻度推定法を組み合わせの結果を用いている。この結果から提案手法により検索が大幅に高速化され、特にAND演算子、ランキング検索に対する効果が大きいことが確認できる。また、COLD，WARM，HOT となるにしたがって高速化効果が大きく、HOTでは73〜250%に達していることから、提案手法はディスクアクセスよりもCPU処理の削減に効果が大きいことがわかる。

　つぎにランキング検索における単語索引n-gram索引の性能比較結果を示す。

　この表で、n-gram索引は従来方式、改良n-gram索引は提案方式の結果である。改良n-gram索引では検索精度をほとんど低下させることなく検索を高速化した結果、単語索引に対する検索時間の差異が小さくなることが確認できた。特にHOTにおいては検索時間の差は約10%と小さい。本実験はbi-gram索引を使用するというn-gram索引にとって不利な状況での測定結果ということを考慮すると、検索が遅いというn-gram索引の問題点は提案手法によりかなり克服できたと言える。

　また、物理編成法の改良に関する性能評価も行った。本研究で提案した出現位置情報の分離とブロック化自体の組み合わせにより、基本的な転置ファイルの物理編成法に対して 81%(COLD)，128%(WARM)，860%(HOT)の高速化を達成できることを確認した。

　本研究の成果は全文検索エンジンであるFTSサーバとして製品化され、当社の図書管理システムやオフィス向け文書管理システムなどで広く採用されている。FTS最初のバージョンの開発時に行った性能比較によれば、当時市場で最高速であるという評判の商用文書検索システムに対して2.5倍(HOT)から4.0倍(COLD)高速であり、提案高速化手法の有効性が製品レベルでも確認できた。

　今後の課題としては、日本語以外の言語に対する提案手法の有効性の検証、更新性能を考慮した複数索引への対応、質問拡張の高速化検討などがあげられる。日本語以外の言語の対応では中国・韓国語等の東アジアの言語が主な対象となるが、言語特性から提案手法が有効であることが期待できる。複数索引への対応についてはランキング検索の高速化が問題となるが、順序入れ替え法を拡張することで対応可能と考えられる。質問拡張については、選択する関連語の選択時の頻度取得が速度上の問題となるが、頻度推定法の適用により対応可能と考えられる。

　本論文は「日本語文書を対象としたn-gram 索引による高速検索手法の研究」と題し、IT社会の進展に伴う文書検索に対する高速化要求の高まりを受け、日本語文書に対する代表的な索引の一つであるn-gram(n文字組)を索引要素とするn-gram索引の検索高速化に関し纏めたものであり、検索においてコスト増大の主要因である位置検査処理を可能な限り削減することにより処理の効率化を図る高速検索手法および当該手法に適したn-gram索引の物理編成法を提案すると共に、評価実験によりその有効性を検証しており、9章から構成される。

　第1章は「序論」であり、本研究の背景および目的について概観し、本論文の構成を述べている。

　第2章は「n-gram 索引の基本概念」と題し、3章以降の議論の前提となるn-gram 索引の基本概念を説明している。まず、登録処理、検索条件を満足する文書を特定するブーリアン検索処理、検索文書を検索条件に対する適切さに応じて順序付けるランキング検索処理などn-gram 索引の基本動作について述べ、つぎにn-gram索引のファイル形式である転置ファイルの基本構成と圧縮方法を紹介している。

　第3章は「ブーリアン検索処理の高速化」と題し、検索文字列中のn-gram群が文書中で文字列を構成することを確認する位置検査を削減・省略することにより検索を高速化する手法を提案している。

　第4章は「ブーリアン検索高速化手法の評価」と題し、新聞記事8年分、約85万件、約750MBの検索対象文書と、280個の検索条件を用いて、ブーリアン検索の高速化手法を評価している。単一検索文字列における速度向上は二次記憶装置へのアクセスを伴うCOLDでは8.3%、主記憶上の処理のみであるHOTでは73%であり、論理演算子における速度向上はCOLDでは10.7%、HOTでは110%に達し、提案手法の有効性が確認されている。

　第5章は「ランキング検索処理の高速化」と題し、ランキング検索では検索条件に対する文書の適切さを表す文書スコア計算に文書頻度、文書内頻度の2種類の頻度情報が必要となり、両頻度を求めるごとに位置検査が発生するため検索コストが大きいことを指摘した後、位置検査を削減する2つの高速化手法を提案している。1つ目の順序入れ替え法は、検索文字列が出現する文書を特定した結果から文書内頻度を算出することにより、従来必要であった文書頻度のみを求める処理を省略し、検索を高速化するものであり、他の1つの頻度推定法は、検索文字列を構成するn-gramの頻度情報から文書頻度および文書内頻度を近似的に求めることにより位置検査を省略し、検索を高速化するものである。さらに、両手法の組み合わせについても考察している。

　第6章は「ランキング検索高速化手法の評価」と題し、ランキング検索用の標準的な評価用データセットであるNTCIR-1予備版(論文要旨約33万件、約270MBの検索対象と、30件の自然言語で記述された検索要求から構成される)を用いて、提案した高速化手法を評価している。その結果、順序入れ替え法と頻度推定法の組み合わせにより、36.2%から91.7%の速度向上が得られる一方で検索精度には統計的に有意な差が生じないことが確認され、提案手法の有効性が検証されている。

　第7章は「高速検索手法向きの転置ファイルの物理編成法」と題し、n-gram索引を構成する転置ファイルの物理編成法を高速検索手法の視点から検討し、文書IDと文書内頻度・出現位置の分離、固定長ブロック単位の圧縮などを組み合わせた物理編成法を提案している。単純な物理編成法と比較して、最大で9.6倍の高速化が達成されることが確認されている。

　第8章は「実システムにおける評価」と題し、提案手法を組み込んだFTSという文書検索システムについて説明している。さらに特許システムの事例データを用いてFTSと他の検索システムの性能比較を行い、FTSの優位性が確認されている。

　第9章は「結論」であり、本研究の成果と今後の課題について総括されている。

　以上、これを要するに本論文は、n-gram索引による文書検索に関して、位置検査の低減を図ったブーリアン検索およびランキング検索に対する新しい高速検索手法を提案するとともに、当該手法に適したn-gram索引の物理編成法を提案し、評価実験によりその有効性を示したものであり、電子情報工学上貢献するところが少なくない。

　よって、本論文は、博士(工学)の学位請求論文として合格と認められる。