(57)【要約】【課題】本発明の課題は、文書間の相関値を算出する際の計算量を軽減することを目的とする。【解決手段】上記課題は、比較対象の複数の文書それぞれを複数の要素に分離し、前記複数の文書の全てのずれ位置における、前記複数の要素それぞれの、要素間の重み付けを含めた相関値を、該要素の特徴をベクトルで表すことで、各要素に対応付けた該ベクトルの内積とした離散フーリエ変換により算出する処理をコンピュータに行わせる文書比較プログラムにより達成される。【選択図】図６
2018063596.tif 000002
【特許請求の範囲】
【請求項１】
比較対象の複数の文書それぞれを複数の要素に分離し、
前記複数の文書の全てのずれ位置における、前記複数の要素それぞれの、要素間の重み付けを含めた相関値を、該要素の特徴をベクトルで表すことで、各要素に対応付けた該ベクトルの内積とした離散フーリエ変換により算出する
処理をコンピュータに行わせる文書比較プログラム。
【請求項２】
前記コンピュータに、
前記ベクトルの次元ごとに、前記複数の文書の前記各要素に対応付けた前記ベクトルの内積とした前記離散フーリエ変換により畳み込み演算を行って、該次元の各ずれ位置における演算値を取得し、
各ずれ位置で前記ベクトルの次元ごとで得た演算値を合計する
処理を行わせる請求項1記載の文書比較プログラム。
【請求項３】
前記コンピュータに、
前記複数の文書を、品詞、文字、フレーズ、又は空白を区切りとした単語のいずれかを要素として分離させる
ことを特徴とする請求項１又は２記載の文書比較プログラム。
【請求項４】
比較対象の複数の文書それぞれを複数の要素に分離し、
前記複数の文書の全てのずれ位置における、前記複数の要素それぞれの、要素間の重み付けを含めた相関値を、該要素の特徴をベクトルで表すことで、各要素に対応付けた該ベクトルの内積とした離散フーリエ変換により算出する
処理をコンピュータが行う文書比較方法。
【請求項５】
比較対象の複数の文書それぞれを複数の要素に分離する分離部と、
前記複数の文書の全てのずれ位置における、前記複数の要素それぞれの、要素間の重み付けを含めた相関値を、該要素の特徴をベクトルで表すことで、各要素に対応付けた該ベクトルの内積とした離散フーリエ変換により算出する算出部と
を有する文書比較装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書比較プログラム、文書比較方法、及び文書比較装置に関する。
【背景技術】
【０００２】
従来より、文書間の比較を行う際は、計算量を削減するため、各文書について、特徴量や特徴を表わす文を抽出し、抽出した特徴量や文書同士を比較することで文書間の類似度を評価している。
【０００３】
類似度を評価する観点において、１つ以上の検索キーワードの、データベースに予め保存された文書での出現頻度、検索キーワード間の近接度及び検索キーワードを評価する技術が提案されている。
【０００４】
特定のユーザの嗜好情報のベクトル値と、複数の任意のユーザの嗜好情報の各ベクトル値との内積が所定の値を上回っている場合にユーザの嗜好情報の一致を判別する技術等が知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特表２００９−５１５２４９号公報
【特許文献２】特開２００１−３０６６０６号公報
【特許文献３】特開２０１２−２５２４８４号公報
【非特許文献】
【０００６】
【非特許文献１】D．Gusfield：Algorithms  on  Strings，Trees  and  Sequences：Computer  Science  and  Computational  Biology，Cambridge  University  Press，1997
【非特許文献２】T．Mikolov，K．Chen，G．Corrado，and  J．Dean．Efficient  estimation  of  word  representations  in  vector  space．ICLR，2013
【非特許文献３】“MeCab（和布蕪）とは”、［online］、［平成２８年７月２１日検索］、インターネット＜ＵＲＬ：http：//taku910．github．io/mecab＞
【非特許文献４】C．D．Manning，P．Raghavan，H．Schutze：Introduction  to  Information  Retrieval，Cambridge  University  Press，2008
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述した技術では、類似度を評価するが、類似と剽窃の区別など、文書間の類似の詳細について、情報を得ることは困難である。
【０００８】
近年、機械学習やニューラルネットワーク等の技術を用いることにより、文書ごとの語のベクトル表現を得られるようになっているが、単純に、文中に出現する語の間の重みを計算すると、計算量が非常に膨大となってしまう。
【０００９】
したがって、１つの側面では、本発明は、文書間の相関値を算出する際の計算量を軽減することを目的とする。
【課題を解決するための手段】
【００１０】
一態様によれば、比較対象の複数の文書それぞれを複数の要素に分離し、前記複数の文書の全てのずれ位置における、前記複数の要素それぞれの、要素間の重み付けを含めた相関値を、該要素の特徴をベクトルで表すことで、各要素に対応付けた該ベクトルの内積とした離散フーリエ変換により算出する処理をコンピュータに行わせる文書比較プログラムが提供される。
【００１１】
また、上記課題を解決するための手段として、文書比較方法及び文書比較装置とすることもできる。
【発明の効果】
【００１２】
文書間の相関値を算出する際の計算量を軽減することができる。
【図面の簡単な説明】
【００１３】
【図１】位置ずれを説明するための図である。
【図２】重みテーブルの例を示す図である。
【図３】計算と計算時間との関係を説明するための図である。
【図４】相関計算の結果例を示す図である。
【図５】文書比較装置のハードウェア構成を示す図である。
【図６】文書比較装置の機能構成例を示す図である。
【図７】ベクトル表現収集処理を説明するためのフローチャート図である。
【図８】文書比較処理を説明するためのフローチャート図である。
【図９】図８のステップＳ２０４を第１の計算方法の場合の重み付き相関計算処理を説明するためのフローチャート図である。
【図１０】図８のステップＳ２０４を第２の計算方法の場合の重み付き相関計算処理を説明するためのフローチャート図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態を図面に基づいて説明する。先ず、２つの文書の重み付き相関を求める問題について考察する。ここで、
「相関」とは、すべての位置ずれで対応させた語との一致数を表し、
「重み」とは、語の対に付加されるある値域の連続値で表される。
【００１５】
文章間の相関を求める既存手法には、以下の２つが存在する。第１の手法は、語の比較を順に行い、重みを表から参照するものである。第２の手法は、相関を比較的高速に求める手法として知られている重み無しのFFT(Fast  Fourier  Transform)-based  algorithmである。それぞれの計算時間は、σを語の種類の数、nを各文章の長さとした場合、
第１の手法に掛る時間は、O(n2(logσ)2)で表され、
第２の手法に掛る時間は、O(σn2logn)で表される。
【００１６】
第１の手法及び第２の手法について考察する前に、２つの文書の重み付き相関を求める問題について、以下のように定式化するものとする。
・文書：語の列、W：語の集合、Wn：長さ（語の数）nの文書全体からなる集合
・si：文章sのi番目の語
・st：文章sとtとをつなげた文書、wn：n個の語wからなる文書
【００１７】
【数１】
2018063596.tif 000003
の相関C(s，t)は、2n-1次元ベクトルで、i番目の要素は、
【００１８】
【数２】
2018063596.tif 000004
で表される。ただし、
【００１９】
【数３】
2018063596.tif 000005
について、
【００２０】
【数４】
2018063596.tif 000006
のように文字列を数式のように表わすことで、範囲外の形式的な比較のためにダミーの語を付加することを表現する。このようにすることで、位置ずれを考慮して相関を算出できる。
【００２１】
図１は、位置ずれを説明するための図である。図１では、文書sの文書tに対するi番目の要素の位置ずれを考慮するために、文書tの前後に、文書sにも文書tにも属さないダミーの語xを付加する概念図を示している。
【００２２】
文章sを１語ずつずらして、ずらした位置における文書ｔの１語との相関を算出する。文書tに対して、文書ｓでは語順を変えてある場合がずれ位置に相当する。
【００２３】
更に、φを２つの語から連続的な値への関数とすると、
【００２４】
【数５】
2018063596.tif 000007
の重み付き関数C’(s，t)は、
【００２５】
【数６】
2018063596.tif 000008
で表される。数６において、各φは-１から+１の間の値を取り、j=1〜nまでを積算することにより、重み付き相関の要素C’iは、-nから+nの値を取る。
【００２６】
既存の第１の手法について、３つの文章s、t及びuを
文章s：This  is  a  dog．
文章t：That  is  a  cat．
文章u：This  is  a  pen．
とする。この場合、図２に示すような重みテーブルが作成される。図２は、重みテーブルの例を示す図である。
【００２７】
図２において、重みテーブル３は、文章s、t及びuから得た語をマトリクスで示し、語と語の相関の重みを示している。重みテーブル３を参照すると、語義が一致する場合、重み「1」が与えられ、一致しない場合、重み「0」が与えられる。また、語義の類似度は、０と１の間の数値で与えられる。例えば、「cat」と「dog」の語義の類似度に対する重みは「0．7」が与えられ、「pen」と「cat」の語義の類似度に対して重みは「0．1」が与えられている。
【００２８】
第１の手法において、重み無しの相関Cは、
C(s，t)=(0，0，0，2，0，0，0)
C(s，u)=(0，0，0，3，0，0，0)
C(t，u)=(0，0，0，2，0，0，0)
として得られ、それぞれに重みテーブル３を参照して、
C’(s，t)=(0，0，0，3．5，0，0，0)
C’(s，u)=(0，0，0，3．1，0，0，0)
C’(t，u)=(0，0，0，2．9，0，0，0)
このような重み付き相関C’を得る。この結果から、文書sと文書tとが最も近く、次に、文書sと文書uとが近く、文書tと文書uとは最も似ていない、と判断できる。
【００２９】
この第１の手法では、予め語の対ごとに重みを示す重みテーブル３を作成し、語の比較を順に行い、重みテーブル３を参照して重みを取得する。具体的には、
【００３０】
【数７】
2018063596.tif 000009
として、σ×σの語の対から重みへの表を予め準備する。
【００３１】
すべての位置ずれについて、対応する語を順に比較し、語の対に対応する重みを重みテーブル３から取得する。
【００３２】
上述した処理手順により、語の比較はO(n2)回行われ、１回の重みテーブル３の参照がO((logσ)2)時間で表される。即ち、全ての語の対に対して、
O(n2)  ×  O((logσ)2)  ＝  O(n2(logσ)2)時間
掛ると考えられる。ここで、nは語数を示し、σは重みテーブル３の長さを示す。
【００３３】
既存の第２の手法に関して、まず、ＦＦＴによる畳み込みの計算について説明する。
【００３４】
２つのn次元ベクトルuとvとの巡回畳み込みrは、
【００３５】
【数８】
2018063596.tif 000010
で表される。ただし、-n+1≦i≦０についてはvi=vn+iである。
【００３６】
R，U，Vをそれぞれr，u，vの離散フーリエ変換としoを要素ごとの積とすると、
【００３７】
【数９】
2018063596.tif 000011
で表される。このことから、rは、uとvとからＦＦＴによりO(nlogn)時間で計算可能である。計算ルートと計算時間との関係を図３で説明する。
【００３８】
図３は、計算と計算時間との関係を説明するための図である。図３において、nは文章の長さを表わす。uとvとからrを得る計算、即ち、語uと語vの比較rを行う計算の場合、計算時間O(n2)で表される。
【００３９】
一方、u，vの離散フーリエ変換U，Vの計算時間はO(nlogn)であり、U，Vの要素毎の積Rの計算時間は、O(n)である。また、Rからrへの逆離散フーリエ変換の計算時間は、O(nlogn)である。
【００４０】
次に、FFT-based  Algorithmの概要について説明する。文書間の重み無し関数を語を数値化して得られるベクトルの畳み込みにより計算する。語の集合W内のある語aを1、それ以外を0に置き換えると、aの一致のみを考慮した相関を畳み込みで表すことができ、O(nlogn)時間で計算可能である。文書から数値列への置き換えはO(n)時間である。また、乗算で一致又は不一致を表現できるので、畳み込み演算が適用可能である。
【００４１】
O(nlogn)時間の畳み込み演算をσ回繰り返し、要素ごとの和をとることで相関を計算する。具体的には、
【００４２】
【数１０】
2018063596.tif 000012
について、φaは、aを1、それ以外を0に写す関数である。定義より、1≦i≦2n-1について、相関Ciは、
【００４３】
【数１１】
2018063596.tif 000013
と表される。
【００４４】
（ua，1，  ua，2，．．．，  ua，2n-1）と（va，1，  va，2，．．．，  va，2n-1）とを、
【００４５】
【数１２】
2018063596.tif 000014
である２ｎ−１次元ベクトルとすると、数１１は、
【００４６】
【数１３】
2018063596.tif 000015
で表される。数１３内の
【００４７】
【数１４】
2018063596.tif 000016
は畳み込み演算である。
【００４８】
このFFT-based  Algorithmでは、第１の手法では、文書長さnの自乗時間（O(n2logσ)  2時間）に比べて、重み無し相関については非常に高速（O(σnlogn)時間）に行える。しかしながら、φの評価を重みテーブル３を用いて実現使用とすると、C’(s，t)の式を畳み込みとみなすことができないため、重みテーブル３を用いて第２の手法の拡張は困難である。既存の手法の組合せでは、高速化することが困難である。
【００４９】
出願人は、上述したような既存の第１の手法及び第２の手法の考察において、２以上の文章の各要素間の相関を表わす行列、即ち、相関Cが疎であり、内積を用いても計算量を抑えられることに着目した。即ち、重みを重みテーブル３の代わりにベクトルの内積により第２の手法を重み付き関数へと拡張することを見出した。
【００５０】
以下に、発明者による実施例について説明する。
【００５１】
β：W→Rd：ベクトル表現、R：実数全体からなる集合
【００５２】
【数１５】
2018063596.tif 000017
について、
【００５３】
【数１６】
2018063596.tif 000018
で表す。定数α、γについて
【００５４】
【数１７】
2018063596.tif 000019
としてもよい。
【００５５】
重みをベクトルの内積で表現することで、重み付き相関を畳み込み演算によりO(dnlogn)時間で行える。
【００５６】
d＝σであるベクトル表現でも計算をO(σnlogn)時間で行える。一例として、ある語に対応する要素が1、それ以外が0のベクトルであり、ベクトルが疎で、すべて直交している場合等である。
【００５７】
現実的な文書又は言語ではd<<σであると考えられる。つまり、重みの値の分布は何らかの偏りを持つので、表のサイズσよりも小さい次元dでφを表わすことができる。誤記を表わすベクトルがすべて直交するようなベクトル表現でなくてもよい。
【００５８】
既存の第１の手法の重みテーブル３の参照をベクトルの内積に置き換えた場合の計算時間はO(dn2)である。
【００５９】
次に、語のベクトル表現を用いることによる、第２の手法の重み付き相関への拡張について、以下に示す。定義により重み付き相関は、1≦i≦2n-1について、数６に数１６を適用することで、
【００６０】
【数１８】
2018063596.tif 000020
ベクトル表現に置き換えて、内積についての畳み込み演算を得る。
【００６１】
そして、d次元におけるベクトル内積の積算に変形し、
【００６２】
【数１９】
2018063596.tif 000021
を得る。この数１８に対して、発明者は、積算する順番を入れ替えることで、
【００６３】
【数２０】
2018063596.tif 000022
を得る。
【００６４】
即ち、次元毎にすべてのずれ位置におけるベクトルの内積を算出した後、d次元全体で合計値を得ることで、数１９内の
【００６５】
【数２１】
2018063596.tif 000023
が畳み込み演算となる。後述にて、数２０は、配列[Zk，i]で表される。
【００６６】
図２に示す重みテーブル３を行列と考えた場合、各要素間の相関を表わす行列が疎であり、内積を用いても計算量が抑えられる。1≦i≦2n-1についての数２０の計算は、第１の手法と同様にO(nlogn)時間で行える。よって、重み付き相関C’(s，t)は次元数dを乗算したd×O(nlogn)時間で計算可能になる。
【００６７】
次に、重みの有無による文書間の相関計算の結果例について例示する。図４は、相関計算の結果例を示す図である。図４中、縦軸にベクトルの値を示し、横軸に文書内の要素の順番（i番目）を示している。上段には重み無し相関を示し、下段には重み付き相関を示している。更に、剽窃無、剽窃有、言い換えを含む剽窃有のそれぞれを上下で対応させて示している。
【００６８】
剽窃無の場合、いずれの場合も変動幅に突出する変化はない。単純なコピーによる剽窃有の場合、重み無し相関においてピーク６ａが示され、また、重み付き相関においてもピーク６ｂが出現している。
【００６９】
しかしながら、言い換えを含む剽窃有については、重み無し相関と重み付き相関とでは異なっている。重み無し相関では、ピークを特定することが困難であるのに対して、重み付き相関では、ピーク６ｃを特定できる。
【００７０】
本実施例では、重みテーブル３を用いた第１の手法と比べて、計算時間をO(dnlogn)時間に抑えて、重み付き相関の算出を実現することができる。
【００７１】
本実施例に係る文書比較装置１００は、図５に示すようなハードウェア構成を有する。図５は、文書比較装置のハードウェア構成を示す図である。図５において、文書比較装置１００は、コンピュータによって制御される情報処理装置であって、ＣＰＵ（Central  Processing  Unit）１１と、主記憶装置１２と、補助記憶装置１３と、入力装置１４と、表示装置１５と、通信Ｉ／Ｆ（インターフェース）１７と、ドライブ装置１８とを有し、バスＢに接続される。
【００７２】
ＣＰＵ１１は、主記憶装置１２に格納されたプログラムに従って文書比較装置１００を制御するプロセッサに相当する。主記憶装置１２には、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）等が用いられ、ＣＰＵ１１にて実行されるプログラム、ＣＰＵ１１での処理に必要なデータ、ＣＰＵ１１での処理にて得られたデータ等を記憶又は一時保存する。
【００７３】
補助記憶装置１３には、ＨＤＤ（Hard  Disk  Drive）等が用いられ、各種処理を実行するためのプログラム等のデータを格納する。補助記憶装置１３に格納されているプログラムの一部が主記憶装置１２にロードされ、ＣＰＵ１１に実行されることによって、各種処理が実現される。
【００７４】
入力装置１４は、マウス、キーボード等を有し、ユーザが文書比較装置１００による処理に必要な各種情報を入力するために用いられる。表示装置１５は、ＣＰＵ１１の制御のもとに必要な各種情報を表示する。入力装置１４と表示装置１５とは、一体化したタッチパネル等によるユーザインタフェースであってもよい。通信Ｉ／Ｆ１７は、有線又は無線などのネットワークを通じて通信を行う。通信Ｉ／Ｆ１７による通信は無線又は有線に限定されるものではない。  
文書比較装置１００によって行われる処理を実現するプログラムは、例えば、ＣＤ−ＲＯＭ（Compact  Disc  Read-Only  Memory）等の記憶媒体１９によって文書比較装置１００に提供される。
【００７５】
ドライブ装置１８は、ドライブ装置１８にセットされた記憶媒体１９（例えば、ＣＤ−ＲＯＭ等）と文書比較装置１００とのインターフェースを行う。
【００７６】
また、記憶媒体１９に、後述される本実施の形態に係る種々の処理を実現するプログラムを格納し、この記憶媒体１９に格納されたプログラムは、ドライブ装置１８を介して文書比較装置１００にインストールされる。インストールされたプログラムは、文書比較装置１００により実行可能となる。
【００７７】
尚、プログラムを格納する記憶媒体１９はＣＤ−ＲＯＭに限定されず、コンピュータが読み取り可能な、構造（structure）を有する１つ以上の非一時的（non-transitory）な、有形（tangible）な媒体であればよい。コンピュータ読取可能な記憶媒体として、ＣＤ−ＲＯＭの他に、ＤＶＤ（Digital  Versatile  Disk）ディスク、ＵＳＢメモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリであっても良い。
【００７８】
図６は、文書比較装置の機能構成例を示す図である。図６において、文書比較装置１００は、主に、ベクトル表現収集部４０と、文書比較部５０とを有する。ベクトル表現収集部４０と、相関取得部５０とは、ＣＰＵ１１が対応するプログラムを実行することで行われる処理により実現される。
【００７９】
また、記憶部１３０は、複数の文書７０の集合、文書７０ごとの語の列７２の集合、ベクトル表現ＤＢ７４、比較対象の２以上の文書８０、比較対象の文書８０ごとの語の列８２、重み付き相関結果８９等を記憶する。
【００８０】
ベクトル表現収集部４０は、予め収集し蓄積された文書７０の集合を用いて、文書の構成単位でベクトル表現に変換し、ベクトル表現ＤＢ７４に記憶する処理部であり、分解部４１と、変換部４２とを有する。文書の構成単位は、品詞ごとであっても良いし、文字又はフレーズごとであってもよい。構成単位は、文書の要素である。
【００８１】
分解部４１は、記憶部１３０から文書７０を読み込んで、読み込んだ文書７０を空白の検出、又は形態素解析により構成単位に分割して、語の列７２を生成する。文書７０ごとの語の列７２が記憶部１３０に記憶される。文書７０が英文の場合、空白により文書７０を分解してもよい。文書７０が和文の場合、形態素解析（mecab等）による分かち書きにより分解してもよい。
【００８２】
変換部４２は、語の列７２をベクトル表現に変換する。ベクトル表現として、出現頻度、出現位置、それらの組合等へ変換すればよい。出現頻度への変換は、tfidf、LSI等を用いればよい。また、出現位置への変換は、word2vec等を用いればよい。ベクトル表現は、ベクトル列で表される。
【００８３】
文書比較部５０は、比較対象の文書８０を重み付きで相関を計算し、重み付き相関結果８９を記憶部１３０に出力する。文書比較部５０は、更に、分解部５１と、変換部５２と、重み付き相関計算部５３とを有する。
【００８４】
分解部５１は、比較対象の２つの文書８０を入力して、それぞれの文書８０を構成単位で分割することで、２つの語の例７２を生成する。入力する文書８０は、３以上であってもよい。文書８０ごとに語の列７２が生成され記憶部１３０に記憶される。構成単位への分割は、ベクトル表現収集部４０での分解部４１と同様でよい。
【００８５】
変換部５２は、ベクトル表現ＤＢ７４を参照して、分解部５１によって得られた語の列８０を、それぞれベクトル列８４へと変換する。比較対象の各文書８０に対するベクトル列８４が記憶部１３０に記憶される。
【００８６】
重み付き相関計算部５３は、ベクトル列８４を用いて、構成単位ごとの２つのベクトルの内積を重みとして用いて、文書８０の相関を計算する。重み付き相関計算部５３は、畳み込み演算部５４をするように構成することで、計算時間を抑えることができる。得られた重み付き相関結果８９は、記憶部１３０に記憶される。
【００８７】
次に、処理フローについて説明する。先ず、ベクトル表現収集部４０によるベクトル表現収集処理の手順について説明する。図７は、ベクトル表現収集処理を説明するためのフローチャート図である。
【００８８】
図７において、ベクトル表現収集部４０では、分解部４１が文書７０の集合から１つの文書７０を読み込み（ステップＳ１０１）、読み込んだ文書７０を構成単位に分解して、語の列７２を作成する。文章７０が「吾輩は猫である」を例とすると、この文章７０は、「吾輩、は、猫、で、ある」の語の列７２で表される。語の列７２は記憶部１３０に記憶される。
【００８９】
語の列７２が作成されると、次に、変換部４２が、語の列７２の各語をベクトルに変換してベクトル列を生成し、ベクトル表現ＤＢ７４に蓄積する（ステップＳ１０３）。ベクトル表現ＤＢ７４には、語「吾輩」に対応付けてベクトル表現（１，０，１）、語「は」に対応付けてベクトル表現（０，１，２）、語「猫」に対応付けてベクトル表現（１，１，３、語「で」に対応付けてベクトル表現（０，２，４）、そして、語「ある」に対応付けてベクトル表現（０，３，５）が蓄積される。
【００９０】
ベクトル表現収集部４０は、文書７０の集合に未処理の文書７０があるか否かを判断する（ステップＳ１０４）。未処理の文章７０がある場合（ステップＳ１０４のＹＥＳ）、ベクトル表現収集部４０は、ステップＳ１０１へと戻り、上述同様の処理を繰り返す。一方、未処理の文章７０がある場合（ステップＳ１０４のＮＯ）、ベクトル表現収集部４０は、このベクトル表現収集処理を終了する。
【００９１】
文書７０を分解する構成単位は、文字であってもよい。この場合、英文の場合等での空白による分割、和文の場合等での分かち書きの必要がない。上記文章例「吾輩は猫である」の場合、［“吾”，“輩”，“は”，“猫”，“で”，“あ”，“る”］に分解される。分割した各文字をベクトルで示したベクトル列を生成しベクトル表現ＤＢ７４に蓄積する。
【００９２】
また、文字単位によるベクトル表現の獲得方法は、文書比較部５０においてベクトル表現ＤＢ７４を参照して行われる。この際には、語でなく文字単位で分割して、文字に対応付けられたベクトルを取得し、ベクトル列を作成する。
【００９３】
他の例として、構成単位は、フレーズであってもよい。フレーズを構成単位とする場合、フレーズを定義し、それに基づいた構文解析が必要となる。上記文章例「吾輩は猫である」の場合、［“吾輩は”，“猫である”］に分解される。
【００９４】
フレーズに対するベクトル表現を獲得する場合には、フレーズを構成する語のベクトル表現から計算すればよい。即ち、
β（“吾輩は”）＝（β（“吾輩”）＋β（“は”））／２
により得られる。ベクトル表現取得の前にフレーズを設定し、それらを語とみなしてベクトル表現を学習する。
【００９５】
次に、文書比較部５０による文書比較処理について説明する。図８は、文書比較処理を説明するためのフローチャート図である。図８における説明では、比較対象の文書８０をそれぞれ文書Ａ及び文書Ｂとする。
【００９６】
文書比較部５０において、分割部５１は、比較対象の文書Ａ及び文書Ｂとを読み込む（ステップＳ２０１）。そして、分割部５１は、文書Ａと文書Ｂとをそれぞれ構成単位で分割して、語の列Ａと語の列Ｂとを作成する（ステップＳ２０２）。
【００９７】
次に、変換部５２は、ベクトル表現ＤＢ７４を参照して、語の列Ａをベクトル列Ａに変換し、同様に、語の列Ｂをベクトル列Ｂに変換する（ステップＳ２０３）。
【００９８】
そして、重み付き相関計算部５３は、ベクトル列Ａとベクトル列Ｂとの相関を重み付けして算出する（ステップＳ２０４）。重み付き計算結果８９が記憶部１３０に出力される。重み付き計算結果８９が表示装置１５に表示されるようにしてもよい。図４の下段の重み付き相関のグラフが表示されることで、ユーザは、視覚的に類似又は剽窃の有無を知ることができる。
【００９９】
次に、重み付き相関の計算手順について説明する。重み付き相関の計算では、数１８による第１の計算方法と、計算量を抑えることができる数１９による第２の計算方法とがある。先ず、図８のステップＳ２０４において、第１の計算方法にて重み付き相関を計算する場合について説明する。第１の計算方法は、内積についての畳み込みを行うが、重み付き相関計算部５３に図６の畳み込み演算部５４は含まれない。
【０１００】
図９は、図８のステップＳ２０４を第１の計算方法の場合の重み付き相関計算処理を説明するためのフローチャート図である。図９において、重み付き相関計算部５３は、２つのベクトル列Ａ及びＢを読み込み（ステップＳ２１１）、変数i及び変数kを1に設定する（ステップＳ２１２）。変数ｉはずれ位置を示し、変数kはベクトルの次元を示す。
【０１０１】
ベクトル列Ａの各要素（構成単位のベクトル）は、
【０１０２】
【数２２】
2018063596.tif 000024
で表される。β(si)は、文書Ａのi番目の構成のベクトル表現を示す。また、ベクトル列Ｂの各要素は、
【０１０３】
【数２３】
2018063596.tif 000025
で表される。β(ti)は、文書Ｂのi番目の構成のベクトル表現を示す。
【０１０４】
変数i及び変数jの初期化後、重み付き相関計算部５３は、変数iが2n-1以下か否かを判断する（ステップＳ２１３）。
【０１０５】
一方、変数iが2n-1以下の場合（ステップＳ２１３のＹＥＳ）、重み付き相関計算部５３は、C’iをゼロに初期化する（ステップＳ２１４）。C’iは、ずれ位置iにおける重み付き相関の要素を示す変数である。
【０１０６】
そして、重み付き相関計算部５３は、変数jが1以上かつn以下であるか否かを判断する（ステップＳ２１５）。nは、文章Ａ及びＢの長さを示す。変数jが1以上かつn以下である場合（ステップＳ２１５のＹＥＳ）、重み付き相関計算部５３は、変数xjをゼロに初期化する（ステップＳ２１６）。変数xjは、すべてのベクトル次元ｄに対する内積を示す。
【０１０７】
そして、重み付き相関計算部５３は、変数kが1以上かつ次元ｄ以下であるか否かを判断する（ステップＳ２１７）。変数kが1以上かつ次元ｄ以下である場合（ステップＳ２１７のＹＥＳ）、重み付き相関計算部５３は、次元kのベクトルの内積ykを求め（ステップＳ２１８）、内積ykを変数xjに加算する（ステップＳ２１９）。そして、重み付き相関計算部５３は、ステップＳ２１７へと戻り上述同様の処理を繰り返し、次元ｄまでのベクトルの内積を全て加算する。
【０１０８】
一方、変数kが1以上かつ次元ｄ以下でない場合（ステップＳ２１７のＮＯ）、重み付き相関計算部５３は、ずれ位置iの相関C’iに変数xjの値を加算して（ステップＳ２２０）、ステップＳ２１５へと戻り、上述同様の処理を繰り返すことでずれ位置iに対する重み付き相関値を得る。
【０１０９】
一方、変数jが1以上かつn以下でない場合（ステップＳ２１５のＮＯ）、重み付き相関計算部５３は、ずれ位置iに対応付けて相関C’iの値を重み付き相関結果８９に記録する（ステップＳ２２１）。ステップＳ２１３へと戻り、ダミーの語の列の長さを含めてずれ位置iにおける重み付き相関値を取得するため、上記同様の処理を繰り返す。
【０１１０】
そして、最終的に、変数iが2n-1以下でないと判断した場合（ステップＳ２１３のＮＯ）、すべてのずれ位置に対する重み付き相関を得られたため、重み付き相関計算部５３は、すべてのずれ位置の重み付き相関値を示す重み付き相関結果８９を記憶部１３０に出力して（ステップＳ２２２）、重み付き相関計算処理を終了する。
【０１１１】
図１０は、図８のステップＳ２０４を第２の計算方法の場合の重み付き相関計算処理を説明するためのフローチャート図である。図１０において、重み付き相関計算部５３は、２つのベクトル列Ａ及びＢを読み込み（ステップＳ２３１）、変数i及び変数kを1に設定する（ステップＳ２３２）。変数iはずれ位置を示し、変数kはベクトルの次元を示す。
【０１１２】
ベクトル列Ａの各要素（構成単位のベクトル）は数２１で表され、ベクトル列Ｂの各要素は数２２で表されるのは、図９で説明した通りである。変数i及び変数jの初期化後、重み付き相関計算部５３は、すべてのC’i（１≦ｉ≦２ｎ−１）をゼロに初期化する（ステップＳ２３３）。
【０１１３】
重み付き相関計算部５３は、変数kが1以上かつ次元ｄ以下であるか否かを判断する（ステップＳ２３４）。変数kが1以上かつ次元ｄ以下である場合（ステップＳ２３４のＹＥＳ）、重み付き相関計算部５３は、畳み込み演算を行う（ステップＳ２３５）。配列[Zk，i]（数２０）が求められる。
【０１１４】
重み付き相関計算部５３は、変数iが1以上かつ2n-1であるか否かを判断する（ステップＳ２３６）。変数iが1以上かつ2n-1である場合（ステップＳ２３６のＹＥＳ）、重み付き相関計算部５３は、畳み込み演算結果をずれ位置iの相関C’iに加算する（ステップＳ２３７）。配列[Zk，i]の値が相関C’iに蓄積される。変数iが2n-1まで、重み付き相関計算部５３は、相関C’iの値を加算する。
【０１１５】
変数iが1以上かつ2n-1でない場合（ステップＳ２３６のＮＯ）、重み付き相関計算部５３は、ずれ位置iの相関C’iを重み付き相関結果８９に記録して（ステップＳ２３８）、ステップＳ２３４へと戻り、上述同様の処理を繰り返す。
【０１１６】
一方、変数kが1以上かつ次元ｄ以下でない場合（ステップＳ２３４のＮＯ）、すべてのずれ位置に対する重み付き相関を得られたため、重み付き相関計算部５３は、すべてのずれ位置の重み付き相関値を示す重み付き相関結果８９を記憶部１３０に出力して（ステップＳ２３９）、重み付き相関計算処理を終了する。
【０１１７】
上述した第２の計算方法では、文書８０間の重み付き相関を文書サイズの準線形時間で取得可能である。
【０１１８】
また、第１の計算方法も第２の計算方法も同様に、重みをベクトルの内積で表現することで文書８０間の相関を得るものであるが、図９に示す第１の計算方法では、ステップＳ２１３、ステップＳ２１５、及びステップＳ２１７の判断により、繰り返し処理が３重構造を示す。よって、
(2n-1)  ×  n  ×  d  回
の繰り返し処理を行うことになる。
【０１１９】
一方、図１０に示す第２の計算方法では、畳み込み演算へと変形させたことで、ステップ２３３での単独の繰り返し処理と、ステップＳ２３４及びＳ２３６による２重構造の繰り返し処理で行われる。よって
(2n-1)  +  (2n-1)  ×  d  回
の繰り返し処理で行うことができ、第１の計算方法よりも計算処理の負担をより軽減することができる。
【０１２０】
ここで、文書８０の実データのサイズについて、概ねの範囲を示す。
【０１２１】
σについて、
・２バイト文字：６５５３６
・単一言語の語録数：数千〜数万
nについて
・ニュース記事：数百〜
・学術論文（語の数）：数千〜数万
dについて
・word2vecのデフォルト値：２００
文書データより分散表現（低次元のベクトル表現）を得るツールとして、word2vecを一例とした場合の次元数である。ベクトルの近さが概ね語義の近さを表わす。文書分類等で精度良く類似を判定できる。
【０１２２】
このようにd<<σであるため、既存の第１の手法（重み無し相関）のO(n2(logσ)2)時間に比べ、本実施例における重み付き相関であってもO(dnlogn)時間であることから、大幅に計算時間を短縮できる。
【０１２３】
また、本実施例では、重み付き相関をえることができるため、図４の下段に示すように、重み無し相関では検出の困難な言い換えを含む剽窃あることを検出できる。より精度良く、文書間の類似を評価可能である。
【０１２４】
上述した実施例において、分解部５１は分離部に相当し、重み付き相関計算部５３は算出部に相当する。
【０１２５】
本発明は、具体的に開示された実施例に限定されるものではなく、特許請求の範囲から逸脱することなく、主々の変形や変更が可能である。
【０１２６】
以上の実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
比較対象の複数の文書それぞれを複数の要素に分離し、
前記複数の文書の全てのずれ位置における、前記複数の要素それぞれの、該要素間の重み付けを含めた相関値を、該要素の特徴をベクトルで表すことで、各要素に対応付けた該ベクトルの内積とした離散フーリエ変換により算出する
処理をコンピュータに行わせる文書比較プログラム。
（付記２）
前記コンピュータに、
前記ベクトルの次元ごとに、前記複数の文書の前記各要素に対応付けた前記ベクトルの内積とした前記離散フーリエ変換により畳み込み演算を行って、該次元の各ずれ位置における演算値を取得し、
各ずれ位置で前記ベクトルの次元ごとで得た演算値を合計する
処理を行わせる付記１記載の文書比較プログラム。
（付記３）
前記コンピュータに、
前記複数の文書を、品詞、文字、フレーズ、又は空白を区切りとした単語のいずれかを要素として分離させる
ことを特徴とする付記１又は２記載の文書比較プログラム。
（付記４）
前記コンピュータに、
複数のサンプル文書から分離した要素ごとに特徴を表わす前記ベクトルを記憶した記憶部を参照して、前記複数の文書それぞれの各要素を、特徴を表わす前記ベクトルに変換する処理を行わせる
ことを特徴とする付記１乃至３のいずれか一項記載の文書比較プログラム。
（付記５）
比較対象の複数の文書それぞれを複数の要素に分離し、
前記複数の文書の全てのずれ位置における、前記複数の要素それぞれの、要素間の重み付けを含めた相関値を、該要素の特徴をベクトルで表すことで、各要素に対応付けた該ベクトルの内積とした離散フーリエ変換により算出する
処理をコンピュータが行う文書比較方法。
（付記６）
比較対象の複数の文書それぞれを複数の要素に分離する分離部と、
前記複数の文書の全てのずれ位置における、前記複数の要素それぞれの、要素間の重み付けを含めた相関値を、該要素の特徴をベクトルで表すことで、各要素に対応付けた該ベクトルの内積とした離散フーリエ変換により算出する算出部と
を有する文書比較装置。
【符号の説明】
【０１２７】
１１          ＣＰＵ
１２          主記憶装置
１３          補助記憶装置
１４          入力装置
１５          表示装置
１７          通信Ｉ／Ｆ
１８          ドライブ装置
１９          記憶媒体
４０          ベクトル表現収集部
４１          分割部
４２          変換部
５０          文書比較部
５１          分割部
５２          変換部
５３          重み付き相関計算部
５４          畳み込み演算部
７０、８０    文章
７２、８２    語の列
７４          ベクトル表現ＤＢ
８４          ベクトル列
８９          重み付き相関結果
【図１】
2018063596.tif 000026
【図２】
2018063596.tif 000027
【図３】
2018063596.tif 000028
【図４】
2018063596.tif 000029
【図５】
2018063596.tif 000030
【図６】
2018063596.tif 000031
【図７】
2018063596.tif 000032
【図８】
2018063596.tif 000033
【図９】
2018063596.tif 000034
【図１０】
2018063596.tif 000035