(57)【要約】  検索結果の周辺文脈を、限られた範囲内で適切に集約して表示することを可能ならしめる技法を提供すること。  全文脈文字列C={c1, …, cn}に対して、文字列sがカバーする面積を、sをプリフィックスとするcの数とsの長さの積で定義する。そして、全文脈の集合に対して、最大K個、長さL以下の文字列集合の内、他の文字列の部分文字列を選択しない制約下で、 全体でカバーする面積を最大にするものを求める。本発明によれば、この問題は全文脈をTRIEにした頻度順文脈木上の動的計画法で効率的に解ける。本発明の別の知見によれば、動的計画法で最大面積を求める際に、探索で得られる面積の上限を見積もることで、大幅な探索の枝刈りが可能になり、以って処理を高速化できる。さらにまた、文書の接尾辞木の子ノードを出現頻度順に並べた、頻度順接尾辞木を作ることで、検索と最大面積を求めることの両方を高速化することが可能となる。
2012017782.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理によって、表示すべき文字列を生成する方法であって、
キーワードに従い、文書に対する検索によって、前記キーワードを含む、n個(nは、1以上の整数)の要素cからなる文脈文字列Cを得るステップと、
文字列sが文脈文字列Cをカバーする面積を、sをプリフィックスとする、Cの要素であるcの数とsの長さの積で定義したとき、表示される文字列の最大数がK個(Kは、1以上の整数)以下であるとの条件の下で、前記面積の和を最大にするsの集合を求めるステップとを有する、
文字列生成方法。
【請求項２】
前記sの集合を求めるステップは、動的計画法に基づく、請求項１に記載の方法。
【請求項３】
検索すべき文書集合が、頻度順接尾辞木データとして構成され、前記動的計画法は、前記頻度順接尾辞木に対する検索結果から得られた頻度順文脈木データ上の動的計画法である、請求項２に記載の方法。
【請求項４】
前記動的計画法は、頻度順文脈木データ上の探索途中の最大値を渡し、上限がそこに達しなければあきらめる、枝刈り処理を行う、請求項３に記載の方法。
【請求項５】
コンピュータの処理によって、表示すべき文字列を生成するプログラムであって、
前記コンピュータをして、
キーワードに従い、文書に対する検索によって、前記キーワードを含む、n個(nは、1以上の整数)の要素cからなる文脈文字列Cを得るステップと、
文字列sが文脈文字列Cをカバーする面積を、sをプリフィックスとする、Cの要素であるcの数とsの長さの積で定義したとき、表示される文字列の最大数がK個(Kは、1以上の整数)以下であるとの条件の下で、前記面積の和を最大にするsの集合を求めるステップを実行させる、
文字列生成プログラム。
【請求項６】
前記sの集合を求めるステップは、動的計画法に基づく、請求項５に記載のプログラム。
【請求項７】
検索すべき文書集合が、頻度順接尾辞木データとして構成され、前記動的計画法は、前記頻度順接尾辞木に対する検索結果から得られた頻度順文脈木データ上の動的計画法である、請求項６に記載のプログラム。
【請求項８】
前記動的計画法は、頻度順文脈木データ上の探索途中の最大値を渡し、上限がそこに達しなければあきらめる、枝刈り処理を行う、請求項７に記載のプログラム。
【請求項９】
コンピュータの処理によって、表示すべき文字列を生成するシステムであって、
キーワードに従い、文書に対する検索によって、前記キーワードを含む、n個(nは、1以上の整数)の要素cからなる文脈文字列Cを得る手段と、
文字列sが文脈文字列Cをカバーする面積を、sをプリフィックスとする、Cの要素であるcの数とsの長さの積で定義したとき、表示される文字列の最大数がK個(Kは、1以上の整数)以下であるとの条件の下で、前記面積の和を最大にするsの集合を求める手段を有する、
文字列生成システム。
【請求項１０】
前記sの集合を求める手段は、動的計画法に基づく、請求項９に記載のシステム。
【請求項１１】
検索すべき文書集合が、頻度順接尾辞木データとして構成され、前記動的計画法は、前記頻度順接尾辞木に対する検索結果から得られた頻度順文脈木データ上の動的計画法である、請求項１０に記載のシステム。
【請求項１２】
前記動的計画法は、頻度順文脈木データ上の探索途中の最大値を渡し、上限がそこに達しなければあきらめる、枝刈り処理を行う、請求項１１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、主として自然言語テキストの文字列検索技術に関し、特に、検索結果を表示するための技術に関するものである。
【背景技術】
【０００２】
テキストの文字列検索において、ヒット位置の前後の文脈は、有用な情報を与える。例えば、「ボタン」を検索したときに、その後に「クリックする」が続くか「押す」が続くかなどにより、文書の表現の統一を調べたり、特定の英語の固有名詞に定冠詞がつくかどうか確認したり、その他、連語や人名検索などでも、ヒット位置の前後の文脈の情報は重要である。【０００３】
そこで、従来技術において、検索単語の前後に出現する文字列をソートして表示する，ＫＷＩＣ（KeyWord In Context）が知られている。【０００４】
ＫＷＩＣにおいて、「ボタン」で検索したときの全文脈の例は、次のとおりである。
ボタンが大きくて・・・
ボタンが赤い．・・・
ボタンという表・・・
ボタンに書いてあ・・・
ボタンをクリックしたら・・・
ボタンをクリックして下・・・
ボタンをクリックしよう・・・
ボタンをクリックできな・・・
ボタンをクリックできま・・・
ボタンをクリック．・・・
ボタンを押したら・・
ボタンを押しては・・・
ボタンを押せませ・・・
ボタンを押そうと・・・【０００５】
しかし、ＫＷＩＣは、ヒット数が多すぎるときに全体の傾向を一目で把握できないという問題点があった。【０００６】
山本真人, 田中久美子, 中川裕志. 検索エンジンに基づく多言語用例指南ツール：KIWI. 言語処理学会全国大会2005、及び特開２００４−１６４１３３号公報によって開示されている技術は、ＫＷＩＣを拡張した手法を提案し、すなわち、表示する文脈の重要度を測ることを可能ならしめる。しかし、この拡張された手法も、複数文脈の最適な組み合わせを選択することは可能ではなく、類似文書が多数表示されるという問題が残る。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４−１６４１３３号公報
【非特許文献】
【０００８】
【非特許文献１】山本真人, 田中久美子, 中川裕志. 検索エンジンに基づく多言語用例指南ツール：KIWI. 言語処理学会全国大会2005
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従って、本発明の目的は、検索結果の周辺文脈を、限られた範囲内で適切に集約して表示することを可能ならしめる技法を提供することにある。
【課題を解決するための手段】
【００１０】
本発明においては、先ず、全文脈文字列C={c1, …, cn}に対して、文字列sがカバーする面積を、sをプリフィックスとするcの数とsの長さの積で定義する。【００１１】
すると、本発明は、全文脈の集合に対して、最大K個、長さL以下の文字列集合の内、他の文字列の部分文字列を選択しない制約下で、 全体でカバーする面積を最大にするものを求める技法である。本発明の知見によれば、この問題は全文脈をTRIEにした頻度順文脈木上の動的計画法で効率的に解ける。【００１２】
本発明の別の知見によれば、動的計画法で最大面積を求める際に、探索で得られる面積の上限を見積もることで、大幅な探索の枝刈りが可能になり、以って処理を高速化できる。【００１３】
さらにまた、文書の接尾辞木の子ノードを出現頻度順に並べた、頻度順接尾辞木を作ることで、検索と最大面積を求めることの両方を高速化することが可能となる。【００１４】
以上の処理は、後方文脈のみではなく前方文脈に対しても自然に適応可能である。また、単語区切りを利用していないため、英語をはじめとした任意の言語データ、さらに時刻付きのイベント列などの解析にも適応できる。
【発明の効果】
【００１５】
この発明によれば、検索結果を、限られた領域に出来るだけ沢山の情報を与えるように圧縮して表示する技法が提供される。しかも、動的計画法を使うことで、そのための計算が、高速化される。
【図面の簡単な説明】
【００１６】
【図１】本発明を実施するためのハードウェア構成のブロック図である。
【図２】本発明を実施するための機能構成のブロック図である。
【図３】頻度順接尾辞木を構築する処理のフローチャートを示す図である。
【図４】頻度順接尾辞木と、頻度順文脈木の例を示す図である。
【図５】頻度順接尾辞木データを検索するための処理を示す図である。
【図６】検索と最適文脈の探索全体の処理のフローチャートを示す図である。
【図７】動的計画法を使った探索の処理のフローチャートを示す図である。
【図８】枝刈り付き動的計画法を使った探索の処理のフローチャートを示す図である。
【図９】枝刈り付き動的計画法を使った探索の処理のフローチャートを示す図である。
【図１０】最大面積ノード集合の復元処理のフローチャートを示す図である。
【図１１】ＫＷＩＣの非可逆圧縮表示の例を示す図である。
【図１２】従来の典型的な技法と、本発明の実施例の技法との文脈表示の比較を示す図である。
【発明を実施するための形態】
【００１７】
以下、図面に基づき、この発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。尚、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことを理解されたい。
【００１８】
図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・パス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＰｅｎｔｉｕｍ（商標）  ４、Ｃｏｒｅ（商標）２  Ｄｕｏ、Ｘｅｏｎ（商標）、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。主記憶１０６は、好適には、２ＧＢ以上の容量をもつものである。ハードディスク・ドライブ１０８は、大量の文書データ及び検索のための頻度順接尾辞木データを格納できるように、例えば、３２０ＧＢ以上の容量をもつものであることが望ましい。
【００１９】
ハードディスク・ドライブ１０８には、個々に図示しないが、オペレーティング・システムが、予め格納されている。オペレーティング・システムは、Ｌｉｎｕｘ（商標）、マイクロソフト社のＷｉｎｄｏｗｓ（商標）７、Ｗｉｎｄｏｗｓ  ＸＰ（商標）、Ｗｉｎｄｏｗｓ（商標）２０００、アップルコンピュータのＭａｃ  ＯＳ（商標）などの、ＣＰＵ１０４に適合する任意のものでよい。
【００２０】
ハードディスク・ドライブ１０８にはさらに、検索されるテキスト・データと、テキスト・データから頻度順接尾辞木データを生成する頻度順接尾辞木作成モジュールと、頻度順接尾辞木作成モジュールによって作成された頻度順接尾辞木データと、ユーザが指定したキーワードに基づき、本発明の技法によって文脈文字列を求め、表示を圧縮した態様で文字列を出力する文字列検索モジュールと、文字列検索モジュールによって出力された文字列を、ディスプレイ１１４に表示するためのＧＵＩモジュールが保存されている。これらのデータ及びモジュールについては、図２の機能ブロック図を参照して、後で、より詳しく説明する。
【００２１】
キーボード１１０及びマウス１１２は、オペレーティング・システムまたは、ハードディスク・ドライブ１０８から主記憶１０６にロードされ、ディスプレイ１１４に表示されたプログラム（図示しない）を起動したり、検索するための文字を打ち込んだりするために使用される。
【００２２】
ディスプレイ１１４は、好適には、液晶ディスプレイであり、例えば、ＸＧＡ（１０２４×７６８の解像度）、またはＵＸＧＡ（１６００×１２００の解像度）などの任意の解像度のものを使用することができる。
【００２３】
次に、図２の機能ブロック図を参照して、本発明の処理のための機能要素について説明する。テキスト・ファイル２０２は、ハードディスク・ドライブ１０８に保存された大容量ファイルであり、好適には自然言語テキスト・データを含む。
【００２４】
頻度順接尾辞木構築モジュール２０４は、テキスト・ファイル２０２を読み取って、頻度順接尾辞木データ２０６として、ハードディスク・ドライブ１０８に保存する。頻度順接尾辞木構築モジュール２０４の処理については、図３のフローチャートを参照して、後でより詳細に説明する。
【００２５】
文字列検索モジュール２０８は、本発明の要部をなす処理に関する機能を含むものであって、ユーザーが入力したキーワードに基づき、文脈文字列を検索し、さらに、それを基に、圧縮表示文字列を計算して与える。文字列検索モジュール２０８の処理は、図６以下のフローチャートを参照して、後でより詳細に説明する。
【００２６】
ＧＵＩモジュール２１０は、キーボード１１０及びマウス１１２を用いてユーザーが入力した文字列を文字列検索モジュール２０８に渡し、文字列検索モジュール２０８の文脈文字列の出力を、ディスプレイ１１４に表示する機能をもつ。
【００２７】
頻度順接尾辞木構築モジュール２０４、文字列検索モジュール２０８、及びＧＵＩモジュール２１０は、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ（商標）などの既存のプログラム言語で書くことができる。ＧＵＩモジュール２１０は、ユーザーの文字列入力を読み込み、あるいは、文脈文字列の出力を、ディスプレイ１１４に表示するために、好適には、オペレーティング・システムが提供するＡＰＩ関数を呼び出すようにプログラミングされる。
【００２８】
次に、図３のフローチャートを参照して、頻度順接尾辞木構築モジュール２０４が頻度順接尾辞木データを作成して出力する処理について説明する。この処理は、従来技術の範囲であって、本発明の特徴を構成するものでないことを理解されたい。
【００２９】
頻度順接尾辞木とは、文書の全接尾辞に対してＴＲＩＥを作ったものである。全接尾辞とは、文書の全ての位置以降の文字列の集合のことである。よって、長さnの文書に対して、n個存在する。但し、ＴＲＩＥの各ノードの子ノードは、葉の総数が多い順にソートする。葉の総数でなく、アルファベット順にソートしたのが、一般の接尾辞木である。サイズは、接尾辞木と同じＯ(n)であり、最大でも2n個のノードである。
【００３０】
さて、頻度順接尾辞木構築モジュール２０４は、図３のステップ３０２において、テキスト・ファイル２０２を読取って、ステップ３０４で、接尾辞配列構築を行う。この処理は例えば、Ge Nong, Sen Zhang, Wai Hong Chan, "Two Efficient Algorithms for Linear Suffix Array Construction", IEEE Transactions on Computers, 2008に記述されている技法を使う。
【００３１】
ステップ３０６において、頻度順接尾辞木構築モジュール２０４は、最大接頭辞長の計算を行う。この処理は例えば、Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In proc. of 12th Annual Symposium on Combinatorial Pattern Matching, pp. 181-192. 2001に記述されている技法を使う。
【００３２】
ステップ３０８において、頻度順接尾辞木構築モジュール２０４は、帰りがけ順で最初のノードをnとおく。接尾辞配列を帰りがけ順に辿る処理も、例えば、Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In proc. of 12th Annual Symposium on Combinatorial Pattern Matching, pp. 181-192. 2001に記述されている。
【００３３】
ステップ３１０では、頻度順接尾辞木構築モジュール２０４は、nが帰りがけ順で最後のノードであるかどうかを判断し、もしそうなら、処理を終わる。
【００３４】
そうでなければ、ステップ３１２に進み、頻度順接尾辞木構築モジュール２０４は、nの子ノードを頻度順にソートし、ステップ３１４で、nの子ノードをファイルに出力し、これは、頻度順接尾辞木データ２０６としてハードディスク・ドライブ１０８に保存される。
【００３５】
ステップ３１６では、nにnの次のノードが代入されて、処理は、ステップ３１０の判断に戻る。
【００３６】
図４(a)は、このようにして構築された頻度順接尾辞木の一例の木構造を示す図である。図４において、「ボ」「タ」などはそれぞれ、頻度順接尾辞木のノードであり、ノードの上に示された数字は、出現回答を示す。特に図４で、参照番号４０２で示した領域は、「ボタン」に対する頻度順文脈木を示す。頻度順接尾辞木は、所定の検索すべきテキスト・ファイルに対して、一度だけ作成して、ハードディスク・ドライブ１０８に保存しておけば、テキスト・ファイルが変わらない限り作成し直さないで、何度でも検索に使用することができる。
【００３７】
一方、図４(b)は、頻度順文脈木の例を示す図である。頻度順文脈木は、特定のキーワードで、頻度順接尾辞木を検索することによって、主記憶またはハードディスク・ドライブ１０８上に動的に生成される。後述する、本発明の動的計画法は、このように動的に生成された頻度順文脈木上で実行される。
【００３８】
頻度順接尾辞木上での検索は、接尾辞木と同様の方法で実行可能である。但し、各子ノードは、アルファベット順に並んでいないので、線形探索が必要である。このとき、子ノードをデータ構造中に連続させておけば、クエリ長に比例した回数のランダムアクセスだけで検索可能である。そして、検索し終わったノードをルートとする部分木が、頻度順文脈木となる。
【００３９】
次に、図３の処理によって構築された頻度順接尾辞木データ２０６を検索するための処理を、図５に示す。この処理は、好適には、文字列検索モジュール２０８がもつサブルーチンとしての関数の１つであるsearch()として実装される。
【００４０】
図５のsearchという関数のフローチャートにおいて、sをクエリ文字列とする。ステップ５０２では、nにルートノード(ROOT)が代入される。ステップ５０４では、p = 0と置かれ、ステップ５０６では、p = |s|かどうかが判断される。ここで、|s|とは、sの長さである。もしp = |s|であるなら、関数searchは、nを返して終了する。
【００４１】
もしp = |s|でないなら、ステップ５０８に進み、そこでn = nullかどうかが判断される。もしn = nullなら、関数searchは、nを返して終了する。
【００４２】
もしn = nullでないなら、ステップ５１０に進み、そこで、c = get_char(n)が実行される。get_char(n)は、ノードnに対する文字を返す。
【００４３】
ステップ５１２では、s[p] = cかどうかが判断される。ここで、s[p]とは、文字列sのp番目の文字である。もしs[p] = cであるなら、ステップ５１４で、p = p + 1によりpが増分され、ステップ５１６で、n = chd(n)により、nの最初の子ノードであるchd(n)がnに代入される。そうして処理は、ステップ５０６に戻る。
【００４４】
ステップ５１２で、s[p] = cでないなら、ステップ５１８で、n = sib(n)により、nの次の兄弟ノードであるsib(n)がnに代入される。そうして処理は、ステップ５０８に戻る。このsearch(s)の実行後、戻り値のnをルートとする頻度順接尾辞木の部分木が、図４(b)に例示するような頻度順文脈木として、主記憶１０６または、ハードディスク・ドライブ１０８上に構築される。
【００４５】
図６は、文字列検索モジュール２０８が実行する、検索と最適文脈の探索全体の処理のフローチャートを示す図である。
【００４６】
文字列検索モジュール２０８は、ステップ６０２で、図５のフローチャートで示す関数search(s)を呼び出して、その結果をnに返す。ここで、sはクエリ文字列であり、ＧＵＩモジュール２１０を介してユーザが入力したものである。
【００４７】
文字列検索モジュール２０８は、ステップ６０４でnがnullであるかどうかを判断し、もしそうなら、ステップ６０６で、文字列が見つからない旨を出力して処理を終わる。この処理は典型的には、文字列検索モジュール２０８がＧＵＩモジュール２１０にメッセージを渡して、ディスプレイ１１４に表示させることによって行われる。
【００４８】
文字列検索モジュール２０８がステップ６０４でnがnullでないと判断すると、ステップ６０８で、文字列検索モジュール２０８は、ステップ６０８で、動的計画法を使った探索の処理を行う。この実施例では、文字列検索モジュール２０８は、動的計画法として、図７のフローチャートに基づき後で説明する動的計画法の関数f(n,K)または、図８及び図９のフローチャートに基づき後で説明する枝刈り付き動的計画法の関数g(n,K,0)をどちらか一方、または両方をサブルーチンとしてもつようにしてよい。なお、ここで、Kは最大文字列選択数である。このステップでは、ステップ６０２で、search(s)が構築した頻度順文脈木上で、動的計画法が適用される。
【００４９】
g(n,K,0)は、枝刈り付き処理により、f(n,K)よりも大規模な頻度順文脈木に対する探索に適合する。従って、文字列検索モジュール２０８は、頻度順文脈木が所定の規模よりも大きい場合にg(n,K,0)を適用し、そうでない場合にf(n,K)を適用するようにしてもよい。
【００５０】
ステップ６０８で、f(n,K)またはg(n,K,0)の一方を実行した後、文字列検索モジュール２０８は、ステップ６１０で、(n,K)に関して最大値を返したノードを関数rで復元する。関数rの処理は、図１０のフローチャートを参照して、後で詳細に説明する。
【００５１】
こうして、各ノードに対応する文字列が得られると、文字列検索モジュール２０８は、それらの文字列を、ステップ６１２でＧＵＩモジュール２１０に渡して、ディスプレイ１１４に表示させる。
【００５２】
次に、本発明の動的計画法の処理に関する説明に移るが、その前に、本発明における面積、及び面積最大化の定義について説明する。
【００５３】
先ず、最大で縦K行、横L文字の表示域に文脈の要約を表示するとする。そこで、n件の文脈集合C = {c1,...,cn}と、m件の文字列集合S = {s1,...,sm}とする。但し、m ≦ K, len(s) ≦ Lとする。ここで、len(s)は、文字列sの長さである。
【００５４】
また、S中の任意の文字列は、他の文字列のプリフィックスではないとする。これは、「を」と「を使う」と「を使うとき」のような類似文字列がでるのを防ぐためである。
【００５５】
そこで、SがCをカバーする面積A(S,C)を、下記の式で定義する。
【数１】
2012017782.tif 000003
ここで、CP(s,C)は、C中でsをプリフィックスとするものの個数である。そこで、求めたいのは、あるCに対して、面積を最大にするS、つまりargmax S A(S,C)を求めることである。
【００５６】
しかし一般的に、Sの候補は膨大なので、本発明では、動的計画法を適用して計算合理的にSを求めるようにする。
【００５７】
以上の定義の下で、図７のフローチャートを参照して、f(n,k)の処理を説明する。f(n,k)とは、ノードn、その子、その弟のうち、最大k個を選択したとき得られる最大面積を返す関数である。
【００５８】
ステップ７０２では、変数aについて、a = 0と置かれる。ステップ７０４では、n = nullかどうかが判断される。もしn = nullなら、関数f()は、aを返して終了する。
【００５９】
もしn = nullでないなら、ステップ７０６に進み、(n,k)は処理済かどうか判断される。もし(n,k)が処理済なら、ステップ７０８で、aとして(n,k)についての前回処理時の値を用いて、関数f()は、aを返して終了する。
【００６０】
(n,k)が処理済でないなら、ステップ７１０で、ss = f(sib(n),k-1)によって、f()が再帰呼び出しされ、それの戻り値がssに代入される。ここで、sib(n)は、nの次の兄弟ノードである。
【００６１】
ステップ７１２では、a = s(n) + ssによって、計算された値がaに代入される。ここで、s(n)とは、上記で定義した面積を用いた場合の、ノードnがカバーする面積である。ステップ７１２での計算結果を、*Aとする。
【００６２】
次に、ステップ７１４ではc = 0と置き、ステップ７１６からステップ７２４までは、cを1つずつ増分しつつ、ステップ７１６でc > kと判断されるまで、処理を繰り返す。
【００６３】
すなわち、ステップ７１８では、cs = f(chd(n),c)によって、計算された値がcsに代入される。ここで、chd(n)とは、ノードnの最初の子ノードである。
【００６４】
ステップ７２０では、ss = f(sib(n),k-c)によって、計算された値がssに代入される。
【００６５】
ステップ７２２では、a = max(a, cs + ss)によって、計算された値がaに代入される。ステップ７２２での計算結果を、*Bとする。
【００６６】
ステップ７２４では、c = c + 1によってcが増分されて、ステップ７１６での判断に戻る。ループが廻ってステップ７１６でc > kとなると、ステップ７２６で(n,k)を処理済にして、関数f()は、aを返して終了する。
【００６７】
次に、図８及び図９のフローチャートを参照して、枝刈り付き動的計画法の関数g(n,k,m)の処理について説明する。図７で説明した関数fは最大値を取る組み合わせを探索する関数であったため、関数gは、探索途中での最大値を渡し、残りの処理を続けてもこれに達しないことがわかれば処理を中断してもよいという方針で処理する。そのため、真の最大値の上限を見積もり、これが探索途中での最大値を超えなければ処理を中断する。すなわち、効率よく枝刈りするためには、真の最大値をなるべく先に探索し、またなるべく真の最大値に近い上限値を、効率よく計算する必要がある。
このとき、計算する順番は、経験的に、c(子ノードへの割当て)が少ない場合が最適値をとることが多いため、cを昇順に探索するのが望ましい。
また、上限値u(n, k)は真の最大値f(n, k)以上の値を返す任意の関数を適用できる。例えば、「自分を含めたk個の兄弟が最大長までに達した」場合の値と、k, k+1,・・・のときの上限値のうちの最小値、というようなヒューリスティックスを使うようにする。このとき、子ノードが頻度順に並んでいる性質によって、真の値の上限になっていることが示される。また、計算量が検索ヒット数に依存しないので、効率がよい。
【００６８】
このような前提で、枝刈り付き動的計画法の関数g(n,k,m)の処理が構成されている。
【００６９】
ステップ８０２では、変数aについて、a = 0と置かれる。ステップ８０４では、n = nullかどうかが判断される。もしn = nullなら、関数g()は、aを返して終了する。
【００７０】
図８において、もしn = nullでないなら、ステップ８０６に進み、(n,k)は処理済かどうか判断される。もし(n,k)が処理済なら、ステップ８０８で、aとして(n,k)についての前回処理時の値を用いることにし、関数g()は、aを返して終了する。
【００７１】
さて、(n,k)が処理済でないなら、ステップ８１２で、u(n,k) <= mかどうか判断され、もしそうなら、ステップ８１０で、upper[n,k] = u(n,k)として、関数g()は、aを返して終了する。ここでupper[n,k]は、図７に関して説明した関数f(n,k)の上限値であり、２次元配列で、各要素は、システム的に∞とみなされる値で初期化されている。また、u(n,k)は、u(n,k) ≧ f(n,k)なる適当な関数であり、その一例を後で、図９のフローチャートを参照して説明する。ステップ８１２で、u(n,k) <= mでないと判断されると、ステップ８１４で、ss = g(sib(n),k-1,m-s(n))によって、g()が再帰呼び出しされ、それの戻り値がssに代入される。ここで、sib(n)は、nの次の兄弟ノードである。また、s(n)は、上述のように、ノードnがカバーする面積である。
【００７２】
ステップ８１６では、a = max(m,s(n) + ss)によって、値がaに代入される。この値は、*Aとして、一旦保存される。
【００７３】
次のステップ８１８では、c = 0とセットされ、c > kとなるまで、ステップ８２０〜８３２が繰り返される。
【００７４】
すなわち、ステップ８２２では、su = u(sib(n),k-c)によって、計算された値がsuに代入され、ステップ８２４では、cs = g(chd(n),c,a-su)により、g()を再帰呼び出しして計算した結果がcsに代入される。
【００７５】
ステップ８２６では、cs <= a - suかどうか判断し、そうでなければ、ステップ８２８に進み、ss = g(sib(b),k-c,a-cs)計算された値がssに代入され、ステップ８３０で、a = max(a,cs + ss)によって、計算された値がaに代入される。この値は、*Bとして、一旦保存される。次にステップ８３２で、c = c + 1でcが増分され、ステップ８２０に戻る。
【００７６】
ステップ８２６では、cs <= a - suであると判断されると、直接ステップ８３２に行って、c = c + 1でcが増分され、ステップ８２０に戻る。
【００７７】
ステップ８２０で、c > kであると判断されると、ステップ８３４で、a <= mかどうか判断され、もしそうなら、ステップ８３６で、upper[n,k] = mとして、関数g()は、aを返して終了する。
【００７８】
ステップ８３４で、a <= mであると判断されるなら、ステップ８３８で(n,k)を評価済みにし、ステップ８４０で、upper[n,k] = aとして、関数g()は、aを返して終了する。
【００７９】
次に、図９のフローチャートを参照して、関数g()から呼び出される関数u(n,k)の処理を説明する。まず、ステップ９０２でv = 0、ステップ９０４でm = n、ステップ９０６でi = 1、と変数がセットされる。
【００８０】
ステップ９０８では、i > kかどうか判断され、そうでないなら、ステップ９１０で、 v = v + count(m) * Lによって、計算された値がvに代入される。ここでLとは、最大文字列長である。また、count(m)とはmの出現回数である。次に、ステップ９１２では、m = sib(m)によって、mが、その次の兄弟ノードに置き換えられる。そして、ステップ９１４、i = i + 1で増分されて、ステップ９０８に戻る。
【００８１】
ステップ９０８で、i > kであると判断されると、ステップ９１６に進んで、そこで、k' = kと代入し、次に、ステップ９１８では、k' > Kであるかどうかが判断される。ここでKとは、最大文字列選択数である。
【００８２】
ステップ９１８で、k' > Kでないと判断されると、ステップ９２０で、v = min(v,upper[n,k'])によって、計算された値がvに代入される。そして次に、k' = k' + 1でk'が増分されて、ステップ９１８に戻る。
【００８３】
こうして、ステップ９２０とステップ９２２が繰り返されて、ステップ９１８で、k' > Kであると判断されると、関数u()は、vを返して終了する。
【００８４】
ところで、関数u(n,k)は、関数f(n,k)の上限、つまり必ずu(n,k) ≧ f(n,k)の条件が成り立つような関数である。この条件さえ満たせば、本発明のアルゴリズムは正しく動くが、u(n,k)-f(n,k)が小さいほど枝刈りが効率的に働く。つまり、uの値は条件を満たす中で小さければ小さいほどよく、真の値f(n,k)と一致しているときが最良である。
【００８５】
upper[n,k]は過去に計算した上限を保存したもので、上述したように初期値は∞、つまり、upper[n,k]≧f(n,k)が必ず成り立つ。すなわち、upperを使って、uを設計している。
【００８６】
さて、kは選択する行数なので、kが大きいほどf(n,k)は大きな値になる。従って，k < k'ならf(n,k) < f(n,k')である。そのため、f(n,k) < f(n,k') ≦ upper[n,k']となる。つまり，upper[n,k']はf(n,k)の上限の条件を満たす。kの値は最大でもKまでなので，k以上K以下のk'の値の中で一番小さなupper[n,k']を関数u(n,k)の出力として採用している。
【００８７】
それならば、upper[n,k]が一番小さくなるのではと思われるかもしれないが、計算順序の関係で、先に大きなkの値に対して上限を計算することがありえる。この計算結果が再利用されている。
【００８８】
次に、図１０のフローチャートを参照して、図６のフローチャートにおける(n,K)に関して最大値を返したノードを関数rで復元、とある関数rの処理を説明する。関数rは、ノードnと、整数kを引数とする。
【００８９】
ステップ１００２では、n = nullかどうかが判断される。もしそうなら、関数rは、直ちに終了する。
【００９０】
ステップ１００４では、(n,k)が*Aで最大かどうか判断される。この判断は、図７の関数f(n,k)が動的計画法で使われた場合は、ステップ７１２の計算結果と、ステップ７２２の計算結果を比較して、ステップ７１２の計算結果で最大値を計算したことを意味する。図８の関数g(n,k,m)が枝刈り付き動的計画法として使われた場合は、ステップ８１６の計算結果と、ステップ８３０の計算結果を比較して、ステップ８１６の計算結果で最大値を計算したことを意味する。
【００９１】
ステップ１００４で、(n,k)が*Aで最大であると判断されると、ステップ１００６でnがノード集合に追加され、ステップ１００８では、r(sib(n),k-1)により、r()が再帰的に呼び出されて、関数rは終了する。
【００９２】
ステップ１００４で、(n,k)が*Aで最大でないと判断されると、ステップ１０１０に進み、そこで、(n,k)が*Bで最大であるかどうかが判断される。この判断は、図７の関数f(n,k)が動的計画法で使われた場合は、ステップ７１２の計算結果と、ステップ７２２の計算結果を比較して、ステップ７２２の計算結果で最大値を計算したことを意味する。図８の関数g(n,k,m)が枝刈り付き動的計画法として使われた場合は、ステップ８１６の計算結果と、ステップ８３０の計算結果を比較して、ステップ８３０の計算結果で最大値を計算したことを意味する。
【００９３】
ステップ１０１０で、(n,k)が*Bで最大であると判断されると、ステップ１０１２でr(chd(n),c)が再帰的に呼び出され、ステップ１０１４では、r(sib(n),k-c)により、r()が再帰的に呼び出されて、関数rは終了する。ここでcとは、図７のフローチャートでは、ステップ７１４で初期化され、その後ステップ７２２でaの最大値を計算したときの値であり、図８のフローチャートでは、ステップ８１８で初期化され、その後ステップ８３０でaの最大値を与えたときの値である。
【００９４】
ステップ１０１０で、(n,k)が*Bで最大でないと判断されると、関数rは、直ちに終了する。このようにして復元されたノードが、図６のステップ６１２でＧＵＩモジュール２１０に渡されて、ディスプレイ１１４に表示される。
【００９５】
図１１は、背景技術のところで示したＫＷＩＣを、本発明の技法に従い、K = 3という極端に狭い領域に圧縮して表示する例である。この例では、K = 3でも、「ボタンをクリックし・・・」「ボタンをクリックでき・・・」「ボタンを押・・・」で、示されているＫＷＩＣのよい要約になっていることが見て取れる。
【００９６】
図１２は、ある特定のマニュアル文書に対して、「データベース」というクエリで、背景技術で記述したような従来の典型的に技法でサーチした結果と、本発明の技法でサーチした結果を比較する図である。特に、長さL（=10）で切って、出現頻度の多いK（=10）件を表示した例で比較している。「22:」などと表示されているのは、出現頻度である。
【００９７】
本発明の技法は、「データベース・サーバーを起動」「データベース・サーバーが停止する」などを「データベース・サーバー」に集約してカウントするので、頻出文脈が分かりやすい。一方、従来技術では、頻出単語の出現総数が少なく数えられて、最悪、頻出文脈が発見できないということもある。
【００９８】
また、特に、枝刈り付き動的計画法を使った実施例の場合、実験では、20MB程度のデータに対して、枝刈りなしの動的計画法に比べ、最大20倍の高速化に成功した。
【００９９】
さらに、事前に頻度順接尾辞木を作ることで、Nグラムインデックスなどで検索してから頻度順文脈木を作るよりも効率的である。そのため、大規模化に耐えられるようになる。
【０１００】
本発明は、マニュアルやビジネス文書における、表現統一や事例検索にも、有利に適用することができる。
【０１０１】
テキストマイニング・プログラムで、頻度トップのK個を表示するアルゴリズムを用いているものがあるが、その際、集計単位は単語単位となり必ずしもユーザの興味と合わないことが問題となっている。本発明は、ある文脈を適切に表現する可変長のトップK個を表示することが可能になり、テキストマイニング・プログラムでの応用も期待できる。
【０１０２】
尚、上記実施例では、頻度順接頭辞木を構築したが、文書を逆向きにして、接尾辞木を構築することも可能である。これを行うと前方文脈を纏め上げることができる。例えば「サーバー」というクエリに対して「メールサーバー」「NFSサーバー」「ウェブサーバー」などを返すことが可能となる。
【０１０３】
その具体的な処理は、文書を逆向きにして頻度順接尾辞木を構築することと、クエリ文字列を逆向きにし、面積最大化の文脈集合を探索し、探索結果を逆向きにして表示することである。
【０１０４】
以上、本発明の実施例を説明してきたが、本発明は、任意のコンピュータのハードウェア及びプラットフォームで実施可能であることを理解されたい、また、日本語以外の任意の言語に適用可能であることも、この分野の当業者なら、理解するであろう。
【符号の説明】
【０１０５】
１０２  システム・パス
１０４  ＣＰＵ
１０６  主記憶
１０８  ハードディスク・ドライブ
１１０  キーボード
１１２  マウス
１１４  ディスプレイ
２０２  テキスト・ファイル
２０４  頻度順接尾辞木構築モジュール
２０６  頻度順接尾辞木データ
２０８  文字列検索モジュール
２１０  ＧＵＩモジュール
【図１】
2012017782.tif 000004
【図２】
2012017782.tif 000005
【図３】
2012017782.tif 000006
【図４】
2012017782.tif 000007
【図５】
2012017782.tif 000008
【図６】
2012017782.tif 000009
【図７】
2012017782.tif 000010
【図８】
2012017782.tif 000011
【図９】
2012017782.tif 000012
【図１０】
2012017782.tif 000013
【図１１】
2012017782.tif 000014
【図１２】
2012017782.tif 000015
【国際調査報告】
2012017782.tif 000016
2012017782.tif 000017
2012017782.tif 000018
2012017782.tif 000019