JP2012018510A - 文書処理装置、文書処理方法、文書処理プログラム、及び文書処理プログラムを記録したコンピュータ読み取り可能な記録媒体 - Google Patents

Abstract

【課題】 インターネット上の文書から、正当な引用を行なっている文書を含めたオリジナルな文書の抽出を可能にする。
【解決手段】 複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段とを備える。
【選択図】 図１

Description

本発明は、インターネット上に存在する文書、例えば、ブログ等の文書から、分析対象とする目的の文書を抽出する文書処理装置に関する。

インターネットの発展により、入手可能な文書データの量は、飛躍的に増大した。これらの文書データの中には、ブログ等を通じて、個人が自発的に興味の対象や、社会事象に対する意見等を述べたものも数多く含まれるようになった。そこで、このような意見等を述べた文書データを収集して分析することにより、従来は、回答者を募集してアンケートを実施する必要があった社会風潮や消費者動向の把握が、網羅的、かつリアルタイムに実施可能になると期待されている。
一方、ディジタルデータは、入手が容易であると同時に、引用・編集・改変して再発信することも容易であり、インターネット上の文書には、こうした二次情報も多く含まれていると言われている。オリジナルな一次情報とその流用による二次情報が混在していると、同様なデータが重複して格納されることによる記憶効率の低下や、検索問い合わせに対して同様な結果が繰り返し提示されることによる一覧性の低下といった問題が生じる。そこで、各文書データから部分文字列を取り出し、部分文字列毎に出現文書の一覧を管理することで、重複部分を含む文書の提示を可能にするシステムが提案されている（例えば、特許文献１及び２参照）。

特開２００８−３３７２８号公報 特表２００８−５１１０８１号公報

ブログ等の中には、記事本体よりも、記事に付随する広告の発信を主眼としたものも存在する。このような広告記事の作成者は、なるべく労力をかけずに記事を作成するために、他のブログ記事を取得して引用するコンピュータプログラムを利用して、広告記事を自動生成することが多い。スパムブログと呼ばれるこのようなブログ記事が大量に存在すると、前述の社会風潮や消費者動向の把握を目的として、全文書データの統計処理を行なった際に、自動引用された情報の出現頻度が増加し、現実において話題とされる頻度の実態と大きく乖離してしまうという問題が生じる。

従来の文書処理装置においては、例えば、特許文献１では、重複の可能性のある文書の検出に止まっており、文書の削除などの最終的な処置は、文書処理装置の利用者が文書の内容を判断した上で実施する必要がある。なぜなら、ブログにおいては、ニュース記事などの一次情報に対する所感を述べる際に、正当な引用が行なわれることもあるため、重複が検出された文書を全て一律に削除するのは不適当であり、利用者が一つ一つの記事を精査しなくてはならないからである。特許文献１の技術は、データベースを管理する際に意図せずに生じてしまう重複の検出を目的としており、他者により意図的にデータが引用・複製される状況には対処することができない。

また、特許文献２はインターネット上の文書を想定したものであるが、２つの文書の組に対して、文書単位での重複の有無を判定する技術である。このため、文書集合から２つ以上の文書の一部を切り出して合成された文書に対しては、切り出された文書の一部を単位として重複の検出を行なうことができず、このような合成された文書を排除することができない。

この発明は、上記のような課題を解決するためになされたもので、文書集合に対し、他の文書にも出現する部分文字列を一定割合以上含む文書を、自動引用により生成された文書として排除することで、正当な引用を行なっている文書を含めたオリジナルな文書データの抽出を可能にするものである。

上記で述べた課題を解決するため、本発明に係る文書処理装置は、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段とを備えることとしたものである。

また、本発明に係る文書処理方法は、部分文字列生成手段が、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成ステップと、一意部分文字列判定手段が、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定ステップと、不要文書検出手段が、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出ステップとを備えることとしたものである。

また、本発明に係る文書処理プログラムは、コンピュータを、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させることとしたものである。

また、本発明に係る文書処理プログラムを記録したコンピュータ読み取り可能な記録媒体は、コンピュータを、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させる文書処理プログラムを記録させることとしたものである。

本発明によれば、複数の文書に含まれる文字列から部分文字列を文書毎に生成し、文書毎に当該文書固有の一意部分文字列の割合を求め、一意部分文字列の割合が低いものを、他の１つ以上の文書の引用を中心とする有用性の低い文書として検出し、これらの文書を除去可能にすることにより、統計的な処理に適した文書集合を得ることができるという効果がある。

この発明の実施の形態１に係る文書処理装置の一例を示す構成図である。 取得文書データ５の詳細な格納形式の一例を示す図である。 部分文字列テーブル６の詳細な格納形式を示す図である。 文書属性テーブル７の詳細な格納形式を示す図である。 部分文字列テーブル６のコンピュータシステムにおける格納方法の詳細を説明する図である。 不要文書除去手段３の動作を示す概略フローチャートである。 ステップＳ１の詳細を示すフローチャートである。 ステップＳ１６の動作の詳細を示すフローチャートである。 ステップＳ１９の動作の詳細を示すフローチャートである。 ステップＳ２の詳細を示すフローチャートである。 この発明の第２の実施の形態に係る文書処理装置の構成図である。 不要ＵＲＬ除去手段１４の動作を示すフローチャートである。 この発明の第３の実施の形態に係る文書処理装置の構成図である。 ｑ＝３の場合のｑ単語列を格納する頻出ｑ単語列テーブル９０を示したものである。 不要文書除去手段３の動作の内、実施の形態１に対して実施の形態３で加わった部分を示すフローチャートである。 ステップＳ３の動作の内、特定のｑ（ｑ＞１）に対応する動作の詳細を示すフローチャートである。

