文書処理装置、文書処理方法、文書処理プログラム、及び文書処理プログラムを記録したコンピュータ読み取り可能な記録媒体
【課題】 インターネット上の文書から、正当な引用を行なっている文書を含めたオリジナルな文書の抽出を可能にする。
【解決手段】 複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段とを備える。
【解決手段】 複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段とを備える。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、インターネット上に存在する文書、例えば、ブログ等の文書から、分析対象とする目的の文書を抽出する文書処理装置に関する。
【背景技術】
【0002】
インターネットの発展により、入手可能な文書データの量は、飛躍的に増大した。これらの文書データの中には、ブログ等を通じて、個人が自発的に興味の対象や、社会事象に対する意見等を述べたものも数多く含まれるようになった。そこで、このような意見等を述べた文書データを収集して分析することにより、従来は、回答者を募集してアンケートを実施する必要があった社会風潮や消費者動向の把握が、網羅的、かつリアルタイムに実施可能になると期待されている。
一方、ディジタルデータは、入手が容易であると同時に、引用・編集・改変して再発信することも容易であり、インターネット上の文書には、こうした二次情報も多く含まれていると言われている。オリジナルな一次情報とその流用による二次情報が混在していると、同様なデータが重複して格納されることによる記憶効率の低下や、検索問い合わせに対して同様な結果が繰り返し提示されることによる一覧性の低下といった問題が生じる。そこで、各文書データから部分文字列を取り出し、部分文字列毎に出現文書の一覧を管理することで、重複部分を含む文書の提示を可能にするシステムが提案されている(例えば、特許文献1及び2参照)。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2008−33728号公報
【特許文献2】特表2008−511081号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
ブログ等の中には、記事本体よりも、記事に付随する広告の発信を主眼としたものも存在する。このような広告記事の作成者は、なるべく労力をかけずに記事を作成するために、他のブログ記事を取得して引用するコンピュータプログラムを利用して、広告記事を自動生成することが多い。スパムブログと呼ばれるこのようなブログ記事が大量に存在すると、前述の社会風潮や消費者動向の把握を目的として、全文書データの統計処理を行なった際に、自動引用された情報の出現頻度が増加し、現実において話題とされる頻度の実態と大きく乖離してしまうという問題が生じる。
【0005】
従来の文書処理装置においては、例えば、特許文献1では、重複の可能性のある文書の検出に止まっており、文書の削除などの最終的な処置は、文書処理装置の利用者が文書の内容を判断した上で実施する必要がある。なぜなら、ブログにおいては、ニュース記事などの一次情報に対する所感を述べる際に、正当な引用が行なわれることもあるため、重複が検出された文書を全て一律に削除するのは不適当であり、利用者が一つ一つの記事を精査しなくてはならないからである。特許文献1の技術は、データベースを管理する際に意図せずに生じてしまう重複の検出を目的としており、他者により意図的にデータが引用・複製される状況には対処することができない。
【0006】
また、特許文献2はインターネット上の文書を想定したものであるが、2つの文書の組に対して、文書単位での重複の有無を判定する技術である。このため、文書集合から2つ以上の文書の一部を切り出して合成された文書に対しては、切り出された文書の一部を単位として重複の検出を行なうことができず、このような合成された文書を排除することができない。
【0007】
この発明は、上記のような課題を解決するためになされたもので、文書集合に対し、他の文書にも出現する部分文字列を一定割合以上含む文書を、自動引用により生成された文書として排除することで、正当な引用を行なっている文書を含めたオリジナルな文書データの抽出を可能にするものである。
【課題を解決するための手段】
【0008】
上記で述べた課題を解決するため、本発明に係る文書処理装置は、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段とを備えることとしたものである。
【0009】
また、本発明に係る文書処理方法は、部分文字列生成手段が、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成ステップと、一意部分文字列判定手段が、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定ステップと、不要文書検出手段が、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出ステップとを備えることとしたものである。
【0010】
また、本発明に係る文書処理プログラムは、コンピュータを、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させることとしたものである。
【0011】
また、本発明に係る文書処理プログラムを記録したコンピュータ読み取り可能な記録媒体は、コンピュータを、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させる文書処理プログラムを記録させることとしたものである。
【発明の効果】
【0012】
本発明によれば、複数の文書に含まれる文字列から部分文字列を文書毎に生成し、文書毎に当該文書固有の一意部分文字列の割合を求め、一意部分文字列の割合が低いものを、他の1つ以上の文書の引用を中心とする有用性の低い文書として検出し、これらの文書を除去可能にすることにより、統計的な処理に適した文書集合を得ることができるという効果がある。
【図面の簡単な説明】
【0013】
【図1】この発明の実施の形態1に係る文書処理装置の一例を示す構成図である。
【図2】取得文書データ5の詳細な格納形式の一例を示す図である。
【図3】部分文字列テーブル6の詳細な格納形式を示す図である。
【図4】文書属性テーブル7の詳細な格納形式を示す図である。
【図5】部分文字列テーブル6のコンピュータシステムにおける格納方法の詳細を説明する図である。
【図6】不要文書除去手段3の動作を示す概略フローチャートである。
【図7】ステップS1の詳細を示すフローチャートである。
【図8】ステップS16の動作の詳細を示すフローチャートである。
【図9】ステップS19の動作の詳細を示すフローチャートである。
【図10】ステップS2の詳細を示すフローチャートである。
【図11】この発明の第2の実施の形態に係る文書処理装置の構成図である。
【図12】不要URL除去手段14の動作を示すフローチャートである。
【図13】この発明の第3の実施の形態に係る文書処理装置の構成図である。
【図14】q=3の場合のq単語列を格納する頻出q単語列テーブル90を示したものである。
【図15】不要文書除去手段3の動作の内、実施の形態1に対して実施の形態3で加わった部分を示すフローチャートである。
【図16】ステップS3の動作の内、特定のq(q>1)に対応する動作の詳細を示すフローチャートである。
【発明を実施するための形態】
【0014】
実施の形態1.
図1は、この発明の実施の形態1に係る文書処理装置の一例を示す構成図である。
図1において、文書処理装置1は、サーバA〜C等の外部サーバ上の文書を取得する文書取得手段2と、不要文書を除去する不要文書除去手段3とを備え、文書URLリスト4、取得文書データ5、部分文字列テーブル6、及び文書属性テーブル7によって構成される。不要文書除去手段3は、文書中の文字列から部分文字列を生成する部分文字列生成手段8と、生成された部分文字列の内、他の文書には出現せずに一意に定まる部分文字列(一意部分文字列)を判定する一意部分文字列判定手段9と、一意部分文字列数と総部分文字列数との比により、不要文書を検出する不要文書検出手段10とを備える。文書URLリスト4は、文書取得手段2が取得すべき外部サーバ上の文書を特定するアドレス、例えば、URL(Uniform Resource Locator)の一覧を保持する。取得文書データ5は、文書取得手段2が取得した複数の文書データを格納する。部分文字列テーブル6は、不要文書除去手段3による処理の中間状態を格納する。文書属性テーブル7は、不要文書除去手段3による処理結果を格納する。
【0015】
文書処理装置1は、CPU、RAM、磁気ディスク装置、及びネットワークインタフェース等のハードウェアと、ハードウェアを制御するオペレーティングシステムソフトウェアを備える一般的なコンピュータシステムと、CPUの動作を規定するプログラムを用いて実現することができる。この場合、文書取得手段2と不要文書除去手段3とは、磁気ディスク装置からRAMに読み込まれてCPUにより実行されるプログラムとして実現され、文書URLリスト4、取得文書データ5、部分文字列テーブル6、及び文書属性テーブル7は、RAM、または、磁気ディスク装置上の固有の格納領域として実現される。
【0016】
図2は、取得文書データ5の詳細な格納形式の一例を示す図である。
取得文書データ5は、複数のエントリからなり、各エントリは、1つの文書の文書URL51、取得日時52、及び文書内容53を格納する。文書URL51は、文書URLリスト4に記憶されていた取得対象文書のアドレスの1つであり、取得日時52は、文書取得手段2が実際に当該文書データを取得した日時である。また、文書内容53は、文書取得手段2が取得した文書の内容データである。ここで、外部サーバ上の文書のアドレスは、文書URL51により一意に識別されるが、同一の文書URL51から異なる時点で取得した文書内容は異なることもあり得る。そのため、取得文書データ5においては、文書URL51が共通で、取得日時52が異なる複数のエントリが存在しても良い。また、取得文書データ5における各エントリの格納位置には特段の制約を設けず、任意とする。
【0017】
図3は、部分文字列テーブル6の詳細な格納形式を示す図である。
部分文字列テーブル6は、複数のエントリからなり、各エントリは、1つの部分文字列に関するハッシュ値61、文書URL62、取得日時63、及び重複フラグ64を格納する。ここでいう部分文字列とは、図2に示す取得文書データ5の文書内容53から取り出した固定単語数の文字列である。ここでは、単語の数をkとする(例えばk=5)。
【0018】
ハッシュ値61には、当該エントリに対応する部分文字列に対し、CRC(Cyclic Redundancy Code)やSHA‐256(Secure Hash Algorithm 256‐bit)などの公知の一方向性ハッシュ関数により計算したハッシュ値を格納する。このようなハッシュ値は、実用上、元の部分文字列と1対1に対応すると考えることができるので、部分文字列テーブル6のエントリを一意に識別するキーとして用いる。
【0019】
ここで、ハッシュ値61の一意性を維持するため、部分文字列テーブル6における各エントリの格納位置は、ハッシュ値61に基づいて一意に定まる必要がある。しかし、同一の部分文字列であっても、取得文書データ5には、文書URL51や取得日時52が異なる複数のエントリが存在するため、文書URL62及び取得日時63の組み合わせが一意に定まらない。そこで、部分文字列テーブル6の各エントリに重複フラグ64を設け、次のようにして、部分文字列テーブル6における各エントリの一意性を維持する。
【0020】
文書URL62及び取得日時63には、当該エントリに対応する部分文字列が取り出された取得文書データ5のエントリの文書URL52及び取得日時53の組み合わせを、1つ指定する。指定する文書URL52及び取得日時53の組み合わせは、当該エントリに対応する部分文字列を含む文書の内、取得日時が最も古い文書の文書URL52と取得日時53を用いるものとする。あるいは、文書取得手段2によらずに収集された文書集合を分析対象にする場合は、文書URL52と取得日時53の代わりに、当該エントリに対応する部分文字列が最初に生成された文書の識別情報と、文書が作成・更新された日時を用いるものとする。
【0021】
重複フラグ64には、当該エントリに対応する部分文字列が、文書URL62及び取得日時63の組み合わせで指定される文書だけに含まれる場合に、例えば、0が格納され、そうでない場合には、1が格納される。
【0022】
図4は、文書属性テーブル7の詳細な格納形式を示す図である。
文書属性テーブル7は、複数のエントリからなり、各エントリは、1つの文書の文書URL71、取得日時72、部分文字列数73、一意部分文字列数74、及び除去フラグ75を格納する。文書属性テーブル7の各エントリは、取得文書データ5のエントリと1対1に対応しており、文書URL71及び取得日時72は、それぞれ取得文書データ5の文書URL51及び取得日時52に対応する。文書属性テーブル7の各エントリの格納位置は、文書URL71及び取得日時72により一意に定まる必要がある。また、部分文字列数73は、当該エントリに対応する取得文書データ5の文書内容53に含まれる部分文字列の総数を表し、一意部分文字列数74は、当該部分文字列の内、他のエントリの文書内容53に含まれない部分文字列の数を表す。除去フラグ75には、当該エントリに対応する文書が自動引用により生成されたものであり、不要とみなされる場合に、1が格納され、そうでない場合に、0が格納される。
【0023】
図5は、部分文字列テーブル6のコンピュータシステムにおける格納方法の詳細を説明する図である。
図5において、文書処理装置1は、CPU11、RAM12、磁気ディスク装置13により構成されるコンピュータシステムとして示されている。
【0024】
部分文字列テーブル6は、ハッシュ値61に基づいてランダムにアクセスされるため、RAM12に格納することが望ましいが、部分文字列テーブル6のエントリ数、すなわち部分文字列の種類は非常に多く、RAM12に部分文字列テーブル6の全体を格納するだけの容量がない場合が生じる。そこで、部分文字列テーブル6を複数の断片に分割し、RAM12に格納される部分文字列テーブル片(0)と、必要に応じて磁気ディスク装置13に格納される部分文字列テーブル片(1)、部分文字列テーブル片(2)、部分文字列テーブル片(3)、...を設ける。RAM12上の部分文字列テーブル片(0)は、ハッシュ値61をキーとする赤黒木や、ハッシュテーブル等の公知の探索構造により実現する。また、磁気ディスク装置13上の部分文字列テーブル片(j)(j=1,2,...)においては、各エントリをハッシュ値61の順に配置するものとする。
【0025】
また、文書属性テーブル7は、文書URL71及び取得日時72に基づいてランダムにアクセスされるが、多くの場合、RAM12に格納可能と想定されるため、文書URL71及び取得日時72をキーとするRAM12上の赤黒木や、ハッシュテーブルとして実現し、処理終了時に磁気ディスク装置13に内容を書き出せば良い。
【0026】
取得文書データ5は、各エントリの書き込みと読み出しが一度ずつ行なわれるだけであり、容量も大きいため、磁気ディスク装置13上に格納する。
【0027】
次に、文書処理装置1の動作を説明する。
文書取得手段2は、文書URLリスト4から文書URLを読み込み、当該URL中のサーバ名に従って外部サーバへの接続を行ない、公知のHTTP(Hyper‐Text Transfer Protocol)に従って当該URLを送付して文書データを要求する。次いで文書取得手段2は、当該外部サーバからの応答を受信し、前記URLを文書URL51、現在時刻を取得日時52、受信内容を文書内容53として取得文書データ5の末尾に追記する。この処理を文書URLリスト4の全てのURLに対して繰り返す。各文書の取得は逐次に行なう必要はなく、複数文書を同時に並行して取得して所要時間を短縮しても良い。
【0028】
次に、不要文書除去手段3の動作を、フローチャートを用いて説明する。
図6は、不要文書除去手段3の動作を示す概略フローチャートである。
始めに、ステップS1において、不要文書除去手段3は、取得文書データ5に格納された全てのエントリを処理し、部分文字列テーブル6及び文書属性テーブル7の設定を行なう。
次に、ステップS2で、不要文書除去手段3は、部分文字列テーブル6の各エントリに基づいて文書属性テーブル7を更新し、各文書に対する最終的な処理結果を格納する。
【0029】
以下、図6のステップS1における動作の詳細を、フローチャートを用いて説明する。
図7は、ステップS1の詳細を示すフローチャートである。
【0030】
始めに、ステップS11において、不要文書除去手段3は、部分文字列生成手段8により、磁気ディスク装置13上の部分文字列テーブル片の数を表す変数fを0に初期化する。
【0031】
次に、ステップS12において、部分文字列生成手段8は、取得文書データ5から未処理エントリを1つ選択して処理対象とし、その文書内容53に公知の形態素解析処理を施して、単一文字列を複数の単語列に分割する。ここで、当該エントリの文書URL51と取得日時52の組で識別される文書データをdとし、文書dの文書内容53を形態素解析して得られる単語列の要素数をnd、単語列をW1、W2、...、Wndとする。なお、取得文書データ5の各エントリの処理順序は任意であり、例えば、先頭エントリから順に処理対象とすれば良い。
【0032】
次に、ステップS13において、部分文字列生成手段8は、文書dの文書URL51と取得日時52に対応する文書属性テーブル7のエントリを生成し、文書URL71と取得日時72をそれぞれ文書URL51と取得日時52に、部分文字列数73をnd−k+1(kは部分文字列の単語数)に、一意部分文字列数74を0に、除去フラグを1に、それぞれ設定する。
【0033】
次に、ステップS14において、部分文字列生成手段8は、文書dにおける部分文字列を識別する変数iを0に設定し、続くステップS15で変数iに1を加える。
【0034】
次に、ステップS16において、部分文字列生成手段8は、後述する手順により、文書dの形態素解析結果の単語列の内、i番目以降の連続するk個の単語列(Wi、Wi+1、...、Wi+k−1)からなる第i部分文字列のハッシュ値Siに基づき、部分文字列テーブル片の更新を行なう。
ステップS17では、変数iをnd−k+1と比較し、両者が等しければステップS18に進み、そうでなければステップS15に戻る。
【0035】
次に、ステップS18において、部分文字列生成手段8は、取得文書データ5の全てのエントリが処理されたかどうか判定し、未処理のエントリが残っていればステップS12に戻り、全て処理されていればステップS19に進む。
【0036】
最後に、ステップS19において、部分文字列生成手段8は、後述する手順により、f+1個の部分文字列テーブル片を統合し、単一の部分文字列テーブル6を生成して処理を終了する。
【0037】
次に、図7のステップS16における動作の詳細を、フローチャートを用いて説明する。
図8は、ステップS16の動作の詳細を示すフローチャートである。
始めに、ステップS101において、部分文字列生成手段8は、第i部分文字列(Wi、Wi+1、...、Wi+k−1)のハッシュ値Siを計算する。
【0038】
次に、ステップS102において、部分文字列生成手段8は、部分文字列テーブル片(0)を検索し、ハッシュ値61がSiと等しいエントリが存在するかどうか判定する。エントリが存在する場合はステップS107に進み、そうでない場合はステップS103に進む。
【0039】
次に、ステップS103において、部分文字列生成手段8は、部分文字列テーブル片(0)の現在のエントリ数を調べ、その値が所定値未満であるかどうか判定する。所定値未満である場合は、ステップS106に進み、そうでない場合は、ステップS104に進む。ここで、所定値とは、例えば、RAM12の容量に格納可能な部分文字列テーブル片(0)のエントリ数の上限値を意味するものとする。
【0040】
次に、ステップS104において、部分文字列生成手段8は、部分文字列テーブル片(0)に新たなエントリを生成できないため、RAM12上の部分文字列テーブル片(0)を磁気ディスク装置13上の新たな部分文字列テーブル片(f+1)に書き出し、部分文字列テーブル片(0)を空にする処理を行なう。この時、部分文字列テーブル片(0)のエントリをハッシュ値61の順に出力するようにする。部分文字列テーブル片(0)を木構造として実現していればこれは容易であり、部分文字列テーブル片(0)をハッシュテーブルとして実現している場合は、全エントリのソート処理を行なえば良い。
【0041】
続いて、ステップS105で、部分文字列生成手段8は、磁気ディスク装置13上の部分文字列テーブル片の数を表す変数fに1を加える。
【0042】
次に、ステップS106において、部分文字列生成手段8は、部分文字列テーブル片(0)に新たなエントリを割り当て、当該エントリのハッシュ値61をSiに、文書URL62及び取得日時63を現在処理中の文書dに対応する文書URL51及び取得日時52に、重複フラグ64を0に設定し、処理を終了する。
【0043】
一方、ステップS107においては、不要文書除去手段3は、一意部分文字列判定手段9により、部分文字列テーブル片(0)上の既存のエントリの文書URL62及び取得日時63を調べ、文書dの文書URL51及び取得日時52とそれぞれ一致するかどうか判定する。一致する場合は、同一文書内に部分文字列が複数回含まれていることを示しており、文書間の引用を示唆しないので、処理を終了する。そうでない場合は、ステップS108に進む。
【0044】
次に、ステップS108において、一意部分文字列判定手段9は、前記既存エントリの重複フラグを1に設定し、当該部分文字列が複数文書に重複して存在することを記録する。
【0045】
続いて、ステップS109において、一意部分文字列判定手段9は、当該既存エントリの取得日時63が文書dの取得日時52より新しいかどうか判定し、新しければステップS110に進み、そうでなければ処理を終了する。
【0046】
最後に、ステップS110において、一意部分文字列判定手段9は、当該既存エントリの文書URL62及び取得日時63を、文書dの文書URL51及び取得日時52にそれぞれ設定し、処理を終了する。
【0047】
次に、図7のステップS19の動作の詳細を、フローチャートを用いて説明する。
図9は、ステップS19の動作の詳細を示すフローチャートである。
始めに、ステップS21において、不要文書除去手段3は、部分文字列生成手段8により、統合対象の部分文字列テーブル片のそれぞれの先頭エントリを調べ、ハッシュ値の最小値を求める。次に、先頭エントリのハッシュ値が最小値である部分文字列テーブル片の全てから先頭エントリを取得し、当該部分文字列テーブル片から先頭エントリを除去する。
【0048】
次に、ステップS22において、部分文字列生成手段8は、取得したエントリが単一であったかどうか判定し、単一であればステップS26に進み、そうでなければステップS23に進む。
【0049】
次に、ステップS23において、不要文書除去手段3は、一意部分文字列判定手段9により、取得した複数エントリにおいて、文書URL62と取得日時63が全て同一かどうか判定し、同一であればステップS25に進み、そうでなければステップS24に進む。
【0050】
次に、ステップS24において、一意部分文字列判定手段9は、同一ハッシュ値に対して複数文書が対応していることが明らかであるため、重複フラグ64を1とし、ハッシュ値61、文書URL62、及び取得日時63のそれぞれを、取得したエントリ中で取得日時63が最小のエントリのハッシュ値61、文書URL62、及び取得日時63に設定して出力し、ステップS27に進む。
ければステップS24に進む。
【0051】
一方、ステップS25では、一意部分文字列判定手段9は、取得したエントリは全て同一文書に対応しているため、取得エントリ中で重複フラグ64が1になっているものが存在する場合は重複フラグ64を1に、そうでない場合は重複フラグ64を0とし、ハッシュ値61、文書URL62、及び取得日時63のそれぞれを、取得した任意エントリのハッシュ値61、文書URL62、及び取得日時63に設定して出力し、ステップS27に進む。
【0052】
また、ステップS26では、部分文字列生成手段8は、取得した単一のエントリ自体の内容を出力し、ステップS27に進む。
【0053】
最後に、ステップS27において、部分文字列生成手段8は、統合対象の部分文字列テーブル片が全て空になったか判定し、空であれば処理を終了し、そうでなければステップS21に戻って処理を繰り返す。
【0054】
なお、図9の処理は、部分文字列テーブル片の数(f)が非常に大きい場合、所定数(例えば16個)の部分文字列テーブル片を中間的な部分文字列テーブル片に統合し、次に中間的な部分文字列テーブル片の統合を行なうというように、次第に部分文字列テーブル片の数を減少させるようにして適用することもできる。これにより、磁気ディスク装置13に対する入出力性能の低下を抑えることが可能となる。
以上が、図6のステップS1の詳細な動作の説明である。
【0055】
次に、図6のステップS2の詳細な動作を、フローチャートを用いて説明する。
図10は、ステップS2の詳細を示すフローチャートである。
【0056】
まず、ステップS31からステップS32を繰り返すことで、部分文字列テーブル6の全てのエントリを順に処理する。
始めに、ステップS31において、不要文書除去手段3は、不要文書検出手段10により、部分文字列テーブル6の未処理エントリの1つを処理対象として選択し、当該エントリの文書URL62及び取得日時63で指定される文書属性テーブル7のエントリに対し、一意部分文字列数74に1を加える。ここで、当該エントリの重複フラグに1が設定されている場合であっても、重複文書中で最も古い取得日時を持つ文書においては当該エントリに対応する部分文字列を一意部分文字列として扱う。これは、重複文書を全て除去対象とすると引用元文書も除去され、当該文書の内容が存在しなかったものとみなされてしまうためである。
【0057】
なお、文書取得手段2によらずに収集された文書集合を分析対象にする場合は、上記の取得日時の情報を持たないため、文書が作成・更新された日時に基づいて、重複文書中で、重複する部分文字列が最初に生成された文書において当該エントリに対応する部分文字列を一意部分文字列として扱っても良い。
【0058】
次に、ステップS32において、不要文書検出手段10は、未処理のエントリの有無を調べ、部分文字列テーブル6の全てのエントリを処理した場合はステップS33に進み、そうでない場合はステップS31に戻る。
【0059】
続いて、ステップS33からステップS34を繰り返すことで、文書属性テーブル7の全てのエントリを順に処理する。
始めに、ステップS33において、不要文書検出手段10は、文書属性テーブル7の未処理エントリの1つを処理対象として選択し、部分文字列数73に対する一意部分文字列数74の割合が所定値以上(例えば60%以上)であれば、当該エントリの除去フラグ75を0に設定する。
【0060】
次に、ステップS34において、不要文書検出手段10は、未処理のエントリの有無を調べ、文書属性テーブル7の全てのエントリを処理した場合は処理を終了し、そうでない場合はステップS33に戻る。
【0061】
なお、以上の説明においては、文書属性テーブル7はRAM12上に存在し、効率的にランダムアクセスできるものと想定したが、文書属性テーブル7のデータ量がRAM12の容量を上回る場合には、次のようにすれば良い。すなわち、図7のステップS13において、文書属性テーブル7の新規エントリを磁気ディスク装置13上の文書属性テーブル7の末尾に追記しておき、図10の処理に先立って文書属性テーブル7のエントリを文書URL71及び取得日時72の順にソートして、入力側文書属性テーブルとする。同様に、部分文字列テーブル6のエントリも文書URL62及び取得日時63の順にソートしておく。
【0062】
ステップS31では、入力側文書属性テーブルのエントリを先頭から処理し、文書URL及び取得日時が一致するエントリが部分文字列テーブル6から読み込まれる限り、当該文書属性テーブルエントリの一意部分文字列数74に1を加え、文書URL及び取得日時が一致しないエントリが部分文字列テーブル6から読み込まれた時点で該文書属性テーブルエントリを出力文書属性テーブルに追記する。
【0063】
また、以上の説明においては、部分文字列をk個の単語の列としたが、形態素解析処理による単語分割を行なわず、部分文字列をk’個の文字の列としても良い。
【0064】
以上のように、この発明の実施の形態1によれば、複数の文書に含まれる文字列から部分文字列を文書毎に生成し、文書毎に当該文書固有の一意部分文字列の割合を求め、一意部分文字列の割合が低いものを、他の1つ以上の文書の引用を中心とする有用性の低い文書として検出し、これらの文書を除去可能にすることにより、統計的な処理に適した文書集合を得ることができるという効果がある。
【0065】
また、複数文書に出現する部分文字列を、最も古い取得日時の文書においては一意部分文字列として扱うことにより、引用元である可能性が高い文書を除去してしまうことを防ぐという効果がある。
【0066】
さらに、一定割合までは他の文書と重複する部分文字列の存在を許すことにより、正当な引用を行なって固有の記述を加えている文書まで除去してしまうことを防ぐという効果がある。
【0067】
実施の形態2.
以上の実施の形態1では、一意部分文字列の割合が低い文書を、他の1つ以上の文書の引用を中心とする有用性の低い文書として除去することにより、統計的な処理に適した文書集合を得ることができる文書処理装置を説明したが、次に、同一文書URLからの文書の取得を繰り返す際に、統計的に有用な文書が得られない見込みが高い文書URLを取得対象から取り除くことにより、不要な文書の取得を避け、外部サーバからの文書取得を効率化する文書処理装置に関する実施の形態2を示す。
【0068】
図11は、この発明の第2の実施の形態に係る文書処理装置の構成図である。
図11において、文書処理装置1から不要文書検出手段10までは、図1の同一番号の構成要素に対応するものであり、不要URL除去手段14が、実施形態1に対して実施形態2で追加された部分である。不要URL除去手段14は、不要文書除去手段3の動作に引き続いて動作する。
【0069】
図12は、不要URL除去手段14の動作を示すフローチャートである。
不要URL除去手段14は、文書属性テーブル7の全てのエントリに対して、同一文書URL71を持つエントリ同士をまとめて順に処理する。
【0070】
始めに、ステップS41において、不要URL除去手段14は、文書属性テーブル7の未処理文書URL71を1つ選択し、当該文書URL71に対応する全てのエントリを取得する。取得したエントリ数が所定値を超え、かつ取得したエントリ中で除去フラグ75が1に設定されたエントリの割合(除去率)が所定値を超える場合、当該文書URLからは重複文書しか得られない可能性が高いと考えられるため、当該文書URLを文書URLリスト4から削除し、次回以降は文書の取得を行なわないようにする。
【0071】
続いて、ステップS42において、不要URL除去手段14は、文書属性テーブル7の全ての文書URLが処理されたか判定し、処理済みでなければステップS41に戻り、処理済みであれば終了する。
【0072】
なお、ここでは、同一文書URLの複数バージョンを対象に除去率を求めたが、URL中のホスト名毎、あるいは上位ドメイン名(例えば、http://blog.foo.com/をURLとした場合のfoo.comなど)毎に除去率を求め、重複文書が多く発生するURL群を一括して文書URLリスト4から除去するようにしても良い。
【0073】
以上のように、この発明の実施の形態2によれば、同一文書URLからの文書の取得を繰り返す際に、統計的に有用な文書が得られない見込みが高い文書URLを取得対象から取り除くことにより、不要な文書の取得を避け、外部サーバからの文書取得を効率化することが可能になるという効果がある。
【0074】
実施の形態3.
以上の実施の形態2では、統計的に有用な文書が得られない見込みが高い文書URLを取得対象から取り除くことにより、不要な文書の取得を避け、外部サーバからの文書取得を効率化する文書処理装置を説明したが、次に、出現頻度の高い語句を不自然に多く含む文書を検出して、この文書を除去することにより、統計的な処理に適した文書集合を得ることができる文書処理装置に関する実施の形態3を示す。
【0075】
図13は、この発明の第3の実施の形態に係る文書処理装置の構成図である。
図13において、文書処理装置1から不要文書検出手段10までは、図1の同一番号の構成要素に対応するものであり、最長頻出部分文字列テーブル15が、実施形態1に対して実施形態3で追加された部分である。
【0076】
まず、最長頻出部分文字列テーブル15の格納形式について、詳細に説明する。部分文字列テーブル6においては、固定単語数k個の単語の列を部分文字列としたが、最長頻出部分文字列テーブル15には、1つの単語からQ個の単語の列までの部分文字列が含まれる(例えばQ=10)。ここで、取得文書データ5の文書内容53に含まれる部分文字列の内、所定数以上(例えば500以上)の文書に出現する部分文字列を、頻出部分文字列と定義すれば、最長頻出部分文字列テーブル15は、頻出部分文字列の内、最長の頻出部分文字列を格納するテーブルである。
【0077】
上記の最長の頻出部分文字列を、以下では、最長頻出q単語列(qは単語の数)と表現する。最長頻出q単語列は、所定数以上の文書に出現するq個の単語の列(q単語列)であって、かつ当該q単語列を含む最長頻出q+1単語列が存在しないものを指す。
【0078】
このような最長頻出部分文字列テーブル15を生成するためには、最長頻出部分文字列の候補をq単語列として格納する頻出q単語列テーブルを利用する。
図14は、q=3の場合のq単語列を格納する頻出q単語列テーブル90を示したものである。
頻出q単語列テーブル90は、単語列91と出現回数92からなる。頻出q単語列テーブル90はRAM12上に配置され、単語列91を一意なキーとして検索可能な構造を有する。出現回数92は、対応する単語列91が出現する文書の数を保持する。
【0079】
次に、最長頻出部分文字列テーブル15を用いた不要文書除去手段3の動作を、フローチャートを用いて説明する。
図15は、不要文書除去手段3の動作の内、実施の形態1に対して実施の形態3で加わった部分を示すフローチャートである。
ステップS3からステップS5は、図6のステップS1及びステップS2に引き続いて実行する。
【0080】
まず、ステップS3において、不要文書除去手段3は、不要文書検出手段10により、後述する処理に従って、q=1、2、3、...、Qの順に、取得文書データ5の文書内容53に含まれるq単語列(q=1の場合は単語)の出現文書数を求め、所定数以上の文書に出現したq単語列を、頻出q単語列テーブル90に格納する。
【0081】
続いて、ステップS4において、不要文書検出手段10は、q=Q、Q−1、...、2、1の順に、頻出q単語列テーブルの各エントリのq単語列に含まれる部分文字列群、すなわちq−1単語列、q−2単語列、...、単語に対して、対応する頻出単語列テーブルのエントリを削除する。各頻出q単語列に残ったエントリは最長頻出q単語列であり、これらを最長頻出部分文字列テーブルとする。
【0082】
最後に、ステップS5において、不要文書検出手段10は、ステップS4で生成された最長頻出部分文字列テーブルを参照して、取得文書データ5の文章内容53に同時に含まれる最長頻出部分文字列の種類を求め、所定種類以上(例えば7種類以上)の最長頻出部分文字列を含む文書に対応する文書属性テーブル7のエントリについて、除去フラグ75を1に設定する。
【0083】
次に、図15のステップS3の動作について、フローチャートを用いて説明する。
図16は、ステップS3の動作の内、特定のq(q>1)に対応する動作の詳細を示すフローチャートである。
【0084】
始めに、ステップS51において、不要文書除去手段3は、取得文書データ5の内、未処理の文書dを選択し、文書内容53を構成する単語の列W1、W2、...、Wndを得る。この処理は、図7のステップS12と同じ形態素解析処理を繰り返すか、ステップS12の以前の実行結果を保存しておいて再利用することで実現できる。
【0085】
次に、ステップS52において、不要文書検出手段10は、前記単語列の内、未処理のq単語列(Wi、Wi+1、...、Wi+q−1)を処理対象として取り上げる。
【0086】
次に、ステップS53において、不要文書検出手段10は、q個の単語Wj(j=i、i+1、...、i+q−1)が全て頻出単語テーブル(頻出1単語列テーブル)90に存在するかどうか判定する。存在する場合は、ステップS54に進み、そうでない場合は、当該q単語列が頻出となることはあり得ないため、ステップS56まで処理をスキップする。
【0087】
続いて、ステップS54において、不要文書検出手段10は、q個の単語列の右端を除いたq−1単語列(Wi、Wi+1、...、Wi+q−2)と、左端を除いたq−1単語列(Wi+1、...、Wi+q−1)のいずれもが頻出q−1単語列テーブル90に存在しているかどうか判定する。存在する場合は、ステップS55に進み、そうでない場合は、当該q単語列が頻出となることはあり得ないため、ステップS56まで処理をスキップする。
【0088】
次に、ステップS55において、不要文書検出手段10は、当該q単語列(Wi、Wi+1、...、Wi+q−1)に対応する頻出q単語列テーブルのエントリにおいて、出現回数92に1を加える。
【0089】
次に、ステップS56において、不要文書検出手段10は、文書dの全てのq単語列が全て処理されたか判定し、処理されていれば、ステップS57に進み、そうでなければ、ステップS52に戻って処理を繰り返す。
【0090】
続いて、ステップS57において、不要文書検出手段10は、取得文書データ7の全ての文書が全て処理されたか判定し、処理されていれば、ステップS58に進み、そうでなければ、ステップS51に戻って処理を繰り返す。
【0091】
最後に、ステップS58において、不要文書検出手段10は、頻出q単語列テーブル90の各エントリを順に調べ、出現回数92が所定値未満のエントリを削除する。削除されずに残ったエントリが頻出q単語列である。
【0092】
以上のように、この発明の実施の形態3によれば、出現頻度の高い語句を不自然に多く含む文書を検出して、この文書を除去することにより、統計的な処理に適した文書集合を得ることができるという効果がある。
【0093】
また、スパムブログを自動生成する作者は、インターネット上で公開されている検索エンジンの検索問合せランキングなどを用いると、こうした出現頻度の高い語句を話題語として容易に捉えることができるので、検索エンジンユーザに検索され易いWebページを自動生成するために、このような話題語を、そのWebページに設定される検索対象キーワードとして利用することがある。この場合、Webページの文章の方には、他の文書を自動引用する代わりにランダムな文字列を用いることがある。このような場合に対しても、この発明の実施の形態3によれば、検索対象キーワードとして設定されている頻出語(話題語)を手掛かりに、上記のような自動生成文書を除去することが可能になる。
【符号の説明】
【0094】
1 文書処理装置、2 文書取得手段、3 不要文書除去手段、4 文書URLリスト、5 取得文書データ、6 部分文字列テーブル、7 文書属性テーブル、8 部分文字列生成手段、9 一意部分文字列判定手段、10 不要文書検出手段、11 CPU、12 RAM、13 磁気ディスク装置、14 不要URL除去手段、15 最長頻出部分文字列テーブル。
【技術分野】
【0001】
本発明は、インターネット上に存在する文書、例えば、ブログ等の文書から、分析対象とする目的の文書を抽出する文書処理装置に関する。
【背景技術】
【0002】
インターネットの発展により、入手可能な文書データの量は、飛躍的に増大した。これらの文書データの中には、ブログ等を通じて、個人が自発的に興味の対象や、社会事象に対する意見等を述べたものも数多く含まれるようになった。そこで、このような意見等を述べた文書データを収集して分析することにより、従来は、回答者を募集してアンケートを実施する必要があった社会風潮や消費者動向の把握が、網羅的、かつリアルタイムに実施可能になると期待されている。
一方、ディジタルデータは、入手が容易であると同時に、引用・編集・改変して再発信することも容易であり、インターネット上の文書には、こうした二次情報も多く含まれていると言われている。オリジナルな一次情報とその流用による二次情報が混在していると、同様なデータが重複して格納されることによる記憶効率の低下や、検索問い合わせに対して同様な結果が繰り返し提示されることによる一覧性の低下といった問題が生じる。そこで、各文書データから部分文字列を取り出し、部分文字列毎に出現文書の一覧を管理することで、重複部分を含む文書の提示を可能にするシステムが提案されている(例えば、特許文献1及び2参照)。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2008−33728号公報
【特許文献2】特表2008−511081号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
ブログ等の中には、記事本体よりも、記事に付随する広告の発信を主眼としたものも存在する。このような広告記事の作成者は、なるべく労力をかけずに記事を作成するために、他のブログ記事を取得して引用するコンピュータプログラムを利用して、広告記事を自動生成することが多い。スパムブログと呼ばれるこのようなブログ記事が大量に存在すると、前述の社会風潮や消費者動向の把握を目的として、全文書データの統計処理を行なった際に、自動引用された情報の出現頻度が増加し、現実において話題とされる頻度の実態と大きく乖離してしまうという問題が生じる。
【0005】
従来の文書処理装置においては、例えば、特許文献1では、重複の可能性のある文書の検出に止まっており、文書の削除などの最終的な処置は、文書処理装置の利用者が文書の内容を判断した上で実施する必要がある。なぜなら、ブログにおいては、ニュース記事などの一次情報に対する所感を述べる際に、正当な引用が行なわれることもあるため、重複が検出された文書を全て一律に削除するのは不適当であり、利用者が一つ一つの記事を精査しなくてはならないからである。特許文献1の技術は、データベースを管理する際に意図せずに生じてしまう重複の検出を目的としており、他者により意図的にデータが引用・複製される状況には対処することができない。
【0006】
また、特許文献2はインターネット上の文書を想定したものであるが、2つの文書の組に対して、文書単位での重複の有無を判定する技術である。このため、文書集合から2つ以上の文書の一部を切り出して合成された文書に対しては、切り出された文書の一部を単位として重複の検出を行なうことができず、このような合成された文書を排除することができない。
【0007】
この発明は、上記のような課題を解決するためになされたもので、文書集合に対し、他の文書にも出現する部分文字列を一定割合以上含む文書を、自動引用により生成された文書として排除することで、正当な引用を行なっている文書を含めたオリジナルな文書データの抽出を可能にするものである。
【課題を解決するための手段】
【0008】
上記で述べた課題を解決するため、本発明に係る文書処理装置は、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段とを備えることとしたものである。
【0009】
また、本発明に係る文書処理方法は、部分文字列生成手段が、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成ステップと、一意部分文字列判定手段が、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定ステップと、不要文書検出手段が、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出ステップとを備えることとしたものである。
【0010】
また、本発明に係る文書処理プログラムは、コンピュータを、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させることとしたものである。
【0011】
また、本発明に係る文書処理プログラムを記録したコンピュータ読み取り可能な記録媒体は、コンピュータを、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させる文書処理プログラムを記録させることとしたものである。
【発明の効果】
【0012】
本発明によれば、複数の文書に含まれる文字列から部分文字列を文書毎に生成し、文書毎に当該文書固有の一意部分文字列の割合を求め、一意部分文字列の割合が低いものを、他の1つ以上の文書の引用を中心とする有用性の低い文書として検出し、これらの文書を除去可能にすることにより、統計的な処理に適した文書集合を得ることができるという効果がある。
【図面の簡単な説明】
【0013】
【図1】この発明の実施の形態1に係る文書処理装置の一例を示す構成図である。
【図2】取得文書データ5の詳細な格納形式の一例を示す図である。
【図3】部分文字列テーブル6の詳細な格納形式を示す図である。
【図4】文書属性テーブル7の詳細な格納形式を示す図である。
【図5】部分文字列テーブル6のコンピュータシステムにおける格納方法の詳細を説明する図である。
【図6】不要文書除去手段3の動作を示す概略フローチャートである。
【図7】ステップS1の詳細を示すフローチャートである。
【図8】ステップS16の動作の詳細を示すフローチャートである。
【図9】ステップS19の動作の詳細を示すフローチャートである。
【図10】ステップS2の詳細を示すフローチャートである。
【図11】この発明の第2の実施の形態に係る文書処理装置の構成図である。
【図12】不要URL除去手段14の動作を示すフローチャートである。
【図13】この発明の第3の実施の形態に係る文書処理装置の構成図である。
【図14】q=3の場合のq単語列を格納する頻出q単語列テーブル90を示したものである。
【図15】不要文書除去手段3の動作の内、実施の形態1に対して実施の形態3で加わった部分を示すフローチャートである。
【図16】ステップS3の動作の内、特定のq(q>1)に対応する動作の詳細を示すフローチャートである。
【発明を実施するための形態】
【0014】
実施の形態1.
図1は、この発明の実施の形態1に係る文書処理装置の一例を示す構成図である。
図1において、文書処理装置1は、サーバA〜C等の外部サーバ上の文書を取得する文書取得手段2と、不要文書を除去する不要文書除去手段3とを備え、文書URLリスト4、取得文書データ5、部分文字列テーブル6、及び文書属性テーブル7によって構成される。不要文書除去手段3は、文書中の文字列から部分文字列を生成する部分文字列生成手段8と、生成された部分文字列の内、他の文書には出現せずに一意に定まる部分文字列(一意部分文字列)を判定する一意部分文字列判定手段9と、一意部分文字列数と総部分文字列数との比により、不要文書を検出する不要文書検出手段10とを備える。文書URLリスト4は、文書取得手段2が取得すべき外部サーバ上の文書を特定するアドレス、例えば、URL(Uniform Resource Locator)の一覧を保持する。取得文書データ5は、文書取得手段2が取得した複数の文書データを格納する。部分文字列テーブル6は、不要文書除去手段3による処理の中間状態を格納する。文書属性テーブル7は、不要文書除去手段3による処理結果を格納する。
【0015】
文書処理装置1は、CPU、RAM、磁気ディスク装置、及びネットワークインタフェース等のハードウェアと、ハードウェアを制御するオペレーティングシステムソフトウェアを備える一般的なコンピュータシステムと、CPUの動作を規定するプログラムを用いて実現することができる。この場合、文書取得手段2と不要文書除去手段3とは、磁気ディスク装置からRAMに読み込まれてCPUにより実行されるプログラムとして実現され、文書URLリスト4、取得文書データ5、部分文字列テーブル6、及び文書属性テーブル7は、RAM、または、磁気ディスク装置上の固有の格納領域として実現される。
【0016】
図2は、取得文書データ5の詳細な格納形式の一例を示す図である。
取得文書データ5は、複数のエントリからなり、各エントリは、1つの文書の文書URL51、取得日時52、及び文書内容53を格納する。文書URL51は、文書URLリスト4に記憶されていた取得対象文書のアドレスの1つであり、取得日時52は、文書取得手段2が実際に当該文書データを取得した日時である。また、文書内容53は、文書取得手段2が取得した文書の内容データである。ここで、外部サーバ上の文書のアドレスは、文書URL51により一意に識別されるが、同一の文書URL51から異なる時点で取得した文書内容は異なることもあり得る。そのため、取得文書データ5においては、文書URL51が共通で、取得日時52が異なる複数のエントリが存在しても良い。また、取得文書データ5における各エントリの格納位置には特段の制約を設けず、任意とする。
【0017】
図3は、部分文字列テーブル6の詳細な格納形式を示す図である。
部分文字列テーブル6は、複数のエントリからなり、各エントリは、1つの部分文字列に関するハッシュ値61、文書URL62、取得日時63、及び重複フラグ64を格納する。ここでいう部分文字列とは、図2に示す取得文書データ5の文書内容53から取り出した固定単語数の文字列である。ここでは、単語の数をkとする(例えばk=5)。
【0018】
ハッシュ値61には、当該エントリに対応する部分文字列に対し、CRC(Cyclic Redundancy Code)やSHA‐256(Secure Hash Algorithm 256‐bit)などの公知の一方向性ハッシュ関数により計算したハッシュ値を格納する。このようなハッシュ値は、実用上、元の部分文字列と1対1に対応すると考えることができるので、部分文字列テーブル6のエントリを一意に識別するキーとして用いる。
【0019】
ここで、ハッシュ値61の一意性を維持するため、部分文字列テーブル6における各エントリの格納位置は、ハッシュ値61に基づいて一意に定まる必要がある。しかし、同一の部分文字列であっても、取得文書データ5には、文書URL51や取得日時52が異なる複数のエントリが存在するため、文書URL62及び取得日時63の組み合わせが一意に定まらない。そこで、部分文字列テーブル6の各エントリに重複フラグ64を設け、次のようにして、部分文字列テーブル6における各エントリの一意性を維持する。
【0020】
文書URL62及び取得日時63には、当該エントリに対応する部分文字列が取り出された取得文書データ5のエントリの文書URL52及び取得日時53の組み合わせを、1つ指定する。指定する文書URL52及び取得日時53の組み合わせは、当該エントリに対応する部分文字列を含む文書の内、取得日時が最も古い文書の文書URL52と取得日時53を用いるものとする。あるいは、文書取得手段2によらずに収集された文書集合を分析対象にする場合は、文書URL52と取得日時53の代わりに、当該エントリに対応する部分文字列が最初に生成された文書の識別情報と、文書が作成・更新された日時を用いるものとする。
【0021】
重複フラグ64には、当該エントリに対応する部分文字列が、文書URL62及び取得日時63の組み合わせで指定される文書だけに含まれる場合に、例えば、0が格納され、そうでない場合には、1が格納される。
【0022】
図4は、文書属性テーブル7の詳細な格納形式を示す図である。
文書属性テーブル7は、複数のエントリからなり、各エントリは、1つの文書の文書URL71、取得日時72、部分文字列数73、一意部分文字列数74、及び除去フラグ75を格納する。文書属性テーブル7の各エントリは、取得文書データ5のエントリと1対1に対応しており、文書URL71及び取得日時72は、それぞれ取得文書データ5の文書URL51及び取得日時52に対応する。文書属性テーブル7の各エントリの格納位置は、文書URL71及び取得日時72により一意に定まる必要がある。また、部分文字列数73は、当該エントリに対応する取得文書データ5の文書内容53に含まれる部分文字列の総数を表し、一意部分文字列数74は、当該部分文字列の内、他のエントリの文書内容53に含まれない部分文字列の数を表す。除去フラグ75には、当該エントリに対応する文書が自動引用により生成されたものであり、不要とみなされる場合に、1が格納され、そうでない場合に、0が格納される。
【0023】
図5は、部分文字列テーブル6のコンピュータシステムにおける格納方法の詳細を説明する図である。
図5において、文書処理装置1は、CPU11、RAM12、磁気ディスク装置13により構成されるコンピュータシステムとして示されている。
【0024】
部分文字列テーブル6は、ハッシュ値61に基づいてランダムにアクセスされるため、RAM12に格納することが望ましいが、部分文字列テーブル6のエントリ数、すなわち部分文字列の種類は非常に多く、RAM12に部分文字列テーブル6の全体を格納するだけの容量がない場合が生じる。そこで、部分文字列テーブル6を複数の断片に分割し、RAM12に格納される部分文字列テーブル片(0)と、必要に応じて磁気ディスク装置13に格納される部分文字列テーブル片(1)、部分文字列テーブル片(2)、部分文字列テーブル片(3)、...を設ける。RAM12上の部分文字列テーブル片(0)は、ハッシュ値61をキーとする赤黒木や、ハッシュテーブル等の公知の探索構造により実現する。また、磁気ディスク装置13上の部分文字列テーブル片(j)(j=1,2,...)においては、各エントリをハッシュ値61の順に配置するものとする。
【0025】
また、文書属性テーブル7は、文書URL71及び取得日時72に基づいてランダムにアクセスされるが、多くの場合、RAM12に格納可能と想定されるため、文書URL71及び取得日時72をキーとするRAM12上の赤黒木や、ハッシュテーブルとして実現し、処理終了時に磁気ディスク装置13に内容を書き出せば良い。
【0026】
取得文書データ5は、各エントリの書き込みと読み出しが一度ずつ行なわれるだけであり、容量も大きいため、磁気ディスク装置13上に格納する。
【0027】
次に、文書処理装置1の動作を説明する。
文書取得手段2は、文書URLリスト4から文書URLを読み込み、当該URL中のサーバ名に従って外部サーバへの接続を行ない、公知のHTTP(Hyper‐Text Transfer Protocol)に従って当該URLを送付して文書データを要求する。次いで文書取得手段2は、当該外部サーバからの応答を受信し、前記URLを文書URL51、現在時刻を取得日時52、受信内容を文書内容53として取得文書データ5の末尾に追記する。この処理を文書URLリスト4の全てのURLに対して繰り返す。各文書の取得は逐次に行なう必要はなく、複数文書を同時に並行して取得して所要時間を短縮しても良い。
【0028】
次に、不要文書除去手段3の動作を、フローチャートを用いて説明する。
図6は、不要文書除去手段3の動作を示す概略フローチャートである。
始めに、ステップS1において、不要文書除去手段3は、取得文書データ5に格納された全てのエントリを処理し、部分文字列テーブル6及び文書属性テーブル7の設定を行なう。
次に、ステップS2で、不要文書除去手段3は、部分文字列テーブル6の各エントリに基づいて文書属性テーブル7を更新し、各文書に対する最終的な処理結果を格納する。
【0029】
以下、図6のステップS1における動作の詳細を、フローチャートを用いて説明する。
図7は、ステップS1の詳細を示すフローチャートである。
【0030】
始めに、ステップS11において、不要文書除去手段3は、部分文字列生成手段8により、磁気ディスク装置13上の部分文字列テーブル片の数を表す変数fを0に初期化する。
【0031】
次に、ステップS12において、部分文字列生成手段8は、取得文書データ5から未処理エントリを1つ選択して処理対象とし、その文書内容53に公知の形態素解析処理を施して、単一文字列を複数の単語列に分割する。ここで、当該エントリの文書URL51と取得日時52の組で識別される文書データをdとし、文書dの文書内容53を形態素解析して得られる単語列の要素数をnd、単語列をW1、W2、...、Wndとする。なお、取得文書データ5の各エントリの処理順序は任意であり、例えば、先頭エントリから順に処理対象とすれば良い。
【0032】
次に、ステップS13において、部分文字列生成手段8は、文書dの文書URL51と取得日時52に対応する文書属性テーブル7のエントリを生成し、文書URL71と取得日時72をそれぞれ文書URL51と取得日時52に、部分文字列数73をnd−k+1(kは部分文字列の単語数)に、一意部分文字列数74を0に、除去フラグを1に、それぞれ設定する。
【0033】
次に、ステップS14において、部分文字列生成手段8は、文書dにおける部分文字列を識別する変数iを0に設定し、続くステップS15で変数iに1を加える。
【0034】
次に、ステップS16において、部分文字列生成手段8は、後述する手順により、文書dの形態素解析結果の単語列の内、i番目以降の連続するk個の単語列(Wi、Wi+1、...、Wi+k−1)からなる第i部分文字列のハッシュ値Siに基づき、部分文字列テーブル片の更新を行なう。
ステップS17では、変数iをnd−k+1と比較し、両者が等しければステップS18に進み、そうでなければステップS15に戻る。
【0035】
次に、ステップS18において、部分文字列生成手段8は、取得文書データ5の全てのエントリが処理されたかどうか判定し、未処理のエントリが残っていればステップS12に戻り、全て処理されていればステップS19に進む。
【0036】
最後に、ステップS19において、部分文字列生成手段8は、後述する手順により、f+1個の部分文字列テーブル片を統合し、単一の部分文字列テーブル6を生成して処理を終了する。
【0037】
次に、図7のステップS16における動作の詳細を、フローチャートを用いて説明する。
図8は、ステップS16の動作の詳細を示すフローチャートである。
始めに、ステップS101において、部分文字列生成手段8は、第i部分文字列(Wi、Wi+1、...、Wi+k−1)のハッシュ値Siを計算する。
【0038】
次に、ステップS102において、部分文字列生成手段8は、部分文字列テーブル片(0)を検索し、ハッシュ値61がSiと等しいエントリが存在するかどうか判定する。エントリが存在する場合はステップS107に進み、そうでない場合はステップS103に進む。
【0039】
次に、ステップS103において、部分文字列生成手段8は、部分文字列テーブル片(0)の現在のエントリ数を調べ、その値が所定値未満であるかどうか判定する。所定値未満である場合は、ステップS106に進み、そうでない場合は、ステップS104に進む。ここで、所定値とは、例えば、RAM12の容量に格納可能な部分文字列テーブル片(0)のエントリ数の上限値を意味するものとする。
【0040】
次に、ステップS104において、部分文字列生成手段8は、部分文字列テーブル片(0)に新たなエントリを生成できないため、RAM12上の部分文字列テーブル片(0)を磁気ディスク装置13上の新たな部分文字列テーブル片(f+1)に書き出し、部分文字列テーブル片(0)を空にする処理を行なう。この時、部分文字列テーブル片(0)のエントリをハッシュ値61の順に出力するようにする。部分文字列テーブル片(0)を木構造として実現していればこれは容易であり、部分文字列テーブル片(0)をハッシュテーブルとして実現している場合は、全エントリのソート処理を行なえば良い。
【0041】
続いて、ステップS105で、部分文字列生成手段8は、磁気ディスク装置13上の部分文字列テーブル片の数を表す変数fに1を加える。
【0042】
次に、ステップS106において、部分文字列生成手段8は、部分文字列テーブル片(0)に新たなエントリを割り当て、当該エントリのハッシュ値61をSiに、文書URL62及び取得日時63を現在処理中の文書dに対応する文書URL51及び取得日時52に、重複フラグ64を0に設定し、処理を終了する。
【0043】
一方、ステップS107においては、不要文書除去手段3は、一意部分文字列判定手段9により、部分文字列テーブル片(0)上の既存のエントリの文書URL62及び取得日時63を調べ、文書dの文書URL51及び取得日時52とそれぞれ一致するかどうか判定する。一致する場合は、同一文書内に部分文字列が複数回含まれていることを示しており、文書間の引用を示唆しないので、処理を終了する。そうでない場合は、ステップS108に進む。
【0044】
次に、ステップS108において、一意部分文字列判定手段9は、前記既存エントリの重複フラグを1に設定し、当該部分文字列が複数文書に重複して存在することを記録する。
【0045】
続いて、ステップS109において、一意部分文字列判定手段9は、当該既存エントリの取得日時63が文書dの取得日時52より新しいかどうか判定し、新しければステップS110に進み、そうでなければ処理を終了する。
【0046】
最後に、ステップS110において、一意部分文字列判定手段9は、当該既存エントリの文書URL62及び取得日時63を、文書dの文書URL51及び取得日時52にそれぞれ設定し、処理を終了する。
【0047】
次に、図7のステップS19の動作の詳細を、フローチャートを用いて説明する。
図9は、ステップS19の動作の詳細を示すフローチャートである。
始めに、ステップS21において、不要文書除去手段3は、部分文字列生成手段8により、統合対象の部分文字列テーブル片のそれぞれの先頭エントリを調べ、ハッシュ値の最小値を求める。次に、先頭エントリのハッシュ値が最小値である部分文字列テーブル片の全てから先頭エントリを取得し、当該部分文字列テーブル片から先頭エントリを除去する。
【0048】
次に、ステップS22において、部分文字列生成手段8は、取得したエントリが単一であったかどうか判定し、単一であればステップS26に進み、そうでなければステップS23に進む。
【0049】
次に、ステップS23において、不要文書除去手段3は、一意部分文字列判定手段9により、取得した複数エントリにおいて、文書URL62と取得日時63が全て同一かどうか判定し、同一であればステップS25に進み、そうでなければステップS24に進む。
【0050】
次に、ステップS24において、一意部分文字列判定手段9は、同一ハッシュ値に対して複数文書が対応していることが明らかであるため、重複フラグ64を1とし、ハッシュ値61、文書URL62、及び取得日時63のそれぞれを、取得したエントリ中で取得日時63が最小のエントリのハッシュ値61、文書URL62、及び取得日時63に設定して出力し、ステップS27に進む。
ければステップS24に進む。
【0051】
一方、ステップS25では、一意部分文字列判定手段9は、取得したエントリは全て同一文書に対応しているため、取得エントリ中で重複フラグ64が1になっているものが存在する場合は重複フラグ64を1に、そうでない場合は重複フラグ64を0とし、ハッシュ値61、文書URL62、及び取得日時63のそれぞれを、取得した任意エントリのハッシュ値61、文書URL62、及び取得日時63に設定して出力し、ステップS27に進む。
【0052】
また、ステップS26では、部分文字列生成手段8は、取得した単一のエントリ自体の内容を出力し、ステップS27に進む。
【0053】
最後に、ステップS27において、部分文字列生成手段8は、統合対象の部分文字列テーブル片が全て空になったか判定し、空であれば処理を終了し、そうでなければステップS21に戻って処理を繰り返す。
【0054】
なお、図9の処理は、部分文字列テーブル片の数(f)が非常に大きい場合、所定数(例えば16個)の部分文字列テーブル片を中間的な部分文字列テーブル片に統合し、次に中間的な部分文字列テーブル片の統合を行なうというように、次第に部分文字列テーブル片の数を減少させるようにして適用することもできる。これにより、磁気ディスク装置13に対する入出力性能の低下を抑えることが可能となる。
以上が、図6のステップS1の詳細な動作の説明である。
【0055】
次に、図6のステップS2の詳細な動作を、フローチャートを用いて説明する。
図10は、ステップS2の詳細を示すフローチャートである。
【0056】
まず、ステップS31からステップS32を繰り返すことで、部分文字列テーブル6の全てのエントリを順に処理する。
始めに、ステップS31において、不要文書除去手段3は、不要文書検出手段10により、部分文字列テーブル6の未処理エントリの1つを処理対象として選択し、当該エントリの文書URL62及び取得日時63で指定される文書属性テーブル7のエントリに対し、一意部分文字列数74に1を加える。ここで、当該エントリの重複フラグに1が設定されている場合であっても、重複文書中で最も古い取得日時を持つ文書においては当該エントリに対応する部分文字列を一意部分文字列として扱う。これは、重複文書を全て除去対象とすると引用元文書も除去され、当該文書の内容が存在しなかったものとみなされてしまうためである。
【0057】
なお、文書取得手段2によらずに収集された文書集合を分析対象にする場合は、上記の取得日時の情報を持たないため、文書が作成・更新された日時に基づいて、重複文書中で、重複する部分文字列が最初に生成された文書において当該エントリに対応する部分文字列を一意部分文字列として扱っても良い。
【0058】
次に、ステップS32において、不要文書検出手段10は、未処理のエントリの有無を調べ、部分文字列テーブル6の全てのエントリを処理した場合はステップS33に進み、そうでない場合はステップS31に戻る。
【0059】
続いて、ステップS33からステップS34を繰り返すことで、文書属性テーブル7の全てのエントリを順に処理する。
始めに、ステップS33において、不要文書検出手段10は、文書属性テーブル7の未処理エントリの1つを処理対象として選択し、部分文字列数73に対する一意部分文字列数74の割合が所定値以上(例えば60%以上)であれば、当該エントリの除去フラグ75を0に設定する。
【0060】
次に、ステップS34において、不要文書検出手段10は、未処理のエントリの有無を調べ、文書属性テーブル7の全てのエントリを処理した場合は処理を終了し、そうでない場合はステップS33に戻る。
【0061】
なお、以上の説明においては、文書属性テーブル7はRAM12上に存在し、効率的にランダムアクセスできるものと想定したが、文書属性テーブル7のデータ量がRAM12の容量を上回る場合には、次のようにすれば良い。すなわち、図7のステップS13において、文書属性テーブル7の新規エントリを磁気ディスク装置13上の文書属性テーブル7の末尾に追記しておき、図10の処理に先立って文書属性テーブル7のエントリを文書URL71及び取得日時72の順にソートして、入力側文書属性テーブルとする。同様に、部分文字列テーブル6のエントリも文書URL62及び取得日時63の順にソートしておく。
【0062】
ステップS31では、入力側文書属性テーブルのエントリを先頭から処理し、文書URL及び取得日時が一致するエントリが部分文字列テーブル6から読み込まれる限り、当該文書属性テーブルエントリの一意部分文字列数74に1を加え、文書URL及び取得日時が一致しないエントリが部分文字列テーブル6から読み込まれた時点で該文書属性テーブルエントリを出力文書属性テーブルに追記する。
【0063】
また、以上の説明においては、部分文字列をk個の単語の列としたが、形態素解析処理による単語分割を行なわず、部分文字列をk’個の文字の列としても良い。
【0064】
以上のように、この発明の実施の形態1によれば、複数の文書に含まれる文字列から部分文字列を文書毎に生成し、文書毎に当該文書固有の一意部分文字列の割合を求め、一意部分文字列の割合が低いものを、他の1つ以上の文書の引用を中心とする有用性の低い文書として検出し、これらの文書を除去可能にすることにより、統計的な処理に適した文書集合を得ることができるという効果がある。
【0065】
また、複数文書に出現する部分文字列を、最も古い取得日時の文書においては一意部分文字列として扱うことにより、引用元である可能性が高い文書を除去してしまうことを防ぐという効果がある。
【0066】
さらに、一定割合までは他の文書と重複する部分文字列の存在を許すことにより、正当な引用を行なって固有の記述を加えている文書まで除去してしまうことを防ぐという効果がある。
【0067】
実施の形態2.
以上の実施の形態1では、一意部分文字列の割合が低い文書を、他の1つ以上の文書の引用を中心とする有用性の低い文書として除去することにより、統計的な処理に適した文書集合を得ることができる文書処理装置を説明したが、次に、同一文書URLからの文書の取得を繰り返す際に、統計的に有用な文書が得られない見込みが高い文書URLを取得対象から取り除くことにより、不要な文書の取得を避け、外部サーバからの文書取得を効率化する文書処理装置に関する実施の形態2を示す。
【0068】
図11は、この発明の第2の実施の形態に係る文書処理装置の構成図である。
図11において、文書処理装置1から不要文書検出手段10までは、図1の同一番号の構成要素に対応するものであり、不要URL除去手段14が、実施形態1に対して実施形態2で追加された部分である。不要URL除去手段14は、不要文書除去手段3の動作に引き続いて動作する。
【0069】
図12は、不要URL除去手段14の動作を示すフローチャートである。
不要URL除去手段14は、文書属性テーブル7の全てのエントリに対して、同一文書URL71を持つエントリ同士をまとめて順に処理する。
【0070】
始めに、ステップS41において、不要URL除去手段14は、文書属性テーブル7の未処理文書URL71を1つ選択し、当該文書URL71に対応する全てのエントリを取得する。取得したエントリ数が所定値を超え、かつ取得したエントリ中で除去フラグ75が1に設定されたエントリの割合(除去率)が所定値を超える場合、当該文書URLからは重複文書しか得られない可能性が高いと考えられるため、当該文書URLを文書URLリスト4から削除し、次回以降は文書の取得を行なわないようにする。
【0071】
続いて、ステップS42において、不要URL除去手段14は、文書属性テーブル7の全ての文書URLが処理されたか判定し、処理済みでなければステップS41に戻り、処理済みであれば終了する。
【0072】
なお、ここでは、同一文書URLの複数バージョンを対象に除去率を求めたが、URL中のホスト名毎、あるいは上位ドメイン名(例えば、http://blog.foo.com/をURLとした場合のfoo.comなど)毎に除去率を求め、重複文書が多く発生するURL群を一括して文書URLリスト4から除去するようにしても良い。
【0073】
以上のように、この発明の実施の形態2によれば、同一文書URLからの文書の取得を繰り返す際に、統計的に有用な文書が得られない見込みが高い文書URLを取得対象から取り除くことにより、不要な文書の取得を避け、外部サーバからの文書取得を効率化することが可能になるという効果がある。
【0074】
実施の形態3.
以上の実施の形態2では、統計的に有用な文書が得られない見込みが高い文書URLを取得対象から取り除くことにより、不要な文書の取得を避け、外部サーバからの文書取得を効率化する文書処理装置を説明したが、次に、出現頻度の高い語句を不自然に多く含む文書を検出して、この文書を除去することにより、統計的な処理に適した文書集合を得ることができる文書処理装置に関する実施の形態3を示す。
【0075】
図13は、この発明の第3の実施の形態に係る文書処理装置の構成図である。
図13において、文書処理装置1から不要文書検出手段10までは、図1の同一番号の構成要素に対応するものであり、最長頻出部分文字列テーブル15が、実施形態1に対して実施形態3で追加された部分である。
【0076】
まず、最長頻出部分文字列テーブル15の格納形式について、詳細に説明する。部分文字列テーブル6においては、固定単語数k個の単語の列を部分文字列としたが、最長頻出部分文字列テーブル15には、1つの単語からQ個の単語の列までの部分文字列が含まれる(例えばQ=10)。ここで、取得文書データ5の文書内容53に含まれる部分文字列の内、所定数以上(例えば500以上)の文書に出現する部分文字列を、頻出部分文字列と定義すれば、最長頻出部分文字列テーブル15は、頻出部分文字列の内、最長の頻出部分文字列を格納するテーブルである。
【0077】
上記の最長の頻出部分文字列を、以下では、最長頻出q単語列(qは単語の数)と表現する。最長頻出q単語列は、所定数以上の文書に出現するq個の単語の列(q単語列)であって、かつ当該q単語列を含む最長頻出q+1単語列が存在しないものを指す。
【0078】
このような最長頻出部分文字列テーブル15を生成するためには、最長頻出部分文字列の候補をq単語列として格納する頻出q単語列テーブルを利用する。
図14は、q=3の場合のq単語列を格納する頻出q単語列テーブル90を示したものである。
頻出q単語列テーブル90は、単語列91と出現回数92からなる。頻出q単語列テーブル90はRAM12上に配置され、単語列91を一意なキーとして検索可能な構造を有する。出現回数92は、対応する単語列91が出現する文書の数を保持する。
【0079】
次に、最長頻出部分文字列テーブル15を用いた不要文書除去手段3の動作を、フローチャートを用いて説明する。
図15は、不要文書除去手段3の動作の内、実施の形態1に対して実施の形態3で加わった部分を示すフローチャートである。
ステップS3からステップS5は、図6のステップS1及びステップS2に引き続いて実行する。
【0080】
まず、ステップS3において、不要文書除去手段3は、不要文書検出手段10により、後述する処理に従って、q=1、2、3、...、Qの順に、取得文書データ5の文書内容53に含まれるq単語列(q=1の場合は単語)の出現文書数を求め、所定数以上の文書に出現したq単語列を、頻出q単語列テーブル90に格納する。
【0081】
続いて、ステップS4において、不要文書検出手段10は、q=Q、Q−1、...、2、1の順に、頻出q単語列テーブルの各エントリのq単語列に含まれる部分文字列群、すなわちq−1単語列、q−2単語列、...、単語に対して、対応する頻出単語列テーブルのエントリを削除する。各頻出q単語列に残ったエントリは最長頻出q単語列であり、これらを最長頻出部分文字列テーブルとする。
【0082】
最後に、ステップS5において、不要文書検出手段10は、ステップS4で生成された最長頻出部分文字列テーブルを参照して、取得文書データ5の文章内容53に同時に含まれる最長頻出部分文字列の種類を求め、所定種類以上(例えば7種類以上)の最長頻出部分文字列を含む文書に対応する文書属性テーブル7のエントリについて、除去フラグ75を1に設定する。
【0083】
次に、図15のステップS3の動作について、フローチャートを用いて説明する。
図16は、ステップS3の動作の内、特定のq(q>1)に対応する動作の詳細を示すフローチャートである。
【0084】
始めに、ステップS51において、不要文書除去手段3は、取得文書データ5の内、未処理の文書dを選択し、文書内容53を構成する単語の列W1、W2、...、Wndを得る。この処理は、図7のステップS12と同じ形態素解析処理を繰り返すか、ステップS12の以前の実行結果を保存しておいて再利用することで実現できる。
【0085】
次に、ステップS52において、不要文書検出手段10は、前記単語列の内、未処理のq単語列(Wi、Wi+1、...、Wi+q−1)を処理対象として取り上げる。
【0086】
次に、ステップS53において、不要文書検出手段10は、q個の単語Wj(j=i、i+1、...、i+q−1)が全て頻出単語テーブル(頻出1単語列テーブル)90に存在するかどうか判定する。存在する場合は、ステップS54に進み、そうでない場合は、当該q単語列が頻出となることはあり得ないため、ステップS56まで処理をスキップする。
【0087】
続いて、ステップS54において、不要文書検出手段10は、q個の単語列の右端を除いたq−1単語列(Wi、Wi+1、...、Wi+q−2)と、左端を除いたq−1単語列(Wi+1、...、Wi+q−1)のいずれもが頻出q−1単語列テーブル90に存在しているかどうか判定する。存在する場合は、ステップS55に進み、そうでない場合は、当該q単語列が頻出となることはあり得ないため、ステップS56まで処理をスキップする。
【0088】
次に、ステップS55において、不要文書検出手段10は、当該q単語列(Wi、Wi+1、...、Wi+q−1)に対応する頻出q単語列テーブルのエントリにおいて、出現回数92に1を加える。
【0089】
次に、ステップS56において、不要文書検出手段10は、文書dの全てのq単語列が全て処理されたか判定し、処理されていれば、ステップS57に進み、そうでなければ、ステップS52に戻って処理を繰り返す。
【0090】
続いて、ステップS57において、不要文書検出手段10は、取得文書データ7の全ての文書が全て処理されたか判定し、処理されていれば、ステップS58に進み、そうでなければ、ステップS51に戻って処理を繰り返す。
【0091】
最後に、ステップS58において、不要文書検出手段10は、頻出q単語列テーブル90の各エントリを順に調べ、出現回数92が所定値未満のエントリを削除する。削除されずに残ったエントリが頻出q単語列である。
【0092】
以上のように、この発明の実施の形態3によれば、出現頻度の高い語句を不自然に多く含む文書を検出して、この文書を除去することにより、統計的な処理に適した文書集合を得ることができるという効果がある。
【0093】
また、スパムブログを自動生成する作者は、インターネット上で公開されている検索エンジンの検索問合せランキングなどを用いると、こうした出現頻度の高い語句を話題語として容易に捉えることができるので、検索エンジンユーザに検索され易いWebページを自動生成するために、このような話題語を、そのWebページに設定される検索対象キーワードとして利用することがある。この場合、Webページの文章の方には、他の文書を自動引用する代わりにランダムな文字列を用いることがある。このような場合に対しても、この発明の実施の形態3によれば、検索対象キーワードとして設定されている頻出語(話題語)を手掛かりに、上記のような自動生成文書を除去することが可能になる。
【符号の説明】
【0094】
1 文書処理装置、2 文書取得手段、3 不要文書除去手段、4 文書URLリスト、5 取得文書データ、6 部分文字列テーブル、7 文書属性テーブル、8 部分文字列生成手段、9 一意部分文字列判定手段、10 不要文書検出手段、11 CPU、12 RAM、13 磁気ディスク装置、14 不要URL除去手段、15 最長頻出部分文字列テーブル。
【特許請求の範囲】
【請求項1】
複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、
前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、
文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段と
を備える文書処理装置。
【請求項2】
前記部分文字列生成手段により生成された前記部分文字列と、この部分文字列が最初に生成された文書の識別情報と、前記部分文字列が異なる文書間で重複しているか否かを示す重複フラグとを対応付けて記憶する部分文字列テーブルを備え、
前記一意部分文字列判定手段は、前記部分文字列テーブルに記憶された前記重複フラグが重複していることを示す場合、前記最初に生成された文書においては当該部分文字列を一意部分文字列として判定し、それ以外の文書においては一意部分文字列としないと判定する請求項1記載の文書処理装置。
【請求項3】
URL(Uniform Resource Locator)で指定される外部サーバ上の文書をネットワーク経由で取得し、前記URLと取得日時と共に前記取得文書データに格納する文書取得手段と、
前記部分文字列生成手段により生成された前記部分文字列と、この部分文字列を含む文書の内、前記取得日時が最も古い文書の前記URLと、前記取得日時と、前記部分文字列が異なる文書間で重複しているか否かを示す重複フラグとを対応付けて記憶する部分文字列テーブルとを備え、
前記一意部分文字列判定手段は、前記部分文字列テーブルに記憶された前記重複フラグが重複していることを示す場合、前記取得日時が最も古い文書においては当該部分文字列を一意部分文字列として判定し、それ以外の文書においては一意部分文字列としないと判定する請求項1記載の文書処理装置。
【請求項4】
前記文書取得手段により文書を取得する前記URLを取得対象URLとして格納する文書URLリストを備え、
前記不要文書検出手段により検出した前記不要文書の前記URLに基づいて、前記文書URLリストに格納された前記取得対象URLの削除を行なう不要URL除去手段を備えた請求項3記載の文書処理装置。
【請求項5】
前記不要URL除去手段は、前記不要文書検出手段により検出した前記不要文書が、所定数以上の取得日時において繰り返して不要文書として検出されている場合、この不要文書のURLを前記文書URLリストに格納された前記取得対象URLから削除する請求項4記載の文書処理装置。
【請求項6】
前記不要URL除去手段は、前記不要文書検出手段により検出した前記不要文書の前記URLのホスト名または上位ドメイン名が一致するURLを持つ文書の内、所定割合以上が不要文書として検出されている場合、このホスト名または上位ドメイン名が一致する全てのURLを前記文書URLリストに格納された前記取得対象URLから削除する請求項4記載の文書処理装置。
【請求項7】
前記部分文字列生成手段は、前記部分文字列テーブルをRAM(Random Access Memory)に記憶させ、前記部分文字列テーブルが前記RAMの容量に応じた所定の容量に達すると前記RAMに記憶された前記部分文字列テーブルの断片を磁気ディスク装置に書き出して前記RAMに記憶された前記部分文字列テーブルを空にし、前記取得文書データの全てについて前記不要文書の検出を行なった後に、前記RAM及び前記磁気ディスク装置に記憶された前記部分文字列テーブルの断片を部分文字列に基づいて統合する請求項2から6のいずれかに記載の文書処理装置。
【請求項8】
前記不要文書検出手段は、所定の長さ以内の部分文字列の出現文書数に基づき、所定数以上の文書に出現する頻出部分文字列の内、より長い頻出部分文字列に含まれない最長の頻出部分文字列である最長頻出部分文字列を求め、この最長頻出部分文字列を所定種類以上含む文書を不要文書として検出する請求項1から7のいずれかに記載の文書処理装置。
【請求項9】
部分文字列生成手段が、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成ステップと、
一意部分文字列判定手段が、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定ステップと、
不要文書検出手段が、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出ステップとを備える文書処理方法。
【請求項10】
コンピュータを、
複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、
前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、
文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させるための文書処理プログラム。
【請求項11】
コンピュータを、
複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、
前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、
文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させるための文書処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項1】
複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、
前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、
文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段と
を備える文書処理装置。
【請求項2】
前記部分文字列生成手段により生成された前記部分文字列と、この部分文字列が最初に生成された文書の識別情報と、前記部分文字列が異なる文書間で重複しているか否かを示す重複フラグとを対応付けて記憶する部分文字列テーブルを備え、
前記一意部分文字列判定手段は、前記部分文字列テーブルに記憶された前記重複フラグが重複していることを示す場合、前記最初に生成された文書においては当該部分文字列を一意部分文字列として判定し、それ以外の文書においては一意部分文字列としないと判定する請求項1記載の文書処理装置。
【請求項3】
URL(Uniform Resource Locator)で指定される外部サーバ上の文書をネットワーク経由で取得し、前記URLと取得日時と共に前記取得文書データに格納する文書取得手段と、
前記部分文字列生成手段により生成された前記部分文字列と、この部分文字列を含む文書の内、前記取得日時が最も古い文書の前記URLと、前記取得日時と、前記部分文字列が異なる文書間で重複しているか否かを示す重複フラグとを対応付けて記憶する部分文字列テーブルとを備え、
前記一意部分文字列判定手段は、前記部分文字列テーブルに記憶された前記重複フラグが重複していることを示す場合、前記取得日時が最も古い文書においては当該部分文字列を一意部分文字列として判定し、それ以外の文書においては一意部分文字列としないと判定する請求項1記載の文書処理装置。
【請求項4】
前記文書取得手段により文書を取得する前記URLを取得対象URLとして格納する文書URLリストを備え、
前記不要文書検出手段により検出した前記不要文書の前記URLに基づいて、前記文書URLリストに格納された前記取得対象URLの削除を行なう不要URL除去手段を備えた請求項3記載の文書処理装置。
【請求項5】
前記不要URL除去手段は、前記不要文書検出手段により検出した前記不要文書が、所定数以上の取得日時において繰り返して不要文書として検出されている場合、この不要文書のURLを前記文書URLリストに格納された前記取得対象URLから削除する請求項4記載の文書処理装置。
【請求項6】
前記不要URL除去手段は、前記不要文書検出手段により検出した前記不要文書の前記URLのホスト名または上位ドメイン名が一致するURLを持つ文書の内、所定割合以上が不要文書として検出されている場合、このホスト名または上位ドメイン名が一致する全てのURLを前記文書URLリストに格納された前記取得対象URLから削除する請求項4記載の文書処理装置。
【請求項7】
前記部分文字列生成手段は、前記部分文字列テーブルをRAM(Random Access Memory)に記憶させ、前記部分文字列テーブルが前記RAMの容量に応じた所定の容量に達すると前記RAMに記憶された前記部分文字列テーブルの断片を磁気ディスク装置に書き出して前記RAMに記憶された前記部分文字列テーブルを空にし、前記取得文書データの全てについて前記不要文書の検出を行なった後に、前記RAM及び前記磁気ディスク装置に記憶された前記部分文字列テーブルの断片を部分文字列に基づいて統合する請求項2から6のいずれかに記載の文書処理装置。
【請求項8】
前記不要文書検出手段は、所定の長さ以内の部分文字列の出現文書数に基づき、所定数以上の文書に出現する頻出部分文字列の内、より長い頻出部分文字列に含まれない最長の頻出部分文字列である最長頻出部分文字列を求め、この最長頻出部分文字列を所定種類以上含む文書を不要文書として検出する請求項1から7のいずれかに記載の文書処理装置。
【請求項9】
部分文字列生成手段が、複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成ステップと、
一意部分文字列判定手段が、前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定ステップと、
不要文書検出手段が、文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出ステップとを備える文書処理方法。
【請求項10】
コンピュータを、
複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、
前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、
文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させるための文書処理プログラム。
【請求項11】
コンピュータを、
複数の文書に含まれる文字列から、この文字列の一部をなす部分文字列を文書毎に生成する部分文字列生成手段と、
前記部分文字列生成手段により生成された前記部分文字列の内、自らが生成された文書以外の文書に含まれない部分文字列を一意部分文字列として判定する一意部分文字列判定手段と、
文書毎の総部分文字列数と前記一意部分文字列判定手段により判定された前記一意部分文字列数との比が所定の範囲にある文書を不要文書として検出する不要文書検出手段として機能させるための文書処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【公開番号】特開2012−18510(P2012−18510A)
【公開日】平成24年1月26日(2012.1.26)
【国際特許分類】
【出願番号】特願2010−154764(P2010−154764)
【出願日】平成22年7月7日(2010.7.7)
【出願人】(000006013)三菱電機株式会社 (33,312)
【Fターム(参考)】
【公開日】平成24年1月26日(2012.1.26)
【国際特許分類】
【出願日】平成22年7月7日(2010.7.7)
【出願人】(000006013)三菱電機株式会社 (33,312)
【Fターム(参考)】
[ Back to top ]