(57)【要約】【課題】種々の言語により記述された文書に対して適切な用例を検索するのに好適な用例検索装置等を提供する。【解決手段】対象文書入力受付部７０２は、対象文書の入力を受け付け、検索文字列入力受付部７０３は、検索文字列の入力を受け付け、検索部７０４は、抽出装置５０１に、当該対象文書を文字列の入力として与え、当該検索文字列が当該対象文書において出現する場所のそれぞれについて、これに続く位置を開始位置の入力として与え、当該出現する場所から当該抽出された部分文字列の終了位置までの部分文字列を、用例として出力し、抽出装置５０１は、文字列中の開始位置から始まる部分文字列について、長さｉ、出現頻度Ｎｉ、後続する文字の種類の数Ｃｉから評価値ｌｏｇ（ｉ＋１）×ｌｏｇ（Ｎｉ）×（１−１／Ｃｉ）を計算し、長さｉを増やしていって評価値が増加したときに、その長さの文字列を部分文字列として抽出する。【選択図】  図２
2004164133.tif 000002
【特許請求の範囲】
【請求項１】
文字列入力受付部と、開始位置受付部と、評価値計算部と、抽出部と、を備える、部分文字列の抽出装置であって、
前記文字列入力受付部は、長さＮ  （Ｎ≧１）の文字列
ｓ  ＝  Ｘ１，…，ＸＮ
の入力を受け付け、
前記開始位置受付部は、前記入力を受け付けられた文字列における開始位置ｋ  （１≦ｋ≦Ｎ）の入力を受け付け、
前記評価値計算部は、長さｉ  （１≦ｉ≦Ｎ−ｋ＋１）の部分文字列
ｓｉ  ＝  Ｘｋ，…，Ｘｋ＋ｉ−１
について、当該部分文字列ｓｉのｓにおける出現頻度Ｎｉと、ｓにおいて当該部分文字列ｓｉに続いて出現する文字の種類の数Ｃｉとから、評価値
ＳＣ（ｓｉ）  ＝  ｌｏｇ（ｉ＋１）×ｌｏｇ（Ｎｉ）×（１−１／Ｃｉ）
を計算し、
前記抽出部は、前記計算された評価値が
ＳＣ（ｓｉ＋１）  ＞  ＳＣ（ｓｉ）
を満たす場合、当該部分文字列ｓｉ＋１を抽出する
ことを特徴とするもの。
【請求項２】
対象文書入力受付部と、検索文字列入力受付部と、検索部と、を備える用例検索装置であって、
前記対象文書入力受付部は、対象文書の入力を受け付け、
前記検索文字列入力受付部は、検索文字列の入力を受け付け、
前記検索部は、請求項１に記載の抽出装置に、当該対象文書を文字列の入力として与え、当該検索文字列が当該対象文書において出現する場所のそれぞれについて、これに続く位置を開始位置の入力として与え、当該出現する場所から当該抽出された部分文字列の終了位置までの部分文字列を、用例として出力する
ことを特徴とするもの。
【請求項３】
請求項２に記載の用例検索装置であって、
前記検索部は、当該用例に対応して抽出された部分文字列の評価値により、当該用例を整列して出力する
ことを特徴とするもの。
【請求項４】
対象文書入力受付部と、検索文字列入力受付部と、検索部と、を備える用例検索装置であって、
前記対象文書入力受付部は、対象文書の入力を受け付け、
前記検索文字列入力受付部は、検索文字列の入力を受け付け、
前記検索部は、当該検索文字列を接頭辞とし、当該対象文書に２回以上出現する部分文字列（以下「接頭重複文字列」という。）であって、他の接頭重複文字列の接頭辞となっていないものを、用例として出力する
ことを特徴とするもの。
【請求項５】
コンピュータを、請求項１に記載の抽出装置、または、請求項２から４のいずれか１項に記載の用例検索装置のいずれかとして機能させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、種々の言語により記述された文書に対して形態素解析を行わなくとも適切な用例を検索し、これをＫＷＩＣ（ＫｅｙＷｏｒｄｓ  Ｉｎ  Ｃｏｎｔｅｘｔ）形式で提示するのに好適な、部分文字列の抽出装置、用例検索装置、ならびに、これらをコンピュータ上に実現するプログラムに関する。
【０００２】
【従来の技術】
従来から、英語やフランス語などの空白で区切られる言語については、ＫＷＩＣ形式の索引が用いられてきた。ＫＷＩＣ形式の索引とは、索引に列挙されるキーワードを、当該キーワードが本文中で出現する際の前後の文字列とともに提示するものである。
【０００３】
したがって、たとえば、ある用語がインターネット上で利用されている様子を検索して、これをＫＷＩＣ形式で提示すれば、当該用語がインターネット内でどのように利用されているか、の用例を得ることができる。
【０００４】
【発明が解決しようとする課題】
このようなＫＷＩＣ形式での用例提示においては、検索対象となるキーワードの前後をどこまで文脈（Ｃｏｎｔｅｘｔ）として表示するか、その重要性はどのように見積もるか、についての技術が求められている。
【０００５】
また、日本語に限らず、わかち書きをしない言語において容易にＫＷＩＣ形式の用例検索ができるようにするには、辞書を用いた形態素解析を行わずに、必要な文脈の切り出しができるようにしなければならない。辞書を用いたのでは、日々変化する言語の生きた用例を得ることができないほか、形態素解析器の能力が不十分な環境下でも、ＫＷＩＣ形式の用例検索が利用できるようにしたいという要望もあるからである。
【０００６】
本発明は、以上のような課題を解決するためになされたもので、種々の言語により記述された文書に対して形態素解析を行わなくとも適切な用例を検索し、これをＫＷＩＣ形式で提示するのに好適な、部分文字列の抽出装置、用例検索装置、ならびに、これらをコンピュータ上に実現するプログラムを提供することを目的とする。
【０００７】
【課題を解決するための手段】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００８】
本発明の第１の観点に係る部分文字列の抽出装置は、文字列入力受付部と、開始位置受付部と、評価値計算部と、抽出部と、を備え、以下のように構成する。
【０００９】
すなわち、文字列入力受付部は、長さＮ  （Ｎ≧１）の文字列
ｓ  ＝  Ｘ１，…，ＸＮ
の入力を受け付ける。
【００１０】
一方、開始位置受付部は、入力を受け付けられた文字列における開始位置ｋ  （１≦ｋ≦Ｎ）の入力を受け付ける。
【００１１】
さらに、評価値計算部は、長さｉ  （１≦ｉ≦Ｎ−ｋ＋１）の部分文字列
ｓｉ  ＝  Ｘｋ，…，Ｘｋ＋ｉ−１
について、当該部分文字列ｓｉのｓにおける出現頻度Ｎｉと、ｓにおいて当該部分文字列ｓｉに続いて出現する文字の種類の数Ｃｉとから、評価値
ＳＣ（ｓｉ）  ＝  ｌｏｇ（ｉ＋１）×ｌｏｇ（Ｎｉ）×（１−１／Ｃｉ）
を計算する。
【００１２】
そして、抽出部は、計算された評価値が
ＳＣ（ｓｉ＋１）  ＞  ＳＣ（ｓｉ）
を満たす場合、当該部分文字列ｓｉ＋１を抽出する。
【００１３】
本発明の他の観点に係る用例検索装置は、対象文書入力受付部と、検索文字列入力受付部と、検索部と、を備え、以下のように構成する。
【００１４】
すなわち、対象文書入力受付部は、対象文書の入力を受け付ける。
【００１５】
一方、検索文字列入力受付部は、検索文字列の入力を受け付ける。
【００１６】
さらに、検索部は、入力を受け付けられた対象文書に出現する部分文字列であって、入力を受け付けられた検索文字列を接頭辞とするものを、用例として出力する。
【００１７】
また、本発明の用例検索装置において、検索部は、上記の抽出装置に、当該対象文書を文字列の入力として与え、当該検索文字列が当該対象文書において出現する場所のそれぞれについて、これに続く位置を開始位置の入力として与え、当該出現する場所から当該抽出された部分文字列の終了位置までの部分文字列を、用例として出力するように構成することができる。
【００１８】
また、本発明の用例検索装置において、検索部は、当該用例に対応して抽出された部分文字列の評価値により、当該用例を整列して出力するように構成することができる。
【００１９】
また、本発明の用例検索装置において、検索部は、当該検索文字列を接頭辞とし、当該対象文書に２回以上出現する部分文字列（以下「接頭重複文字列」という。）であって、他の接頭重複文字列の接頭辞となっていないものを、用例として出力するように構成することができる。
【００２０】
本発明の他の観点に係るプログラムは、コンピュータを、上記の抽出装置、または、上記の用例検索装置のいずれか１つとして機能させるように構成する。
【００２１】
また、本発明のプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリなどの情報記録媒体に記録することができる。
【００２２】
また、コンピュータとは独立して、本発明のプログラムを記録した情報記録媒体を配布、販売したり、コンピュータ通信網を介して当該プログラムを配布や販売等することができる。
【００２３】
【発明の実施の形態】
以下に本発明の一実施形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本願発明の範囲に含まれる。
【００２４】
（部分文字列の抽出装置の実施の形態）
図１は、本発明に係る部分文字列の抽出装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【００２５】
部分文字列の抽出装置５０１は、文字列入力受付部５０２と、開始位置入力受付部５０３と、評価値計算部５０４と、抽出部５０５と、を備える。
【００２６】
ここで、文字列入力受付部５０２は、長さＮ  （Ｎ≧１）の文字列
ｓ  ＝  Ｘ１，…，ＸＮ
の入力を受け付ける。抽出装置５０１をＫＷＩＣ形式の検索装置にて利用する場合には、当該文字列ｓは、検索キーワードが発見された文書の内容に相当する。
【００２７】
一方、開始位置入力受付部５０３は、入力を受け付けられた文字列における開始位置ｋ  （１≦ｋ≦Ｎ）の入力を受け付ける。抽出装置５０１をＫＷＩＣ形式の検索装置にて利用する場合には、当該開始位置ｋは、検索キーワードが発見された場所のそれぞれについて、当該場所の次の位置、すなわち、検索キーワードに直接後続する位置に相当する。
【００２８】
さらに、評価値計算部５０４は、長さｉ  （１≦ｉ≦Ｎ−ｋ＋１）の部分文字列
ｓｉ  ＝  Ｘｋ，…，Ｘｋ＋ｉ−１
について、当該部分文字列ｓｉのｓにおける出現頻度Ｎｉと、ｓにおいて当該部分文字列ｓｉに続いて出現する文字の種類の数Ｃｉとから、評価値
ＳＣ（ｓｉ）  ＝  ｌｏｇ（ｉ＋１）×ｌｏｇ（Ｎｉ）×（１−１／Ｃｉ）
を計算する。
【００２９】
この評価値は、単語列からコロケーションを抽出するためのＣ−ｖａｌｕｅという評価関数から着想を得たものであり、文字列の文字単位で評価値をローカルに計算できるという特徴を有する。上記の積の第１項は、極端に短い候補の評価値を小さくする一方で、長過ぎる候補が優先されないようにしている。第２項は、出現頻度に対応するものである。第３項は、後続する文字の種類が多い場合に大きい値となる。これは、「極端に長くも短かくもなく、頻出し、後続する文字の種類が多い」ものが「単語候補」としてふさわしい、ということに対応する。
【００３０】
そして、抽出部５０５は、ｉの値を順次増やして走査していき、計算された評価値が
ＳＣ（ｓｉ＋１）  ＞  ＳＣ（ｓｉ）
を満たす場合、当該部分文字列ｓｉ＋１を抽出する。これは、検索キーワードに後続する「文脈」として適当と考えられる部分文字列であり、検索キーワードとこの「文脈」とを連接させたものは、「検索キーワードから開始される生きた用例」と考えることができる。
【００３１】
なお、上記実施形態では、評価値の計算にｌｏｇ（ｉ＋１）、ｌｏｇ（Ｎｉ）、（１−１／Ｃｉ）を用いているが、これらは上記のような性質を維持する関数であれば、種々のものを採用できる。たとえば、
ｆ（ｘ）  ＝  １  −  １／ｘ
ｇ（ｘ）  ＝  １  −  ｅｘｐ（−ｘ）
とおき、各項の式中のｌｏｇ（・）のかわりにａｒｃｔａｎ（・）、ｆ（・）、ｇ（・）等を利用しても良い。
【００３２】
また、（１−１／Ｃｉ）  ＝  ｆ（Ｃｉ）であるが、このかわりにｌｏｇ（Ｃｉ）、ａｒｃｔａｎ（Ｃｉ）、ｇ（Ｃｉ）等を利用しても良い。
【００３３】
ＮｉやＣｉを求めるためには、Ｔｒｉｅ構造を用いることが望ましい。Ｔｒｉｅ構造に対して、所定の最大長さＬまでの部分文字列ｓ１，…，ｓＬを登録し、その際にＮｉやＣｉを更新するとともに、評価値による走査も、Ｔｒｉｅ構造を探索すれば容易に行うことができる。
【００３４】
これらの関数は、いずれも、ある程度以上の大きさの引数に対して単調非減少関数であり、次第に増加率が減少していくものと見ることもできる。したがって、このような性質を有する離散的な関数を、変数テーブルを利用して用意し、上記のような算術演算を行うのではなく、変数テーブルを用いて直ちに関数の結果を得るような態様を採用することもできる。
【００３５】
（検索装置の実施の形態）
以下では、上記の部分文字列の抽出装置５０１を用いた検索装置の概要構成について説明する。図２は、本発明の実施の形態に係る検索装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【００３６】
用例検索装置７０１は、対象文書入力受付部７０２と、検索文字列入力受付部７０３と、検索部７０４と、を備える。
【００３７】
ここで、対象文書入力受付部７０２は、対象文書の入力を受け付け、検索文字列入力受付部７０３は、検索文字列の入力を受け付ける。たとえば、インターネット内におけるある文字列の用例を検索したい場合には、インターネット内で入手可能な文書集合に含まれる文書、もしくは、当該文書集合を当該文字列により他の検索エンジンで検索して得られた結果の文書集合に含まれる文書のそれぞれを、対象文書とする。また、当該文字列を検索文字列とする。
【００３８】
そして、検索部７０４は、上記の抽出装置５０１に、当該対象文書を文字列の入力として与え、当該検索文字列が当該対象文書において出現する場所のそれぞれについて、これに続く位置を開始位置の入力として与え、当該出現する場所から当該抽出された部分文字列の終了位置までの部分文字列を、用例として出力する。
【００３９】
これによって、対象文書に出現する「検索文字列とこれに後続する文脈」のそれぞれが用例として出力される。
【００４０】
ここで、検索文字列に後続する文脈、すなわち、抽出装置５０１が部分文字列として出力したものの、上記評価値により、当該用例を整列して出力すると、用例が頻繁に用いられる順、重要と予想される順に提示されることになる。
【００４１】
たとえば、英語の文書集合に対して、ｆｅｄ  ｕｐを検索文字列とし、既存の検索エンジンを用いてこれを検索した結果を対象文書とし、上記評価値を用いて整列すると、本実施形態を実験すると、以下のような用例が順に得られた。
ｆｅｄ  ｕｐ  ｗｉｔｈ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｔｈｅ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｔｈｅ  ｆａｎｎｙ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｓｃｈｏｏｌ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｔｈｉｓ
ｆｅｄ  ｕｐ  ａｌｌ  ｔｈｅ  ｐｏｗｅ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｓｏｕｒｃｅ  ｃｏｄｅ
ｆｅｄ  ｕｐ  ｂｙ  ｌａｚａｒｕｓ  ｌｏｎｇ
ｆｅｄ  ｕｐ  ｎｏｗ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｄｒｉｖｅｒｓ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｒｏｇｅｒｓ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｓｔｏｎｅｙ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｓｐａｍ
ｆｅｄ  ｕｐ  ａｎｄ  ｈｕｎｇｒｙ
ｆｅｄ  ｕｐ  ｏｆ  ｉｄｉｏｔｓ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｒｐｍ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｎｆｓ
ｆｅｄ  ｕｐ  ｗｉｔｈ  ｎｉｓ
【００４２】
これを見ると、ｗｉｔｈが後続する文脈としてＫＷＩＣ形式で抽出されており、頻出熟語ｆｅｄ  ｕｐ  ｗｉｔｈが用例として検索できている。また、英和辞典などには、ｆｅｄｕｐ  ｗｉｔｈ  〜ｉｎｇのように動名詞が続く形が紹介されているが、生きた英語（インターネットで使われている英語）では、このような用例は見当たらない。これは、英語ネイティブが感じている「ｆｅｄ  ｕｐ  ｗｉｔｈ  〜ｉｎｇは文法的には正しいが、あまり使わない」という印象と合致している。
【００４３】
上記実施形態においては、対象文書が「（英語なので）空白等で区切られている」という性質を直接は利用していないが、上記のようにほぼ適切な単語や単語列で部分文字列が抽出されている。単語と単語を区切る空白の後に出現する文字の種類の数は多いと考えられることから、空白の前後で評価値が抽出条件を満たすように変化したものとと考えられる。
【００４４】
なお、ある検索文字列に先行する文脈を得たい場合には、抽出装置５０１に、当該対象文書の文字列を逆順にしたものを文字列の入力として与え、当該対象文書の文字列を逆順にしたものにおいて当該検索文字列を逆順にしたものが出現する場所のそれぞれについて、これに続く位置を開始位置として与え、当該出現する場所から当該抽出された部分文字列の終了位置までの部分文字列を逆順にしたものを、用例とすればよい。すなわち、上記アルゴリズムの添字を逆順にし、評価値を順に計算していく処理も逆順に行うようにすれば良いのである。したがって、先行する文脈を得る実施形態は、本質的に、上記の後続する文脈を得る実施形態と等価であり、このような実施形態も本発明の範囲に含まれる。
【００４５】
インターネット内に存在する日本語の文書集合についてあらかじめ検索文字列「首相」により文書集合を検索したものに対して、本実施形態を適用した場合、「首相」に先行する文脈として、第１位は「小泉」が、第２位は「マハティール」が、それぞれ得られた。また、「東京」に後続する文脈として、第１位は「都」が、第２位は「大学」が、それぞれ得られた。これは、それぞれの検索文字列の生きた用例としてふさわしいものであると考えられる。
【００４６】
（その他の実施形態）
上記実施形態では、Ｃ−ｖａｌｕｅに類似した手法を用いてある文字列に後続する文脈の抽出と、当該文脈の重要度と、を得ていたが、本実施形態では、以下のようにして、これらの処理を行う。
【００４７】
すなわち、当該検索文字列を接頭辞とし、当該対象文書に２回以上出現する部分文字列（以下「接頭重複文字列」という。）であって、他の接頭重複文字列の接頭辞となっていないものを、用例として出力することとする。
【００４８】
たとえば、対象文書として「ａｂｒａｃａｄａｂｒａ」を、接頭辞として「ａ」を考える。「ａ」を接頭辞とする接頭重複文字列は、以下の通りである。
「ａｂｒａ」…２回出現。
「ａｂｒ」…２回出現。
「ａｂ」…２回出現。
「ａ」…５回出現。
【００４９】
さてここで、２回出現した「ａｂｒ」はいずれも、他の接頭重複文字列「ａｂｒａ」の接頭辞となっている。また、２回出現した「ａｂ」はいずれも、他の接頭重複文字列「ａｂｒａ」の接頭辞となっている。さらに、５回出現した「ａ」のうち２回は、他の接頭重複文字列「ａｂｒａ」の接頭辞となっている。したがって、これらを除いたものが接頭最長重複文字列であり、以下の通りである。
「ａｂｒａ」…２回出現。
「ａ」…３回出現。
【００５０】
このような接頭最長重複文字列を文脈として抽出し、当該出現頻度を重要度と考えることができる。
【００５１】
このほか、ＰＰＭを用いた確率を重要度として採用しても良い。ＰＰＭでは、時系列ｘ０，…，ｘｉが与えられたとき、次の要素ｘｉ＋１が出現する確率を
Ｐ（ｘｉ＋１）  ＝  Σｋ＝−１ｋｍａｘ  ｕｋＰｋ（ｘｉ＋１）
により推定する。この確率の値の順に、候補を提示するのである。
【００５２】
ここで、ｋは、ｘｉ＋１の前ｋ個分の要素を表す。Ｐｋ（ｘｉ＋１）は、前ｋ個分の要素による文脈を考慮した確率であり、自然言語処理で用いられるｎ−ｇｒａｍで考えると、ｋ  ＝  ｎ−１との対応関係がある。すなわち、ｋ  ＝  １ではｂｉｇｒａｍを考えたことに、ｋ  ＝  ３ではｔｒｉｇｒａｍを考えたことになる。
【００５３】
Ｃｋをその文脈が現れた回数、ｃｋ（ｘｉ＋１）をその文脈に続いてｘｉ＋１が現れた回数とすれば、
Ｐｋ（ｘｉ＋１）  ＝  ｃｋ（ｘｉ＋１）／Ｃｋ
のように近似することができる。
【００５４】
ｋ  ＝  −１は、文脈から情報が全く得られない場合に対応する。この場合には、初期確率を適当に決める必要があるが、たとえば、任意のｘｉ＋１について等確率とする手法が採用できる。
【００５５】
また、ｕｋは重みで、各種の決め方が既に提案されている。たとえば、ＰＰＭＡと呼ばれる重みを採用することができる。ｋｍａｘはｋの上限であり、４程度で十分であることが実験により確かめられている。
【００５６】
本実施形態では、時系列ｘ０，…，ｘｉとして、検索文字列とそれに先行する文字列を文字単位で考え、ｘｉ＋１は接頭最長重複文字列のそれぞれと考えて、確率を計算する。このようにすると、当該検索文字列とこれに先行する文字列を含む文脈において、出現する可能性の順に、得られた接頭最長重複文字列を整列することができる。
【００５７】
【発明の効果】
以上説明したように、本発明によれば、種々の言語により記述された文書に対して形態素解析を行わなくとも適切な用例を検索し、これをＫＷＩＣ形式で提示するのに好適な、部分文字列の抽出装置、用例検索装置、ならびに、これらをコンピュータ上に実現するプログラムを提供することができる。
【図面の簡単な説明】
【図１】本発明の実施形態に係る部分文字列の抽出装置の概要構成を示す模式図である。
【図２】本発明の実施形態に係る検索装置の概要構成を示す模式図である。
【符号の説明】
５０１  抽出装置
５０２  文字列入力受付部
５０３  開始位置入力受付部
５０４  評価値計算部
５０５  抽出部
７０１  用例検索装置
７０２  対象文書入力受付部
７０３  検索文字列入力受付部
７０４  検索部
【図１】
2004164133.tif 000003
【図２】
2004164133.tif 000004