実施の形態１．
図１は、この発明の実施の形態１に係る文書処理装置の一例を示す構成図である。
図１において、文書処理装置１は、サーバＡ〜Ｃ等の外部サーバ上の文書を取得する文書取得手段２と、不要文書を除去する不要文書除去手段３とを備え、文書ＵＲＬリスト４、取得文書データ５、部分文字列テーブル６、及び文書属性テーブル７によって構成される。不要文書除去手段３は、文書中の文字列から部分文字列を生成する部分文字列生成手段８と、生成された部分文字列の内、他の文書には出現せずに一意に定まる部分文字列（一意部分文字列）を判定する一意部分文字列判定手段９と、一意部分文字列数と総部分文字列数との比により、不要文書を検出する不要文書検出手段１０とを備える。文書ＵＲＬリスト４は、文書取得手段２が取得すべき外部サーバ上の文書を特定するアドレス、例えば、ＵＲＬ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｌｏｃａｔｏｒ）の一覧を保持する。取得文書データ５は、文書取得手段２が取得した複数の文書データを格納する。部分文字列テーブル６は、不要文書除去手段３による処理の中間状態を格納する。文書属性テーブル７は、不要文書除去手段３による処理結果を格納する。

文書処理装置１は、ＣＰＵ、ＲＡＭ、磁気ディスク装置、及びネットワークインタフェース等のハードウェアと、ハードウェアを制御するオペレーティングシステムソフトウェアを備える一般的なコンピュータシステムと、ＣＰＵの動作を規定するプログラムを用いて実現することができる。この場合、文書取得手段２と不要文書除去手段３とは、磁気ディスク装置からＲＡＭに読み込まれてＣＰＵにより実行されるプログラムとして実現され、文書ＵＲＬリスト４、取得文書データ５、部分文字列テーブル６、及び文書属性テーブル７は、ＲＡＭ、または、磁気ディスク装置上の固有の格納領域として実現される。

図２は、取得文書データ５の詳細な格納形式の一例を示す図である。
取得文書データ５は、複数のエントリからなり、各エントリは、１つの文書の文書ＵＲＬ５１、取得日時５２、及び文書内容５３を格納する。文書ＵＲＬ５１は、文書ＵＲＬリスト４に記憶されていた取得対象文書のアドレスの１つであり、取得日時５２は、文書取得手段２が実際に当該文書データを取得した日時である。また、文書内容５３は、文書取得手段２が取得した文書の内容データである。ここで、外部サーバ上の文書のアドレスは、文書ＵＲＬ５１により一意に識別されるが、同一の文書ＵＲＬ５１から異なる時点で取得した文書内容は異なることもあり得る。そのため、取得文書データ５においては、文書ＵＲＬ５１が共通で、取得日時５２が異なる複数のエントリが存在しても良い。また、取得文書データ５における各エントリの格納位置には特段の制約を設けず、任意とする。

図３は、部分文字列テーブル６の詳細な格納形式を示す図である。
部分文字列テーブル６は、複数のエントリからなり、各エントリは、１つの部分文字列に関するハッシュ値６１、文書ＵＲＬ６２、取得日時６３、及び重複フラグ６４を格納する。ここでいう部分文字列とは、図２に示す取得文書データ５の文書内容５３から取り出した固定単語数の文字列である。ここでは、単語の数をｋとする（例えばｋ＝５）。

ハッシュ値６１には、当該エントリに対応する部分文字列に対し、ＣＲＣ（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｎｃｙ Ｃｏｄｅ）やＳＨＡ‐２５６（Ｓｅｃｕｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈｍ ２５６‐ｂｉｔ）などの公知の一方向性ハッシュ関数により計算したハッシュ値を格納する。このようなハッシュ値は、実用上、元の部分文字列と１対１に対応すると考えることができるので、部分文字列テーブル６のエントリを一意に識別するキーとして用いる。

ここで、ハッシュ値６１の一意性を維持するため、部分文字列テーブル６における各エントリの格納位置は、ハッシュ値６１に基づいて一意に定まる必要がある。しかし、同一の部分文字列であっても、取得文書データ５には、文書ＵＲＬ５１や取得日時５２が異なる複数のエントリが存在するため、文書ＵＲＬ６２及び取得日時６３の組み合わせが一意に定まらない。そこで、部分文字列テーブル６の各エントリに重複フラグ６４を設け、次のようにして、部分文字列テーブル６における各エントリの一意性を維持する。

文書ＵＲＬ６２及び取得日時６３には、当該エントリに対応する部分文字列が取り出された取得文書データ５のエントリの文書ＵＲＬ５２及び取得日時５３の組み合わせを、１つ指定する。指定する文書ＵＲＬ５２及び取得日時５３の組み合わせは、当該エントリに対応する部分文字列を含む文書の内、取得日時が最も古い文書の文書ＵＲＬ５２と取得日時５３を用いるものとする。あるいは、文書取得手段２によらずに収集された文書集合を分析対象にする場合は、文書ＵＲＬ５２と取得日時５３の代わりに、当該エントリに対応する部分文字列が最初に生成された文書の識別情報と、文書が作成・更新された日時を用いるものとする。

重複フラグ６４には、当該エントリに対応する部分文字列が、文書ＵＲＬ６２及び取得日時６３の組み合わせで指定される文書だけに含まれる場合に、例えば、０が格納され、そうでない場合には、１が格納される。

