(57)【特許請求の範囲】
【請求項１】
データベースの各文書から長さmのm-サブシークエンスを、互いにn-1(n:n-gramの長さずつ重なるように抽出し、m-サブシークエンスが文書上で出現したオフセットを保存する第１工程、
前記第１工程で保存した各オフセットに対して、所定のm-サブシークエンスが所定文書のオフセットで出現した場合、前記所定のm-サブシークエンスに該当するバックエンド逆索引の用語に対する第１ポスティングリストに該当の第１ポスティングを追加してバックエンド逆索引を構築する第２工程、
前記第１工程で得られたm-サブシークエンス集合の各m-サブシークエンスからn-gramを抽出し、n-gramがm-サブシークエンス上で出現したオフセットを保存する第３工程、及び、
前記第３工程で保存した各オフセットに対して、所定のn-gramが所定のm-サブシークエンスのオフセットに出現した場合、前記所定のn-gramに該当するフロントエンド逆索引の用語に対する第２ポスティングリストに該当の第２ポスティングを追加してフロントエンド逆索引を構成する第４工程、からなり、
前記第１ポスティングは文書識別子と位置情報を合わせたものであり、一つの前記第１ポスティングリストは、一つの用語に関連して、文書識別子と位置情報がリスト構造に管理され、前記文書識別子は文章を識別し、前記位置情報は用語の出現に対応し、前記オフセットは、該当用語が出現する位置を示し、
前記第２ポスティングはm-サブシークエンス識別子と位置情報を合わせたものであり、一つの前記第２ポスティングリストは、一つの用語に関連して、m-サブシークエンス識別子と位置情報がリスト構造に管理され、前記m-サブシークエンス識別子はm-サブシークエンスを識別し、前記位置情報は用語の出現に対応し、前記オフセットは、該当用語が出現する位置を示すことを特徴とするコンピュータによって実行される２工程n-gram逆索引構成方法。
【請求項２】
前記第１工程では、最後のm-サブシークエンスの長さがmより小さい場合、文字列の後ろ部分に空白文字を付け加えて長さがmになるようにすることを特徴とする、
請求項１に記載のコンピュータによって実行される２工程n-gram逆索引構成方法。
【請求項３】
前記第３工程で前記サブシークエンスからn-gramの抽出が、１-スライディング方式で行なわれることを特徴とする、請求項１に記載のコンピュータによって実行される２工程n-gram逆索引構成方法。
【請求項４】
請求項１に記載の２工程n-gram逆索引構成方法により構成された前記バックエンド逆索引及び前記フロントエンド逆索引を使用してクエリを処理する方法であって、
所定クエリをn-gramに分割する第１工程、
前記フロントエンド逆索引を使用して前記第１工程で求めた各n-gramに対する前記第２ポスティングリスト間でm-サブシークエンス識別子を用いてマージ外部結合(merge-outer-join)し、前記クエリをカバーするm-サブシークエンスを所定集合に追加する第２工程、及び、
前記バックエンド逆索引を使用して前記第２工程で求めた所定集合に含まれたm-サブシークエンスに対する前記第１ポスティングリストを文書識別子でマージ外部結合しながら、所定の同一な文書から抽出されたm-サブシークエンスの集合が前記クエリを包含するかどうかを検査して、クエリに包含されば前記所定の同一な文書をクエリ結果として返す第３工程、からなることを特徴とするコンピュータによって実行される２工程n-gram逆索引を利用したクエリ処理方法。
【請求項５】
前記m-サブシークエンスがクエリをカバーするかどうかは、マージ外部結合される前記第２ポスティングが持っている位置情報を利用して確認することを特徴とする、
請求項４に記載のコンピュータによって実行される２工程n-gram逆索引を利用したクエリ処理方法。
【請求項６】
前記第３工程での集合がクエリを包含するかどうかは、マージ外部結合される前記第１ポスティングが持っている位置情報を利用して確認することを特徴とする、
請求項４に記載のコンピュータによって実行される２工程n-gram逆索引を利用したクエリ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、逆索引構造及びその構築成方法に関するもので、特にn-gram逆索引（n-gram索引と省略される）に存在する位置情報の冗長性を除去してn-gram索引のサイズを減らし、且つクエリ処理性能を高めた2工程n-gram逆索引（n-gram/2Lと省略される）の構造及び、その構成方法とクエリ処理方法とその索引導出方法とに関するものである。
【背景技術】
【０００２】
テキスト文書データに対する検索は、非常に基本的で重要な演算として日常生活で広く使われている。その例として、情報検索、タンパク質とDNAのシーケンスに対する類似シーケンスマッチング等がある。DNA及びタンパク質のシーケンスは、特別なアルファベット(例えば、DNAの場合には{A、C、G、T})に対するテキスト文書データであると見なされる。このようなテキスト文書データに対する検索演算を効率的に処理するために多様な索引構造が研究されてきた。その中で実用的に一番広く使われる索引構造は、逆索引(Inverted Index)である(Ricardo Baeza-Yates and Berthier Ribeiro-Neto、Modern Information Retrieval、ACM Press、1999年)。
【０００３】
逆索引は、クエリで与えられた用語を含んでいる文書を早く検索するターム指向(term-oriented)のメカニズムである。ここで文章(document)は文字(character)の限定されたシークエンスで、用語(term)は文書のサブシークエンスである。逆索引は、基本的に用語に対するポスティングリストで構成される(Falk Scholer、Hugh E. Williams、John Yiannis and Justin Zobel、"Compression of Inverted Indexes for Fast Query Evaluation、" In Proc. Int'l Conf. on Information Retrieval、ACM SIGIR、Tampere、Finland、2002年,  8月,  222-229頁)。
【０００４】
一つのポスティングリストは一つの用語に関連する。文章識別子と位置情報がリスト構造で管理され、文書識別子は文章を識別し、位置情報は用語の出現に対応する。ここで、文書識別子と位置情報を合わせてポスティングと呼ぶ。
【０００５】
各用語tに対してポスティング<d、[o1、...、of]>を含むポスティングリストが存在する。但し、dは文書識別子であり、[o1、...、of]はオフセットoのリストであり、そしてｆは文書の中に用語tが出現する回数を表す(Falk Scholer、Hugh E. Williams、John Yiannis and Justin Zobel、"Compression of Inverted Indexes for Fast Query Evaluation、" In Proc. Int'l Conf. on Information Retrieval、ACM SIGIR、Tampere、Finland、2002年,  8月,  222-229頁)。
【０００６】
一般的にクエリ処理を容易にするために、ポスティングリスト内のポスティングは、文書識別子dの昇順に保存され、ポスティング内のオフセットはオフセットoの昇順に保存される。また、ポスティングリストを早く検索するためにB+-ツリー等の索引が用語に対して構成される。図1はこのような逆索引の構造を示している。
【０００７】
逆索引は、用語の種類によって単語を用語として使用した単語ベースの逆索引と、n-gramを用語として使用したn-gramベースの逆索引(n-gram検索と省略する)に区分される(Ethan Miller, Dan Shen, Junli Liu and Charles Nicholas, Performance and Scalability of a Large-Scale N-gram Based Information Retrieval System, Joournal of Digital Infoormation 1(5), 1〜25頁, 2002年1月)。
【０００８】
この中でn-gram索引は、n-gramを用語として抽出して構成された逆索引である。n-gramは文書dが文字のシーケンスc0、c1、...、cN-1で与えられた時、dから抽出されたn個の連続的な文字からなる文字列である。
【０００９】
n-gram索引を構成するために与えられた文書dからn-gramをもれ無く抽出する方法は、1-スライディング方式で、すなわちn個の連続的な文字からなるウィンドウをc0からcN-nまでスライドさせ、ウィンドウ内に位置した文字列を保存するのである。したがって、dのi番目n-gramは文字列ci、ci+1、...、ci+n-1になる。
【００１０】
図2は、与えられた文書の集合からn-gram索引を構成した例である。ここで、n=2である。図2aは、与えられた文書集合を示し、図2bはそれに対して構成されたn-gram索引を示す。
【００１１】
n-gram逆索引を使用したクエリの処理は、次の２つの工程で実行される。
（１）クエリ文字列を複数のn-gramに分割し、そのn-gramのポスティングリストを捜す工程。
（２）前記ポスティングリストをマージする工程(Ricardo Baeza-Yates and Berthier Ribeiro-Neto、Modern Information Retrieval、ACM Press、1999年)。
【００１２】
例えば、図2のn-gram逆索引で文字列"BCDD"を含んでいる文書を捜すクエリは、次の二つの工程で行われる。
【００１３】
第一工程では、クエリ文字列を"BC"、"CD"、"DD"の三つの2-gramに分割し、逆索引で各2-gramを捜す。
【００１４】
第二工程では、各2-gramに対するポスティングリストは文書識別子でマージ結合され、"BC"、"CD"、"DD"のように三つの2-gramが連続して出現して"BCDD"を構成する文書が探される。ポスティングリストをスキャンした文書 0及び2で三つの2-gramが連続して出現するのでクエリ結果は、文書識別子0及び2になる。
【００１５】
n-gram逆索引は、言語中立的であり、エラートレラントであるという長所を有する(Ethan Miller, Dan Shen, Junli Liu and Charles Nicholas, Performance and Scalability of a Large-Scale N-gram Based Information Retrieval System, Joournal of Digital Infoormation 1(5), 1〜25頁, 2002年1月)。
【００１６】
言語中立的と言うのは、索引用語を機械的な方式で抽出するので言語的な知識を要しないということを意味する。
【００１７】
このような特性によって、n-gram索引は複雑な言語的な知識を要するアジア圏言語に対する情報検索や、単語の概念が明確ではないDNA及びタンパク質のデータベースに多く使用されている。
【００１８】
エラートレラントと言うのは、索引用語を1-スライド方式で抽出するので、例えばタイプミスやＯＣＲソフトウェアによるご認識など、文書にいくらかのエラーがあっても、その文書を検索することができるということを意味する。
【００１９】
このような特性によってn-gram索引は、近似文字列マッチングのようにエラーを許容して文書を検索するためのアプリケーションにおいて有用に使用できる。
【００２０】
しかし、n-gram逆索引は、索引サイズが大きくて、クエリ処理時間が長くかかるという短所を有している(James Mayfield and Paul McNamee, Single N-gram Stemming, In Proc. Int’l Conf. On Information Retrieval, ACM SIGIR, Toronto, Canada, 415〜466頁, 2003年7〜8月)。
【００２１】
この短所は、例えば1-スライディング方式のような用語抽出方法の特性が原因である。
【００２２】
1-スライディング方式は抽出されるn-gramの数が急激に増えるので、n-gram索引サイズも大きくなる。
【００２３】
また、クエリ処理時にアクセスしなければならないポスティングの数が多くなるため、クエリ処理時間も長くかかる短所がある。
【発明の開示】
【発明が解決しようとする課題】
【００２４】
このような問題点を解決するために、本発明は、n-gram索引に存在する位置情報の冗長性を除去してn-gram検索のサイズを減らし、且つクエリ処理性能を高めたn-gram/2Lの構造及び、その構成方法とクエリ処理方法とその索引導出方法を提供することにある。
【課題を解決するための手段】
【００２５】
本発明の前記目的は、文書から抽出されたサブシークエンスを用語として使用するバックエンド逆索引、及び前記サブシークエンスから抽出されたn-gramを用語として使用するフロントエンド逆索引、からなることを特徴とする。
【００２６】
前記バックエンド逆索引は、文書から互いにn-1(n:n-gramの長さ)ずつ重なるように抽出された所定長さのサブシークエンスを用語として使用して、各サブシークエンスに対するポスティングリストにはそのサブシークエンスが文書上で出現した位置情報を保存する。
前記フロントエンド逆索引は、前記サブシークエンスから1-スライディング方式で抽出された所定長さのn-gramを用語として使用して、各n-gramに対するポスティングリストにはそのn-gramがサブシークエンス上で出現した位置情報を保存する。
【００２７】
本発明の別の目的は、データベースにおいて各文書から長さmを有するm-サブシークエンスを互いに一部分ずつ重なるように抽出し、m-サブシークエンスが文書上で出現した位置情報を記録する第1工程、前記第1工程で記録した各位置情報に対して、所定のm-サブシークエンスが所定文書のオフセットで示されたら前記所定のm-サブシークエンスに該当するバックエンド逆索引の用語に対するポスティングリストに該当ポスティングを追加してバックエンド逆索引を構築する第2工程、前記第1工程で得られたm-サブシークエンス集合の各m-サブシークエンスからn-gramを抽出、n-gramがm-サブシークエンス上で出現した位置情報を記録する第3工程、及び前記第3工程で記録した各位置情報に対して、所定のn-gramが所定のm-サブシークエンスのオフセットで出現した場合前記所定のn-gramに該当フロントエンド逆索引の用語に対するポスティングリストに該当ポスティングを追加してフロントエンド逆索引を構成する第4工程、からなるn-gram/2L索引構築成方法を提供することである。
【００２８】
前記第1工程では、前記m-サブシークエンスをn-1(n:n-gramの長さ)ずつ重なるように抽出して、また最後のm-サブシークエンスの長さがmより小さい場合、文字列の後ろ部分に空白文字を付け加えて長さがmになるようにすることが好ましい。
【００２９】
本発明の更に別の目的は、n-gram/2L索引を利用したクエリ処理方法を提供することでありは、前記クエリ処理方法は、文書から抽出されたサブシークエンスを用語として使用するバックエンド逆索引及び前記サブシークエンスから抽出されたn-gramを用語として使用するフロントエンド逆索引を使用する。前記方法は、所定のクエリを複数のn-gramに分割する第1工程、前記フロントエンド逆索引を使用して前記第1工程で求めた各n-gramに対するポスティングリスト間でm-サブシークエンス識別子を用いてマージ外部結合(merge-outer-join)し、前記クエリをカバーするm-サブシークエンスを所定集合に追加する第2工程、及び前記バックエンド逆索引を使用して前記第2工程で求めた所定集合に含まれたm-サブシークエンスに対するポスティングリストを文書識別子間でマージ-外部結合し、所定の同一な文書から抽出されたm-サブシークエンスの集合が前記クエリを含むかどうかを検査して、クエリに含まれれば前記所定の同一な文書をクエリ結果として返す第3工程、からなる。
【００３０】
前記m-サブシークエンスがクエリをカバーするかどうかは、マージ外部結合されるポスティングが持っているオフセット情報を利用して確認し、前記第3工程での集合がクエリを包含するかどうかはマージ外部結合されるポスティングが持っているオフセット情報を利用して確認することが好ましい。
【００３１】
本発明の更に別の目的は、n-gram/2L索引導出方法を提供することであり、逆索引導出方法は、n-gram逆索引からフロントエンド逆索引とバックエンド逆索引とで構成され、前記方法はn-gram逆索引を第1正規形(1NF)にしたがうリレーションに変換する第1工程、前記第1工程で求めたリレーションに存在する、自明でない多値従属性(MVD)による位置情報の冗長性が存在することを確認する第2工程、前記第2工程で確認された冗長性を除去するために前記第1で求めたリレーションを第4正規形(4NF)にしたがう二つのリレーションに分解する第3工程、及び前記第3工程で求めた二つのリレーションをそれぞれフロントエンド逆索引とバックエンド逆索引とに変換で表現する第4工程、とからなる。
【発明の効果】
【００３２】
本発明は、n-gram索引に存在する自明でない多値従属性による位置情報の冗長性を除去することにより、n-gram索引に比べてそのサイズを大きく減らしてクエリ処理性能を高める効果を有する。
【発明を実施するための最良の形態】
【００３３】
以下、本発明の好ましい実施例を、添付図面を参照してより詳細に説明する。本発明は下記実施例に限定されず、本発明の精神及び範囲内で数多くの変化が可能である。本発明の実施例は当業者により完全に説明するために提供される。
【００３４】
本発明は、n-gram索引のサイズが大きくなる要因を分析して、その主要因がn-gramの位置情報の冗長性のためであることことを明らかにして、その冗長性を除去する方案に対して説明する。
【００３５】
図3は、n-gram索引に存在する位置情報の冗長性と、その冗長性を除去するための方法、すなわち2工程n-gram索引（これからn-gram/2Lと省略する）を示したのである。
【００３６】
図3の(a)は、N個の文書で構成されている文書集合の例である。文字列 "a1a2a3a4"をサブシークエンスAとする時、サブシークエンスAは文書1、2およびNのオフセット o1、o3、o5に出現し、文字列"b1b2b3b4"をサブシークエンスBとする時、サブシークエンス Bは文書1およびNのオフセットo2、o4に出現する。
【００３７】
したがって、三つの連続的な2-gram"a1a2"、"a2a3"および"a3a4"が文書1、2およびNに出現し、三つの連続的な2-gram "b1b2"、"b2b3"および"b3b4"が文書1およびNに出現する。
【００３８】
図3の(b)は、図3の(a)から構成された2-gram索引を示す。図３の(b)では、斜線のポスティングが位置情報の冗長性を有する。
【００３９】
すなわち、図3の(b)における2-gram逆索引で2-gram"a1a2"、"a2a3"および"a3a4"のポスティングリストには、2-gram "a2a3"および"a3a4"のオフセットが2-gram"a1a2"のオフセットよりそれぞれ1および2ずつ大きいという事実が文書1の他に文書2およびNにも繰り返して示される。
【００４０】
このような繰り返しはまた、2-gram"b1b2"、"b2b3"および"b3b4"のポスティングリストでも出現する。
【００４１】
すなわち、サブシークエンスが文書で頻繁に繰り返される場合、そのサブシークエンスから抽出されるn-gramの相対的な位置情報が何回か繰り返されて索引される。
【００４２】
もし、頻繁に発生するサブシークエンスから抽出されるn-gramの相対的な位置情報を一回だけ索引化することができたら、このような冗長性を除去して索引のサイズを減らすことができる。
【００４３】
図3の(c)は、文章から生成されるn-gram/2L索引を示す。三つの2-gram "a1a2"、"a2a3"および"a3a4"の文書上での位置情報は以下のように2工程で表される。第１工程は図3の(c)の右側のように、文章におけるサブシークエンスAの位置情報になり、第2工程は図3の(c)の左側のようにサブシークエンスAにおける2-gram"a1a2"、"a2a3"および"a3a4"の位置情報になり、したがって位置情報の冗長性を除去している。
【００４４】
このようにn-gram索引を二つの逆索引(n-gram/2L索引)に分解することは、自明でない多値従属性(MVD)による冗長性を消去する関連データベース分野の正規化処理と理論的に等しい。
【００４５】
図4は、本発明を具現化するためのハードウェア構造を図示したブロック図で、n-gram/2Lサーバー100、データベース管理システム200及びデータベース300で構成される。
【００４６】
前記n-gram/2Lサーバー100は、n-gram/2Lの索引を生成するための索引構築機110及びn-gram/2L索引を使用してクエリを処理するクエリ処理機120で構成される。前記データベース300は、各種テキスト情報が保存されるテキスト情報DB310及びn-gram/2L索引が保存されるn-gram/2L索引情報DB320で構成される。
【００４７】
前記データベース管理システム200に接続される前記n-gram/2Lサーバー100は、データベース300のn-gram/2L索引情報DB320にn-gram/2L索引を生成し、これを使用してクエリを処理する。
【００４８】
前記データベース管理システム200は、データベース300に保存されたテキスト情報DB310を管理する。
【００４９】
次に、このようなシステムで具現される本発明のn-gram/2L索引の構造に対して詳しく見てみる。
【００５０】
本発明のn-gram/2L索引は、フロントエンド逆索引とバックエンド逆索引とで構成され、図5は本発明によるn-gram/2L索引の構造を示したものである。
【００５１】
本発明では長さmのサブシークエンスをm-サブシークエンスとし、n-gramの長さをnで、m-サブシークエンスの長さをmで表記する。
【００５２】
バックエンド逆索引は、文書から抽出されたm-サブシークエンスを用語として使用して、m-サブシークエンスが文書上に出現した位置情報を、各m-サブシークエンスに対応するポスティングリストに保存する。
【００５３】
フロントエンド逆索引は、m-サブシークエンスから抽出されたn-gramを用語として使用して、n-gramがm-サブシークエンス上に出現した位置情報を、各n-gramに対応するポスティングリストに保存する。
【００５４】
次は、2工程n-gram逆索引(n-gram/2L索引)の索引構築方法に対して詳しく見てみる。
【００５５】
データベース300のテキスト情報DB310から与えられたテキスト情報からn-gram/2L索引を構築するために、以下の4つの工程、（１）m-サブシークエンス抽出する工程、（２）バックエンド逆索引を構築する工程、（３）n-gramを抽出する工程、（４）フロントエンド逆索引を構築する工程を経て、前記n-gram/2Lサーバー100の索引構築機110で実行される。
【００５６】
前記m-サブシークエンス抽出工程では、m-サブシークエンスの長さをmに固定して、連続したサブシークエンスが互いにn-1ずつ重なるように抽出する。このような重なりは、抜け落または重複を防止するためである。この方法が正しいことは、次の定理1からわかる。
【００５７】
定理1：
m-サブシークエンスを抽出する工程で、m-サブシークエンスを互いにn-1ずつ重なるようにすれば、n-gram抽出過程で抜け落ちたり重複したりするn-gramは発生しない。
【００５８】
証明：
文書dが、文字のシーケンスc0、c1、...、cN-1で与えられた時、文書dから抽出されるn-gramの個数はN-n+1個であり、各n-gramの開始文字はciである(0≦i<N-n+1)。
【００５９】
また、m-サブシークエンスの長さがmで与えられた時、文書dから抽出されるm-サブシークエンスの個数は(N-n+1)/(m-n+1)個で、各m-サブシークエンスの開始文字はcjである(0≦j<(N-n+1)/(m-n+1))。説明の便宜上、ciを開始文字にするn-gramをNiで表記して、cjを開始文字にするm-サブシークエンスをSjで表記する。
【００６０】
文書dから抽出される隣接した任意の二つのm-サブシークエンスをSp、Sqであるとする時、Spから抽出されるn-gramはNp、...、Np+m-nで、Sqから抽出されるn-gramはNq、...、Nq+m-nである。
【００６１】
m-サブシークエンス同士お互いに重なる区間の長さをlとする時、長さlは、（１）l=n-1、（２）l<n-1および（３）l>n-1の三種類の場合に分けられる。それぞれの場合に対して二つのm-サブシークエンスSp、Sqから抽出されるn-gramの中で抜け落ちたり重複したりするn-gramがあるかどうかを検査することにより定理を証明する。
【００６２】
●ケース（1）l=n-1:お互いにn-1ずつ重なるので q=p+m-n+1で、Sqから抽出されるn-gramはまた、Np+m-n+1、...、Np+2m-2n+1で表現される。Spから抽出されるn-gramはNp、...、Np+m-nなので、二つのm-サブシークエンスSp、SqからNp、...、Np+m-n、Np+m-n+1、...、Np+2m-2n+1のn-gram等が抜け落ちたり重複したりしないで一回ずつのみ抽出される。
【００６３】
●ケース（2）l<n-1:l=n-2であると仮定して、一般性を失わない。互いにn-2ずつ重なるのでq=p+m-n+2で、したがって、Sqから抽出されるn-gramは再びNp+m-n+2、...、Np+2m-2n+2で表現される。二つのm-サブシークエンスSpまたはSqのいずれからもn-gram  Np+m-n+1が抽出されないので、抜け落ちるn-gramが発生する。
【００６４】
●ケース（3）l>n-1:l=nであると仮定して、一般性を失わない。互いにnずつ重なるので q=p+m-nで、したがって、Sqから抽出されるn-gramはまたNp+m-n、...、Np+2m-2nで表現される。二つのm-サブシークエンスSp、Sqからn-gramNp+m-nがそれぞれ一回ずつ、合わせて二度抽出されるので、重複するn-gramが発生する。
【００６５】
したがって、m-サブシークエンスを抽出する工程で隣接した二つのm-サブシークエンスが互いにn-1ずつ重なるようにすることにより、n-gramの抜け落ちや重複を防止することができる。
【００６６】
次に、n-gram/2L索引の索引構築アルゴリズムは、文書データベースとm-サブシークエンスの長さと、n-gramの長さとを入力として受けとり、n-gram/2L索引を出力として構築する図6は、本発明に従うn-gram/2L索引構築の詳細なアルゴリズムを示す流れ図である。
【００６７】
図6を参照すると、工程S110で、アルゴリズムはデータベース300のテキスト情報DB310において各文書からm-サブシークエンスを互いにn-1ずつ重なるように抽出し、m-サブシークエンスが文書上で出現した位置情報を保存する。
【００６８】
すなわち、各文書が文字のシーケンスc0、c1、...、cN-1から成るとき、0≦i<(N-n+1)/(m-n+1)であるすべてのiに対して、アルゴリズムは文字ci*(m-n+1)で始まる長さmのサブシークエンスを抽出する。もし、最後のm-サブシークエンスの長さがmより小さければ文字列の後ろ部分に空白文字を付け加えて長さがmになるようにする。
【００６９】
工程S120では、前記工程S110で保存した各位置情報に対して、m-サブシークエンスsが文書dのオフセットo1、...、ofで出現した場合、sのバックエンド逆索引用語に対するポスティングリストにポスティング<d、[o1、...、of]>を追加することにより、アルゴリズムはバックエンド逆索引を構築する。
【００７０】
そして、工程S130では、工程S110で求めたm-サブシークエンス集合の各m-サブシークエンスからn-gramを1-スライディング方式で抽出し、n-gramがm-サブシークエンス上で出現した位置情報を保存する。
【００７１】
工程S140では、前記工程S130で保存した各位置情報に対して、m-サブシークエンスvのオフセットo1、...、ofで各ｍ−サブシークエンスが出現した場合、gのバックエンド索引用語に対するポスティングリストにポスティング<v、[o1、...、of]>を追加することにより、アルゴリズムはフロントエンド逆索引を構築する。
【００７２】
図7は、与えられた文書の集合からn-gram/2L索引を構築した例である。ここで、n=2およびm=4である。
【００７３】
図7の(a)は、与えられた文書集合を示し、図7の(b)は前記工程S110によって図7の(a)に示した文書集合から抽出された4-サブシークエンスの集合を示す。文書は長さが4でお互いに1(すなわち、n-1)ずつ重なる4-サブシークエンスに分けられるので文書0から抽出される4-サブシークエンスは、"ABCD"、"DDAB"、"BBCD"である。
【００７４】
図7の(c)は、前記工程S120で抽出された4-サブシークエンス集合から構成されたバックエンド逆索引である。4-サブシークエンス"ABCD"は、文書0、3および4においてそれぞれ0、3および6のオフセットで出現したので、4-サブシークエンス"ABCD"と関連したポスティングリストには、ポスティング<0、[0]>、<3、[3]>および<4、[6]>が加えられる。
【００７５】
図7の(d)は、4-サブシークエンスの集合で、図7の(e)は工程S130で4-サブシークエンス集合から抽出された2-gram集合を示す。1-スライディング方式で2-gramを抽出するので、4-サブシークエンス0から抽出される2-gramは、"AB"、"BC"、"CD"である。
【００７６】
図7の(f)は、前記工程S140で2-gram集合から構築されたフロントエンド逆索引である。2-gram"AB"は、4-サブシークエンス0、3、4および5でそれぞれ0、2、1および2のオフセットで出現したので、2-gram"AB"と連関したポスティングリストにはポスティング<0、[0]>、<3、[2]>、<4、[1]>および<5、[2]>が加えられる。
【００７７】
次は、2工程n-gram逆索引(n-gram/2L索引)のクエリ処理方法に対して詳しくみてみる。
【００７８】
本発明でn-gram/2L索引を使ったクエリ処理は、n-gram/2Lサーバー100のクエリ処理機120で実行され、次の二つの工程からなる。（１）フロントエンド逆索引を検索して候補の結果を検索する、（２）バックエンド逆索引を検索して最終結果を得る。
【００７９】
第一工程では、クエリ文字列を分割して抽出されたn-gramを使ってフロントエンド逆索引を検索することにより、クエリ文字列をカバーするm-サブシークエンスを捜し出す。この工程でクエリ文字列をカバーしないm-サブシークエンスは、フィルターされる。
【００８０】
第二工程では、第一工程で検索されたm-サブシークエンスを使ってバックエンド逆索引を検索することにより、クエリ文字列を含むm-サブシークエンスの集合{Si}を持つ文書を捜し出す。
【００８１】
これに対して次の定義1でカバーという用語を正式に定義して、定義3で包含という用語を正式に定義する。
【００８２】
定義1：
SがQをカバーするとは、m-サブシークエンスSがクエリ文字列Qに対して次の四種類の条件中の一つを満たすことである。(1)SのサフィックスがQのプレフィックスと一致する。(2)S全体がQのサブストリングと一致する。(3)SのプレフィックスがQのサフィックスと一致する。(4)SのサブストリングがQ全体と一致する。
【００８３】
定義2：
文字列のシークエンスを一つの文字列で展開する関数エクスパンドを次のように定義する:(1)二つの文字列Si、Spがそれぞれ文字列ci...cjと cp...cqで与えられて、SiのサフィックスとSpのプレフィックスがcj-k+1...cj=cp...cp+k-1のようにk個重なっているとする(k≧0)。このとき、expand(SiSp)=ci...cjcp+k...cqである。(2)二つ以上の文字列S1、Sl+1、...、Smに対してexpand(S1Sl+1...Sm)=expand(expand(SlSl+1)、Sl+2...Sm)である。
【００８４】
定義3：
{Si}がQを包含するとは、m-サブシークエンスの集合{Si}が次の条件を満足することである。:{Si}に属したm-サブシークエンスが重なるように連続的に連結されたシーケンスをS1Sl+1...Smとする時、expand(S1Sl+1...Sm)のサブストリングがクエリ文字列Q全体と一致する。
【００８５】
図8は、クエリ文字列Qをカバーするm-サブシークエンスの例とカバーしないm-サブシークエンスの例を示したものである。図8aではSのサフィックスがQのプレフィックスと一致するので、SはQをカバーする。図8bではSのサブストリング"BCD"が定義1の四種類の条件をいずれも満足しないので、SはQをカバーしない。
【００８６】
補助定理1：
クエリ文字列Qを包含するm-サブシークエンスの集合{Si}を有する文章は、Qをカバーするm-サブシークエンスを一つ以上含む。
【００８７】
証明は： 
まず、m-サブシークエンスの集合{Si}がQを含むすべての場合を示すと、図9a〜図9cのようになる。ここで、図9はQの長さLen(Q)に対してLen(Q)≧mである図9a、およびLen(Q)<mである図9bと図9cとを示す。
【００８８】
図9aでは、(j-i+1)個のm-サブシークエンスの集合{Si、...、Sj}がQを包含する。図9bでは一つのm-サブシークエンスSkがQを包含する。図9cでは二つのm-サブシークエンスの集合{Sp、Sq}がQを包含する。
【００８９】
このように、m-サブシークエンスの集合{Si}がQを包含する場合、{Si}に属した各m-サブシークエンスはQをカバーすることが分かる。
【００９０】
したがって、そのようなm-サブシークエンスの集合{Si}が抽出された文章では、Qをカバーするm-サブシークエンスを最小限一つ以上含むことになる。
【００９１】
次に、n-gram/2L索引のクエリ処理では、n-gram/2L索引とクエリQを入力として受けて、Qに一致する文書識別子を見つけ、出力として返す。
【００９２】
図10は、本発明に従うn-gram/2L索引を使用するクエリ処理アルゴリズムに対する流れ図を示したのである。
【００９３】
図10を参照すると、工程S210では、まずクエリ文字列Qを複数のn-gramに分割した後、アルゴリズムはフロントエンド逆索引を使用して各n-gramに対するポスティングリスト間でm-サブシークエンス識別子を用いてマージ外部結合し、前記クエリ処理過程での定義1に従ってQをカバーする(すなわち、補助定理1の必要条件を満足する)m-サブシークエンスを集合Scoverに追加する。
【００９４】
Qをカバーするm-サブシークエンスは一般的に、Qから抽出されたすべてのn-gramを持っていないのでクエリ処理過程の工程S210でマージ外部結合を遂行する。
【００９５】
ここで、アルゴリズムはポスティングが持っているオフセット情報を利用して、m-サブシークエンスがQをカバーするかどうかを確認するために、マージ外部結合する。
【００９６】
そして、工程S220では、バックエンド逆索引を使用して前記工程S210で求めたScoverに含まれたm-サブシークエンスに対するポスティングリストを文書識別子でマージ外部結合し、同一文書diから抽出されたm-サブシークエンスの集合{Si}が定義3に従ってQを包含するかどうかを検査する。
【００９７】
もし、集合{Si}がQを包含すれば、アルゴリズムはdiをクエリの結果として返す。ここで、アルゴリズムはポスティングが持っているオフセット情報を利用して、集合{Si}がQを包含するかどうかを確認するためにマージ外部結合する。
【００９８】
次は、n-gram/2L索引構造を導出する方法にが、図11を参照しながら記載される。
【００９９】
本発明では、n-gram索引からn-gram/2L索引を以下の4つの工程を通じて導出する。n-gramを、索引が第1正規形(1NF)にしたがうリレーションとして表現する工程(S310)、該工程S310で求めたリレーションに自明でない多値従属性(MVD)による位置情報の冗長性が存在することを確認する工程(S320)、該工程S320で確認された冗長性を除去するために前記工程S310で求めたリレーションを第4正規形(4NF)にしたがう二つのリレーションに分解する工程(S330)、および該工程S330で求めた二つのリレーションをそれぞれフロントエンド逆索引とバックエンド逆索引とに変換する工程(S340)。
【０１００】
まず、前記工程S310では、n-gram索引を第1正規形に変換したリレーションを理論的な発展のために考慮する。このようなリレーションをNDOリレーションと呼ぶ。このリレーションは、N、D、Oの三つのアトリビュート(attribute)で構成される。ここで、Nはn-gramを、Dは文書識別子を、Oはオフセットを示す。
【０１０１】
そして、NDOリレーションにアトリビュートSを追加して、アトリビュートOをアトリビュートO1、O2に分ける。合わせて五つのアトリビュートS、N、D、O1、O2を持つように変換されたリレーションをSNDO1O2リレーションであると呼ぶ。
ここで、Sはn-gramが抽出されるm-サブシークエンスを、O1はn-gramが出現するm-サブシークエンス上におけるオフセットを、O2はm-サブシークエンスが出現する文書におけるオフセットを示す。
【０１０２】
SNDO1O2リレーションに付随するアトリビュートS、O1、O2の値は、NDOリレーションにおけるアトリビュートN、D、Oの値によって自動的に決まる。与えられた文書集合の各文書がm-サブシークエンスでn-1ずつ重なるように分けられていると仮定しよう。そうすると、文書集合から抽出される特定のn-gramは、前記定理1に従う一つのm-サブシークエンスにのみ属するようになる。
【０１０３】
NDOリレーションの任意のタプル(n、d、o)から自動的に決まるSNDO1O2リレーションのタプル(s、n、d、o1、o2)において、sは文書dのオフセットoに出現するn-gram  nが属しているm-サブシークエンスである。そして、o1はs上でn-gram  nが出現したオフセットであり、o2は文書d上でsが出現したオフセットである。
【０１０４】
図12は、図2bの2-gram逆索引から変換されたリレーションNDOの例であり、リレーションNDOから導かれたm=4の時のリレーションSNDO1O2の例である。ここでは、リレーションSNDO1O2はアトリビュートSの値によって整列される。
【０１０５】
図12において、リレーションSNDO1O2のマークされたタプルは、リレーションNDOのマークされたタプルから自動的に決まる。
【０１０６】
図7の(a)において、文書0におけるオフセット1に出現する2-gram"BC"は4-サブシークエンス"ABCD"に属するので、マークされたタプルのアトリビュートSの値は"ABCD"に決まる。
【０１０７】
アトリビュートO1およびO2の値は、2-gram"BC"が4-サブシークエンス"ABCD"において出現したオフセット1と文書0で4-サブシークエンス"ABCD"が出現したオフセット0でそれぞれ決まる。
【０１０８】
次に前記工程S320では、次の補助定理2を通じて前記工程S310で求めたリレーションSNDO1O2に自明でないMVDが存在することが見られる。
【０１０９】
補助定理2：
リレーションSNDO1O2には、S→→NO1とS→→DO2との自明でないMVDが存在する。ここで、Sはスーパーキーではない。
【０１１０】
証明： 
MVDの定義(Jeffery D. Ullman、Principles of Database and Knowledge-Base Systems Vol. I、Computer Science Press、USA、1988.、 Ramez Elmasri and Shamkant B. Navathe、Fundamentals of Database Systems、Addison Wesley、4th ed.、2003.、Abraham Silberschatz、Henry F. Korth、and S. Sudarshan、Database Systems Concepts、McGraw-Hill、4th ed.、2001年)によると、スキーマRにおいてX、Yは、Rの部分集合だとする。Rに付随する任意のリレーションrにおいて、μ[X]=ν[X]を満たす二つのタプルμ、ν（μ、ν∈ｒ、）が存在し、且つリレーションrが次の三種類の条件を満足する二つのタプルφ、Ψをも含んでいる時、自明でないMVD  X→→Yが存在する。
【０１１１】
更に、Y⊂/XおよびX∪Y≠R(即ち、R-X-Y≠O)(YとR-X-Yがアトリビュートの空集合ではない)場合、X→→Yは自明でないMVDである(Ramez Elmasri and Shamkant B. Navathe、Fundamentals of Database Systems、Addison Wesley、4th ed.、2003年、Abraham Silberschatz、Henry F. Korth、and S. Sudarshan、Database Systems Concepts、McGraw-Hill、4th ed.、2001年)。
【０１１２】
すなわち、アトリビュートXの任意の値に対してアトリビュートYの値とアトリビュートR-X-Yの値がカルテシアン積を形成する時、自明でないMVDが存在する(Raghu Ramakrishnan、Database Management Systems、McGraw-Hill、1998年)。
【０１１３】
1.φ[X]=Ψ[X]=μ[X]=ν[X]
2.φ[Y]=μ[Y]  且つ  φ[R-X-Y]=ν[R-X-Y]
3.Ψ[Y]=ν[Y]  且つ  Ψ[R-X-Y]=μ[R-X-Y]
与えられた文書集合から抽出されるm-サブシークエンスの集合を{S1、...、Sr}とする時、m-サブシークエンスSiから抽出されるn-gramの集合{Ni1、...、Niq}は、Siが出現する文書の集合{Di1、...、Dip}からもいつも抽出される(1≦i≦r)。
【０１１４】
したがって、アトリビュートSの値がm-サブシークエンスSiであるタプルの集合において、Siから抽出されたn-gramを表すアトリビュートNO1の値と、Siを含んでいる文書を表すアトリビュートDO2の値とは、いつもカルテシアン積を形成する。
【０１１５】
R=SNDO1O2、X=S、Y=NO1およびR-X-Y=DO2とすると、アトリビュートXの任意の値に対してアトリビュートYの値とアトリビュートR-X-Yの値がカルテシアン積形態を成すので、上の三種類の条件が満足される。Y=DO2としても同じの事実が成り立つ。
【０１１６】
また、NO1⊂/S、DO2⊂/S、NO1∪S≠SNDO1O2およびDO2∪S≠SNDO1O2である。
【０１１７】
したがって、リレーションSNDO1O2にはS→→NO1とS→→DO2との自明でないMVDが存在する。ここで、図12の右側の例から分かるようにSはスーパーキーではない。
【０１１８】
直観的に説明すると、リレーションSNDO1O2に自明でないMVDが存在する理由は、m-サブシークエンスが出現する文書と、そのm-サブシークエンスから抽出されるn-gramとは、互いに無関係であるためである。
【０１１９】
このように互いに無関係であるアトリビュートが一つのリレーションに存在する場合には、自明でないMVDが存在する( Jeffery D. Ullman、Principles of Database and Knowledge-Base Systems Vol. I、Computer Science Press、USA、1988.、Raghu Ramakrishnan、Database Management Systems、McGraw-Hill、1998.、Ramez Elmasri and Shamkant B. Navathe、Fundamentals of Database Systems、Addison Wesley、4th ed.、2003.、Abraham Silberschatz、Henry F. Korth、and S. Sudarshan、Database Systems Concepts、McGraw-Hill、4th ed.、2001年) 
リレーションSNDO1O2では、文書とn-gramの集合との間の独立性によって、文書識別子とn-gramとの可能なすべての組み合わせに対応するタプルが各m-サブシークエンスごとに存在する。
【０１２０】
図12の右側は、リレーションSNDO1O2における自明でないMVD  S→→NO1およびS→→DO2が存在する例である。図12の右側で示されるリレーションSNDO1O2の斜線のタプルを見ると、二つのアトリビュートNおよびO1の値("AB"、0)、("BC"、1)、("CD"、2)に対して二つのアトリビュートDおよびO2の値(0、0)、(3、3)、(4、6)が繰り返し出現する冗長性が存在する。すなわち、S="ABCD"であるタプルにおいて、NO1とDO2とがカルテシアン積を成す。アトリビュートSの残りの値に対してもこのような繰り返しが出現することを見ることができる。
【０１２１】
前記工程S330では、前記工程S320で確認された位置情報の冗長性を除去するために前記工程S310で求めたリレーションSNDO1O2を第4正規形(4NF)にしたがうように二つのリレーションに分解する。
【０１２２】
まず、次の定理2を通じてリレーションSNDO1O2が4NFではないことが証明され、次に補助定理3を通においてリレーションSNDO1O2によって分解された二つのリレーションSNO1とSDO2とがそれぞれ4NFに従うことが証明される。
【０１２３】
定理2：
リレーションSNDO1O2は第4正規形ではない。
【０１２４】
証明： 
自明でないMVD  S→→NO1が存在し、Sはスーパーキーではない。
【０１２５】
補助定理3：
リレーションSNDO1O2をSNO1とSDO2との二つのリレーションに分解した時、それぞれのリレーションは4NFである。
【０１２６】
証明： 
リレーションSNO1における自明でないMVDは、SO1→→NとSNO1→→S|N|O1である。また、リレーションSDO2における自明でないMVDは、DO2→→SとSDO2→→S|D|O2である。これらのMVDはすべて自明なMVDなので第4正規形に反しない。
【０１２７】
次は、前記工程S340に対して詳しくみてみる。
【０１２８】
前記工程S340では前記工程S330でリレーションSNDO1O2を第4正規形にしたがうように分解することにより得られる二つのリレーションがSNO1およびSNO2が、n-gram/2L索引のフロントエンド逆索引とバックエンド逆索引とに変換され得ることを、次の定理3を通じて証明される。
【０１２９】
これによりn-gram/2L索引には、自明でないMVDによる冗長性が除去されることが、理論的に証明される(Jeffery D. Ullman、Principles of Database and Knowledge-Base Systems Vol. I、Computer Science Press、USA、1988年)。
【０１３０】
定理3：
リレーションSNDO1O2を第4正規形に従うように分解したリレーションSNO1とリレーションSDO2とは、それぞれn-gram/2L索引のフロントエンド逆索引とバックエンド逆索引になる。
【０１３１】
証明：
リレーションSNO1は、アトリビュートN、SおよびO1がそれぞれ用語、m-サブシークエンス識別子および位置情報と見なすことによりフロントエンド逆索引として表現される。また、リレーションSDO2は、アトリビュートS、DおよびO2がそれぞれ用語、文書識別子、位置情報であると見なすことによりバックエンド逆索引として表現される。
【０１３２】
したがって、リレーションSNDO1O2をリレーションSNO1とリレーションSDO2とに分解した結果は、n-gram/2L索引のフロントエンド逆索引とバックエンド逆索引になる。
【０１３３】
図13は、図12のリレーションSNDO1O2が二つのリレーションSNO1とSDO2とに分解された結果である。リレーションSDO2のアトリビュートSの値において、丸括弧の中の値は、m-サブシークエンスに付与された識別子を示す。
【０１３４】
図12のリレーションSNDO1O2で斜線のタプルは、図13のリレーションSNO1とリレーションSDO2とで、斜線のタプルに分解される。図12で見られた冗長性、すなわちNO1とDO2との間のカルテシアン積が図13では除去されたことが分かる。
【０１３５】
リレーションSNO1を逆索引形態で表現すると、図7のフロントエンド逆索引と同一になり、リレーションSDO2を逆索引形態で表現すると図7のバックエンド逆索引と等しくなる。
【０１３６】
前記のような本発明に従って、n-gram/2L索引構造は、n-gram検索において存在する位置情報の冗長性を排除することにより、n-gram索引に比べて索引のサイズを減らすことができ、クエリ処理性能が向上することができる。このことを次のように分析する。
【０１３７】
まず、索引サイズに対して分析する。
n-gram/2L索引のサイズに影響を及ぼすパラメーターは、n-gramの長さであるnおよびm-サブシークエンスの長さであるmである。この中でnの値は一般的にアプリケーションによって決まる数値である一方、mの値は本発明におけるn-gram/2L索引の構築のために取り入れた数値として自由に調節することができる。
【０１３８】
したがって、索引のサイズを最小にする最適な長さm(以下、moと省略する)の値を決めるための方法に議論を方向付け、それによるn-gram/2L索引のサイズを分析する。
【０１３９】
次の表1でmoを求めるために使用するいくつかの基本的な表記法を定義する。ここで、索引に保存されたオフセットの数は、n-gram索引とn-gram/2L索引のサイズとして使用される。
【０１４０】
これは、索引のサイズが、文書上で用語が出現したオフセットの個数にほぼ比例するからである(I. Witten、A. Moffat、and T. Bell、Managing Gigaバイトs: Compressing and Indexing Documents and Images、Morgan Kaufmann Publishers、Los Altos、California、2nd ed.、1999年) 
【０１４１】
【表１】
0004414989.tif 000002
分割を通じて索引サイズの減少する割合が最大になるmoの値を決めるため、次の定義4で分割効率を定義する。
【０１４２】
定義4：
分割効率とは、n-gram/2L索引サイズに対するn-gram索引サイズの比である。これを表1の表記法で示すと下記のようになる。
【０１４３】
【数１】
0004414989.tif 000003
定義4の分割効率は、数式(1)〜(5)のように計算することができる。ここで、SNDO1O2リレーションを利用してn-gram索引あるいは、n-gram/2L索引におけるオフセット数を計算する。SNDO1O2リレーションは、n-gram索引を第1正規化により生成されたので、オフセット数がすなわちタプル数になる。
【０１４４】
n-gram索引を表すSNDO1O2リレーションにおいて、アトリビュートSの値がsであるタプルの数は、kngram(s)×kdoc(s)である。これは、前記補助定理2で見たように、SNDO1O2リレーションにおいてアトリビュートSの任意の値に対してアトリビュートNO1とアトリビュートDO2との値がカルテシアン積を形成するからである。よって、n-gram索引の全体サイズは、すべてのm-サブシークエンスに対するkngram(s)×kdoc(s)の合計である公式(2)になる。
【０１４５】
フロントエンド逆索引に該当するSNO1リレーションにおいて、アトリビュートSの値がsであるタプルの数は、kngram(s)である。よって、フロントエンド逆索引の全体サイズは、すべてのm-サブシークエンスに対するkngram(s)の合計である公式(3)になる。
【０１４６】
バックエンド逆索引に該当するSDO2リレーションにおいて、アトリビュートSの値がsであるタプルの個数は、kdoc(s)である。よって、バックエンド逆索引の全体サイズは、すべてのm-サブシークエンスに対するkdoc(s)の合計である公式(4)になる。その結果として、数式(1)〜(4)から数式(5)を得る。
【０１４７】
【数２】
0004414989.tif 000004
分割効率は、文書集合を前処理して、S、kngram(s)、kdoc(s)を求めることにより計算することができる。これは、文書集合を順次に一回スキャンすることで処理することができる(O(data size))。このように、moの候補になるに値するm値に対して分割効率を求めて、その中で最大分割効率を持つmoを捜す。
【０１４８】
公式(5)から分かるように、n-gram索引の領域計算量は、O(|S|×(αvgngram×αvgdoc))で、n-gram/2L索引の領域計算量は、O(|S|×(αvgngram+αvgdoc))である。公式(5)で分割効率が最大になる条件は、与えられたデータに対してαvgngramとαvgdocが同じになる場合である。
【０１４９】
ところで、αvgdocは、データが大きくなれば自然に増加する一方、αvgngramはmが大きくなると増加する。よって、与えられたデータを前処理してmoを求めて見ると、データが大きいほどmoもさらに大きい値で決まる傾向がある。
【０１５０】
すなわち、与えられたデータが大きくなる時、αvgngramとαvgdocも増加して、ここで(αvgngram+αvgdoc)より(αvgngram×αvgdoc)がさらに多く増加するので、分割効率もさらに大きくなる。よって、n-gram/2L索引は、さらに大きいデータで索引のサイズをさらにもっと効果的に減らす良い特性を有することが分かる。
【０１５１】
次は、クエリ処理性能の分析に対して詳しくみてみる。
【０１５２】
n-gram/2L索引のクエリ処理性能に影響を及ぼすパラメーターは、m、n及びクエリ文字列Qの長さであるLen(Q)である。したがって、以下ではこれらパラメーターの変化によるn-gram/2L索引のクエリ処理性能の傾向を知るための概略的な分析をする。
【０１５３】
先に、分析を単純化するために次の二つの仮定をする。
【０１５４】
第一に、クエリ処理時間は、アクセスするオフセットの数とアクセスするポスティングリストの数に比例すると仮定する。ポスティングリストにアクセスする時には、ディスクヘッドを移動させるシークタイムが発生するので、アクセスするポスティングリストの数が多くなるほど、更に必要となるクエリ処理時間が大きくなる。
【０１５５】
第二に、アルファベットをΣとする時、文書データが非常に大きくてすべての種類の数(=│Σ│n)のn-gram、またはすべての種類の数(=│Σ│m)のm-サブシークエンスがバックエンド逆索引に索引されると仮定する(例えば、│Σ│=26、m=5である場合、│Σ│m=11,881,376)。クエリ処理性能は、特に大容量データで重要なので、第2の仮定は合理的であると言える。
【０１５６】
n-gram/2L索引のクエリ性能に対するn-gram索引のクエリ性能の比は、数式(6)〜(9)のように計算することができる。
【０１５７】
ポスティングリスト当たりのオフセットの平均数をkoffsetとして、クエリ処理の間にアクセスするポスティングリストの数をkplistとする時、クエリ処理のためにアクセスするオフセットの数は、koffset× kplistである。
【０１５８】
n-gram索引でkoffsetは、(sizengram/│Σ│n)で、kplistは、(Len(Q)-n+1)なので、n-gram索引のクエリ処理時間は公式(6)になる。
【０１５９】
n-gram/2L索引のフロントエンド逆索引において、koffsetは、(sizefront/│Σ│n)で、kplistは (Len(Q)-n+1)なので、クエリ処理時間は公式(7)になる。
【０１６０】
n-gram/2L索引のバックエンド逆索引において、koffsetは(sizeback/│Σ│m)であり、kplistはQをカバーするm-サブシークエンスの数である。ここで、その計算された数はLen(Q)<mの場合とLen(Q)≧mの場合とで異る。
【０１６１】
Len(Q)≧mの場合、図9aのSi+1、...、Sj-1の場合に該当するm-サブシークエンスの数は、(Len(Q)-m+1)で、SiまたはSjの場合にあたるm-サブシークエンスの数はそれぞれ、Σi=0m-n-1│Σ│m-n-iである。Len(Q)<mの場合、図9bのSkの場合に該当するm-サブシークエンスの個数は((m-Len(Q)+1)×|Σ|m-Len(Q)))で、SpまたはSqの場合に該当するm-サブシークエンスの個数はそれぞれ、Σi=0Len(Q)-n-1│Σ│m-n-iである。
【０１６２】
したがって、バックエンド逆索引でのクエリ処理時間は、公式(8)になる。最後に、公式(9)はクエリ処理時間の割合を示す。
【０１６３】
【数３】
0004414989.tif 000005
sizengram=|S|(αvgngram×αvgdoc)なので、公式(9)からn-gram索引のクエリ処理の時間計算量は、O(|S|(αvgngram×αvgdoc))で、同じくn-gram/2L索引のクエリ処理の時間計算量は、O(|S|(αvgngram×αvgdoc))である。
【０１６４】
すなわち、n-gram索引とn-gram/2L索引の時間計算量は、空間計算量と同じである。よって、n-gram/2L索引は、n-gram索引に比べてクエリ処理性能を改善するる良い特性を有し、更に改善はデータベースのサイズが大きくなるほどよくなることを、時間計算量は示している。
【０１６５】
前記公式(6)〜(9)から分かるように、n-gram索引では、Len(Q)に比例してクエリ処理時間が増加する。逆に、n-gram/2L索引では、Len(Q)が長くなってもクエリ処理時間がほとんど増加しない。
【０１６６】
フロントエンド逆索引の場合、Len(Q)に比例してクエリ処理時間が増加するが、その索引のサイズは非常に小さい。バックエンド逆索引の場合、Σm-nが非常に大きいので(例えば、|Σ|=26、m=6、n=3である場合、|Σ|m-n=17,576)、Len(Q)はほとんど影響を及ぼさない。
【０１６７】
フロントエンド逆索引サイズが小さい理由は、文書集合よりサイズがずっと小さなm-サブシークエンスの集合に対して索引が構築されるからである(すなわち、文書集合のサイズが1Gバイトでm=5の時、m-サブシークエンス集合のサイズは、13〜27Mバイト)。
【０１６８】
n-gram逆索引は、クエリの長さが非常に長いくなるにつれ、クエリ処理時間も非常に大きいということが問題点を有するるので(Hugh E. Williams、"Genomic Information Retrieval、" In Proc. the 14th Australasian Database Conferences、2003年)、Len(Q)が長くなる時、非常に優れたクエリ処理性能は重要である。
【０１６９】
クエリ処理時間に対してさらに詳しい分析をするためには、ポスティングリストにアクセスするために必要な時間を考慮しなければならない。一つのポスティングリストにアクセスするために必要なシーク時間をαとする時、さらに必要となるクエリ処理時間は、（kplist×α）である。
【０１７０】
公式(6)〜(8)にあるkplistを利用してポスティングリストにアクセスするために必要な時間(plist_time)を求めると、公式(10)〜(12)になる。
【０１７１】
【数４】
0004414989.tif 000006
数式(10)および(12)から分かるように、plist_timengram=plist_timefrontで、したがって、n-gram/2L索引のポスティングリストにアクセスするために必要な時間は、n-gram索引に比べてplist_timebackだけ長い。
【０１７２】
公式(12)においおて、kplistの主要因子はLen(Q)≧mの場合、(2
Σi=0m-n-1|Σ|m-n-i)がであり、Len(Q)<mの場合、(2Σi=0Len(Q)-n-1|Σ|m-n-i)であり、それぞれの値はmが増加するにつれて指数的に大きくなる。
【０１７３】
ゆえに、m-サブシークエンスの長さにmoの代わりに(mo-1)を使えば、索引サイズの側面で多少損をしたりするが、クエリ処理性能は大きく改善され得る。
【０１７４】
また、本発明による1Gバイトのテキストデータ(TREC-1G)およびタンパク質シーケンスデータ(PROTEIN-1G)に対する実験をの結果、m-サブシークエンスの長さに(mo-1)を使用した時、n-gram/2L索引はn-gram逆索引に比べて最大1.9倍(PROTEIN-1G、m=4)〜2.7倍(PROTEIN-1G、m=5)さらに小さなサイズを持ち、且つ同時に3〜18の範囲の長さを有するクエリに対してクエリ処理性能を最大13.1倍(PROTEIN-1G、m=4)向上させた。
【０１７５】
以上で説明したように、本発明は、n-gram索引に存在する自明でない多値従属性による位置情報の冗長性を除去することにより、n-gram索引に比べてそのサイズを大きく減らしてクエリ処理性能を高める効果を有する。
【０１７６】
また、n-gram/2L索引は、索引サイズの側面において索引をしようとするデータベースのサイズが大きいほど、n-gram逆索引に比べて有利である。すなわち、データのサイズが大きくなるほど、既存のn-gram索引のサイズと比べたn-gram/2L索引の相対的サイズは小くなる。
【０１７７】
また、クエリ処理性能の側面でも本発明のn-gram/2L索引は、索引をしようとするデータの大きさが大きいほど、n-gram索引に比べて有利である。すなわち、既存のn-gram索引と比べたn-gram/2L索引の相対的なサイズは、データのサイズが大きくなるほど良くなる。
【０１７８】
それだけではなく、n-gram/2L索引は、クエリ文字列の長さが長くなってもクエリ処理時間がほとんど増加しない。
【０１７９】
上述したように、本発明の好ましい実施例を参照して説明したが、当業者は、特許請求の範囲に記載された本発明の思想及び領域から逸脱しない範囲内で本発明を多様に修正または変形して実施することができることは理解されるであろう。
【０１８０】
尚、外国語細書中にＪＩＳコードで表記できない箇所があったため、この翻訳文では代替表記を使用した、具体的には、
は、Σi=0m-n-1、Σi=0Len(Q)-n-1及び⊂/は、
【０１８１】
【数５】
0004414989.tif 000007
のように、外国語明細書では総和を表す記号があったが、便宜上、翻訳文ではΣ記号と下付き文字及び上付き文字等で表現した。
【図面の簡単な説明】
【０１８２】
【図１】一般的な逆索引の構造を示した図。
【図２ａ】n-gram索引例を示した図。
【図２ｂ】n-gram索引の例を示した図。
【図３】n-gram索引における位置情報の冗長性とその冗長性を除去する方法を示した図。
【図４】本発明を具現するためのハードウェア構成のブロック図。
【図５】本発明によるn-gram/2L索引の構造を示した図。
【図６】本発明によるn-gram/2L索引の索引構築アルゴリズムの流れ図。
【図７】本発明によるn-gram/2L索引の構築の例を示した図。
【図８ａ】m-サブシークエンスSがクエリQをカバーする例を示した図。
【図８ｂ】m-サブシークエンスSがクエリQをカバーしない例を示した図。
【図９ａ】m-サブシークエンスの集合がクエリQを包含する例を示す図。
【図９ｂ】m-サブシークエンスの集合がクエリQを包含する例を示した図。
【図９ｃ】m-サブシークエンスの集合がクエリQを包含する例を示した図。
【図１０】本発明によるn-gram/2L索引を使用するクエリ処理アルゴリズムに対する流れ図。
【図１１】本発明による2 n-gram/2L索引構造を導出するためのアルゴリズムに対する流れ図。
【図１２】SNDO1O2リレーションに自明でない多値従属性(MVD)が存在する例を示す図。
【図１３】SNDO1O2リレーションが二つのリレーションに分解された結果の例を示す図。
【図１】
0004414989.tif 000008
【図２ａ】
0004414989.tif 000009
【図２ｂ】
0004414989.tif 000010
【図３】
0004414989.tif 000011
【図４】
0004414989.tif 000012
【図５】
0004414989.tif 000013
【図６】
0004414989.tif 000014
【図７】
0004414989.tif 000015
【図８ａ】
0004414989.tif 000016
【図８ｂ】
0004414989.tif 000017
【図９ａ】
0004414989.tif 000018
【図９ｂ】
0004414989.tif 000019
【図９ｃ】
0004414989.tif 000020
【図１０】
0004414989.tif 000021
【図１１】
0004414989.tif 000022
【図１２】
0004414989.tif 000023
【図１３】
0004414989.tif 000024