(57)【要約】  パターン中の部分文字列がテキスト中に出現する位置を効率よく検出する。部分文字列位置検出装置１は、テキストtの秘匿文〔t〕、パターンpの秘匿文〔p〕、ベクトルcの秘匿文〔c〕及び行列Eの秘匿文〔E〕を入力とし、行列Hの秘匿文〔H〕を出力する。第一行列生成部２０は、F[i][j]=E[i][j+i mod n+1]（ただし、E[i][n]=¬c[i]とみなす）となる行列Fの秘匿文〔F〕を生成する。第二行列生成部３０は、c[i]=0である場合またはc[i]=1かつk=i,…,n-1で連続してc[k]=1であるすべてのkについてF[k][j]=1である場合にF'[i][j]=1が設定され、それ以外であればF'[i][j]=0が設定される行列F'の秘匿文〔F'〕を生成する。第三行列生成部４０は、〔H[i][j]〕=〔F'[i][j-i mod n+1]〕∧〔c[i]〕∧¬〔c[i-1]〕を計算して秘匿文〔H〕を生成する。
2016056503.tif 000002
【特許請求の範囲】
【請求項１】
長さnのテキストtの秘匿文〔t〕、長さmのパターンpの秘匿文〔p〕、長さmのベクトルcの秘匿文〔c〕及びm行n列の行列Eの秘匿文〔E〕を入力とし、m行n列の行列Hの秘匿文〔H〕を出力する部分文字列位置検出装置であって、
p[i]は上記パターンpのi番目の要素であり、t[i]は上記テキストtのi番目の要素であり、c[i]は上記ベクトルcのi番目の要素であり、E[i][j]は上記行列Eのi行j列目の要素であり、H[i][j]は上記行列Hのi行j列目の要素であり、
上記ベクトルcは、p[i]が任意の長さの文字列を表す無限長ギャップでない場合にはc[i]=1が設定され、そうでない場合にはc[i]=0が設定されるものであり、
上記行列Eは、c[i]=0またはp[i]=t[j]ならばE[i][j]=1が設定され、そうでない場合にはE[i][j]=0が設定されるものであり、
上記行列Hは、p[i]が上記パターンpを上記無限長ギャップで分割した部分文字列の先頭の要素であり、かつ、上記部分文字列が上記テキストtのj番目の位置に出現するならばH[i][j]=1が設定され、それ以外であればH[i][j]=0が設定されるものであり、
F[i][j]=E[i][j+i mod n+1]（ただし、E[i][n]=¬c[i]とみなす）となるm行(n+1)列の行列Fの秘匿文〔F〕を生成する第一行列生成部と、
c[i]=0である場合またはc[i]=1かつkをiから1ずつ加算したとき連続してc[k]=1であるすべてのkについてF[k][j]=1である場合にF'[i][j]=1が設定され、それ以外であればF'[i][j]=0が設定されるm行(n+1)列の行列F'の秘匿文〔F'〕を生成する第二行列生成部と、
〔H[i][j]〕=〔F'[i][j-i mod n+1]〕∧〔c[i]〕∧¬〔c[i-1]〕を計算して上記秘匿文〔H〕を生成する第三行列生成部と、
を含む部分文字列位置検出装置。
【請求項２】
請求項１に記載の部分文字列位置検出装置であって、
【数１４】
2016056503.tif 000016
を、
【数１５】
2016056503.tif 000017
で定義される二項演算とし、pi:=(c[i],ej[i])とし、
上記第二行列生成部は、次式により計算されるSiの1番目の要素をe’j[i]とするものである
【数１６】
2016056503.tif 000018
部分文字列位置検出装置。
【請求項３】
長さnのテキストtの秘匿文〔t〕、長さmのパターンpの秘匿文〔p〕、長さmのベクトルcの秘匿文〔c〕及びm行n列の行列Eの秘匿文〔E〕を入力とし、m行n列の行列Hの秘匿文〔H〕を出力する部分文字列位置検出方法であって、
p[i]は上記パターンpのi番目の要素であり、t[i]は上記テキストtのi番目の要素であり、c[i]は上記ベクトルcのi番目の要素であり、E[i][j]は上記行列Eのi行j列目の要素であり、H[i][j]は上記行列Hのi行j列目の要素であり、
上記ベクトルcは、p[i]が任意の長さの文字列を表す無限長ギャップでない場合にはc[i]=1が設定され、そうでない場合にはc[i]=0が設定されるものであり、
上記行列Eは、c[i]=0またはp[i]=t[j]ならばE[i][j]=1が設定され、そうでない場合にはE[i][j]=0が設定されるものであり、
上記行列Hは、p[i]が上記パターンpを上記無限長ギャップで分割した部分文字列の先頭の要素であり、かつ、上記部分文字列が上記テキストtのj番目の位置に出現するならばH[i][j]=1が設定され、それ以外であればH[i][j]=0が設定されるものであり、
第一行列生成部が、F[i][j]=E[i][j+i mod n+1]（ただし、E[i][n]=¬c[i]とみなす）となるm行(n+1)列の行列Fの秘匿文〔F〕を生成する第一行列生成ステップと、
第二行列生成部が、c[i]=0である場合またはc[i]=1かつkをiから1ずつ加算したとき連続してc[k]=1であるすべてのkについてF[k][j]=1である場合にF'[i][j]=1が設定され、それ以外であればF'[i][j]=0が設定されるm行(n+1)列の行列F'の秘匿文〔F'〕を生成する第二行列生成ステップと、
第三行列生成部が、〔H[i][j]〕=〔F'[i][j-i mod n+1]〕∧〔c[i]〕∧¬〔c[i-1]〕を計算して上記秘匿文〔H〕を生成する第三行列生成ステップと、
を含む部分文字列位置検出方法。
【請求項４】
請求項３に記載の部分文字列位置検出方法であって、
【数１７】
2016056503.tif 000019
を、
【数１８】
2016056503.tif 000020
で定義される二項演算とし、pi:=(c[i],ej[i])とし、
上記第二行列生成ステップは、次式により計算されるSiの1番目の要素をe’j[i]とするものである
【数１９】
2016056503.tif 000021
部分文字列位置検出方法。
【請求項５】
請求項１または２に記載の部分文字列位置検出装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号応用技術に関し、特に、入力データを明かすことなくパターンに含まれる部分文字列のテキスト中の出現位置を検出する技術に関する。
【背景技術】
【０００２】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば、非特許文献１参照）。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、３つの秘密計算装置が協調計算を行うことにより、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。【０００３】
文字列のパターンマッチングを行う場合、パターンに含まれる部分文字列のテキスト中の出現位置を求め、その出現位置の情報を基にテキストがパターンにマッチしているかどうかの判定をすることがよく行われる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司、濱田浩気、五十嵐大、高橋克巳、“軽量検証可能3パーティ秘匿関数計算の再考”、CSS、2010年
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、秘密計算で部分文字列の位置を求めようとすると、テキストとパターンの内容を秘匿したまま処理をする必要がある。そのため、素朴な方法でパターンマッチングを行う場合、入力テキスト長をn、パターン長をmとすると、O(1)ラウンド、Ω(m3n)の通信量を要していた。【０００６】
この発明の目的は、パターンマッチングを行う場合にパターン中の部分文字列がテキスト中に出現する位置を効率よく検出することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明の部分文字列位置検出装置は、長さnのテキストtの秘匿文〔t〕、長さmのパターンpの秘匿文〔p〕、長さmのベクトルcの秘匿文〔c〕及びm行n列の行列Eの秘匿文〔E〕を入力とし、m行n列の行列Hの秘匿文〔H〕を出力する。p[i]はパターンpのi番目の要素であり、t[i]はテキストtのi番目の要素であり、c[i]はベクトルcのi番目の要素であり、E[i][j]は行列Eのi行j列目の要素であり、H[i][j]は行列Hのi行j列目の要素である。ベクトルcは、p[i]が任意の長さの文字列を表す無限長ギャップでない場合にはc[i]=1が設定され、そうでない場合にはc[i]=0が設定されるものである。行列Eは、c[i]=0またはp[i]=t[j]ならばE[i][j]=1が設定され、そうでない場合にはE[i][j]=0が設定されるものである。行列Hは、p[i]がパターンpを無限長ギャップで分割した部分文字列の先頭の要素であり、かつ、部分文字列がテキストtのj番目の位置に出現するならばH[i][j]=1が設定され、それ以外であればH[i][j]=0が設定されるものである。第一行列生成部は、F[i][j]=E[i][j+i mod n+1]（ただし、E[i][n]=¬c[i]とみなす）となるm行(n+1)列の行列Fの秘匿文〔F〕を生成する。第二行列生成部は、c[i]=0である場合またはc[i]=1かつkをiから1ずつ加算したとき連続してc[k]=1であるすべてのkについてF[k][j]=1である場合にF'[i][j]=1が設定され、それ以外であればF'[i][j]=0が設定されるm行(n+1)列の行列F'の秘匿文〔F'〕を生成する。第三行列生成部は、〔H[i][j]〕=〔F'[i][j-i mod n+1]〕∧〔c[i]〕∧¬〔c[i-1]〕を計算して上記秘匿文〔H〕を生成する。
【発明の効果】
【０００８】
この発明の部分文字列位置検出技術によれば、テキストとパターンの文字ごとのマッチング結果が与えられているときに、パターン中の部分文字列のテキスト中での出現位置をO(log m)ラウンド、O(mn)の通信量で検出することができる。したがって、パターンマッチングを行う場合にパターン中の部分文字列がテキスト中に出現する位置を効率よく検出することができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、部分文字列位置検出装置の機能構成を例示する図である。
【図２】図２は、部分文字列位置検出方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１０】
実施形態の説明に先立ち、この明細書における表記方法および用語の定義について説明する。
【００１１】
＜表記方法＞
ある値aを暗号化や秘密分散などにより秘匿化した値をaの秘匿文と呼び、〔a〕と表記する。秘匿化が秘密分散である場合は、〔a〕により各秘密計算装置が持つ秘密分散の断片の集合を参照する。
【００１２】
行列Xの第i行をX[i]と表記する。ベクトルuの第i要素をu[i]と表記する。行列Xの各要素を秘匿化した行列全体を〔X〕と表記し、Xの秘匿文と呼ぶ。ベクトルuの各要素を秘匿化したベクトル全体を〔u〕と表記し、uの秘匿文と呼ぶ。
【００１３】
・Tは・の転置を表す。
【００１４】
＜加算、減算、乗算＞
加算、減算、乗算の各演算は二つの値a, bの秘匿文〔a〕,〔b〕を入力とし、それぞれa+b, a-b, abの計算結果c1, c2, c3の秘匿文〔c1〕,〔c2〕,〔c3〕を計算する。これらの演算の実行をそれぞれ次式のように記述する。
【数１】
2016056503.tif 000003
【００１５】
なお、誤解を招く恐れのない場合は、Add(〔a〕,〔b〕),Sub(〔a〕,〔b〕),Mul(〔a〕,〔b〕)をそれぞれ〔a〕+〔b〕,〔a〕-〔b〕,〔a〕×〔b〕と略記する。
【００１６】
＜論理演算＞
論理和、論理積、否定の各演算は二つの値a, b∈{0,1}の秘匿文〔a〕,〔b〕を入力とし、それぞれaとbの論理和, aとbの論理積, aの否定の計算結果c1, c2, c3の秘匿文〔c1〕,〔c2〕,〔c3〕を計算する。これらの演算の実行をそれぞれ次式のように記述する。
【数２】
2016056503.tif 000004
【００１７】
これらの論理演算は、次式の計算により実現される。
【数３】
2016056503.tif 000005
【００１８】
＜等号判定＞
等号判定の演算は２つの値a, bの秘匿文〔a〕,〔b〕を入力とし、それぞれa=b, a≠bの真偽値c1, c2の秘匿文〔c1〕,〔c2〕を計算する。真偽値は真のときは１、偽のときは０とする。
【００１９】
これらの演算の実行をそれぞれ次式のように記述する。
【数４】
2016056503.tif 000006
【００２０】
秘匿化、復元、加算、減算、乗算は、例えば、非特許文献１に記載の方法を用いればよい。また、等号判定は、例えば、「Ivan Damgard, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, and Tomas Toft, “Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation”, TCC, pp. 285-304, 2006.（参考文献１）」に記載の方法を用いればよい。
【００２１】
＜パターンマッチング＞
パターンマッチングとは、テキストtとパターンpの二つの文字列が与えられたときに、テキストtがパターンpに記述された条件を満たしているかどうかを判定する問題である。テキストtはアルファベットΣ={a,b,c,…,z}の要素を0個以上並べたベクトルである。パターンpは0個以上のアルファベットまたは特殊記号からなるベクトルである。特殊記号としては、データベース操作のための言語であるSQLのLIKEコマンドや基本ソフト（OS）操作のための言語であるシェルの多くで使われている特殊記号「?」や「*」が挙げられる。前者の特殊記号「?」は、任意のアルファベット1個を表す特殊記号であり、ワイルドカードと呼ばれる。後者の特殊記号「*」は、0個以上の任意の長さのアルファベットの列を表す特殊記号であり、無限長ギャップと呼ばれる。テキストtがパターンpにマッチするとは、パターンpが表すことのできる文字列の集合にテキストtが含まれていることを言う。
【００２２】
例えば、パターンpをp=(a,b,?,a,b,*)とする。パターンpは、t0=(a,b,c,a,b)やt1=(a,b,a,a,b,x,x)を表すことができるが、t2=(a,b,a,b,a)は表すことができない。したがって、前者二つのテキストt0,t1はパターンpにマッチするが、後者のテキストt2はパターンpにマッチしない。
【００２３】
このようなパターンマッチングを行う場合の有力な方法は、パターンを無限長ギャップで区切られた部分文字列の配列とみなし、各部分文字列のテキスト中の出現位置を計算し、その出現位置の情報を用いてテキストがパターンにマッチしているかどうかを判定する方法である。
【００２４】
パターンpを無限長ギャップ「*」で区切られた部分文字列s0,…,sk-1（si[j]∈（Σ∪{?}））を無限長ギャップ「*」で連結したベクトルとみなす。ここで、kはパターンp中の部分文字列の個数である。このとき、次式を満たせば、部分文字列siはテキストtの位置jに出現するという。
【数５】
2016056503.tif 000007
【００２５】
ただし、λiは部分文字列siのサイズである。
【００２６】
例えば、テキストt=(a,a,b,a,a,b,a)、パターンp=(*,a,?,*,b,*)のとき、パターンpは無限長ギャップ「*」で二つの部分文字列(a,?),(b)に分割できる。したがって、k=2、s0=(a,?)、s1=(b)である。このとき、s0=(a,?)はj=0,1,3,4の位置に出現し、s1=(b)はj=2,5の位置に出現する。
【００２７】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２８】
実施形態の部分文字列位置検出装置１は、図１に例示するように、入力部１０、第一行列生成部２０、第二行列生成部３０、第三行列生成部４０及び出力部５０を含む。
【００２９】
部分文字列位置検出装置１は、例えば、中央演算処理装置（Central Processing Unit、CPU）、主記憶装置（Random Access Memory、RAM）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。部分文字列位置検出装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。部分文字列位置検出装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００３０】
部分文字列位置検出装置１は、長さnのテキストtの秘匿文〔t〕、長さmのパターンpの秘匿文〔p〕、長さmのベクトルcの秘匿文〔c〕及びm行n列の行列Eの秘匿文〔E〕を入力とし、m行n列の行列Hの秘匿文〔H〕を出力する。
【００３１】
ベクトルcは、p[i]が任意の長さの文字列を表す無限長ギャップでない場合にはc[i]=1が設定され、そうでない場合にはc[i]=0が設定される。ここで、p[i]はパターンpのi番目の要素である。c[i]はベクトルcのi番目の要素である。
【００３２】
行列Eは、c[i]=0またはp[i]=t[j]ならばE[i][j]=1が設定され、そうでない場合にはE[i][j]=0が設定される。ここで、t[i]はテキストtのi番目の要素である。E[i][j]は行列Eのi行j列目の要素である。
【００３３】
行列Hは、p[i]がパターンpを無限長ギャップで分割した部分文字列sλの先頭の要素であり、かつ、部分文字列sλがテキストtのj番目の位置に出現するならばH[i][j]=1が設定され、それ以外であればH[i][j]=0が設定される。ここで、H[i][j]は行列Hのi行j列目の要素である。ここで、λは部分文字列のインデックスであり、パターンpを無限長ギャップで分割した部分文字列がL個あるとして、λ=0,…,L-1である。
【００３４】
以下、図２を参照して、実施形態の部分文字列位置検出方法を説明する。
【００３５】
ステップＳ１０において、入力部１０へ、テキストtの秘匿文〔t〕、パターンpの秘匿文〔p〕、ベクトルcの秘匿文〔c〕及び行列Eの秘匿文〔E〕が入力される。
【００３６】
ステップＳ２０において、第一行列生成部２０は、F[i][j]=E[i][j+i mod n+1]（ただし、E[i][n]=¬c[i]とみなす）となるm行(n+1)列の行列Fの秘匿文〔F〕を生成する。行列Fは、行列Eの最終列に¬cTを連結した行列を、i=0,…,m-1について第i行でiだけ左にシフトした行列となる。
【００３７】
ステップＳ３０において、第二行列生成部３０は、c[i]=0である場合またはc[i]=1かつkをiから1ずつ加算したとき連続してc[k]=1であるすべてのkについてF[k][j]=1である場合にF'[i][j]=1が設定され、それ以外であればF'[i][j]=0が設定されるm行(n+1)列の行列F'の秘匿文〔F'〕を生成する。
【００３８】
行列F'は以下のように生成すればよい。行列Fの第j列ベクトルをejとする。ベクトルcとベクトルejを用いて、次のようにしてベクトルe’jを生成する。ベクトルe’jは、c[i]=0∨（c[i]=1∧(c[i]以降の連続するすべてのc[k]=1を満たすkについてej[k]=1)）である場合にe’j[i]=1を設定し、それ以外の場合にe’j[i]=0を設定する。行列F'はベクトルe’jを用いてF'[i][j]=e'j[i]として生成する。
【００３９】
ベクトルe’jを計算する具体的な方法は、以下のようにすればよい。まず、次式で定義される二項演算
【数６】
2016056503.tif 000008
を考える。
【数７】
2016056503.tif 000009
【００４０】
pi:=(c[i],ej[i])と定義し、次式により計算されるSiの1番目の要素Si[0]をe’j[i]とする。これにより、上記の条件を満たすベクトルe’jを生成することができる。
【数８】
2016056503.tif 000010
【００４１】
このとき二項演算
【数９】
2016056503.tif 000011
が結合性を持つことを利用して、「Richard E. Ladner and Michael J. Fischer, “Parallel prefix computation”, J. ACM, vol. 27, no. 4, pp. 831-838, 1980.（参考文献２）」に記載された手法を適用することができる。参考文献２は、二項演算の順序を変えて効率よく計算する手法である。これにより、S1,…,Sm-1をO(m)回、O(log m)段の二項演算で計算することができ、より効率的にベクトルe’jを計算することができる。
【００４２】
ステップＳ４０において、第三行列生成部４０は、〔H[i][j]〕=〔F'[i][j-i mod (n+1)]〕∧〔c[i]〕∧¬〔c[i-1]〕を計算して行列Hの秘匿文〔H〕を生成する。
【００４３】
ステップＳ５０において、出力部５０は、m行n列の行列Hの秘匿文〔H〕を出力する。行列Hは、p[i]をパターンpの部分文字列sλの先頭の要素とすると、行列Hのi行目においてH[i][j]=1であるjが存在すれば、テキストtのj番目の位置に部分文字列sλが検出されることを表している。
【００４４】
以下、上述の方法により部分文字列の位置を検出できることを、具体例を用いて示す。
【００４５】
例えば、ステップＳ１０において、次式に示すテキストt、パターンp、ベクトルc及び行列Eが入力されたものとする。
【数１０】
2016056503.tif 000012
【００４６】
この例では、n=10、m=7である。
【００４７】
ステップＳ２０において、次式に示す行列Fが生成される。
【数１１】
2016056503.tif 000013
【００４８】
ステップＳ３０において、次式に示す行列F'が生成される。
【数１２】
2016056503.tif 000014
【００４９】
ステップＳ４０において、次式に示す行列Hが生成される。
【数１３】
2016056503.tif 000015
【００５０】
例えば、パターンp=(*,a,b,*,?,b,*)の部分文字列(p[4],p[5])=(?,b)がテキストt=(a,a,b,a,b,a,b,b,a,b)で出現するのは、t[1]=(a,b), t[3]=(a,b), t[5]=(a,b), t[6]=(b,b), t[8]=(a,b)である。行列Hでは、ベクトルH[4]=(0 1 0 1 0 1 1 0 1 0)において、要素H[4][1], H[4][3], H[4][5], H[4][6], H[4][8]が1であり、その他の要素が0となっていることがわかる。このようにして、行列Hを用いてパターンpの部分文字列の出現位置を検出することが可能となっている。
【００５１】
＜発明の効果＞
この発明の部分文字列位置検出技術によれば、テキストとパターンの文字ごとのマッチングの結果が与えられているときに、パターン中の部分文字列のテキスト中での出現位置をO(log m)ラウンド、O(mn)の通信量で実現できる。
【００５２】
＜発明のポイント＞
この発明では、パターン中の各部分文字列のテキスト中での出現位置をパターン中の部分文字列ごとに計算するのではなく、文字ごとのマッチングの結果を使って一括で計算することにより、部分文字列ごとに計算するとΩ(m3n)の通信量を要する処理をO(mn)の通信量で実現する。
【００５３】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００５４】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００５５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2016056503.tif 000022
【図２】
2016056503.tif 000023
【手続補正書】
【提出日】平成29年3月28日(2017.3.28)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
ステップＳ２０において、次式に示す行列Fが生成される。
【数１１】
2016056503.tif 000024
【国際調査報告】
2016056503.tif 000025
2016056503.tif 000026