図４は、文書属性テーブル７の詳細な格納形式を示す図である。
文書属性テーブル７は、複数のエントリからなり、各エントリは、１つの文書の文書ＵＲＬ７１、取得日時７２、部分文字列数７３、一意部分文字列数７４、及び除去フラグ７５を格納する。文書属性テーブル７の各エントリは、取得文書データ５のエントリと１対１に対応しており、文書ＵＲＬ７１及び取得日時７２は、それぞれ取得文書データ５の文書ＵＲＬ５１及び取得日時５２に対応する。文書属性テーブル７の各エントリの格納位置は、文書ＵＲＬ７１及び取得日時７２により一意に定まる必要がある。また、部分文字列数７３は、当該エントリに対応する取得文書データ５の文書内容５３に含まれる部分文字列の総数を表し、一意部分文字列数７４は、当該部分文字列の内、他のエントリの文書内容５３に含まれない部分文字列の数を表す。除去フラグ７５には、当該エントリに対応する文書が自動引用により生成されたものであり、不要とみなされる場合に、１が格納され、そうでない場合に、０が格納される。

図５は、部分文字列テーブル６のコンピュータシステムにおける格納方法の詳細を説明する図である。
図５において、文書処理装置１は、ＣＰＵ１１、ＲＡＭ１２、磁気ディスク装置１３により構成されるコンピュータシステムとして示されている。

部分文字列テーブル６は、ハッシュ値６１に基づいてランダムにアクセスされるため、ＲＡＭ１２に格納することが望ましいが、部分文字列テーブル６のエントリ数、すなわち部分文字列の種類は非常に多く、ＲＡＭ１２に部分文字列テーブル６の全体を格納するだけの容量がない場合が生じる。そこで、部分文字列テーブル６を複数の断片に分割し、ＲＡＭ１２に格納される部分文字列テーブル片（０）と、必要に応じて磁気ディスク装置１３に格納される部分文字列テーブル片（１）、部分文字列テーブル片（２）、部分文字列テーブル片（３）、．．．を設ける。ＲＡＭ１２上の部分文字列テーブル片（０）は、ハッシュ値６１をキーとする赤黒木や、ハッシュテーブル等の公知の探索構造により実現する。また、磁気ディスク装置１３上の部分文字列テーブル片（ｊ）（ｊ＝１，２，．．．）においては、各エントリをハッシュ値６１の順に配置するものとする。

また、文書属性テーブル７は、文書ＵＲＬ７１及び取得日時７２に基づいてランダムにアクセスされるが、多くの場合、ＲＡＭ１２に格納可能と想定されるため、文書ＵＲＬ７１及び取得日時７２をキーとするＲＡＭ１２上の赤黒木や、ハッシュテーブルとして実現し、処理終了時に磁気ディスク装置１３に内容を書き出せば良い。

取得文書データ５は、各エントリの書き込みと読み出しが一度ずつ行なわれるだけであり、容量も大きいため、磁気ディスク装置１３上に格納する。

次に、文書処理装置１の動作を説明する。
文書取得手段２は、文書ＵＲＬリスト４から文書ＵＲＬを読み込み、当該ＵＲＬ中のサーバ名に従って外部サーバへの接続を行ない、公知のＨＴＴＰ（Ｈｙｐｅｒ‐Ｔｅｘｔ Ｔｒａｎｓｆｅｒ Ｐｒｏｔｏｃｏｌ）に従って当該ＵＲＬを送付して文書データを要求する。次いで文書取得手段２は、当該外部サーバからの応答を受信し、前記ＵＲＬを文書ＵＲＬ５１、現在時刻を取得日時５２、受信内容を文書内容５３として取得文書データ５の末尾に追記する。この処理を文書ＵＲＬリスト４の全てのＵＲＬに対して繰り返す。各文書の取得は逐次に行なう必要はなく、複数文書を同時に並行して取得して所要時間を短縮しても良い。

次に、不要文書除去手段３の動作を、フローチャートを用いて説明する。
図６は、不要文書除去手段３の動作を示す概略フローチャートである。
始めに、ステップＳ１において、不要文書除去手段３は、取得文書データ５に格納された全てのエントリを処理し、部分文字列テーブル６及び文書属性テーブル７の設定を行なう。
次に、ステップＳ２で、不要文書除去手段３は、部分文字列テーブル６の各エントリに基づいて文書属性テーブル７を更新し、各文書に対する最終的な処理結果を格納する。

以下、図６のステップＳ１における動作の詳細を、フローチャートを用いて説明する。
図７は、ステップＳ１の詳細を示すフローチャートである。

始めに、ステップＳ１１において、不要文書除去手段３は、部分文字列生成手段８により、磁気ディスク装置１３上の部分文字列テーブル片の数を表す変数ｆを０に初期化する。

次に、ステップＳ１２において、部分文字列生成手段８は、取得文書データ５から未処理エントリを１つ選択して処理対象とし、その文書内容５３に公知の形態素解析処理を施して、単一文字列を複数の単語列に分割する。ここで、当該エントリの文書ＵＲＬ５１と取得日時５２の組で識別される文書データをｄとし、文書ｄの文書内容５３を形態素解析して得られる単語列の要素数をｎｄ、単語列をＷ１、Ｗ２、．．．、Ｗｎｄとする。なお、取得文書データ５の各エントリの処理順序は任意であり、例えば、先頭エントリから順に処理対象とすれば良い。

