(57)【要約】【課題】本発明の課題は、文字または文字列の種類が増大した場合であっても計算量を抑えることを目的とする。【解決手段】上記課題は、複数の文書データに含まれる文字または文字列ごとに該複数の文書データをベクトル化した複数のベクトルを生成し、前記複数のベクトルのそれぞれについてフーリエ変換した結果の要素ごとの積を算出し、前記文字または文字列それぞれに対し、前記積を前記要素ごとに加算した合算ベクトルを生成し、前記合算ベクトルより、フーリエ逆変換を用いて、前記複数の文書データ間の相関値を生成する処理をコンピュータが行う類似度算出プログラムにより達成される。【選択図】図４
2018085051.tif 000002
【特許請求の範囲】
【請求項１】
複数の文書データに含まれる文字または文字列ごとに該複数の文書データをベクトル化した複数のベクトルを生成し、
前記複数のベクトルのそれぞれについてフーリエ変換した結果の要素ごとの積を算出し、
前記文字または文字列それぞれに対し、前記積を前記要素ごとに加算した合算ベクトルを生成し、
前記合算ベクトルより、フーリエ逆変換を用いて、前記複数の文書データ間の相関値を生成する、
処理をコンピュータに行わせる類似度算出プログラム。
【請求項２】
前記コンピュータに、
前記複数の文書を、品詞、文字、フレーズ、又は空白を区切りとした単語のいずれかで分割し、分割した単語ごとに、前記複数の文書データの各ずれ位置における該単語との一致または不一致を前記要素の値として前記複数のベクトルを生成させることを特徴とする請求項１記載の類似度算出プログラム。
【請求項３】
前記要素は、前記複数の文書データ間のずれ位置に相当することを特徴とする請求項１又は２記載の類似度算出プログラム。
【請求項４】
複数の文書データに含まれる文字または文字列ごとに該複数の文書データをベクトル化した複数のベクトルを生成し、
前記複数のベクトルのそれぞれについてフーリエ変換した結果の要素ごとの積を算出し、
前記文字または文字列それぞれに対し、前記積を前記要素ごとに加算した合算ベクトルを生成し、
前記合算ベクトルより、フーリエ逆変換を用いて、前記複数の文書データ間の相関値を生成する、
処理をコンピュータが行う類似度算出方法。
【請求項５】
複数の文書データに含まれる文字または文字列ごとに該複数の文書データをベクトル化した複数のベクトルを生成するベクトル変換部と、
前記複数のベクトルのそれぞれについてフーリエ変換した結果の要素ごとの積を算出する第１変換部と、
前記文字または文字列それぞれに対し、前記積を前記要素ごとに加算した合算ベクトルを生成する加算部と、
前記合算ベクトルより、フーリエ逆変換を用いて、前記複数の文書データ間の相関値を生成する第２変換部と、
を有する類似度算出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似度算出プログラム、類似度算出方法、および類似度算出装置に関する。
【背景技術】
【０００２】
近年、文書間の比較を行い、類似箇所を抽出することが行われている。例えば、２つの文章の文字列を行と列に配置し、文字間の類似度に基づいて、文字列の類似箇所を抽出する際に、終点からの不一致又は読み飛ばしが連続する文字数を制限し、抽出をリセットして再開することで、代表的な局所対応を網羅的に抽出する技術が知られている。
【０００３】
また、文書内の文字列に対して検索文字列との一致若しくは類似する文字列の分布状態及びその一致度を表示する技術等が提案されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１２−５９１００号公報
【特許文献２】特開平７−１４６８７２号公報
【特許文献３】特開平８−２４９４４５号公報
【非特許文献】
【０００５】
【非特許文献１】M．J．Fischer  and  M．S．Paterson:String-matching  and  other  products， Complexity  of  Computation  (Proceedings  of  the  SIAM-AMS  Applied  Mathematics  Symposium， New  York， 1973)，pp．113-125，1974
【非特許文献２】D．Gusfield:  Algorithms  on  Strings，Trees  and  Sequences:  Computer  Science  and  Computational  Biology，Cambridge  University  Press，1997
【非特許文献３】M．J．Atallah  et  al．:A  randomized  algorithm  for  approximate  string  matching．Algorithmica，29:468-486，2001
【非特許文献４】K．Baba  et  al．:A  Note  on  Randomized  Algorithm  for  String  Matching  with  Mismatches，Nordic  Journal  of  Computing，10(1):2-12，2003
【非特許文献５】T．Schoenmeyr  and  D．Yu-Zhang:  FFT-based  Algorithms  for  the  String  Matching  with  Mismatches  Problem，  Journal  of  Algorithms，57:130-139，2005
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述した技術では、２文書間で互いに対応する位置での類似度を算出、検索対象の文書に対して与えられた検索文字列に一致若しくは類似する文字列を抽出等を行う技術である。したがって、２文書に対してすべての位置ずれで文書間の類似を算出する場合、文書の文字の種類の多さや文書の区切り等で抽出した文字列の長さに応じて処理負担が大きくなるといった問題がある。
【０００７】
したがって、１つの側面では、本発明は、文字単位の比較により文書間の比較を行う際の計算量を抑えることを目的とする。
【課題を解決するための手段】
【０００８】
一態様によれば、複数の文書データに含まれる文字または文字列ごとに該複数の文書データをベクトル化した複数のベクトルを生成し、前記複数のベクトルのそれぞれについてフーリエ変換した結果の要素ごとの積を算出し、前記文字または文字列それぞれに対し、前記積を前記要素ごとに加算した合算ベクトルを生成し、前記合算ベクトルより、フーリエ逆変換を用いて、前記複数の文書データ間の相関値を生成する処理をコンピュータが行う類似度算出プログラムが提供される。
【０００９】
また、上記課題を解決するための手段として、類似度算出方法および類似度算出装置とすることもできる。
【発明の効果】
【００１０】
文字単位の比較により文書間の比較を行う際の計算量を抑えることができる。
【図面の簡単な説明】
【００１１】
【図１】位置ずれを説明するための図である。
【図２】文書間の相関の例を示す図である。
【図３】計算と計算時間との関係を説明するための図である。
【図４】計算方法の概念図を示す図である。
【図５】計算量の削減を説明するための図である。
【図６】類似度算出装置のハードウェア構成を示す図である。
【図７】類似度算出装置の機能構成例を示す図である。
【図８】２文書間の相関を求める第１の類似算出処理を説明するためのフローチャートである。
【図９】図８のフローチャートでの処理例を示す図である。
【図１０】１対Ｎ相関を求める第２の類似算出処理を説明するためのフローチャートである。
【図１１】語彙数に対する実行時間の比較結果を示す図である。
【図１２】文書長に対する実行時間の比較結果を示す図である。
【図１３】文書中の語彙数と処理時間の比較結果を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態を図面に基づいて説明する。先ず、２つの文書のそれぞれの文字列を入力とし、すべての位置ずれについての文字の一致の数（相関）を計算する問題を考察する。「相関」とは、すべての位置ずれで対応させた語との一致数をいう。
【００１３】
文章間の相関を求める関連技術として、相関を求める高速アルトリズムFFT(Fast  Fourier  Transform)-based  Algorithmが存在する。FFTは高速フーリエ変換の略である。
【００１４】
FFT-based  Algorithmの処理は、O(nlogn)時間の畳み込み演算をσ回繰り返す。ここで、σは文字又は文字列の種類の数を示し、nは各文章の文字列の長さを示す。
【００１５】
次に、相関の計算時間について考察する。相関計算の例として、語の比較を順に行う単純計算と、FFT-Based  Algorithmを用いた計算量について比較する。
【００１６】
基本的に、σ≦nと見なせる場合、FFT-Based  Algorithmが単純計算より高速である。即ち、σが一定で小さい場合、O(n2)とO(nlogn)の比較と見なせる。しかしながら、σが不定で小さい場合、O(n2logσ)に対するO(σnlogσ)の利点が小さい。即ち、σが大きい場合は想定されておらず、一定で小さいσを想定し、計算時間をO(nlogn)として扱っている（非特許文献１、２）。そのため、FFTの実行回数が多くなるという問題がある。
【００１７】
この問題に対して、畳み込みの繰り返しからk回分の結果だけを使って近似することが提案されている（非特許文献３、４、５）。しかしがら、畳み込み演算を一つの処理単位として扱っているため、畳み込み演算の処理回数の削減に留まっている。
【００１８】
さらに、このような近似的手法（非特許文献３、４、５）では、厳密な値でなく近似値を出力している。長さnの文書について、k回の繰り返しによる相関ciの推定値の分散は(n-ci)/kで表される。近似値が正しい値ciに対して散らばる程度を表わす。大きなnについて誤差が大きく、長い文書に適していない。さらに、小さなciについて誤差が大きい。相関のうち小さい値の推定値の精度が低いことを示す。つまり、移動平均の計算や相関全体をベクトルとして機械学習等に用いる場合に適用できない。
【００１９】
従来より、畳み込み演算は信号処理等の分野で一般的な概念である。信号処理では、データは、送受信間の通信で定められるデータ長を処理単位として処理されるためσが小さい。
【００２０】
また、畳み込み演算は、プログラミング言語においても既存の関数を利用できる。このような開発環境において、畳み込み演算内での処理負荷について詳細な解析がなさることがなかった。学会誌、学術論文等の文書の長さは、通信におけるデータ長よりはるかに大きい。
【００２１】
本実施例では、σが大きな場合に、更なる処理の高速化を実現し、近年の文書間の比較等での大きなσの大量データに対して相関を求める需要に対応する。
【００２２】
ここで、相関の計算時間における課題は、現実的な実行時間の削減である。具体的には、σnlogσに対する係数部分、即ち、FFTの実行回数を削減することである。発明者は、畳み込み演算が、離散フーリエ変換と逆離散フーリエ変換の処理により行われることに着目し、大きなσの大量データを扱う場合の相関の計算処理の高速化を実現した。大きなσの大量データを、以下の説明では、文書を例として説明する。
【００２３】
２文書s，t間の相関を求める場合、２文書s，tの各文字列内で連続した２文字以上で類似する類似部分の位置は必ずしも同一位置ではない。類似部分が出現する位置がずれている場合についても考慮する必要がある。相関で考慮される位置ずれについて説明する。
【００２４】
まず、２つの文字列間の相関計算に係る表記を以下に定義する。
【００２５】
【数１】
2018085051.tif 000003
文書sと文書tの文字は、長さnの文字列全体からなる集合Σnの要素として表される。
【００２６】
【数２】
2018085051.tif 000004
文書sと文書tとの相関c(s，t)は、2n-1次元ベクトルで表され、i番目の要素は、
【００２７】
【数３】
2018085051.tif 000005
で表される。ただし、
【００２８】
【数４】
2018085051.tif 000006
について、
【００２９】
【数５】
2018085051.tif 000007
のように文字列を数式のように表わすことで、範囲外の形式的な比較のためにダミーの語を付加することを表現する。このようにすることで、位置ずれを考慮して相関を算出できる。
【００３０】
図１は、位置ずれを説明するための図である。図１では、文書sの文書tに対する語の位置ずれを考慮するために、文書tの前後に、文書sにも文書tにも属さないダミーの語を付加する概念図を示している。
【００３１】
文章sを１語ずつずらして、ずらした位置における文書tの１語との相関を算出する。文書tに対して、文書sでは語順を変えてある場合がずれ位置に相当する。１語ずらすごとに相関を算出することで、ずれごとの相関c1，  c2，・・・，  c2n-1を得る。
【００３２】
全ての位置ずれを考慮した相関c(s，t)は、全ての位置ずれでの文字の一致の数に相当するとした場合、単純な計算ではO(n2)回の文字比較が行われる。ここで、１回の文字比較の時間はlogσに依存する。
【００３３】
図２は、文書間の相関の例を示す図である。図２では、文章sは文字列“abbacab”であり、文書tは文字列“ababbac”である場合の相関の例を示している。図２において、ダミーの語xは空欄で表している。
【００３４】
文書tの前後にn-1後のダミーを付加した文書t’の先頭に文書sの先頭を合せて、一語ずつ文書sをずらして一致する文字数をカウントする。この例では、文書t’の先頭に文書sの先頭を合せた場合には、文書sと文書tとに一致する文字が存在しない。従って、相関c1は0となる。一語ずらすと、文書sの末尾２文字と文書tの先頭２文字とが一致する。従って、相関c2は2となる。
【００３５】
更に１語ずらした相関c3は０となる。順に、相関c4は３、相関c5は１、相関c6は２、相関c7は３、相関c8は１、相関c9は５、相関c10は１、相関c11は０、相関c12は１、そして、相関c13は０となる。
【００３６】
ここで、文字又は文字列の種類毎に行われるFFTによる畳み込みの計算について説明する。２つのn次元ベクトルuとvとの巡回畳み込みrは、
【００３７】
【数６】
2018085051.tif 000008
で表される。ただし、-n+1≦i≦0についてはvi=vn+iである。
【００３８】
R，U，Vをそれぞれr，u，vの離散フーリエ変換としoを要素ごとの積とすると、
【００３９】
【数７】
2018085051.tif 000009
で表される。このことから、rは、uとvとからFFTにより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の概要について説明する。FFT-based  Algorithmでは、文字を数値化し、文字列間の相関をベクトルの畳み込みにより計算する。そうすることで、文字列全体の集合Σ内のある文字aを1、それ以外を0に置き換えると、文字aの一致のみを考慮した相関を畳み込み演算で算出でき、O(nlogn)時間で計算可能である。文書から数値列への置き換えはO(n)時間である。また、乗算で一致又は不一致を表現できるため、畳み込み演算が適用可能である。
【００４３】
文字列全体の集合Σ内の要素である文字又は文字列の種類ごとに、O(nlogn)時間の畳み込み演算を行うため、文字又は文字列の種類の数のσ回繰り返される。そして、ベクトルの要素ごとの和をとることで相関を算出する。即ち、ある位置ずれでの相関ciが求まる。
【００４４】
より具体的に、FFT-based  Algorithmの計算式を以下に示す。
【００４５】
【数８】
2018085051.tif 000010
について、φaはaを1、それ以外を0に写す関数とし、定義（数３）より、n≦i≦2n-1について、
【００４６】
【数９】
2018085051.tif 000011
と表される。ここで、加算の順序を入れ替えて、
【００４７】
【数１０】
2018085051.tif 000012
とする。
【００４８】
（ua，1，  ua，2，．．．，  ua，2n-1）と（va，1，  va，2，．．．，  va，2n-1）とを、
【００４９】
【数１１】
2018085051.tif 000013
である。数１１では、1≦i≦nのときには、片方を反転させ、n≦i≦2n-1のときには、0を埋める。2n-1次元ベクトルとすると、数１０は、
【００５０】
【数１２】
2018085051.tif 000014
で表される。数１２内の
【００５１】
【数１３】
2018085051.tif 000015
は巡回畳み込み演算である。
【００５２】
類似部分の位置ずれを考慮した場合、文字又は文字列の種類（文字列全体の集合Σ内の要素）の数分の畳み込み演算を繰り返すことになり、計算時間が長くなる。
・１回の畳み込み演算に対して、２回のFFT、１回のベクトルの要素ごとの積、１回の逆FFTが行われる。ここで、逆FFTの計算時間はFFTの計算時間に相当すると考えられる。
・それぞれの１回の計算時間は、FFTがO(nlogn)時間、要素ごとの積はO(n)時間であり、FFTが支配的である。
・従って、１回の相関の計算で、FFTが3σ回必要であることが分かる。
【００５３】
また、畳み込み演算の繰り返しの回数σは、アルファベットサイズσに対する論理的な最小値である。
【００５４】
文字又は文字列の種類ごとに畳み込み演算を行い、その結果を集約する関連技術に対して、発明者は、畳み込み演算の最後の処理であるフーリエ変換（逆FFT）の前に集約することで、フーリエ変換の回数を削減することを見出した。フーリエ変換の回数を削減するために、発明者が着目した計算式の変形について説明する。
【００５５】
raをuaとvaの巡回畳み込みとすると、相関c(s，t)は、
【００５６】
【数１４】
2018085051.tif 000016
のベクトルから得られる。このベクトルを
【００５７】
【数１５】
2018085051.tif 000017
と表示することにする。そして、fを離散フーリエ変換、Ra=f(ra)とすると、数１５は、
【００５８】
【数１６】
2018085051.tif 000018
と変形できる。数１６の右辺より、ベクトルの要素ごとの加算後に逆FFTを行なえばよいことが分かる。要素ごとの加算後の逆FFTは、１回のFFTと見なせる。
【００５９】
図４は、計算方法の概念図を示す図である。図４において、畳み込み演算２ｐと、畳み込み演算２ｐを行わない単純な方法の計算部分は、集合Σの要素（文字又は文字列の種類）ごとに処理が繰り返される部分である。即ちσ回数繰り返される。その後、得られたσ個のベクトルの要素ごとに値を合算して、文書sと文書tとの相関c(s，t)が得られる。
【００６０】
関連技術において、畳み込み演算２ｐでは、FFTの計算が、離散フーリエ変換時に2σ回行われ、逆離散フーリエ変換時にσ回行われるため、合計3σ回行われる。
【００６１】
一方、本実施例では、畳み込み演算２ｐのうち、逆FFTの実行前に、ベクトルの要素ごとの加算を行い、その結果に対して逆FFTを行うことで、逆FFTの計算回数をσ回から１回に削減する。本実施例では、σが大きいほど効果を奏し、関連技術に比べて、約３分の２の時間で２文書間の相関を取得できる。
【００６２】
また、σが小さい場合、応用の観点から各文字での相関が得ることが必要となる場合があるが、σが大きい場合、特定文字での相関が必要であっても、その他の文字として大きなσを考える必要があり、その観点において、本実施例がより適していると言える。
【００６３】
図４における関連技術と本実施例の計算例を図５に示し、計算量の削減について更に説明する。図５は、計算量の削減を説明するための図である。
【００６４】
図５では、文章sは文字列“abca”であり、文書tは文字列“abcb”である場合の２文書s，t間の相関c(s，t)を求めるまでの計算例を示す。左にベクトルの例を示し、右にベクトルの離散フーリエ変換の例を示す。
【００６５】
文書s，tに存在する語の種別毎にベクトルへと変換する。文書s，tには３つの文字a、bおよびcが存在する。まず、文書s，tのそれぞれにおいて、文字a、b、cごとに、一致する箇所に1を示し、一致しない箇所を0で示したベクトルに変換する。文書sはベクトル
ua=(1，0，0，1)、
ub=(0，1，0，0)、
uc=(0，0，1，0)
に変換され、文書tはベクトル
va=(0，0，0，1)、
vb=(1，0，1，0)、
vc=(0，1，0，0)
に変換される。
【００６６】
文書sに関して、ベクトルua、ub、ucのそれぞれを離散フーリエ変換し、
【００６７】
【数１７】
2018085051.tif 000019
同様に、文書tに関して、ベクトルva、vb、vcのそれぞれを離散フーリエ変換し、
【００６８】
【数１８】
2018085051.tif 000020
を得る。即ち、離散フーリエ変換が６（2×σ）回行われる。
【００６９】
次に、UxとVxの要素ごとの積Rx（x=a，b，c）を求める。従って、
【００７０】
【数１９】
2018085051.tif 000021
を得る。
【００７１】
関連技術では、各Ra、Rb、Rcについて、逆離散フーリエ変換を行うことで、
ra=(0，0，0，1)、
rb=(1，0，1，0)、
rc=(0，1，0，0)
を得る。関連技術では、逆離散フーリエ変換が３（σ）回行われる。その後、要素ごとの和を求めて、２つの文書sと文書tの相関値
(0，1，0，3，0，0，1)
を得る。
【００７２】
一方、本実施例では、UxとVxの要素ごとの積Rx（x=a，b，c）を求めた後、要素ごとの逆離散フーリエ変換を行わずに、要素ごとの和を求める。求めた
【００７３】
【数２０】
2018085051.tif 000022
に対して、逆離散フーリエ変換を行なえば、関連技術と同様に、相関値
(0，1，0，3，0，0，1)
を得る。即ち、１回の逆離散フーリエ変換で、２つの文書sと文書tの相関を得ることができる。この例では、σは3であるため、逆離散フーリエ変換に係る処理時間は１／３になる。全体の処理として、関連技術ではFFTの回数が9σ（=6σ+3σ）、即ち、２７回行われたのに対して、本実施例ではFFTの回数が7σ（=6σ+σ）、即ち、２１回に削減される。σ=3の場合で説明したが、σが大きい程、本実施例の効果は大きい。
【００７４】
次に、上述した処理を行う類似度算出装置１００（図６）のハードウェア構成について説明する。図６は、類似度算出装置のハードウェア構成を示す図である。図６において、類似度算出装置１００は、コンピュータによって制御される情報処理装置であって、ＣＰＵ（Central  Processing  Unit）１１と、主記憶装置１２と、補助記憶装置１３と、入力装置１４と、表示装置１５と、通信Ｉ／Ｆ（インターフェース）１７と、ドライブ装置１８とを有し、バスＢに接続される。
【００７５】
ＣＰＵ１１は、主記憶装置１２に格納されたプログラムに従って類似度算出装置１００を制御するプロセッサに相当する。主記憶装置１２には、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）等が用いられ、ＣＰＵ１１にて実行されるプログラム、ＣＰＵ１１での処理に必要なデータ、ＣＰＵ１１での処理にて得られたデータ等を記憶又は一時保存する。
【００７６】
補助記憶装置１３には、ＨＤＤ（Hard  Disk  Drive）等が用いられ、各種処理を実行するためのプログラム等のデータを格納する。補助記憶装置１３に格納されているプログラムの一部が主記憶装置１２にロードされ、ＣＰＵ１１に実行されることによって、各種処理が実現される。
【００７７】
入力装置１４は、マウス、キーボード等を有し、ユーザが類似度算出装置１００による処理に必要な各種情報を入力するために用いられる。表示装置１５は、ＣＰＵ１１の制御のもとに必要な各種情報を表示する。入力装置１４と表示装置１５とは、一体化したタッチパネル等によるユーザインタフェースであってもよい。通信Ｉ／Ｆ１７は、有線又は無線などのネットワークを通じて通信を行う。通信Ｉ／Ｆ１７による通信は無線又は有線に限定されるものではない。  
類似度算出装置１００によって行われる処理を実現するプログラムは、例えば、ＣＤ−ＲＯＭ（Compact  Disc  Read-Only  Memory）等の記憶媒体１９によって類似度算出装置１００に提供される。
【００７８】
ドライブ装置１８は、ドライブ装置１８にセットされた記憶媒体１９（例えば、ＣＤ−ＲＯＭ等）と類似度算出装置１００とのインターフェースを行う。
【００７９】
また、記憶媒体１９に、後述される本実施の形態に係る種々の処理を実現するプログラムを格納し、この記憶媒体１９に格納されたプログラムは、ドライブ装置１８を介して類似度算出装置１００にインストールされる。インストールされたプログラムは、類似度算出装置１００により実行可能となる。
【００８０】
尚、プログラムを格納する記憶媒体１９はＣＤ−ＲＯＭに限定されず、コンピュータが読み取り可能な、データとしての構造（structure）を有する１つ以上の非一時的（non-transitory）な、有形（tangible）な媒体であればよい。コンピュータ読取可能な記憶媒体として、ＣＤ−ＲＯＭの他に、ＤＶＤ（Digital  Versatile  Disk）ディスク、ＵＳＢメモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリであっても良い。
【００８１】
類似度算出装置１００は、ラップトップ、タブレット端末等であってもよい。その場合、記憶媒体１９は、ＳＤ（Secure  Digital）メモリカード等であり、ドライブ装置１８は、ドライブ装置１８にセットされた記憶媒体１９と類似度算出装置１００とのインターフェースを行う。
【００８２】
図７は、類似度算出装置の機能構成例を示す図である。図７において、類似度算出装置１００は、ベクトル変換部６１と、離散フーリエ変換部６２と、要素乗算部６３と、要素加算部６４と、逆離散フーリエ変換部６５とを有する。記憶部１３０は、文書データ７０、ベクトルデータ７１、変換後ベクトルデータ７２、積ベクトルデータ７３、合算ベクトル７４、相関結果７９等を記憶する。
【００８３】
ベクトル変換部６１は、記憶部１３０に記憶されている文書データ７０の文書s、t等をそれぞれベクトルに変換する。ベクトルへの変換方法は、上述したように、文字の種別ごとに一致を１、不一致を０で表わせばよい。ベクトル変換部６１によって得られたベクトルu、v等を含むベクトルデータ７１が記憶部１３０に記憶される。
【００８４】
離散フーリエ変換部６２は、記憶部１３０に記憶されたベクトルデータ７１のベクトルu、v等をそれぞれに対して離散フーリエ変換を実行する。離散フーリエ変換は、（文書数）×（文字又は文字列の種類の数σ）の回数分実行される。離散フーリエ変換後のベクトルU、V等を含む変換後ベクトルデータ７２が記憶部１３０に記憶される。
【００８５】
要素乗算部６３は、変換後ベクトルデータ７２内の全てのベクトルを対象に、要素ごとの積（アダマール積）を求める。全ての文字の種類のそれぞれに対して得られたベクトルRを含む積ベクトルデータ７３が記憶部１３０に記憶される。
【００８６】
要素加算部６４は、積ベクトルデータ７３の文字又は文字列の種類毎のベクトルRに対して、要素ごとの和を求めることで、合算ベクトル７４を得る。得られた合算ベクトル７４は、記憶部１３０に記憶される。
【００８７】
逆離散フーリエ変換部６５は、合算ベクトル７４に対して、逆離散フーリエ変換を行って、文書s、t等に関する相関値を示す相関結果７９を取得する。相関結果７９は記憶部１３０に記憶される。また、相関結果７９を表示装置１５に表示するようにしてもよい。
【００８８】
文書データ７０は、文書s、t等の２以上の文書を含み、ユーザによって与えられる。ユーザは、予め相関を検証する対象文書として複数の文書を用意し、特定文書（例えば、オリジナル文書）を入力とし類似度算出装置１００に与えてもよい。
【００８９】
ベクトルデータ７１は、文書データ７０の各文書s、t等ごとにベクトル変換した結果を示す。例えば、文書sがベクトルuに相当し、文書tがベクトルvに相当する。他の文書に対しても同様に変換されたベクトルが示される。本実施例において、「文書」は種々のデータファイルに相当する。
【００９０】
変換後ベクトルデータ７２は、文書s、t等のそれぞれに対してベクトルu、v等を含み、各ベクトルu、v等は、文字の種類ごとに存在する。変換後ベクトルデータ７２は、（文書数）×（文字の種類の数σ）の数のベクトルを含む。
【００９１】
積ベクトルデータ７３は、文字又は文字列の種類ごとに、要素ごとの積を示すベクトルRを示す。積ベクトルデータ７３は、文字又は文字列の種類の数のベクトルRを含む。特定文書に対して複数の対象文書で相関を算出する１対Ｎ相関の場合には、各対象文書ごとに、文字の種類の数のベクトルRが生成される。
【００９２】
合算ベクトル７４は、文字の種類ごとのベクトルRに対して要素ごとの和を示す。２文書s、t間の相関に対しては、１の合算ベクトル７４が生成される。本実施例において、逆離散フーリエ変換が行われるのはこの合算ベクトル７４のみである。１対Ｎ相関の場合には、Ｎ個の合算ベクトル７４が生成されるため、逆離散フーリエ変換はＮ回行われるが、畳み込み演算を行う関連技術と比べた場合、１／（文字又は文字列の種類の数）回に削減可能である。
【００９３】
相関結果７９は、合算ベクトル７４に対して逆フーリエ変換を行うことにより得られた文書間の相関を示す。２文書s、t間の相関に対しては、１つの相関値が示される。１対Ｎ相関では、各対象文書との相関値が出力されるため、相関結果７９によって、Ｎ個の相関値が示される。
【００９４】
本実施例では、文書の文字列からベクトルへの変換を任意の関数としても、処理時間の削減が可能である。一例として、出力される相関の各要素は文字の一致の数ではなく、ベクトルの内積の和で示しても良い。文書を空白等による分ち書き、句読点等による分割等により抽出した処理単位を要素とする配列を作成し、要素の特徴を表わすベクトルの内積の和をとる。ベクトルの内積の和は、文字の類似度を表わすベクトルへの変換（例えば、文書データから学習した語の分散表現）により、重み付きの相関とみなすことができる。
【００９５】
次に、２文書s，t間の相関を求める第１の類似算出処理について説明する。図８は、２文書間の相関を求める第１の類似算出処理を説明するためのフローチャートである。
【００９６】
図８において、ベクトル変換部６１は、文書データ７０から文書sと文書tとを読み込み（ステップＳ３０１）、各文書s，tを文字の種類ごとにベクトルに変換する（ステップＳ３０２）。文書sはベクトルuに変換され、文書tはベクトルvに変換される。ベクトルuとベクトルvとを含むベクトルデータ７１が、記憶部１３０に記憶される。
【００９７】
離散フーリエ変換部６２は、ベクトルuに対して離散フーリエ変換を行ってベクトルUを生成し、ベクトルvに対して離散フーリエ変換を行ってベクトルVを生成する（ステップＳ３０３）。ベクトルUとベクトルVとを含む変換後ベクトルデータ７２が、記憶部１３０に記憶される。
【００９８】
要素乗算部６３は、文字又は文字列の種類ごとに、ベクトルの各要素の積を算出し（アダマール積を求め）、文字の種類ごとのベクトルRを取得する（ステップＳ３０４）。ベクトルRは、文字の種類の数だけ生成される。文字の種類の数のベクトルRを含む積ベクトルデータ７３が、記憶部１３０に記憶される。
【００９９】
要素加算部６４は、文字又は文字列の種類ごとのベクトルRの要素を加算して、合算ベクトル７４を取得する（ステップＳ３０５）。合算ベクトル７４が、記憶部１３０に記憶される。
【０１００】
逆離散フーリエ変換部６５は、合算ベクトル７４に対して逆離散フーリエ変換を行って、相関結果７９を得る（ステップＳ３０６）。相関結果７９が、記憶部１３０に記憶される。また、相関結果７９が表示装置１５に表示されるようにしてもよい。
【０１０１】
図９は、図８のフローチャートでの処理例を示す図である。図９では、図８のステップ番号と対応付けている。ベクトル変換部６１が文書s，tを読み込んだ後のステップＳ３０２から説明する。
【０１０２】
図９において、文書s，tのいずれかに含まれる文字の種類は複数存在し、文字の種類をa、b、・・・zで表す。英数字、日本語（ひらがな、カタカナ、及び漢字）、その他の言語の各文字が、文字の種類に相当する。
【０１０３】
また、語、フレーズ等を文字とみなすことで本実施例を適用可能である。この場合、各文書s，tにおいて文字とみなす処理単位からベクトルへの変換の前に、空白等による分ち書き、句読点等による分割等により処理単位を抽出することで、処理単位を要素とする配列を作成すればよい。また、処理単位は、品詞ごとであっても良いし、文字又はフレーズごとであってもよい。処理単位は、文書内の文字又は文字列の種類である。処理単位で表される配列それぞれを文書s，tとすることで、以下のように処理される。
【０１０４】
ベクトル変換部６１は、文書sに対して、文字の種類a、b、・・・zの各々に関してベクトル変換し、ベクトルua、ub、・・・uzを得る（ステップＳ３０２ｓ）。また、ベクトル変換部６１は、文書tに対して、文字の種類a、b、・・・zの各々に関してベクトル変換し、ベクトルva、vb、・・・vzを得る（ステップＳ３０２ｔ）。
【０１０５】
離散フーリエ変換部６２は、文書sから生成したベクトルua、ub、・・・uzの各々について、離散フーリエ変換を行ってベクトルUa、Ub、・・・Uzを得る（ステップＳ３０３ｕａ、Ｓ３０３ｕｂ、・・・、及びＳ３０３ｕｚ）。また、離散フーリエ変換部６２は、文書tから生成したベクトルva、vb、・・・vzの各々について、離散フーリエ変換を行ってベクトルVa、Vb、・・・Vzを得る（ステップＳ３０３ｖａ、Ｓ３０３ｖｂ、・・・、及びＳ３０３ｖｚ）。
【０１０６】
要素乗算部６３は、文書s，t間で、文字の種類ごとに、ベクトルの各要素の積を算出し、文字の種別ごとのベクトルRa、Rb、・・・Rzを取得する（ステップＳ３０４ａ、Ｓ３０５ｂ、・・・Ｓ３０４ｚ）。
【０１０７】
要素加算部６４は、更に、ベクトルRa、Rb、・・・Rzにおいて同一ずれ位置の要素の値を加算して、１つの合算ベクトル７４を得る（ステップＳ３０５）。その後、逆離散フーリエ変換部６５は、合算ベクトル７４に対して逆離散フーリエ変換を行い、相関r(s，t)を示す相関結果を得る（ステップＳ３０６）。
【０１０８】
次に、１対Ｎ相関を求める第２の類似算出処理について説明する。図１０は、１対Ｎ相関を求める第２の類似算出処理を説明するためのフローチャートである。図１０では、特定文書sと各対象文書t1〜tnとの相関を求める。
【０１０９】
図１０において、ベクトル変換部６１は、文書データ７０から特定文書sとｎ個の対象文書t1〜tnとを読み込んで（ステップＳ４０１）、各文書s及びt1〜tnを文字の種類ごとにベクトルに変換する（ステップＳ４０２）。特定文書sはベクトルuに変換され、対象文書t1〜tnはそれぞれベクトルv1〜vnに変換される。ベクトルuとベクトルv1〜vnとを含むベクトルデータ７１が、記憶部１３０に記憶される。
【０１１０】
離散フーリエ変換部６２は、ベクトルuに対して離散フーリエ変換を行ってベクトルUを生成し、ベクトルv1〜vnのそれぞれに対して離散フーリエ変換を行ってベクトルV1〜Vnを生成する（ステップＳ３０３）。ベクトルUとベクトルV1〜Vnとを含む変換後ベクトルデータ７２が、記憶部１３０に記憶される。
【０１１１】
要素乗算部６３は、対象文書t1〜tnに係るベクトルV1〜Vnの中から１つ選択し（ステップＳ４０４−１）、特定文書sに係るベクトルUと選択したベクトルViとにおいて、文字の種類ごとに、ベクトルの各要素の積を算出し（アダマール積を求め）、文字の種類ごとのベクトルRiを取得する（ステップＳ４０４−２）。ベクトルRiは、文字の種類の数だけ生成される。文字の種類の数のベクトルRiを含む積ベクトルデータ７３が、記憶部１３０に記憶される。
【０１１２】
要素加算部６４は、文字の種類ごとのベクトルRiの要素を加算して、合算ベクトル７４iを取得する（ステップＳ４０５）。合算ベクトル７４iが、記憶部１３０に記憶される。逆離散フーリエ変換部６５は、合算ベクトル７４iに対して逆離散フーリエ変換を行って、記憶部１３０の相関結果７９に追加する（ステップＳ４０６）。
【０１１３】
その後、第２の類似算出処理は、変換後ベクトルデータ７２に未処理のベクトルViが存在するか否かを判断する（ステップＳ４０７）。存在する場合には、第２の類似算出処理は、ステップＳ４０１−１へと戻り、上述同様の処理を繰り返す。
【０１１４】
一方、存在しない場合、第２の類似算出処理は、終了する。記憶部１３０内の相関結果７９には、特定文書sと各対象文書t1〜tnの相関値r1〜rnが記憶されている。未処理のベクトルViが存在しない場合、相関結果７９を表示装置１５に表示して、第２の類似算出処理を終了してもよい。
【０１１５】
ここで、文書８０の実データのサイズについて、概ねの範囲を示す。
【０１１６】
σについて、
・核酸塩基：４〜
・アルファベット：２６
・２バイト文字：６５５３６
・単一言語の語録数（語を文字として扱う）：数千〜数万
nについて、
・学術論文（語の数）：数千〜数万
・ゲノム配列：数十万〜数千万
・センサーデータ：数億以上
関連技術を用いた実行例では、数百編の学術論文間の相関の算出で数日かかる。また、１研究機関がリポジトリで公開する論文数は数万以上である。以下に、本実施例と関連技術との実験結果の比較を示す。
【０１１７】
図１１は、語彙数に対する実行時間の比較結果を示す図である。図１１中、横軸に語彙数を示し、縦軸に実行時間（msec）を示す。語彙数は、文字の種類に相当し、上述では、σで示されている。このグラフでは、文書長が１０２４語、２０４８語、及び４０９６語の場合の実行時間を示している。
【０１１８】
図１１より、本実施例及び関連技術とも、語彙数が増える程、実行時間が長くなっている。しかしながら、いずれの場合においても、本実施例が関連技術より実行時間が短い。特に、文書長が４０９６語の場合、語彙数が８００語を超えた時点において、本実施例の実行時間の方が、関連技術の実行時間より約２０％短い。
【０１１９】
図１２は、文書長に対する実行時間の比較結果を示す図である。図１２中、横軸に文書長を示し、縦軸に実行時間（msec）を示す。このグラフでは、対象となる語彙数が２５６語、５１２語、及び１０２４語の場合の実行時間を示している。
【０１２０】
図１２より、本実施例及び関連技術とも、文書長が増える程、実行時間が長くなっている。しかしながら、いずれの場合においても、本実施例が関連技術より実行時間が短い。特に、語彙数が１０２４語の場合、文書長が３５００語付近において、本実施例の実行時間の方が、関連技術の実行時間より約２０％短い。
【０１２１】
図１３は、文書中の語彙数と処理時間の比較結果を示す図である。図１３中、横軸に文書長を示し、左縦軸に実行時間（msec）を示し、右縦軸に語彙数を示す。右縦軸の語彙数は、文書の長さに応じた語彙数の統計値を示す。
【０１２２】
図１３より、語彙数は、文書長に比例して増加することが分かる。また、本実施例は、文書長が２０００語程度までは、関連技術との実行時間の差は余りない。文書長が４０００語に近付くころには、即ち、σが大きくなるほど、実行時間の差は約２０％に及び、本実施例により高速化が実現されていることが分かる。この約２０％の高速化は、畳み込みに掛る計算量を抑えたことに起因する。
【０１２３】
上述の発明者による実験結果から、本実施例では、文字の種類の数および文字列の長さが増加した場合においても、計算量を抑えることが示されたといえる。
【０１２４】
上述した実施例において、ベクトル変換部６１、離散フーリエ変換部６２および要素乗算部６３が第１変換部に相当し、要素加算部６４が加算部に相当し、および逆離散フーリエ変換部６５が第２変換部に相当する。
【０１２５】
本発明は、具体的に開示された実施例に限定されるものではなく、特許請求の範囲から逸脱することなく、主々の変形や変更が可能である。
【０１２６】
以上の実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
複数の文書データに含まれる文字または文字列ごとに該複数の文書データをベクトル化した複数のベクトルを生成し、
前記複数のベクトルのそれぞれについてフーリエ変換した結果の要素ごとの積を算出し、
前記文字または文字列それぞれに対し、前記積を前記要素ごとに加算した合算ベクトルを生成し、
前記合算ベクトルより、フーリエ逆変換を用いて、前記複数の文書データ間の相関値を生成する、
処理をコンピュータに行わせる類似度算出プログラム。
（付記２）
前記コンピュータに、
前記複数の文書を、品詞、文字、フレーズ、又は空白を区切りとした単語のいずれかで分割し、分割した単語ごとに、前記複数の文書データの各ずれ位置における該単語との一致または不一致を前記要素の値として前記複数のベクトルを生成させることを特徴とする付記１記載の類似度算出プログラム。
（付記３）
前記要素は、前記複数の文書データ間のずれ位置に相当することを特徴とする付記１又は２記載の類似度算出プログラム。
（付記４）
前記積は、アダマール積であることを特徴とする付記１乃至３のいずれか１項記載の類似度算出プログラム。
（付記５）
複数の文書データに含まれる文字または文字列ごとに該複数の文書データをベクトル化した複数のベクトルを生成し、
前記複数のベクトルのそれぞれについてフーリエ変換した結果の要素ごとの積を算出し、
前記文字または文字列それぞれに対し、前記積を前記要素ごとに加算した合算ベクトルを生成し、
前記合算ベクトルより、フーリエ逆変換を用いて、前記複数の文書データ間の相関値を生成する、
処理をコンピュータが行う類似度算出方法。
（付記６）
複数の文書データに含まれる文字または文字列ごとに該複数の文書データをベクトル化した複数のベクトルを生成するベクトル変換部と、
前記複数のベクトルのそれぞれについてフーリエ変換した結果の要素ごとの積を算出する第１変換部と、
前記文字または文字列それぞれに対し、前記積を前記要素ごとに加算した合算ベクトルを生成する加算部と、
前記合算ベクトルより、フーリエ逆変換を用いて、前記複数の文書データ間の相関値を生成する第２変換部と、
を有する類似度算出装置。
【符号の説明】
【０１２７】
６１          ベクトル変換部
６２          離散フーリエ変換部
６３          要素乗算部
６４          要素加算部
６５          逆離散フーリエ変換部
７０          文書データ
７１          ベクトルデータ
７２          変換後ベクトルデータ
７３          積ベクトルデータ
７４          合算ベクトル
７９          相関結果
【図１】
2018085051.tif 000023
【図２】
2018085051.tif 000024
【図３】
2018085051.tif 000025
【図４】
2018085051.tif 000026
【図５】
2018085051.tif 000027
【図６】
2018085051.tif 000028
【図７】
2018085051.tif 000029
【図８】
2018085051.tif 000030
【図９】
2018085051.tif 000031
【図１０】
2018085051.tif 000032
【図１１】
2018085051.tif 000033
【図１２】
2018085051.tif 000034
【図１３】
2018085051.tif 000035