(57)【特許請求の範囲】
【請求項１】
与えられた文書集合の中から、文書集合を代表する1つ以上の文書を選択する代表的文書選択装置であって、
前記文書集合の文書を連結した連結文書を作成する文書連結手段と、
前記連結文書から接尾辞配列を構築する接尾辞配列構築手段と、
前記接尾辞配列を記憶する接尾辞配列記憶手段と、
前記文書集合の各文書に対して、該文書に含まれる部分文字列が、前記連結文書に出現する頻度である出現頻度と、前記連結文書において該部分文字列の次に出現する異なり文字数である異なり次文字数と、を前記接尾辞配列記憶手段の前記接尾辞配列から検索結果として取得する部分文字列検索手段と、
前記部分文字列検索手段の検索結果から前記文書の文書スコアを計算する文書スコア計算手段と、
前記文書スコアを基に、代表的文書集合を決定して出力する文書選択手段と、
を有することを特徴とする代表的文書選択装置。
【請求項２】
前記部分文字列検索手段の検索結果を記憶する検索結果キャッシュ手段を有し、
前記部分文字列検索手段は、
前記文書に含まれる部分文字列の検索結果が前記検索結果キャッシュ手段に含まれていない場合は、該部分文字列の前記出現頻度と前記異なり次文字数を前記接尾辞配列記憶手段の前記接尾辞配列から検索結果として取得すると同時に該検索結果を前記検索結果キャッシュ手段に記憶し、
前記文書に含まれる部分文字列の検索結果が前記検索結果キャッシュ手段に含まれている場合は、該検索結果キャッシュ手段から該検索結果を取得する手段と、
を含む請求項１記載の代表的文書選択装置。
【請求項３】
前記文書集合の各文書に対して、該文書が持つ情報から該文書に荷重を与え、該荷重に比例した確率に従ってサンプリングを行ってサンプリング文書集合を生成するサンプリング文書集合生成手段を有し、
前記文書連結手段は、
前記サンプリング文書集合の文書を連結した連結文書を作成する手段を含む
請求項１または２記載の代表的文書選択装置。
【請求項４】
与えられた文書集合の中から、文書集合を代表する1つ以上の文書を選択する代表的文書選択方法であって、
文書連結手段が、前記文書集合の文書を連結した連結文書を作成する文書連結ステップと、
接尾辞配列構築手段が、前記連結文書から接尾辞配列を構築し、接尾辞配列記憶手段に格納する接尾辞配列構築ステップと、
部分文字列検索手段が、前記文書集合の各文書に対して、該文書に含まれる部分文字列が、前記連結文書に出現する頻度である出現頻度と、前記連結文書において該部分文字列の次に出現する異なり文字数である異なり次文字数と、を前記接尾辞配列記憶手段の前記接尾辞配列から検索結果として取得する部分文字列検索ステップと、
文書スコア計算手段が、前記部分文字列検索手段の検索結果から前記文書の文書スコアを計算する文書スコア計算ステップと、
文書選択手段が、前記文書スコアを基に、代表的文書集合を決定して出力する文書選択ステップと、
を行うことを特徴とする代表的文書選択方法。
【請求項５】
前記部分文字列検索ステップにおいて、
前記部分文字列検索手段の検索結果を記憶するための検索結果キャッシュ手段に、前記文書に含まれる部分文字列の検索結果が含まれていない場合は、該部分文字列の前記出現頻度と前記異なり次文字数を前記接尾辞配列記憶手段の前記接尾辞配列から検索結果として取得すると同時に該検索結果を前記検索結果キャッシュ手段に記憶し、
前記文書に含まれる部分文字列の検索結果が前記検索結果キャッシュ手段に含まれている場合は、該検索結果キャッシュ手段から該検索結果を取得する
請求項４記載の代表的文書選択方法。
【請求項６】
サンプリング文書集合生成手段が、前記文書集合の各文書に対して、該文書が持つ情報から該文書に荷重を与え、該荷重に比例した確率に従ってサンプリングを行ってサンプリング文書集合を生成するサンプリング文書集合生成ステップを更に行い、
前記文書連結ステップにおいて、
前記サンプリング文書集合の文書を連結した連結文書を作成する
請求項４または５記載の代表的文書選択方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載の代表的文書選択装置の各手段として機能させるための代表的文書選択プログラム。
【請求項８】
請求項７記載の代表的文書選択プログラムを格納したことを特徴とするコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、代表的文書選択装置及び方法及びプログラム及びコンピュータ読取可能な記録媒体に係り、特に、文書を単語の集合に分割することなく、どのような言語で記述された文書に対しても、短い時間かつ高い精度で文書集合全体の内容を良く表す代表的な文書を選択することを実現するための代表的文書選択装置及び方法及びプログラム及びコンピュータ読取可能な記録媒体に関する。
【背景技術】
【０００２】
近年では誰もが情報を発信可能なソーシャルメディアが普及しており、大量の文書が溢れている。特に、マイクロブログ（ミニブログとも呼ばれる）という、主に利用者自身の現在の状況や雑感などを短いテキストで記すウェブサイトにおいては、1日1億件程度の大量のテキストが投稿されている。
【０００３】
このような状況の中で、大量に投稿された文書集合や、キーワードを含む文書検索結果集合の中から、情報の少ない、あるいは不必要な文書を取り除き、代表的な文書のみを発見する需要は高まっている。例えば、文書集合に含まれるユーザにとって不必要な文書を取り除くため、文書を単語の集合（Bag-of-words）に分割し、文書分類アルゴリズムを適用することで実現する方法がある（例えば、非特許文献１参照）。している。しかし、崩れた文体で記述されることが多いマイクロブログなどにおいては、日本語などの単語が空白文字で区切られていない言語で記述された文書を高い精度で単語に分割することは非常に難しく、形態素解析に依存しない手法が求められている。また、文書分類アルゴリズムの実現には学習が必要であり、多くの計算時間を要してしまう。
【０００４】
このように、与えられた文書集合に対して短い時間で学習を完了させ、また、文書を単語の集合に分割することなく可変長の部分文字列集合として扱い、どのような言語で記述された文書に対しても、短い時間かつ高い精度で代表的な文書を発見可能な手法は提案されていない。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Irani et al., Study of Trend-Stuffing on Twitter through Text Classification, CEAS 2010 - Seventh annual Collaboration, Electronic messaging, Anti-Abuse and Spam Conference, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記のように、現在は、与えられた文書集合に対して短い時間で学習を完了させ、また、文書を単語の集合に分割することなく可変長の部分文字列集合として扱い、どのような言語で記述された文書に対しても、短い時間かつ高い精度で代表的な文書を発見可能な技術は存在しない。
【０００７】
本発明は、上記の点に鑑みなされたもので、与えられた文書集合の学習を、連結した文書の文字列から接尾辞配列を構築することのみとすることで、形態素解析や部分文字列長の制限が無く、少ない記憶容量・短い学習時間・高精度な文書スコア付けを同時に全て実現する代表的文書選択装置及び方法及びプログラム及びコンピュータ読取可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明（請求項１）は、与えられた文書集合の中から、文書集合を代表する1つ以上の文書を選択する代表的文書選択装置であって、
前記文書集合の文書を連結した連結文書を作成する文書連結手段と、
前記連結文書から接尾辞配列を構築する接尾辞配列構築手段と、
前記接尾辞配列を記憶する接尾辞配列記憶手段と、
前記文書集合の各文書に対して、該文書に含まれる部分文字列が、前記連結文書に出現する頻度である出現頻度と、前記連結文書において該部分文字列の次に出現する異なり文字数である異なり次文字数と、を前記接尾辞配列記憶手段の前記接尾辞配列から検索結果として取得する部分文字列検索手段と、
前記部分文字列検索手段の検索結果から前記文書の文書スコアを計算する文書スコア計算手段と、
前記文書スコアを基に、代表的文書集合を決定して出力する文書選択手段と、を有する。
【０００９】
また、本発明（請求項２）は、前記部分文字列検索手段の検索結果を記憶する検索結果キャッシュ手段を有し、
前記部分文字列検索手段は、
前記文書に含まれる部分文字列の検索結果が前記検索結果キャッシュ手段に含まれていない場合は、該部分文字列の前記出現頻度と前記異なり次文字数を前記接尾辞配列記憶手段の前記接尾辞配列から検索結果として取得すると同時に該検索結果を前記検索結果キャッシュ手段に記憶し、
前記文書に含まれる部分文字列の検索結果が前記検索結果キャッシュ手段に含まれている場合は、該検索結果キャッシュ手段から該検索結果を取得する手段と、を含む。
【００１０】
また、本発明（請求項３）は、前記文書集合の各文書に対して、該文書が持つ情報から該文書に荷重を与え、該荷重に比例した確率に従ってサンプリングを行ってサンプリング文書集合を生成するサンプリング文書集合生成手段を有し、
前記文書連結手段は、
前記サンプリング文書集合の文書を連結した連結文書を作成する手段を含む。
【発明の効果】
【００１１】
上記のように構成された請求項１記載の代表的文書選択装置によれば、文書に含まれる部分文字列の、文書集合全体における出現頻度や異なり次文字数を、接尾辞配列を用いて高速に取得し、訓練集合に基づいた各部分文字列の生起確率を求めることで、文書集合を代表する文書を高い精度かつ短い時間で選択することができる。学習は文書集合を連結した文書から接尾辞配列を構築するのみであるため、形態素解析やn-gram分割の必要が無く、どんな言語で記述された文書に対しても共通の処理を用いて、少ない記憶容量・短い学習時間で代表的文書選択器を実現できる。
【００１２】
本発明は、検索結果のランキング、文書集合中の不要文書削除、マイクロブログからのパーソナライズを行うための文書選択などに応用可能である。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施の形態における代表的文書選択装置の構成図である。
【図２】本発明の一実施の形態における代表的文書選択装置の学習動作のフローチャートである。
【図３】本発明の一実施の形態における文字列"ａｂｒａｋａｄａｂｒａ"から構築した接尾辞配列の例である。
【図４】本発明の一実施の形態における代表的文書選択装置の文書選択動作のフローチャートである。
【図５】本発明の一実施の形態における入力文書に含まれる部分文字列の例である。
【図６】本発明の一実施の形態における文書スコア計算例である。
【図７】本発明の一実施の形態における代表的文書選択例である。
【発明を実施するための形態】
【００１４】
以下図面と共に、本発明の実施の形態を説明する。
【００１５】
図１は、本発明の一実施の形態における代表的文書選択装置の構成を示す。
【００１６】
同図に示す代表的文書選択装置は、サンプリング文書集合生成部１と文書連結部２と接尾辞配列構築部３と接尾辞配列記憶部４と部分文字列検索部５と文書スコア計算部６と文書選択部７と検索結果キャッシュ部８から構成され、訓練文書集合を受け取り、1つ以上の代表的文書を出力する。
【００１７】
まず、学習動作について説明する。当該学習動作は、サンプリング文書集合生成部１、文書連結部２、接尾辞配列構築部３、接尾辞配列記憶部４を用いる。
【００１８】
図２は、本発明の一実施の形態における代表的文書選択装置の学習動作フローチャートである。
【００１９】
ステップ１０１）サンプリング文書集合生成部１は、与えられた文書集合の各文書に対して、該文書が持つ情報から該文書に荷重を与え、前記荷重に比例した確率に従ってサンプリングを行って訓練文書集合を生成する。例えば、文書diの荷重wiの計算は、文書情報として文書の引用回数RTiを用いて、
【００２０】
【数１】
0005575075.tif 000002
と計算できる。
【００２１】
なお、文書情報としては、その他にも文書の生成時刻、文書長、文書著者のマイクロブログにおける友人数などとを利用しても良い。このように文書を確率的にサンプリングすることによって、重要とみなされる文書に含まれる文字列に基づいて、代表的文書を選択することができる。
【００２２】
ステップ１０２）文書連結部２は、ステップ１０１で生成された訓練文書集合から、文書内容を連結した連結文書を作成する。ここで、文書の連結順序は、ランダム順、文書の作成時間順など如何なる順序でも良い。
【００２３】
ステップ１０３）接尾辞配列構築部３は、前記文書連結部２の出力した連結文書から接尾辞配列を構築する。図３に構築された接尾辞配列の例を示す。図３において、列SAは、各接尾辞（suffix）が、基の文書中のどの位置に出現するかを表す。また、列lcpは、接尾辞配列における次行の接尾辞との共通接頭辞長を表す。ここで、接尾辞配列の構築には、文献１（G. Nong, S. Zhang, and W.H. Chan, "Two efficient algorithms for linear suffix array construction", 2008.）で示される手法などの公知のアルゴリズムが利用可能で、文書長の長さに比例する時間で高速に構築することが可能である。また、接尾辞配列よりもさらに必要な記憶容量を減らすことのできるCompressed Suffix Array（文献２：R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching], SIAM Journal on Computing, 35(2), 2005, 378-407.）やFM-index（文献３：Paolo Ferragina and Giovanni Manzini. Indexing compressed text. Journal of the ACM (JACM), 52, 4 (Jul. 2005), 552-581）を用いても良い。
【００２４】
ステップ１０４）接尾辞配列記憶部４は、前記接尾辞配列構築部３によって構築された接尾辞配列を記憶する。
【００２５】
以上で学習動作は完了であり、本発明における学習動作は接尾辞配列の構築のみであるため、非常に短い時間で文書選択の準備を整えることができる。
【００２６】
次に、代表的文書選択装置の文書選択処理について説明する。当該処理は、接尾辞配列記憶部４、部分文字列検索部５、検索結果キャッシュ部８、文書スコア計算部６、文書選択部７を用いる。
【００２７】
図４は、本発明の一実施の形態における代表的文書選択装置の文書選択動作フローチャートである。
【００２８】
ステップ２０１）部分文字列検索部５は、外部から与えられた文書集合の文書ｄに含まれる全ての部分文字列を検索する。
【００２９】
図５に示す、文書が"bracara"の場合を用いて本ステップの説明を行う。当該部分文字列検索部５は、文書の長さがm（この例では7）のとき、m回のループ（ループ1〜ループm）を処理する。
【００３０】
まずループ1では、文字列"b"の出現頻度を、前記検索結果キャッシュ部８または前記接尾辞配列記憶部４から検索して取得する。次は文字列"br"、その次は"bra"、という様に1文字ずつ検索文字列を追加していく。このとき、該部分文字列の接尾辞配列中の出現範囲をメモリ（図示せず）に記録しておき、次の部分文字列の検索範囲として設定することで、効率的な検索が行える。なお、出現頻度が0になったところで、該ループにおける以降の部分文字列の出現頻度は全て0となるので次ループに移る。
【００３１】
ループ2も同様に、文字列"r", "ra", "rac", …の順に検索結果を取得し、以降、最後のループmまで同様の処理を行う。
【００３２】
当該ステップにより、部分文字列検索部５は、前記連結文書において出現頻度が0となる部分文字列を除いた全ての部分文字列に関して、出現頻度と異なり次文字数を取得する。文書に含まれる部分文字列数の総数はm(m+1)/2個であるが、出現頻度が0回の部分文字列については検索処理を打ち切るため、効率的かつ高速に該出現頻度と該異なり次文字数を取得できる。また、検索結果キャッシュ部８に接尾辞配列からの検索結果を記憶しておくことで、さらなる高速化が可能となる。この検索結果キャッシュ部８に検索結果を格納する条件は、全て記憶、部分文字列の長さがN1以上、部分文字列の出現頻度がN2以上、これらの条件の組み合わせ、などとする。
【００３３】
ステップ２０２）文書スコア計算部６は、以下の式に従って文書dのスコアscore(d)を計算する。
【００３４】
【数２】
0005575075.tif 000003
ここで、siは、文書dにおけるi番目の文字、
【００３５】
【数３】
0005575075.tif 000004
は、j番目からi番目までの文字を表す。そして、siが依存する直前の文字数
【００３６】
【数４】
0005575075.tif 000005
は、
【００３７】
【数５】
0005575075.tif 000006
として各文字毎に決定する。ここで、ステップ２０１にて導出済みの
【００３８】
【数６】
0005575075.tif 000007
は
【００３９】
【数７】
0005575075.tif 000008
の出現頻度である。Fcutoffは、ハイパーパラメータである（例えば、3などを設定する）。
【００４０】
また、
【００４１】
【数８】
0005575075.tif 000009
を全ての文字で同じ値としても良い（例えば、5などを設定する）。
【００４２】
文字siの生起確率
【００４３】
【数９】
0005575075.tif 000010
は、以下の通り計算する。
【００４４】
【数１０】
0005575075.tif 000011
ここで、重みwは以下の通り計算できる。
【００４５】
【数１１】
0005575075.tif 000012
ただし、p0は連結文書に出現する全ての異なり文字数の逆数、ei,0=0とする。
【００４６】
そして、
【００４７】
【数１２】
0005575075.tif 000013
とei,nは、以下の通り計算する。
【００４８】
【数１３】
0005575075.tif 000014
ここで、
【００４９】
【数１４】
0005575075.tif 000015
は、ステップ２０２にて導出済みの連結文書中における
【００５０】
【数１５】
0005575075.tif 000016
の後に続く異なり文字数である。
【００５１】
また、
【００５２】
【数１６】
0005575075.tif 000017
は、文献４（北研二, "確率的言語モデル", 東京大学出版会, 1999）にて公知のバックオフスムージングなどにより決定しても良い。
【００５３】
以上の様に文書のスコアを計算することで、文書を単語に分割する必要無く、文書中の2単語以上に跨る情報や、1単語未満の文字レベル情報、文字の出現順序に関する情報を全て利用して、文書集合全体の内容とマッチする文書に高いスコアを与えることが可能となる。
ステップ２０３）文書選択部７は、前記文書スコア計算部６が導出したscore(d)により、スコアが高い順にN個選択する。また、score(d)が閾値θ以上の文書を全て出力する、などとして選択しても良い。
【００５４】
図６に、文書スコアの計算例を示す。文書集合として地震に関する文書を与え、これを基に接尾辞配列を構築すると、集合に含まれるある文書「原子力発電について考える」について、文書集合中には「原子力発電」という文字列が多く出現するため、特にp("電"|"原子力発")の値が1に近づく。結果として、この文書のスコアが高くなる。
【００５５】
図７に、代表的文書の選択例を示す。上記の様に文書集合中の各文書に対して文書スコアを計算し、例えばN=3とすると、文書集合中の代表的な文書3つが選択される。
【００５６】
このように、本発明では、文書集合に含まれる特徴的な部分文字列によって、文書集合を代表する文書を高い精度で選択することができる。学習は文書集合を連結した文書から接尾辞配列を構築するのみであるため、形態素解析やn-gram分割の必要が無く、どんな言語で記述された文書に対しても共通の処理を用いて、少ない記憶容量・短い学習時間で代表的文書選択器を実現できる。
【００５７】
また、本発明は、図１に示す代表文書選択装置の構成要素の動作をプログラムとして構築し、マイクロブログ代表的文書選択装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５８】
また、構築されたプログラムをハードディスクやフレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００５９】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００６０】
１  サンプリング文書集合生成部
２  文書連結部
３  接尾辞配列構築部
４  接尾辞配列記憶部
５  部分文字列検索部
６  文書スコア計算部
７  文書選択部
８  検索結果キャッシュ部
【図１】
0005575075.tif 000018
【図２】
0005575075.tif 000019
【図３】
0005575075.tif 000020
【図４】
0005575075.tif 000021
【図５】
0005575075.tif 000022
【図６】
0005575075.tif 000023
【図７】
0005575075.tif 000024