次に、ステップＳ１３において、部分文字列生成手段８は、文書ｄの文書ＵＲＬ５１と取得日時５２に対応する文書属性テーブル７のエントリを生成し、文書ＵＲＬ７１と取得日時７２をそれぞれ文書ＵＲＬ５１と取得日時５２に、部分文字列数７３をｎｄ−ｋ＋１（ｋは部分文字列の単語数）に、一意部分文字列数７４を０に、除去フラグを１に、それぞれ設定する。

次に、ステップＳ１４において、部分文字列生成手段８は、文書ｄにおける部分文字列を識別する変数ｉを０に設定し、続くステップＳ１５で変数ｉに１を加える。

次に、ステップＳ１６において、部分文字列生成手段８は、後述する手順により、文書ｄの形態素解析結果の単語列の内、ｉ番目以降の連続するｋ個の単語列（Ｗｉ、Ｗｉ＋１、．．．、Ｗｉ＋ｋ−１）からなる第ｉ部分文字列のハッシュ値Ｓｉに基づき、部分文字列テーブル片の更新を行なう。
ステップＳ１７では、変数ｉをｎｄ−ｋ＋１と比較し、両者が等しければステップＳ１８に進み、そうでなければステップＳ１５に戻る。

次に、ステップＳ１８において、部分文字列生成手段８は、取得文書データ５の全てのエントリが処理されたかどうか判定し、未処理のエントリが残っていればステップＳ１２に戻り、全て処理されていればステップＳ１９に進む。

最後に、ステップＳ１９において、部分文字列生成手段８は、後述する手順により、ｆ＋１個の部分文字列テーブル片を統合し、単一の部分文字列テーブル６を生成して処理を終了する。

次に、図７のステップＳ１６における動作の詳細を、フローチャートを用いて説明する。
図８は、ステップＳ１６の動作の詳細を示すフローチャートである。
始めに、ステップＳ１０１において、部分文字列生成手段８は、第ｉ部分文字列（Ｗｉ、Ｗｉ＋１、．．．、Ｗｉ＋ｋ−１）のハッシュ値Ｓｉを計算する。

次に、ステップＳ１０２において、部分文字列生成手段８は、部分文字列テーブル片（０）を検索し、ハッシュ値６１がＳｉと等しいエントリが存在するかどうか判定する。エントリが存在する場合はステップＳ１０７に進み、そうでない場合はステップＳ１０３に進む。

次に、ステップＳ１０３において、部分文字列生成手段８は、部分文字列テーブル片（０）の現在のエントリ数を調べ、その値が所定値未満であるかどうか判定する。所定値未満である場合は、ステップＳ１０６に進み、そうでない場合は、ステップＳ１０４に進む。ここで、所定値とは、例えば、ＲＡＭ１２の容量に格納可能な部分文字列テーブル片（０）のエントリ数の上限値を意味するものとする。

次に、ステップＳ１０４において、部分文字列生成手段８は、部分文字列テーブル片（０）に新たなエントリを生成できないため、ＲＡＭ１２上の部分文字列テーブル片（０）を磁気ディスク装置１３上の新たな部分文字列テーブル片（ｆ＋１）に書き出し、部分文字列テーブル片（０）を空にする処理を行なう。この時、部分文字列テーブル片（０）のエントリをハッシュ値６１の順に出力するようにする。部分文字列テーブル片（０）を木構造として実現していればこれは容易であり、部分文字列テーブル片（０）をハッシュテーブルとして実現している場合は、全エントリのソート処理を行なえば良い。

続いて、ステップＳ１０５で、部分文字列生成手段８は、磁気ディスク装置１３上の部分文字列テーブル片の数を表す変数ｆに１を加える。

次に、ステップＳ１０６において、部分文字列生成手段８は、部分文字列テーブル片（０）に新たなエントリを割り当て、当該エントリのハッシュ値６１をＳｉに、文書ＵＲＬ６２及び取得日時６３を現在処理中の文書ｄに対応する文書ＵＲＬ５１及び取得日時５２に、重複フラグ６４を０に設定し、処理を終了する。

一方、ステップＳ１０７においては、不要文書除去手段３は、一意部分文字列判定手段９により、部分文字列テーブル片（０）上の既存のエントリの文書ＵＲＬ６２及び取得日時６３を調べ、文書ｄの文書ＵＲＬ５１及び取得日時５２とそれぞれ一致するかどうか判定する。一致する場合は、同一文書内に部分文字列が複数回含まれていることを示しており、文書間の引用を示唆しないので、処理を終了する。そうでない場合は、ステップＳ１０８に進む。

次に、ステップＳ１０８において、一意部分文字列判定手段９は、前記既存エントリの重複フラグを１に設定し、当該部分文字列が複数文書に重複して存在することを記録する。

続いて、ステップＳ１０９において、一意部分文字列判定手段９は、当該既存エントリの取得日時６３が文書ｄの取得日時５２より新しいかどうか判定し、新しければステップＳ１１０に進み、そうでなければ処理を終了する。

最後に、ステップＳ１１０において、一意部分文字列判定手段９は、当該既存エントリの文書ＵＲＬ６２及び取得日時６３を、文書ｄの文書ＵＲＬ５１及び取得日時５２にそれぞれ設定し、処理を終了する。

次に、図７のステップＳ１９の動作の詳細を、フローチャートを用いて説明する。
図９は、ステップＳ１９の動作の詳細を示すフローチャートである。
始めに、ステップＳ２１において、不要文書除去手段３は、部分文字列生成手段８により、統合対象の部分文字列テーブル片のそれぞれの先頭エントリを調べ、ハッシュ値の最小値を求める。次に、先頭エントリのハッシュ値が最小値である部分文字列テーブル片の全てから先頭エントリを取得し、当該部分文字列テーブル片から先頭エントリを除去する。

次に、ステップＳ２２において、部分文字列生成手段８は、取得したエントリが単一であったかどうか判定し、単一であればステップＳ２６に進み、そうでなければステップＳ２３に進む。

次に、ステップＳ２３において、不要文書除去手段３は、一意部分文字列判定手段９により、取得した複数エントリにおいて、文書ＵＲＬ６２と取得日時６３が全て同一かどうか判定し、同一であればステップＳ２５に進み、そうでなければステップＳ２４に進む。

次に、ステップＳ２４において、一意部分文字列判定手段９は、同一ハッシュ値に対して複数文書が対応していることが明らかであるため、重複フラグ６４を１とし、ハッシュ値６１、文書ＵＲＬ６２、及び取得日時６３のそれぞれを、取得したエントリ中で取得日時６３が最小のエントリのハッシュ値６１、文書ＵＲＬ６２、及び取得日時６３に設定して出力し、ステップＳ２７に進む。
ければステップＳ２４に進む。

一方、ステップＳ２５では、一意部分文字列判定手段９は、取得したエントリは全て同一文書に対応しているため、取得エントリ中で重複フラグ６４が１になっているものが存在する場合は重複フラグ６４を１に、そうでない場合は重複フラグ６４を０とし、ハッシュ値６１、文書ＵＲＬ６２、及び取得日時６３のそれぞれを、取得した任意エントリのハッシュ値６１、文書ＵＲＬ６２、及び取得日時６３に設定して出力し、ステップＳ２７に進む。

また、ステップＳ２６では、部分文字列生成手段８は、取得した単一のエントリ自体の内容を出力し、ステップＳ２７に進む。

最後に、ステップＳ２７において、部分文字列生成手段８は、統合対象の部分文字列テーブル片が全て空になったか判定し、空であれば処理を終了し、そうでなければステップＳ２１に戻って処理を繰り返す。

なお、図９の処理は、部分文字列テーブル片の数（ｆ）が非常に大きい場合、所定数（例えば１６個）の部分文字列テーブル片を中間的な部分文字列テーブル片に統合し、次に中間的な部分文字列テーブル片の統合を行なうというように、次第に部分文字列テーブル片の数を減少させるようにして適用することもできる。これにより、磁気ディスク装置１３に対する入出力性能の低下を抑えることが可能となる。
以上が、図６のステップＳ１の詳細な動作の説明である。

次に、図６のステップＳ２の詳細な動作を、フローチャートを用いて説明する。
図１０は、ステップＳ２の詳細を示すフローチャートである。

まず、ステップＳ３１からステップＳ３２を繰り返すことで、部分文字列テーブル６の全てのエントリを順に処理する。
始めに、ステップＳ３１において、不要文書除去手段３は、不要文書検出手段１０により、部分文字列テーブル６の未処理エントリの１つを処理対象として選択し、当該エントリの文書ＵＲＬ６２及び取得日時６３で指定される文書属性テーブル７のエントリに対し、一意部分文字列数７４に１を加える。ここで、当該エントリの重複フラグに１が設定されている場合であっても、重複文書中で最も古い取得日時を持つ文書においては当該エントリに対応する部分文字列を一意部分文字列として扱う。これは、重複文書を全て除去対象とすると引用元文書も除去され、当該文書の内容が存在しなかったものとみなされてしまうためである。

なお、文書取得手段２によらずに収集された文書集合を分析対象にする場合は、上記の取得日時の情報を持たないため、文書が作成・更新された日時に基づいて、重複文書中で、重複する部分文字列が最初に生成された文書において当該エントリに対応する部分文字列を一意部分文字列として扱っても良い。

次に、ステップＳ３２において、不要文書検出手段１０は、未処理のエントリの有無を調べ、部分文字列テーブル６の全てのエントリを処理した場合はステップＳ３３に進み、そうでない場合はステップＳ３１に戻る。

続いて、ステップＳ３３からステップＳ３４を繰り返すことで、文書属性テーブル７の全てのエントリを順に処理する。
始めに、ステップＳ３３において、不要文書検出手段１０は、文書属性テーブル７の未処理エントリの１つを処理対象として選択し、部分文字列数７３に対する一意部分文字列数７４の割合が所定値以上（例えば６０％以上）であれば、当該エントリの除去フラグ７５を０に設定する。

次に、ステップＳ３４において、不要文書検出手段１０は、未処理のエントリの有無を調べ、文書属性テーブル７の全てのエントリを処理した場合は処理を終了し、そうでない場合はステップＳ３３に戻る。

なお、以上の説明においては、文書属性テーブル７はＲＡＭ１２上に存在し、効率的にランダムアクセスできるものと想定したが、文書属性テーブル７のデータ量がＲＡＭ１２の容量を上回る場合には、次のようにすれば良い。すなわち、図７のステップＳ１３において、文書属性テーブル７の新規エントリを磁気ディスク装置１３上の文書属性テーブル７の末尾に追記しておき、図１０の処理に先立って文書属性テーブル７のエントリを文書ＵＲＬ７１及び取得日時７２の順にソートして、入力側文書属性テーブルとする。同様に、部分文字列テーブル６のエントリも文書ＵＲＬ６２及び取得日時６３の順にソートしておく。

ステップＳ３１では、入力側文書属性テーブルのエントリを先頭から処理し、文書ＵＲＬ及び取得日時が一致するエントリが部分文字列テーブル６から読み込まれる限り、当該文書属性テーブルエントリの一意部分文字列数７４に１を加え、文書ＵＲＬ及び取得日時が一致しないエントリが部分文字列テーブル６から読み込まれた時点で該文書属性テーブルエントリを出力文書属性テーブルに追記する。

また、以上の説明においては、部分文字列をｋ個の単語の列としたが、形態素解析処理による単語分割を行なわず、部分文字列をｋ’個の文字の列としても良い。

以上のように、この発明の実施の形態１によれば、複数の文書に含まれる文字列から部分文字列を文書毎に生成し、文書毎に当該文書固有の一意部分文字列の割合を求め、一意部分文字列の割合が低いものを、他の１つ以上の文書の引用を中心とする有用性の低い文書として検出し、これらの文書を除去可能にすることにより、統計的な処理に適した文書集合を得ることができるという効果がある。

また、複数文書に出現する部分文字列を、最も古い取得日時の文書においては一意部分文字列として扱うことにより、引用元である可能性が高い文書を除去してしまうことを防ぐという効果がある。

さらに、一定割合までは他の文書と重複する部分文字列の存在を許すことにより、正当な引用を行なって固有の記述を加えている文書まで除去してしまうことを防ぐという効果がある。

実施の形態２．
以上の実施の形態１では、一意部分文字列の割合が低い文書を、他の１つ以上の文書の引用を中心とする有用性の低い文書として除去することにより、統計的な処理に適した文書集合を得ることができる文書処理装置を説明したが、次に、同一文書ＵＲＬからの文書の取得を繰り返す際に、統計的に有用な文書が得られない見込みが高い文書ＵＲＬを取得対象から取り除くことにより、不要な文書の取得を避け、外部サーバからの文書取得を効率化する文書処理装置に関する実施の形態２を示す。

図１１は、この発明の第２の実施の形態に係る文書処理装置の構成図である。
図１１において、文書処理装置１から不要文書検出手段１０までは、図１の同一番号の構成要素に対応するものであり、不要ＵＲＬ除去手段１４が、実施形態１に対して実施形態２で追加された部分である。不要ＵＲＬ除去手段１４は、不要文書除去手段３の動作に引き続いて動作する。

図１２は、不要ＵＲＬ除去手段１４の動作を示すフローチャートである。
不要ＵＲＬ除去手段１４は、文書属性テーブル７の全てのエントリに対して、同一文書ＵＲＬ７１を持つエントリ同士をまとめて順に処理する。

始めに、ステップＳ４１において、不要ＵＲＬ除去手段１４は、文書属性テーブル７の未処理文書ＵＲＬ７１を１つ選択し、当該文書ＵＲＬ７１に対応する全てのエントリを取得する。取得したエントリ数が所定値を超え、かつ取得したエントリ中で除去フラグ７５が１に設定されたエントリの割合（除去率）が所定値を超える場合、当該文書ＵＲＬからは重複文書しか得られない可能性が高いと考えられるため、当該文書ＵＲＬを文書ＵＲＬリスト４から削除し、次回以降は文書の取得を行なわないようにする。

続いて、ステップＳ４２において、不要ＵＲＬ除去手段１４は、文書属性テーブル７の全ての文書ＵＲＬが処理されたか判定し、処理済みでなければステップＳ４１に戻り、処理済みであれば終了する。

なお、ここでは、同一文書ＵＲＬの複数バージョンを対象に除去率を求めたが、ＵＲＬ中のホスト名毎、あるいは上位ドメイン名（例えば、ｈｔｔｐ：／／ｂｌｏｇ．ｆｏｏ．ｃｏｍ／をＵＲＬとした場合のｆｏｏ．ｃｏｍなど）毎に除去率を求め、重複文書が多く発生するＵＲＬ群を一括して文書ＵＲＬリスト４から除去するようにしても良い。

以上のように、この発明の実施の形態２によれば、同一文書ＵＲＬからの文書の取得を繰り返す際に、統計的に有用な文書が得られない見込みが高い文書ＵＲＬを取得対象から取り除くことにより、不要な文書の取得を避け、外部サーバからの文書取得を効率化することが可能になるという効果がある。

実施の形態３．
以上の実施の形態２では、統計的に有用な文書が得られない見込みが高い文書ＵＲＬを取得対象から取り除くことにより、不要な文書の取得を避け、外部サーバからの文書取得を効率化する文書処理装置を説明したが、次に、出現頻度の高い語句を不自然に多く含む文書を検出して、この文書を除去することにより、統計的な処理に適した文書集合を得ることができる文書処理装置に関する実施の形態３を示す。

図１３は、この発明の第３の実施の形態に係る文書処理装置の構成図である。
図１３において、文書処理装置１から不要文書検出手段１０までは、図１の同一番号の構成要素に対応するものであり、最長頻出部分文字列テーブル１５が、実施形態１に対して実施形態３で追加された部分である。

まず、最長頻出部分文字列テーブル１５の格納形式について、詳細に説明する。部分文字列テーブル６においては、固定単語数ｋ個の単語の列を部分文字列としたが、最長頻出部分文字列テーブル１５には、１つの単語からＱ個の単語の列までの部分文字列が含まれる（例えばＱ＝１０）。ここで、取得文書データ５の文書内容５３に含まれる部分文字列の内、所定数以上（例えば５００以上）の文書に出現する部分文字列を、頻出部分文字列と定義すれば、最長頻出部分文字列テーブル１５は、頻出部分文字列の内、最長の頻出部分文字列を格納するテーブルである。

上記の最長の頻出部分文字列を、以下では、最長頻出ｑ単語列（ｑは単語の数）と表現する。最長頻出ｑ単語列は、所定数以上の文書に出現するｑ個の単語の列（ｑ単語列）であって、かつ当該ｑ単語列を含む最長頻出ｑ＋１単語列が存在しないものを指す。

このような最長頻出部分文字列テーブル１５を生成するためには、最長頻出部分文字列の候補をｑ単語列として格納する頻出ｑ単語列テーブルを利用する。
図１４は、ｑ＝３の場合のｑ単語列を格納する頻出ｑ単語列テーブル９０を示したものである。
頻出ｑ単語列テーブル９０は、単語列９１と出現回数９２からなる。頻出ｑ単語列テーブル９０はＲＡＭ１２上に配置され、単語列９１を一意なキーとして検索可能な構造を有する。出現回数９２は、対応する単語列９１が出現する文書の数を保持する。

次に、最長頻出部分文字列テーブル１５を用いた不要文書除去手段３の動作を、フローチャートを用いて説明する。
図１５は、不要文書除去手段３の動作の内、実施の形態１に対して実施の形態３で加わった部分を示すフローチャートである。
ステップＳ３からステップＳ５は、図６のステップＳ１及びステップＳ２に引き続いて実行する。

まず、ステップＳ３において、不要文書除去手段３は、不要文書検出手段１０により、後述する処理に従って、ｑ＝１、２、３、．．．、Ｑの順に、取得文書データ５の文書内容５３に含まれるｑ単語列（ｑ＝１の場合は単語）の出現文書数を求め、所定数以上の文書に出現したｑ単語列を、頻出ｑ単語列テーブル９０に格納する。

続いて、ステップＳ４において、不要文書検出手段１０は、ｑ＝Ｑ、Ｑ−１、．．．、２、１の順に、頻出ｑ単語列テーブルの各エントリのｑ単語列に含まれる部分文字列群、すなわちｑ−１単語列、ｑ−２単語列、．．．、単語に対して、対応する頻出単語列テーブルのエントリを削除する。各頻出ｑ単語列に残ったエントリは最長頻出ｑ単語列であり、これらを最長頻出部分文字列テーブルとする。

最後に、ステップＳ５において、不要文書検出手段１０は、ステップＳ４で生成された最長頻出部分文字列テーブルを参照して、取得文書データ５の文章内容５３に同時に含まれる最長頻出部分文字列の種類を求め、所定種類以上（例えば７種類以上）の最長頻出部分文字列を含む文書に対応する文書属性テーブル７のエントリについて、除去フラグ７５を１に設定する。

次に、図１５のステップＳ３の動作について、フローチャートを用いて説明する。
図１６は、ステップＳ３の動作の内、特定のｑ（ｑ＞１）に対応する動作の詳細を示すフローチャートである。

始めに、ステップＳ５１において、不要文書除去手段３は、取得文書データ５の内、未処理の文書ｄを選択し、文書内容５３を構成する単語の列Ｗ１、Ｗ２、．．．、Ｗｎｄを得る。この処理は、図７のステップＳ１２と同じ形態素解析処理を繰り返すか、ステップＳ１２の以前の実行結果を保存しておいて再利用することで実現できる。

次に、ステップＳ５２において、不要文書検出手段１０は、前記単語列の内、未処理のｑ単語列（Ｗｉ、Ｗｉ＋１、．．．、Ｗｉ＋ｑ−１）を処理対象として取り上げる。

次に、ステップＳ５３において、不要文書検出手段１０は、ｑ個の単語Ｗｊ（ｊ＝ｉ、ｉ＋１、．．．、ｉ＋ｑ−１）が全て頻出単語テーブル（頻出１単語列テーブル）９０に存在するかどうか判定する。存在する場合は、ステップＳ５４に進み、そうでない場合は、当該ｑ単語列が頻出となることはあり得ないため、ステップＳ５６まで処理をスキップする。

続いて、ステップＳ５４において、不要文書検出手段１０は、ｑ個の単語列の右端を除いたｑ−１単語列（Ｗｉ、Ｗｉ＋１、．．．、Ｗｉ＋ｑ−２）と、左端を除いたｑ−１単語列（Ｗｉ＋１、．．．、Ｗｉ＋ｑ−１）のいずれもが頻出ｑ−１単語列テーブル９０に存在しているかどうか判定する。存在する場合は、ステップＳ５５に進み、そうでない場合は、当該ｑ単語列が頻出となることはあり得ないため、ステップＳ５６まで処理をスキップする。

次に、ステップＳ５５において、不要文書検出手段１０は、当該ｑ単語列（Ｗｉ、Ｗｉ＋１、．．．、Ｗｉ＋ｑ−１）に対応する頻出ｑ単語列テーブルのエントリにおいて、出現回数９２に１を加える。

次に、ステップＳ５６において、不要文書検出手段１０は、文書ｄの全てのｑ単語列が全て処理されたか判定し、処理されていれば、ステップＳ５７に進み、そうでなければ、ステップＳ５２に戻って処理を繰り返す。

続いて、ステップＳ５７において、不要文書検出手段１０は、取得文書データ７の全ての文書が全て処理されたか判定し、処理されていれば、ステップＳ５８に進み、そうでなければ、ステップＳ５１に戻って処理を繰り返す。

最後に、ステップＳ５８において、不要文書検出手段１０は、頻出ｑ単語列テーブル９０の各エントリを順に調べ、出現回数９２が所定値未満のエントリを削除する。削除されずに残ったエントリが頻出ｑ単語列である。

以上のように、この発明の実施の形態３によれば、出現頻度の高い語句を不自然に多く含む文書を検出して、この文書を除去することにより、統計的な処理に適した文書集合を得ることができるという効果がある。

また、スパムブログを自動生成する作者は、インターネット上で公開されている検索エンジンの検索問合せランキングなどを用いると、こうした出現頻度の高い語句を話題語として容易に捉えることができるので、検索エンジンユーザに検索され易いＷｅｂページを自動生成するために、このような話題語を、そのＷｅｂページに設定される検索対象キーワードとして利用することがある。この場合、Ｗｅｂページの文章の方には、他の文書を自動引用する代わりにランダムな文字列を用いることがある。このような場合に対しても、この発明の実施の形態３によれば、検索対象キーワードとして設定されている頻出語（話題語）を手掛かりに、上記のような自動生成文書を除去することが可能になる。

１ 文書処理装置、２ 文書取得手段、３ 不要文書除去手段、４ 文書ＵＲＬリスト、５ 取得文書データ、６ 部分文字列テーブル、７ 文書属性テーブル、８ 部分文字列生成手段、９ 一意部分文字列判定手段、１０ 不要文書検出手段、１１ ＣＰＵ、１２ ＲＡＭ、１３ 磁気ディスク装置、１４ 不要ＵＲＬ除去手段、１５ 最長頻出部分文字列テーブル。

Claims (11)

1. 複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、
   前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、
   文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段と
   を備える文書処理装置。
2. 前記部分文字列生成手段により生成された前記部分文字列と、この部分文字列が最初に生成された文書の識別情報と、前記部分文字列が異なる文書間で重複しているか否かを示す重複フラグとを対応付けて記憶する部分文字列テーブルを備え、
   前記一意部分文字列判定手段は、前記部分文字列テーブルに記憶された前記重複フラグが重複していることを示す場合、前記最初に生成された文書においては当該部分文字列を一意部分文字列として判定し、それ以外の文書においては一意部分文字列としないと判定する請求項１記載の文書処理装置。
3. ＵＲＬ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｌｏｃａｔｏｒ）で指定される外部サーバ上の文書をネットワーク経由で取得し、前記ＵＲＬと取得日時と共に前記取得文書データに格納する文書取得手段と、
   前記部分文字列生成手段により生成された前記部分文字列と、この部分文字列を含む文書の内、前記取得日時が最も古い文書の前記ＵＲＬと、前記取得日時と、前記部分文字列が異なる文書間で重複しているか否かを示す重複フラグとを対応付けて記憶する部分文字列テーブルとを備え、
   前記一意部分文字列判定手段は、前記部分文字列テーブルに記憶された前記重複フラグが重複していることを示す場合、前記取得日時が最も古い文書においては当該部分文字列を一意部分文字列として判定し、それ以外の文書においては一意部分文字列としないと判定する請求項１記載の文書処理装置。
4. 前記文書取得手段により文書を取得する前記ＵＲＬを取得対象ＵＲＬとして格納する文書ＵＲＬリストを備え、
   前記不要文書検出手段により検出した前記不要文書の前記ＵＲＬに基づいて、前記文書ＵＲＬリストに格納された前記取得対象ＵＲＬの削除を行なう不要ＵＲＬ除去手段を備えた請求項３記載の文書処理装置。
5. 前記不要ＵＲＬ除去手段は、前記不要文書検出手段により検出した前記不要文書が、所定数以上の取得日時において繰り返して不要文書として検出されている場合、この不要文書のＵＲＬを前記文書ＵＲＬリストに格納された前記取得対象ＵＲＬから削除する請求項４記載の文書処理装置。
6. 前記不要ＵＲＬ除去手段は、前記不要文書検出手段により検出した前記不要文書の前記ＵＲＬのホスト名または上位ドメイン名が一致するＵＲＬを持つ文書の内、所定割合以上が不要文書として検出されている場合、このホスト名または上位ドメイン名が一致する全てのＵＲＬを前記文書ＵＲＬリストに格納された前記取得対象ＵＲＬから削除する請求項４記載の文書処理装置。
7. 前記部分文字列生成手段は、前記部分文字列テーブルをＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）に記憶させ、前記部分文字列テーブルが前記ＲＡＭの容量に応じた所定の容量に達すると前記ＲＡＭに記憶された前記部分文字列テーブルの断片を磁気ディスク装置に書き出して前記ＲＡＭに記憶された前記部分文字列テーブルを空にし、前記取得文書データの全てについて前記不要文書の検出を行なった後に、前記ＲＡＭ及び前記磁気ディスク装置に記憶された前記部分文字列テーブルの断片を部分文字列に基づいて統合する請求項２から６のいずれかに記載の文書処理装置。
8. 前記不要文書検出手段は、所定の長さ以内の部分文字列の出現文書数に基づき、所定数以上の文書に出現する頻出部分文字列の内、より長い頻出部分文字列に含まれない最長の頻出部分文字列である最長頻出部分文字列を求め、この最長頻出部分文字列を所定種類以上含む文書を不要文書として検出する請求項１から７のいずれかに記載の文書処理装置。
9. 部分文字列生成手段が、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成ステップと、
   一意部分文字列判定手段が、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定ステップと、
   不要文書検出手段が、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出ステップとを備える文書処理方法。
10. コンピュータを、
    複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、
    前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、
    文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させるための文書処理プログラム。
11. コンピュータを、
    複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、
    前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、
    文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させるための文書処理プログラムを記録したコンピュータ読み取り可能な記録媒体。

Images