(57)【特許請求の範囲】
【請求項１】
ある文字列からなる目的符号系列に類似した符号系列を、文字列探索によってより長い符号系列であるデータ符号系列中において、検出する類似部分系列検出装置であって、
前記目的符号系列中のある一つの未選択の符号位置を順次選択する符号位置選択手段と、
前記符号位置選択過程の結果を用いて、前記目的符号系列を前記データ符号系列中に位置付ける対応付け手段と、
前記対応付け手段で対応づけた位置が既に照合済の位置か否かを判定する既照合判定手段と、
前記対応付け手段で対応づけた位置において、前記符号位置選択手段で選択した符号位置に対する前記データ符号系列中の符号との類似度を判定する類似度判定手段と、
前記類似度判定手段での結果に基づき、その位置での照合の要否を判定する照合要否判定手段と、
前記照合要となった位置において類似しているか否かを判定して当該位置を照合済とし、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出する照合手段とを備えたことを特徴とする類似部分系列検出装置。
【請求項２】
前記目的符号系列中のある部分系列を選択する部分系列選択手段と、
前記部分系列選択手段で選ばれた部分系列を前記データ符号系列中で検出する部分系列検出手段と、
前記部分系列検出手段により部分系列が検出された位置に基づき、前記目的符号系列をデータ符号系列中に対応付け、対応づけられた該位置に類似部分系列が検出されたとし、当該位置を照合済とする部分系列対応付け手段とを更に備え、
前記照合手段は、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする、請求項１に記載の類似部分系列検出装置。
【請求項３】
入力装置を介して提供される、ある文字列からなる目的符号系列に類似した符号系列を、類似部分系列検出装置により、文字列探索によってより長い符号系列であるデータ符号系列中において検出する類似部分系列検出方法であって、
符号位置選択手段が前記目的符号系列中のある一つの未選択の符号位置を順次選択する符号位置選択過程と、
対応付け手段が前記符号位置選択過程による選択結果を用いて、前記目的符号系列を前記データ符号系列中に位置付ける対応付け過程と、
既照合判定手段が前記対応付けた位置が既に照合済の位置か否かを判定する既照合判定過程と、
類似度判定手段が前記対応付けた位置において、前記選択された符号位置に対する前記データ符号系列中の符号との類似度を判定する類似度判定過程と、
照合要否判定手段が前記類似度判定結果に基づき、その位置での照合の要否を判定する照合要否判定過程と、
照合手段が前記照合要となった位置において類似しているか否かを判定して当該位置を照合済とし、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出する照合過程とを備えたことを特徴とする類似部分系列検出方法。
【請求項４】
それぞれの符号α1，α2，…について、当該符号を並ベて得られる列である符号系列の各符号を順次、［α1，α2，…］と書き表すとし、目的符号系列をＰで表し、目的符号系列の各符号を順にｐ1，ｐ2，…，ｐmで表し、目的符号系列Ｐを［ｐ1，ｐ2，…，ｐm］と書き表すとしたとき、
前記符号位置選択過程において、符号位置選択手段は、符号位置制御に関するパラメータｄを入力として、Ｐ中の符号位置iをi≦ｄ−1、かつi≦ｍの範囲で１から小さい順に選択するものであり、
前記対応付け過程において、対応付け手段は、ｊをｄ−iとし、ｊ≦ｍ'のときに、符号位置選択過程で選択した符号がｊ番目の符号に対応するよう前記目的符号系列を前記データ符号系列中に位置付けるものであり、
前記照合過程において、照合手段は、既照合判定過程と照合要否判定過程の結果、照合要となった位置において、前記対応づけ過程によって対応づけられたデータ符号系列中の部分系列をＰ'と表すとし、当該部分系列Ｐ'の符号の順にｐ'1，ｐ'2，…，ｐ'm'とし、前記符号系列Ｐ'は［ｐ'1，ｐ'2，…，ｐ'm'］と書き表されるとして、符号系列Ｐと符号系列Ｐ'の間の類似度を、Ｐの前からｘ個の符号を並ベてできる符号系列［ｐ1，ｐ2，…，ｐx］と、Ｐの前からｙ個の符号を並ベてできる符号系列符号系列［ｐ'1，ｐ'2，…，ｐ'y］の間の類似度を、
(a) ｘ＋ｙ＜ｄを満たすｘとｙの組については既知であるとし、
(b) ｘ＋ｙ≧ｄとなるｘとｙの組については、
（１）符号系列［ｐ1，ｐ2，…，ｐx-1］と符号系列［ｐ'1，ｐ'2，…，ｐ'y］の類似度、
（２）符号系列［ｐ1，ｐ2，…，ｐx］と符号系列［ｐ'1，ｐ'2，…，ｐ'y-1］の類似度、
（３）符号系列［ｐ1，ｐ2，…，ｐx-1］と符号系列［ｐ'1，ｐ'2，…,ｐ'y-1］の類似度の３つの類似度に、ｐxとｐ'yの類似度を各場合に応じた重み定数をかけて加えた結果の最大値とする（但し、符号系列［ｐ1］と符号系列［ｐ'1］の類似度は符号ｐ1とｐ'1の類似度とし、ｘ＋ｙ＜ｄの場合は（ａ）に従う）として計算するとして、符号系列［ｐ1，ｐ2，…，ｐx］と符号系列［ｐ'1,ｐ'2,…,ｐ'y］の類似度をｘとｙを１から各々ｍとｍ’まで増やして計算すことで符号系列Ｐと符号系列Ｐ'の類似度を求め、符号系列Ｐと符号系列Ｐ'が類似するか否かを判定し、当該位置を照合済とするものであり、
類似部分系列検出装置が前記符号位置選択過程、対応付け過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、ｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする、請求項３に記載の類似部分系列検出方法。
【請求項５】
前記符号位置選択過程において、符号位置選択手段は、符号位置制御に関するパラメータｄを入力として、目的符号系列Ｐを[ｐ1,ｐ2,…,ｐm]とし、データ符号系列中の着目する部分系列の長さをｍ’とするとき、前記目的符号系列と着目する部分系列の類似度の上限値ｓmaxuを、ｕとｖをｕ＋ｖ＝ｄ−１と１≦ｕ≦ｍと１≦ｖ≦ｍ'を満たす任意の自然数の組としたときの長さがｍ−ｕとｍ'−ｖの符号系列の間の類似度の上限値の最大値とし、前記ｓmaxuが与えられた閾値以下なら検出処理全体を処理を終了し、前記ｓmaxuが前記閾値を越える場合に、Ｐ中の符号位置iをi≦ｄ−１かつi≦ｍの範囲で１から小さい順に選択するものであり、
前記符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、前記符号位置選択過程において、符号位置選択手段が終了と判定しない限り、類似部分系列検出装置がｄを２からｍ＋ｍ’まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする、請求項４に記載の類似部分系列検出方法。
【請求項６】
前記照合過程において、照合手段は、前記既照合判定過程と照合要否判定過程の結果、照合要となった位置において、目的符号系列Ｐを[ｐ1,ｐ2,…,ｐm]とし、対応づけられたデータ符号系列中の部分系列Ｐ'を[ｐ'1,ｐ'2,…,ｐ'm ]とし、
ＰとＰ'の間の類似度を、x＋y＜ｄの時は、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は既知であるとしながら、
[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は、[ｐ1,…,ｐx-1]と[ｐ'1,…,ｐ'y]の類似度、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y-1]の類似度、[ｐ1,…,ｐx-1]と[ｐ'1,…,ｐ'y-1]の類似度にｐxとｐ'yの類似度に各々に応じた重み定数をかけたものを加えたもののうち最大のものとしながら、ｘ＋ｙはｄ'とし、各ｄ'においてどのようなｘとｙにおいてもｄ'から計算できる類似度の上限値を加えたとしても、与えられた閾値を越えない場合はＰとＰ'は非類似と判定し、これにより非類似と判定されない限り、順次ｄ'を大きくし、ＰとＰ'の間の類似度を計算し、ＰとＰ'が類似するか否かを判定するものであり、
前記符号位置選択過程、対応付け過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、類似部分系列検出装置がｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする、請求項４に記載の類似部分系列検出方法。
【請求項７】
符号位置選択過程として請求項５に記載の符号位置選択過程を行い、照合過程として請求項６の照合過程を行い、
前記符号位置選択過程、対応付け過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、前記符号位置選択過程において、符号位置選択手段が終了と判定しない限り、類似部分系列検出装置がｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする、請求項４に記載の類似部分系列検出方法。
【請求項８】
部分系列選択手段が前記目的符号系列中のある部分系列を選択する部分系列選択過程と、部分系列検出手段が前記部分系列選択過程で選ばれた部分系列を前記データ符号系列中で検出する部分系列検出過程と、  部分系列対応付け手段が前記部分系列検出過程により部分系列が検出された位置に基づき、前記目的符号系列をデータ符号系列中に対応付け、対応づけられた該位置に類似部分系列が検出されたとし、当該位置を照合済とする部分系列対応付け過程とを更に備え、
類似部分系列検出装置が前記部分系列選択過程、部分系列検出過程、部分系列対応づけ過程による処理を行った後、前記符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を繰り返して、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする、請求項３に記載の類似部分系列検出方法。
【請求項９】
前記部分系列検出過程において、部分系列検出手段は、
前記部分系列選択過程で選ばれた部分系列と完全に一致する部分系列を前記データ符号系列中で検出するものであり、
類似部分系列検出装置が前記部分系列選択過程、部分系列検出過程、部分系列対応づけ過程による処理を行った後、前記符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を繰り返して、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする、請求項８に記載の類似部分系列検出方法。
【請求項１０】
前記照合過程において、照合手段は、閾値θと照合範囲Ｒを入力とし、前記目的符号系列とデータ符号系列の対応付けされた位置の部分系列の照合範囲内での類似度がθより大きいか否か判定することで、当該位置の部分系列が類似部分系列か否かを判定し、当該位置を照合済とするものであり、
類似部分系列検出装置が前記部分系列選択過程、部分系列検出過程、部分系列対応づけ過程を行った後、前記符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、Ｒを目的符号系列の長さから、部分系列検出過程で選択された部分系列の長さまで小さくしながら繰り返して、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする、請求項９に記載の類似部分系列検出方法。
【請求項１１】
コンピュータに請求項３から請求項１０に記載の類似部分系列検出方法を実行させるための類似部分系列検出プログラム。
【請求項１２】
請求項１１に記載の類似部分系列検出プログラムを記録した、コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、目的符号系列と呼ぶ符号系列と、より長いデータ符号系列と呼ぶ２つの符号系列が与えられたとき、データ符号系列中の目的符号系列に類似した部分系列の場所を探し出すことのできる、類似部分系列検出方法および装置、類似部分系列検出プログラムならびにその記録媒体に関する。
【０００２】
【従来の技術】
目的とする符号系列（以下、目的符号系列と称する）が存在する領域を符号系列中から検出する方法として従来から「ずらし照合法」がある。また、２つの符号系列間の類似度を測る従来手法としては「ＤＰマッチング」と称される技術がある。
【０００３】
「ずらし照合法」は、データ符号系列の注目領域（以下、「注目窓」と称する）をずらしながら、該注目窓の符号系列と目的符号系列を照合して該注目窓の符号系列との類似度を計算し、該類似度がある一定以上になると、該注目窓の位置に、目的符号系列に類似する部分系列が存在するものとして判定する手法である。
一方、「ＤＰマッチング法」は、２つ符号系列間において、整合窓等の与えられた条件のもと、各符号間の最適な対応づけにおける累積の類似度を求め、それを正規化したもの符号系列間の正規化類似度とする方法である。以降、符号系列間については累積の類似度を単に類似度という。
【０００４】
以下、ＤＰマッチングの基本的な概念について、島内剛一、有澤誠、野下浩平、浜田穂積、伏見正則（編）、共立出版社株式会社１９９４年発行の「アルゴリズム辞典」に基づいて説明する。いま、２つの符号系列を各々、Ｐ＝[ｐ1,ｐ2,…,ｐm]、Ｐ'＝[ｐ'1,ｐ'2,…,ｐ'm']とする。ここでｐ1（１≦ｉ≦ｍ)，ｐ'j(１≦ｊ≦ｍ')は符号である。
【０００５】
符号は文字集合Ａ＝{ｑ1，ｑ2，…，ｑQ}の内のいずれかの要素を値としてとる。文字と文字の間には類似度が定義されており文字ｑkとｑlの間の類似度をｍ（ｑk，ｑl）で表す。符号ｐiとｐjの値が各々ｑk，ｑlの時、ｐiとｐjの類似度はｍ（ｑk，ｑl）であり、ｓ（ｐi，ｐj）とも書く。そしてｓ（ｐi，ｐ'j）＞０の時、ｐiとｐjは類似すると言う。そして、ＰとＰ'の符号の対応の系列Ｆ＝Ｃ1，Ｃ2，...，ＣH                    
を考える。
【０００６】
ここで、Ｃh＝(ｉh，ｊh)であり、これはｐihとｐ'jhが対応することを示す。そして、累積の類似度ｓを最大化するＦを考える。ここで、ｓは以下の演算式（１）で表される。
【数１】
0003759438.tif 000002
ここで、ωkは正の重み関数であり、ｄ(Ｃh)＝ｓ(ｐih，ｐ'jh)である。そして、例として、ｉh，ｊhは次のａからｃの３つによる条件Ａを満たすとする。
ａ．単調性と連続性
０≦ｉh−ｉh-1
０≦ｉh−ｉh-1
ｂ．境界
ｉ1＝ｊ1＝１，
ｉH＝m，ｊH＝m'
ｃ．整合窓（極端な対応づけを防ぐ）
ｉh−ｊh≦ｒ．
ωh＝(ｉh−ｉh-1)＋(ｊh−ｊh-1)，(ｉ0＝ｊ0＝０)と置くと、以下の演算式（２）（３）式となる。
【数２】
0003759438.tif 000003
【０００７】
このときｓ（Ｐ，Ｐ')は加法的に求められるので、ｓ（Ｐ，Ｐ')を最大にするＣHは以下の演算式（４）により求める。ここで、最大のｓ（Ｐ,Ｐ’）をｓmax（Ｐ,Ｐ’）と書くものとする。
【数３】
0003759438.tif 000004
更に、上記した演算式（４）に、ａ〜ｃに示した各式の条件を加えると、以下の演算式（５）となり、整合窓の範囲内で、順次ｉ、ｊをｍ、ｍ'となるまで増やしていけば、ｓmax（Ｐ，Ｐ')を求めることができる。このようにしてＰとＰ'の類似度ｇ（ｍ，ｍ')および正規化類似度ｓmax（Ｐ，Ｐ')を求め、ＰとＰ'間の類似性を測ることができる。
【数４】
0003759438.tif 000005
【０００８】
【発明が解決しようとする課題】
ここでは、符号の対応に置ける条件として、条件Ａを与えたが、ｓ（Ｐ，Ｐ')が加法的に求められるままで、対応づけや、整合窓の形を変えること等も考えられる。
ｓ（Ｐ，Ｐ')が加法的に求められることは、図１にＤＰマッチングの概念が示されるように、ＤＰマッチングをグラフ上で類似度が最大となる（ｍ，ｍ')への経路を探す問題ととらえた場合に、開始点に近い対応点から順次、類似度最大の経路が求められることにあたる。そして、対応づけの条件は図１上で経路の形に条件を加えることに、整合窓は経路が侵入できない領域をおくことにあたり、この形を変更することで極端な対応づけを防ぐことができる場合がある。
【０００９】
上記のずらし照合法およびＤＰマッチングの技術を用いて、ずらし照合において、注目窓をデータ符号系列上でずらしながら、注目窓内の部分系列と目的符号系列の間でＤＰマッチングにより照合を行うことで類似度を求め、類似度がある一定以上となると、当該注目窓の位置において、「目的符号系列に類似する部分系列が存在する」と判定することで類似部分系列検出を行うことができる。
しかしながら、このような手法では、ＤＰマッチングに大きな計算量がかかること、そして、注目窓を順次ずらして、データ符号系列上の全ての位置で照合を行う必要があるため、計算量が膨大になり、検出時間が長大になるという問題がある。
【００１０】
本発明は上記事情に鑑みてなされたものであり、目的符号系列と、より長いデータ符号系列の符号系列が与えられたとき、データ符号系列中の目的符号系列に類似した部分系列の場所を探し出すのに、照合の際、検索対象位置の符号系列が照合済みか否かを判定した後に照合を行なうことにより、従来長時間要していた類似部分系列の検出をより高速に行なうことのできる、類似部分系列検出方法および装置、類似部分系列検出プログラムならびにその記録媒体を提供することを目的とする。
【００１１】
【課題を解決するための手段】
上記した課題を解決するために、本発明は、入力装置を介して提供される、ある文字列からなる目的符号系列に類似した符号系列を、類似部分系列検出装置により、文字列探索によってより長い符号系列であるデータ符号系列中において検出する類似部分系列検出方法であって、符号位置選択手段が前記目的符号系列中のある一つの未選択の符号位置を順次選択する符号位置選択過程と、対応付け手段が前記符号位置選択過程による選択結果を用いて、前記目的符号系列を前記データ符号系列中に位置付ける対応付け過程と、既照合判定手段が前記対応付けた位置が既に照合済の位置か否かを判定する既照合判定過程と、類似度判定手段が前記対応付けた位置において、前記選択された符号位置に対する前記データ符号系列中の符号との類似度を判定する類似度判定過程と、照合要否判定手段が前記類似度判定結果に基づき、その位置での照合の要否を判定する照合要否判定過程と、照合手段が前記照合要となった位置において類似しているか否かを判定して当該位置を照合済とし、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出する照合過程とを備えたことを特徴とする。
【００１２】
上記類似部分系列検出方法によれば、符号位置選択過程において、目的符号系列中の符号を順次選択し、対応づけ過程によりデータ符号系列中に対応づけられた際、既照合判定過程により対応づけられた当該位置が未照合であり、かつ、類似度判定過程と照合要否判定過程により、当該位置の部分系列が符号位置選択過程で選択した符号位置の符号と類似する符号を対応する位置に持っている場合のみ、照合過程による照合処理を行うものとしている。このことにより、データ符号系列中の部分系列が類似する可能性のある位置のみで照合過程を行うことかでき、従って、照合回数を従来の「ずらし照合法」に比べて削減することができ、従来と比較して高速な検出が可能となる。
【００１３】
本発明の類似部分系列検出方法において、それぞれの符号α1，α2，…について、当該符号を並ベて得られる列である符号系列の各符号を順次、［α1，α2，…］と書き表すとし、目的符号系列をＰで表し、目的符号系列の各符号を順にｐ1，ｐ2，…，ｐmで表し、目的符号系列Ｐを［ｐ1，ｐ2，…，ｐm］と書き表すとしたとき、前記符号位置選択過程において、符号位置選択手段は、符号位置制御に関するパラメータｄを入力として、Ｐ中の符号位置iをi≦ｄ−1、かつi≦ｍの範囲で１から小さい順に選択するものであり、前記対応付け過程において、対応付け手段は、ｊをｄ−iとし、ｊ≦ｍ'のときに、符号位置選択過程で選択した符号がｊ番目の符号に対応するよう前記目的符号系列を前記データ符号系列中に位置付けるものであり、前記照合過程において、照合手段は、既照合判定過程と照合要否判定過程の結果、照合要となった位置において、前記対応づけ過程によって対応づけられたデータ符号系列中の部分系列をＰ'と表すとし、当該部分系列Ｐ'の符号の順にｐ'1，ｐ'2，…，ｐ'm'とし、前記符号系列Ｐ'は［ｐ'1，ｐ'2，…，ｐ'm'］と書き表されるとして、符号系列Ｐと符号系列Ｐ'の間の類似度を、Ｐの前からｘ個の符号を並ベてできる符号系列［ｐ1，ｐ2，…，ｐx］と、Ｐの前からｙ個の符号を並ベてできる符号系列符号系列［ｐ'1，ｐ'2，…，ｐ'y］の間の類似度を、(a) ｘ＋ｙ＜ｄを満たすｘとｙの組については既知であるとし、
(b) ｘ＋ｙ≧ｄとなるｘとｙの組については、（１）符号系列［ｐ1，ｐ2，…，ｐx-1］と符号系列［ｐ'1，ｐ'2，…，ｐ'y］の類似度、（２）符号系列［ｐ1，ｐ2，…，ｐx］と符号系列［ｐ'1，ｐ'2，…，ｐ'y-1］の類似度、（３）符号系列［ｐ1，ｐ2，…，ｐx-1］と符号系列［ｐ'1，ｐ'2，…,ｐ'y-1］の類似度の３つの類似度に、ｐxとｐ'yの類似度を各場合に応じた重み定数をかけて加えた結果の最大値とする（但し、符号系列［ｐ1］と符号系列［ｐ'1］の類似度は符号ｐ1とｐ'1の類似度とし、ｘ＋ｙ＜ｄの場合は（ａ）に従う）として計算するとして、符号系列［ｐ1，ｐ2，…，ｐx］と符号系列［ｐ'1,ｐ'2,…,ｐ'y］の類似度をｘとｙを１から各々ｍとｍ’まで増やして計算すことで符号系列Ｐと符号系列Ｐ'の類似度を求め、符号系列Ｐと符号系列Ｐ'が類似するか否かを判定し、当該位置を照合済とするものであり、類似部分系列検出装置が前記符号位置選択過程、対応付け過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、ｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする。
【００１４】
上記類似部分系列検出方法によれば、部分系列間の類似度が加法的に求められる場合に、目的符号系列Ｐを[ｐ1,ｐ2,…,ｐm]とし、符号位置選択過程によりあるｄを入力として、目的符号系列中の符号位置ｉを１から順に選び、対応づけ過程において、ｊ番目の位置の符号がｐiに対応づけられるように、データ符号系列中に位置付けられる。そして、対応付けられたデータ符号系列中の部分系列Ｐ’を[ｐ’1,ｐ’2,…,ｐ’m']とし、照合過程により、そして、ｘ＋ｙ＜ｄの時、ＰとＰ'の間の類似度を、［ｐ1,…,ｐx］と［ｐ'1,…,ｐ'y］の間の類似度は既知であるとしながら、［ｐ1,…,ｐx］と［ｐ'1,…,ｐ'y］の間の類似度は、［ｐ1,…,ｐx-1］と［ｐ'1,…,ｐ'y］の類似度、［ｐ1,…,ｐx］と［ｐ'1,…,ｐ'y-1］の類似度、［ｐ1,…,ｐx-1］と［ｐ'1,…,ｐ'y-1］の類似度に、ｐxとｐ'yの類似度に各々の場合に応じた重み定数をかけたものを加えたもののうち最大のものとしながらｘとｙを増やして計算し、ＰとＰ'の間の類似度を求め、ＰとＰ'が類似するか否かを判定し、当該位置を照合済とする。
【００１５】
そして、符号位置選択過程、対応付け過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理に関し、ｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、データ符号系列の各符号位置において、目的符号系列に類似しているか否かを判定し、目的符号系列に類似した部分系列をデータ符号系列中において検出する。これは、図１と同様、ＰとＰ'の符号の対応付けを加法的に考える際、図２で示されるように、斜線で示された領域は、既照合判定過程で対応づけられたデータ符号系列中の該部分系列が照合要否判定過程で照合要と判定された場合、これまでの照合過程による照合が行われていない。すなわちｘ＋ｙ＜ｄの場合、ｐ1,…,ｐxとｐ'1,…,ｐ'yの間に類似度判定過程により類似すると判定された符号の組は存在せず、従って、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は０としてよく、それを用いて、照合過程が行われる。この照合過程により、より効率的に照合が行え、高速な検索が可能になる。
【００１６】
本発明の類似部分系列検出方法において、前記符号位置選択過程において、符号位置選択手段は、符号位置制御に関するパラメータｄを入力として、目的符号系列Ｐを[ｐ1,ｐ2,…,ｐm]とし、データ符号系列中の着目する部分系列の長さをｍ’とするとき、前記目的符号系列と着目する部分系列の類似度の上限値ｓmaxuを、ｕとｖをｕ＋ｖ＝ｄ−１と１≦ｕ≦ｍと１≦ｖ≦ｍ'を満たす任意の自然数の組としたときの長さがｍ−ｕとｍ'−ｖの符号系列の間の類似度の上限値の最大値とし、前記ｓmaxuが与えられた閾値以下なら検出処理全体を処理を終了し、前記ｓmaxuが前記閾値を越える場合に、Ｐ中の符号位置iをi≦ｄ−１かつi≦ｍの範囲で１から小さい順に選択するものであり、前記符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、前記符号位置選択過程において、符号位置選択手段が終了と判定しない限り、類似部分系列検出装置がｄを２からｍ＋ｍ’まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする。
【００１７】
上記した類似部分系列検出方法によれば、符号位置選択過程により、図２と同様、照合過程で照合を行う際に、斜線で示される類似度が０と見なされる領域を考え、そして、残りの領域で対応づけを行った場合でもその類似度の上限が類似していると判定される閾値を越えない場合には、以降ｄを大きくしても、類似部分であるとの判定が照合過程で行われることはない。
従って、余分な符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程の繰り返し回数が削減され、照合回数が少なくなり、高速な検索が行える。
【００１８】
本発明の類似部分系列検出方法において、前記照合過程において、照合手段は、前記既照合判定過程と照合要否判定過程の結果、照合要となった位置において、目的符号系列Ｐを[ｐ1,ｐ2,…,ｐm]とし、対応づけられたデータ符号系列中の部分系列Ｐ'を[ｐ'1,ｐ'2,…,ｐ'm ]とし、ＰとＰ'の間の類似度を、x＋y＜ｄの時は、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は既知であるとしながら、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は、[ｐ1,…,ｐx-1]と[ｐ'1,…,ｐ'y]の類似度、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y-1]の類似度、[ｐ1,…,ｐx-1]と[ｐ'1,…,ｐ'y-1]の類似度にｐxとｐ'yの類似度に各々に応じた重み定数をかけたものを加えたもののうち最大のものとしながら、ｘ＋ｙはｄ'とし、各ｄ'においてどのようなｘとｙにおいてもｄ'から計算できる類似度の上限値を加えたとしても、与えられた閾値を越えない場合はＰとＰ'は非類似と判定し、これにより非類似と判定されない限り、順次ｄ'を大きくし、ＰとＰ'の間の類似度を計算し、ＰとＰ'が類似するか否かを判定するものであり、
前記符号位置選択過程、対応付け過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、類似部分系列検出装置がｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする。
【００１９】
上記類似部分系列検出方法によれば、照合過程は、図３に示すように、照合要となった位置において、目的符号系列Ｐ[ｐ1,ｐ2,…,ｐm]とし、対応づけられたデータ符号系列中の部分系列Ｐ'を[ｐ'1,ｐ'2,…,ｐ'm ]とし、ＰとＰ'の間の類似度を、x＋y＜ｄの時は、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は既知であるとしながら、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は、[ｐ1,…,ｐx-1]と[ｐ'1,…,ｐ'y]の類似度、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y-1]の類似度、[ｐ1,…,ｐx-1]と[ｐ'1,…,ｐ'y-1]の類似度に、ｐxとｐ'yの類似度に各々に応じた重み定数をかけたものを加えたもののうち最大のものとする。そして、ｘ＋ｙはｄ'とし、各ｄ'においてどのようなｘとｙにおいてもｄ'から計算できる類似度の上限値を加えたとしても、与えられた閾値を越えない場合、ＰとＰ'は類似しないと判定し、これにより類似しない判定されない限り、順次ｄ'を大きくし、ＰとＰ'の間の類似度を計算し、ＰとＰ'が類似するか否かを判定する。そして、符号位置選択過程、対応付け過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、ｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、データ符号系列の各符号位置において、目的符号系列に類似しているかを判定し、目的符号系列に類似した符号系列をデータ符号系列中において検出する。この照合過程によれば、当該対応位置において、類似すると判定される可能性がなくなり次第以降の計算を行わないため、より効率的な照合が行え、高速な検索が可能になる。
【００２０】
本発明の類似部分系列検出方法において、符号位置選択過程として上述した符号位置選択過程を行い、照合過程として上述した照合過程を行い、前記符号位置選択過程、対応付け過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、前記符号位置選択過程において、符号位置選択手段が終了と判定しない限り、類似部分系列検出装置がｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする。
上記類似部分系列検出方法によれば、余分な符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程の繰り返し回数が削減され、照合回数が少なくなり、また、対応位置において類似すると判定される可能性がなくなり次第以降の計算を行わないため、より効率的な照合が行え、高速な検索が可能になる。
【００２１】
本発明の類似部分系列検出方法において、部分系列選択手段が前記目的符号系列中のある部分系列を選択する部分系列選択過程と、部分系列検出手段が前記部分系列選択過程で選ばれた部分系列を前記データ符号系列中で検出する部分系列検出過程と、部分系列対応付け手段が前記部分系列検出過程により部分系列が検出された位置に基づき、前記目的符号系列をデータ符号系列中に対応付け、対応づけられた該位置に類似部分系列が検出されたとし、当該位置を照合済とする部分系列対応付け過程とを更に備え、類似部分系列検出装置が前記部分系列選択過程、部分系列検出過程、部分系列対応づけ過程による処理を行った後、前記符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を繰り返して、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする
【００２２】
上記類似部分系列検出方法によれば、部分系列選択過程により選択された部分系列の長さは目的符号系列の長さ以下であり、一般に、目的符号系列よりも効率的に検出できる。そして、この部分系列選択過程、部分系列検出過程および部分系列対応付け過程において照合済となった位置においては、部分系列対応付け過程、符号位置選択過程、対応付け過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による繰り返し処理が不要となり、従ってこの繰り返し回数が削減され、照合回数が少なくなるため、類似部分系列のより高速な検出を実現することができる。
【００２３】
本発明の類似部分系列検出方法において、前記部分系列検出過程において、部分系列検出手段は、前記部分系列選択過程で選ばれた部分系列と完全に一致する部分系列を前記データ符号系列中で検出するものであり、類似部分系列検出装置が前記部分系列選択過程、部分系列検出過程、部分系列対応づけ過程による処理を行った後、前記符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を繰り返して、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする
本発明の類似部分系列検出方法によれば、部分系列検出過程は、部分系列選択過程で選ばれた部分系列と完全に一致する部分系列をデータ符号系列中で検出するため、請求項６に示す部分系列検出過程よりも更に効率的に行え、より高速な検出が可能になる。
【００２４】
本発明の類似部分系列検出方法において、前記照合過程において、照合手段は、閾値θと照合範囲Ｒを入力とし、前記目的符号系列とデータ符号系列の対応付けされた位置の部分系列の照合範囲内での類似度がθより大きいか否か判定することで、当該位置の部分系列が類似部分系列か否かを判定し、当該位置を照合済とするものであり、類似部分系列検出装置が前記部分系列選択過程、部分系列検出過程、部分系列対応づけ過程を行った後、前記符号位置選択過程、対応づけ過程、既照合判定過程、類似度判定過程、照合要否判定過程、照合過程による処理を、Ｒを目的符号系列の長さから、部分系列検出過程で選択された部分系列の長さまで小さくしながら繰り返して、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする。
上記類似部分系列検出方法によれば、部分系列検出過程での照合を効率良く行なうことができ、高速な検出が可能となる。
【００２５】
上記した課題を解決するために、本発明は、ある文字列からなる目的符号系列に類似した符号系列を、文字列探索によってより長い符号系列であるデータ符号系列中において検出する類似部分系列検出装置であって、前記目的符号系列中のある一つの未選択の符号位置を順次選択する符号位置選択手段と、前記符号位置選択過程の結果を用いて、前記目的符号系列を前記データ符号系列中に位置付ける対応付け手段と、前記対応付け手段で対応づけた位置が既に照合済の位置か否かを判定する既照合判定手段と、前記対応付け手段で対応づけた位置において、前記符号位置選択手段で選択した符号位置に対する前記データ符号系列中の符号との類似度を判定する類似度判定手段と、前記類似度判定手段での結果に基づき、その位置での照合の要否を判定する照合要否判定手段と、前記照合要となった位置において類似しているか否かを判定して当該位置を照合済とし、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出する照合手段とを備えたことを特徴とする。
【００２６】
本発明の類似部分系列検出装置によれば、符号位置選択手段において目的符号系列中の符号を順次選択し、対応づけ手段によりデータ符号系列中に対応づけられた際、既照合判定手段により対応づけられた当該位置が未照合であり、かつ、類似度判定手段と照合要否判定手段により、当該位置の部分系列が符号位置選択手段で選択した符号位置の符号と類似する符号を対応する位置に持っている場合のみ、照合手段による照合処理を行うものとしている。このことにより、データ符号系列中の部分系列が類似する可能性のある位置のみで照合過程を行うことかでき、従って、照合回数を従来の「ずらし照合法」に比べて削減することができ、より高速な検出が可能にした類似部分系列検出装置を提供することができる。なお、本発明は、音楽、映像、その他時系列情報の検索に用いられ、例えば、大量の音楽の音響信号からなる音楽データベースにおいて、音楽を時系列の音響信号を順次符号化した符号系列、すなわちデータ符号系列として蓄積し、あるお気に入りの楽曲の１フレーズを同様に符号化し、これを目的符号系列として類似部分系列検出を行うことで、お気に入りの楽曲と類似する音楽、例えば、別の編曲、別奏者、ライブ版等の検索が可能になる。また、従来、ＭＩＤＩデータ等を対象とした鼻歌検索などは従来から知られているが、本発明では、自分で歌った歌や鼻歌を符号系列化し目的符号系列とし、上記の音響信号による音楽データベースに対するた歌声や鼻歌による音楽検索も可能になる。
【００２７】
本発明の類似部分系列検出装置において、前記目的符号系列中のある部分系列を選択する部分系列選択手段と、前記部分系列選択手段で選ばれた部分系列を前記データ符号系列中で検出する部分系列検出手段と、前記部分系列検出手段により部分系列が検出された位置に基づき、前記目的符号系列をデータ符号系列中に対応付け、対応づけられた該位置に類似部分系列が検出されたとし、当該位置を照合済とする部分系列対応付け手段とを更に備え、前記照合手段は、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出することを特徴とする。
【００２８】
本発明の類似部分系列検出装置によれば、目的符号系列中のある部分系列を選択する部分系列選択手段と、部分系列選択手段で選択された部分系列をデータ符号系列中で検出する部分系列検出手段と、部分系列が検出された位置に基づき、目的符号系列をデータ符号系列中に対応付け、対応付けられた当該位置に類似部分系列が検出されたとし、当該位置を照合済とする部分系列対応付け手段とを更に備え、照合手段により、データ符号系列の各符号位置において目的符号系列に類似しているか否かを判定し、目的符号系列に類似した符号系列をデータ符号系列中において検出する。
先の部分系列選択手段により選択された部分系列の長さは目的符号系列の長さ以下であり、一般に、目的符号系列よりも効率的に検出できる。そして、この部分系列選択手段、部分系列検出手段および部分系列対応付け手段において照合済となった位置においては、部分系列対応付け手段、符号位置選択手段、対応付け手段、既照合判定手段、類似度判定手段、照合要否判定手段、照合手段による繰り返し処理が不要となり、従ってこの繰り返し回数が削減され、照合回数が少なくなるため、類似部分系列のより高速な検出を実現した類似部分系列検出装置を提供することができる。
【００２９】
上記した課題を解決するために本発明は、ある目的符号系列に類似した符号系列を、より長い符号系列であるデータ符号系列中において検出する類似部分系列検出装置に用いられる類似部分系列検出プログラムであって、前記目的符号系列中のある一つの未選択の符号位置を順次選択する符号位置選択ステップと、前記選択結果を用いて、前記目的符号系列を前記データ符号系列中に位置付ける対応付けステップと、前記位置が既に照合済の位置か否かを判定する既照合判定ステップと、前記対応づけた位置において、前記選択した符号位置に対する前記データ符号系列中の符号との類似度を判定する類似度判定ステップと、前記類似度判定結果に基づき、その位置での照合の要否を判定する照合要否判定ステップと、前記照合要となった位置において類似しているか否かを判定して当該位置を照合済とし、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出する照合ステップと、をコンピュータに実行させることを特徴とする。
【００３０】
上記した類似部分系列検出プログラムをコンピュータ上で実行させることにより、符号位置選択ステップにおいて、目的符号系列中の符号を順次選択し、対応づけ過程によりデータ符号系列中に対応づけられた際、既照合判定ステップにより対応づけられた当該位置が未照合であり、かつ、類似度判定ステップと照合要否判定ステップにより、当該位置の部分系列が符号位置選択ステップで選択した符号位置の符号と類似する符号を対応する位置に持っている場合のみ、照合過ステップによる照合処理を行うものとしている。このことにより、データ符号系列中の部分系列が類似する可能性のある位置のみで照合ステップの実行を行うことかでき、従って、照合回数を従来の「ずらし照合法」に比べて削減することができ、従来と比較して高速な検出が可能となる。
【００３１】
本発明の類似部分系列検出プログラムにおいて、それぞれの符号α1，α2，…について、当該符号を並ベて得られる列である符号系列の各符号を順に書き下した場合、［α1，α2，…］と書き表すとし、目的符号系列をＰで表し、目的符号系列の各符号を順にｐ1．ｐ2，…，ｐmで表し、目的符号系列ｐを［ｐ1，ｐ2，…，ｐm］と書き表すとしたとき、前記符号位置選択ステップは、符号位置制御に関するパラメータｄを入力として、Ｐ中の符号位置iをi≦ｄ−1かつi≦ｍの範囲で１から小さい順に選択するものであり、前記対応付け過程は、ｊをｄ−iとし、ｊ≦ｍ'のときに、符号位置選択過程で選択した符号がｊ番目の符号に対応するよう前記目的符号系列を前記データ符号系列中に位置付けるステップを含み、前記照合ステップは、既照合判定と照合要否判定の各ステップによる処理結果、照合要となった位置において、前記対応づけ過程によって対応づけられたデータ符号系列中の部分系列をＰ'と表すとし、該部分系列Ｐ'を符号の順にｐ'1，ｐ'2，…，ｐ'm'とし、該符号系列Ｐ'は［ｐ'1，ｐ'2，…，ｐ'm'］と書き表されるとして、符号系列Ｐと符号系列Ｐ'の間の類似度を、Ｐの前からｘ個の符号を並ベてできる符号系列［ｐ1，ｐ2，…，ｐx］と、Ｐの前からｙ個の符号を並ベてできる符号系列符号系列［ｐ'1，ｐ'2，…，ｐ'y］の間の類似度を、（ａ）ｘ＋ｙ＜ｄを満たすｘとｙの組については既知であるとし、（ｂ）ｘ＋ｙ≧ｄとなるｘとｙの組については、（１）符号系列［ｐ1，ｐ2，…，ｐx-1］と符号系列［ｐ'1，ｐ'2，…，ｐ'y］の類似度、（２）符号系列［ｐ1，ｐ2，…，ｐx］と符号系列［ｐ'1，ｐ'2，…，ｐ'y-1］の類似度、（３）符号系列［ｐ1，ｐ2，…，ｐx-1］と符号系列［ｐ'1，ｐ'2，…ｐ'y-1］の類似度の３つの類似度に、ｐxとｐ'yの類似度を各場合に応じた重み定数をかけて加えた結果の最大値とする（ただし、符号系列［ｐ1］と符号系列［ｐ'1］の類似度は符号ｐ1とｐ'1の類似度とし、ｘ＋ｙ＜ｄの場合は（ａ）に従う）として計算するとして、符号系列［ｐ1，ｐ2，…，ｐx］と符号系列［ｐ'1,ｐ'2,…ｐ'y］の類似度をｘとｙを１から各々ｍとｍ’まで増やして計算すことで符号系列Ｐと符号系列Ｐ'の類似度を求め、符号系列Ｐと符号系列Ｐ'が類似するか否かを判定し、当該位置を照合済とするステップを含み、前記照合ステップは、更に、前記符号位置選択、対応付け、既照合判定、類似度判定、照合要否判定、照合の各ステップによる処理を、ｄを２からｍ＋ｍ'まで順に大きくしながら繰り返すことにより、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出するステップを含み、前記各ステップをコンピュータに実行させることを特徴とする。
【００３２】
上記した類似部分系列検出プログラムをコンピュータ上で実行させることにより、符号位置選択ステップ、対応付けステップ、既照合判定ステップ、類似度判定ステップ、照合要否判定ステップ、照合ステップによる処理に関し、ｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、データ符号系列の各符号位置において、目的符号系列に類似しているか否かを判定し、目的符号系列に類似した部分系列をデータ符号系列中において検出する。このことは、図１と同様、ＰとＰ'の符号の対応付けを加法的に考える際、図２で示されるように、斜線で示された領域は、既照合判定ステップで対応づけられたデータ符号系列中の該部分系列が照合要否判定ステップで照合要と判定された場合、これまでの照合ステップによる照合が行われていない。すなわち、ｘ＋ｙ＜ｄの場合、ｐ1,…,ｐxとｐ'1,…,ｐ'yの間に類似度判定過程により類似すると判定された符号の組は存在せず、従って、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は０としてよく、それを用いて、照合過程が行われる。この照合ステップによりより効率的に照合が行え、高速な検索が可能になる。
【００３３】
本発明の類似部分系列検出プログラムにおいて、前記符号位置選択ステップは、前記符号位置制御に関するパラメータｄを入力として、目的符号系列Ｐを[ｐ1,ｐ2…,ｐm]とし、データ符号系列中の着目する部分系列の長さをｍ’とするとき、前記目的符号系列と着目する部分系列の類似度の上限値ｓmaxuを、ｕとｖをｕ＋ｖ＝ｄ−１と１≦ｕ≦ｍと１≦ｖ≦ｍ'を満たす任意の自然数の組としたときの長さがｍ−ｕとｍ'−ｖの符号系列の間の類似度の上限値の最大値とし、前記ｓmaxuが与えられた閾値以下なら検出処理全体を処理を終了し、前記ｓmaxuが前記閾値を越える場合に、Ｐ中の符号位置iをi≦ｄ−１かつi≦ｍの範囲で１から小さい順に選択するステップを含み、前記照合ステップは、前記符号位置選択、対応づけ、既照合判定、類似度判定、照合要否判定、照合の各ステップによる処理を、前記符号位置選択過程において終了と判定されない限り、ｄを２からｍ＋ｍ’まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出するステップを含み、前記各ステップをコンピュータに実行させることを特徴とする。
【００３４】
上記した類似部分系列検出プログラムをコンピュータ上で実行させることにより、符号位置選択ステップにより、図２と同様、照合ステップで照合を行う際に、斜線で示される類似度が０と見なされる領域を考え、そして、残りの領域で対応づけを行った場合でもその類似度の上限が類似していると判定される閾値を越えない場合には、以降ｄを大きくしても、類似部分であるとの判定が照合過程で行われることはない。
従って、余分な符号位置選択ステップ、対応付けステップ、既照合判定ステップ、類似度判定ステップ、照合要否判定ステップ、照合ステップの繰り返し回数が削減され、照合回数が少なくなり、高速な検索が行える。
【００３５】
本発明の類似部分系列検出プログラムにおいて、前記照合ステップは、更に、照合要となった位置において、目的符号系列Ｐを[ｐ1,ｐ2,…,ｐm]とし、対応づけられたデータ符号系列中の部分系列Ｐ'を[ｐ'1,ｐ'2,…,ｐ'm ] とし、ＰとＰ'の間の類似度を、ｘ＋ｙ＜ｄの時は、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は既知であるとしながら、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y]の間の類似度は、[ｐ1,…,ｐx-1]と[ｐ'1,…,ｐ'y]の類似度、[ｐ1,…,ｐx]と[ｐ'1,…,ｐ'y-1]の類似度、[ｐ1,…,ｐx-1]と[ｐ'1,…,ｐ'y-1]の類似度に、ｐxとｐ'yの類似度に各々に応じた重み定数をかけたものを加えたもののうち最大のものとしながら、ｘ＋ｙはｄ'とし、各ｄ'においてどのようなｘとｙにおいてもｄ'から計算できる類似度の上限値を加えたとしても、与えられた閾値を越えない場合はＰとＰ'は非類似と判定し、これにより非類似と判定されない限り、順次ｄ'を大きくし、ＰとＰ'の間の類似度を計算し、ＰとＰ'が類似するか否かを判定するステップと、前記符号位置選択、対応付け、既照合判定、類似度判定、照合要否判定、照合の各ステップによる処理を、ｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出するステップとを含み、前記各ステップをコンピュータに実行させることを特徴とする。上記した類似部分系列検出プログラムをコンピュータ上で実行させることにより、照合ステップにより対応位置において類似すると判定される可能性がなくなり次第以降の計算を行わないためにより効率的な照合が行え、高速な検索が可能になる。
【００３６】
本発明の類似部分系列検出プログラムにおいて、前記照合ステップは、前記符号位置選択、対応付け、既照合判定、類似度判定、照合要否判定、照合による各ステップの処理を、前記符号位置選択過程により終了と判定されない限り、ｄを２からｍ＋ｍ'まで順に大きくしながら繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出するステップを含み、前記各ステップをコンピュータに実行させることを特徴とする。
上記した類似部分系列検出プログラムをコンピュータ上で実行させることにより、余分な符号位置選択ステップ、対応付けステップ、既照合判定ステップ、類似度判定ステップ、照合要否判定ステップ、照合ステップの繰り返し回数が削減され、従って、照合回数が少なくなり、また、対応位置において類似すると判定される可能性がなくなり次第以降の計算を行わないため、より効率的な照合が行え、高速な検索が可能になる。
【００３７】
本発明の類似部分系列検出プログラムにおいて、前記目的符号系列中のある部分系列を選択する部分系列選択ステップと、前記選択された部分系列を前記データ符号系列中で検出する部分系列検出ステップと、前記部分系列が検出された位置に基づき、前記目的符号系列をデータ符号系列中に対応付け、対応づけられた当該位置に類似部分系列が検出されたとし、当該位置を照合済とする部分系列対応付けステップと、前記部分系列選択、部分系列検出の各ステップによる処理を行い、前記部分系列対応づけ、符号位置選択、対応づけ、既照合判定、類似度判定、照合要否判定、照合による各ステップの処理を繰り返して、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出する照合ステップとをコンピュータに実行させることを特徴とする。
【００３８】
上記した類似部分系列検出プログラムをコンピュータ上で実行させることにより、部分系列選択ステップにより選択された部分系列の長さは目的符号系列の長さ以下であり、一般に、目的符号系列よりも効率的に検出できる。そして、この部分系列選択ステップ、部分系列検出ステップおよび部分系列対応付けステップにおいて照合済となった位置においては、部分系列対応付けステップ、符号位置選択ステップ、対応付けステップ、既照合判定ステップ、類似度判定ステップ、照合要否判定ステップ、照合ステップによる繰り返し処理が不要となり、従ってこの繰り返し回数が削減され、照合回数が少なくなるため、類似部分系列のより高速な検出を実現することができる。
【００３９】
本発明の類似部分系列検出プログラムにおいて、前記部分系列検出ステップは、前記選択された部分系列と完全に一致する部分系列を前記データ符号系列中で検出するステップを含み、前記照合ステップは、前記部分系列選択、部分系列検出の各ステップによる処理を行い、前記部分系列対応づけ、符号位置選択、対応づけ、既照合判定、類似度判定、照合要否判定、照合の各ステップによる処理を繰り返し、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出するステップを含み、前記各ステップをコンピュータに実行させることを特徴とする。
上記した類似部分系列検出プログラムをコンピュータ上で実行させることにより、部分系列検出ステップは、部分系列選択ステップで選ばれた部分系列と完全に一致する部分系列をデータ符号系列中で検出するため、先に示した部分系列検ステップよりも更に効率的に行え、より高速な検出が可能になる。
【００４０】
本発明の類似部分系列検出プログラムにおいて、前記照合ステップは、閾値θと照合範囲Ｒを入力とし、前記目的符号系列とデータ符号系列の対応付けされた位置の部分系列の照合範囲内での類似度がθより大きいか否か判定することで、当該位置の部分系列が類似部分系列か否かを判定し、当該位置を照合済とするステップと、前記部分系列選択、部分系列検出の各ステップによる処理を行い、前記部分系列対応づけ、符号位置選択、対応づけ、既照合判定、類似度判定、照合要否判定、照合の各ステップによる処理を、Ｒを目的符号系列の長さから、部分系列検出過程で選択された部分系列の長さまで小さくしながら繰り返して、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出するステップとを含み、前記各ステップをコンピュータに実行させることを特徴とする。
上記した類似部分系列検出プログラムをコンピュータ上で実行させることにより、部分系列検出ステップでの照合を効率良く行なうことができ、高速な検出が可能となる。
【００４１】
上記した課題を解決するために本発明は、ある目的符号系列に類似した符号系列を、より長い符号系列であるデータ符号系列中において検出する類似部分系列検出装置に用いられる類似部分系列検出プログラムを記録したコンピュータ読み取り可能な記録媒体であって、前記目的符号系列中のある一つの未選択の符号位置を順次選択する符号位置選択ステップと、前記選択結果を用いて、前記目的符号系列を前記データ符号系列中に位置付ける対応付けステップと、前記位置が既に照合済の位置か否かを判定する既照合判定ステップと、前記対応づけた位置において、前記選択した符号位置に対する前記データ符号系列中の符号との類似度を判定する類似度判定ステップと、前記類似度判定結果に基づき、その位置での照合の要否を判定する照合要否判定ステップと、前記照合要となった位置において類似しているか否かを判定して当該位置を照合済とし、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出する照合ステップと、をコンピュータに実行させる類似部分系列検出プログラムを記録したことを特徴とする。
【００４２】
上記記録媒体に記録された類似部分系列検出プログラムを読み出しコンピュータ上で実行させることにより、符号位置選択ステップにおいて、目的符号系列中の符号を順次選択し、対応づけ過程によりデータ符号系列中に対応づけられた際、既照合判定ステップにより対応づけられた当該位置が未照合であり、かつ、類似度判定ステップと照合要否判定ステップにより、当該位置の部分系列が符号位置選択ステップで選択した符号位置の符号と類似する符号を対応する位置に持っている場合のみ、照合過ステップによる照合処理を行うものとしている。このことにより、データ符号系列中の部分系列が類似する可能性のある位置のみで照合ステップの実行を行うことかでき、従って、照合回数を従来の「ずらし照合法」に比べて削減することができ、従来と比較して高速な検出が可能となる。
【００４３】
本発明の記録媒体において、前記目的符号系列中のある部分系列を選択する部分系列選択ステップと、前記選択された部分系列を前記データ符号系列中で検出する部分系列検出ステップと、前記部分系列が検出された位置に基づき、前記目的符号系列をデータ符号系列中に対応付け、対応づけられた当該位置に類似部分系列が検出されたとし、当該位置を照合済とする部分系列対応付けステップと、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているかを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出する照合ステップと、をコンピュータに実行させる類似部分系列検出プログラムを記録したことを特徴とする。
【００４４】
上記記録媒体に記録された類似部分系列検出プログラムを読み出しコンピュータ上で実行させることにより、部分系列選択ステップにより選択された部分系列の長さは目的符号系列の長さ以下であり、一般に、目的符号系列よりも効率的に検出できる。そして、この部分系列選択ステップ、部分系列検出ステップおよび部分系列対応付けステップにおいて照合済となった位置においては、部分系列対応付けステップ、符号位置選択ステップ、対応付けステップ、既照合判定ステップ、類似度判定ステップ、照合要否判定ステップ、照合ステップによる繰り返し処理が不要となり、従ってこの繰り返し回数が削減され、照合回数が少なくなるため、類似部分系列のより高速な検出を実現することができる。
【００４５】
【発明の実施の形態】
以下、本発明実施形態について詳細に説明する。最初に本発明の第一の実施形態について説明するが、ここでは、音楽の和音系列の各和音を符号化した符号系列を対象とし、検索の対象となるデータ符号系列と目的符号系列とし、この目的符号系列によりデータ符号系列中の類似音楽を検索するものとする。具体的に、長さｍの目的符号系列と、ユーザからの入力である正規化類似度の閾値θuをもとに、長さｍ'の類似部分系列をデータ符号系列中から検出する例について説明する。
なお、ここで、符号系列間の類似度の閾値θはθ＝(ｍ＋ｍ')×θｕとし、目的符号系列との類似度がθより大きい長さｍ'の系列を類似する系列としている。ここで、符号間（文字間）の類似度は０〜１の範囲の実数値である。また、符号系列間の類似度については、ＤＰマッチングを、また、先に説明した条件Ａで用いた結果得られるものとする。
【００４６】
図４に、本発明一実施形態における類似部分系列検出装置の構成が示されている。以下に示す各ブロックは、具体的には、ＣＰＵならびにメモリを含む周辺ＬＳＩで構成され、ＣＰＵがメモリに記録されたプログラムを逐次読み出し実行することによりそのブロックが持つ機能を実現する。すなわち、コンピュータ上で実現される。
本発明の類似部分系列検出装置は、符号系列入力装置１０１と、符号系列入力装置１０２と、パラメータｄ制御装置１０３と、符号位置選択装置１０４と、対応付け装置１０５と、類似度判定装置１０６と、照合要否判定装置１０７と、照合装置１０８と、文字間類似度表入力装置１０９と、既照合判定装置１１０で構成される。
【００４７】
符号系列入力装置１０１は、目的符号系列を受信してパラメータｄ制御装置１０３と対応付け装置１０５へ供給する。符号系列入力装置１０２は、データ符号系列を受信してパラメータｄ制御装置１０３へ供給する。符号位置選択装置１０４は、目的符号系列中のある一つの未選択の符号位置を順次選択して対応付け装置１０５へ供給する。対応付け装置１０５は、符号位置選択装置１０４出力を用いて、目的符号系列をデータ符号系列中に位置付け、既照合判定装置１１０へ供給する。
【００４８】
対応付け装置１０５出力は、他に類似度判定装置１０６にも供給され、類似度判定装置１０６は、対応付け装置１０５で対応づけた位置において、符号位置選択装置１０４で選択した符号位置に対するデータ符号系列中の符号との類似度を判定して照合要否判定装置１０７へ供給する。照合要否判定装置１０７は、類似度判定装置１０６での判定結果に基づき、その位置での照合の要否を判定して照合装置１０８へ供給する。
照合装置１０８へは、他に、既照合判定装置１１０からも対応付け装置１０５で対応づけた位置が既に照合済の位置か否かを判定した結果も供給されており、対応付け装置１０５で対応づけた位置において、符号位置選択装置１０４で選択した符号位置に対するデータ符号系列中の符号との類似度を判定する。照合装置１０８は、更に、照合要否判定装置１０７で照合要とした位置において類似しているか否かを判定して当該位置を照合済とし、データ符号系列の各符号位置において、目的符号系列に類似しているかを判定し、目的符号系列に類似した符号系列をデータ符号系列中において検出する。
【００４９】
図５は、図４に示す類似部分系列検出装置の動作を説明するために引用したフローチャートであり、具体的には、本発明の類似部分系列検出プログラムの処理手順を示す。以下、図５に示すフローチャートを参照しながら図４に示す類似部分系列検出装置の動作について詳細に説明する。まず、符号系列入力装置１０１によりファイルから目的符号系列を読み込む。そして、読み込んだ目的符号系列Ｐを[ｐ1,ｐ2,…,ｐn]とし、パラメータｄ制御装置１０３、符号位置選択装置１０４、対応付け装置１０５に供給する。一方、符号系列入力装置１０２は、ファイルからデータ符号系列を読み込む。読み込んだデータ符号系列Ｔを[ｔ1,ｔ2，…,ｔn]とし、パラメータｄ制御装置１０３、対応付け装置１０５に供給する。
【００５０】
文字間類似度表入力装置１０９は、文字間類似度表をファイルから読み込む。文字間類似度表は、文字間の類似度が書き込まれたファイルであり、この表が類似度判定装置１０６、照合装置装置１０８により参照される。パラメータｄ制御装置１０３は、パラメータｄの値を“２”にセットし（ステップＳ１０１）、ｄ≦ｍ＋ｍ'かを判定し、ここで、条件が成立したらならパラメータｄを符号位置選択装置１０４に入力して待ち状態となる（ステップＳ１０２）。その後は、対応付け装置１０５からのパラメータｄの増加要求があると、パラメータｄを“１”増やし（ステップＳ１０７）、ステップＳ１０２の判定を繰り返す。なお、ステップＳ１０２において、パラメータｄ≦ｍ＋ｍ'が不成立の場合、本類似音楽検索装置は停止する。符号位置選択装置１０４は、パラメータｄを入力とし、ｓmaxu＝ｍ＋ｍ'＋２−dとして計算し（ステップＳ１０３）、ｓmaxu＞θを判定し（ステップＳ１０４）、ここで条件が不成立の場合類似音楽装置を停止させ、条件成立の場合は、ｉ＝１とする（ステップＳ１０５）。そして、ｉ≦ｄ−１、かつ、ｉ≦ｍか否かを判定し（ステップＳ１０６）、条件成立の場合、ｉとｄを対応付け装置１０５に入力して待ち状態になる。条件不成立の場合は、パラメータｄ制御装置１０３にパラメータｉの増加要求を出し、処理を終了する。
【００５１】
待ち状態では、対応付け装置１０５からｉの増加要求を受けとると、ｉを１増やし（ステップＳ１１４）、ｉ≦ｄ−１、かつ、ｉ≦ｍか否かを判定する（ステップＳ１０６）。対応付け装置１０５は、入力されたiにより、ｊ＝ｄ−ｉとし（Ｓ１０８）、目的符号系列をデータ符号系列に対応付ける。本装置では、長さｍ'の注目窓をまだずらせるか否か判定しながらデータ符号系列上で１符号ずつずらしていき（ステップＳ１００）、注目窓が設定できたなら、注目窓内の部分符号系列をＰ'とする（ステップＳ１１０）。ここで、Ｐ’を[ｐ’1,ｐ’2,…,ｐ’m']とする。そして、Ｐ，ｄ，Ｐ’のデータ符号系列中での位置情報と、ｉ，ｊを既照合判定装置１１０と類似度判定装置１０６に供給する。そして、対応付けられる部分がなくなると、符号位置選択装置１０４にｉの増加要求を出す。
【００５２】
既照合判定装置１１０は、与えられたＰ’のデータ符号系列上の位置が未照合か判定し（ステップＳ１１１）、その照合結果と、ｄ，ｉ，ｊ，Ｐ，Ｐ’を照合装置１０６に供給する。
類似度判定装置１００は与えられたｉ，ｊ，Ｐ，Ｐ’と文字間類似度表から、ｓ（ｐi，ｐ’j）を参照し、照合要否判定結果に供給する。照合要否判定装置１０７は、与えられたｓ（ｐi，ｐ’j）が０より大きければ照合要と判定、そうでなければ非照合とする（ステップＳ１１２）。そして、その照合結果を照合装置１０８に供給する。
【００５３】
照合装置１０７は、既照合判定装置１１０による判定結果が未照合で、かつ、照合要否判定装置１０７の判定結果が照合要の場合に照合を行い、そうでない場合は照合を行わず、対応付けを待つ（ステップＳ１１１，Ｓ１１２）。
照合は、ＰとＰ’の間の類似度を、ｘ＋ｙ＜ｄの時は、[ｐ1,…,ｐx]と[ｐ’1,…,ｐ’y]の間の類似度は既知であるとしながら、すなわち、ｘ＋ｙ＜ｄの時は、ｇ（ｘ，ｙ）＝０としながら、ｘ＋ｙ＝ｄ'とし、各ｄ'においてｇ（ｘ，ｙ）＋ｍ＋ｍ'−ｘ−ｙの最大値を求め、この値がθを越えない場合、ＰとＰ'は類似しないと判定し、これにより類似しないと判定されない限り、順次ｄ'を大きくし、ＰとＰ'の間の類似度を計算し、ＰとＰ'が類似するか否かを判定する（ステップＳ１１３）。
類似度がθを越えた場合、このＰ'の位置に類似部分を検出したとする。そして、この照合を行った場合、Ｐ'のデータ符号系列上での位置は既照合とする。そして、照合を行った場合は照合回数を“１”増やす。この照合回数が“ｎ−ｍ'＋1”回を越えた場合、すなわち、照合し得る全ての対応付けで照合を行った場合、本類似音楽検索装置の動作は停止し、否の場合は次の対応付けを待つ（ステップＳ１１５）。
【００５４】
以上、本発明一実施形態の動作を説明したが、対応付け装置１０５に、類似度判定装置１０６と照合要否判定装置１０７の機能を加え、対応付け装置１０５において、ｊ番目にｐｉとの類似度が０より大きい文字をもつ位置にだけ対応付けることも行える。また、ＤＰマッチングにおいて、傾斜制限、各符号の対応付けに異なる制限がある場合でも、符号間の類似度が加法的であれば、上記と同様な発明の実施が可能である。
【００５５】
次に、上記した実施形態の実験結果について説明する。上記した実施形態と、従来技術であるＤＰマッチングならびにずらし照合を行う装置をパソコン上に実装して、その検出速度を計測し比較した。
実験では、約６時間の音楽データから、約１５秒の音楽の断片３０個を検出し、その検出にかかった時間（検出時間）を計測した。平均の検出時間は、上記実装例では２．１秒、従来手法では８．７秒であり、約４倍高速な検出が行えた。
【００５６】
次に本発明の他の実施形態について説明する。この実施形態は、特定の音響信号をより長い音響信号から検出する音響検出システムに採用したものである。この実施形態では、検出したい音響信号を符号系列化したものを目的符号系列、同様により長い音響信号を符号系列化したものをデータ符号系列とする。ここでは、文字間の類似度は２つの文字が一致する場合のみ１、一致しない場合は０である。そして、目的符号系列Ｐを[ｐ1,ｐ2,…,ｐm]とし、データ符号系列Ｔを[ｔ1,ｔ2,…,ｔn]としたとき、目的符号系列との類似度が類似閾値θより大きい、長さｍの部分系列の、データ符号系列での位置を出力する。なお、ここで類似度は、注目する部分系列Ｐ’を[ｐ’1,ｐ’2,…,ｐ’m]としたとき、以下の演算式（６）とする。
【数５】
0003759438.tif 000006
これは、従来技術であるＤＰマッチングにおいて、マッチングを行なう二つの系列の長さを等しいとし、そして、ｉh−ｊh≦ｒで表される整合窓についてｒ＝０とした場合と考えられる。
【００５７】
図６に本実施例における他の実施形態の内部構成をブロック図で示す。ここに示す実施形態も図４に示す実施形態同様、コンピュータ上に展開され実現されるものとする。
図４に示す実施形態との基本的な差異は、パラメータｄ制御装置１０３に代わって、部分系列選択装置２０３と、部分系列抽出装置２０４が付加されていることにある。他は図４に示す実施形態と同様であるため、重複を避ける意味で詳細な説明を省略する。
部分系列選択装置２０３は、符号系列入力装置２０１を介して目的符号系列を取り込み、目的符号系列中のある部分系列を選択して部分系列検出装置２０４へ供給する。部分系列検出装置２０４は、符号系列入力装置を介してデータ符号系列を取り込み、部分系列選択装置２０３で選ばれた部分系列をデータ符号系列中で検出して符号位置選択装置２０５へ供給する。
【００５８】
図７は、図６に示す本発明実施形態の動作を説明するために引用したフローチャートであり、具体的には、本発明の類似部分系列検出プログラムの処理手順を示す。
以下、図７に示すフローチャートを参照しながら図６に示す本発明実施形態の動作について詳細に説明する。
ここでは、符号系列入力装置２０１によりファイルから目的符号系列を読み込む。読み込んだ目的符号系列をとし、部分系列選択装置２０３、符号位置選択装置２０５、対応付け装置２０６に供給する。
そして、符号系列入力装置２０２によりファイルからデータ符号系列を読み込む。読み込んだデータ符号系列Ｔを[ｔ1,ｔ2…,ｔn]とし、部分系列検出装置２０４、対応付け装置２０６に供給する。
【００５９】
部分系列選択装置２０３は、Ｒmin＝θ＋１とし、Ｐの部分系列Ｐpar＝[ｐ1,ｐ2,…,ｐmin]を選択し（ステップＳ２０１）、部分系列検出装置２０４に供給する。部分系列検出装置２０４は、ＰparをＢＭ法等の完全一致の文字列探索によりデータ符号系列のＰparを検出する。ＢＭ法については、「野下浩平、高岡忠雄、町田元（編）、基本的算法、岩波講座、情報科学１０、岩波書店１９８３年発行」に開示されており、完全一致の文字列照合を行う方法である。そして、Ｐparが検出されたデータ符号系列上の位置において、Ｐが検出されたとし、データ符号系列上の該位置は既照合とする（ステップＳ２０２）。そして、制御を符号位置選択装置２０５に移す。
【００６０】
符号位置選択装置２０５は、Ｒ＝ｍとし（ステップＳ２０３）、Ｒ＞ｍminの間（ステップＳ２１１）、Ｒを１減らしながら（ステップＳ２０９）、順次、対応付け装置に２０６にＲを供給する。Ｒ≦ｍminになると、本音響検出システムを停止させる。対応付け装置２０６は、入力されたＲにより、目的符号系列をデータ符号系列に対応付ける。本装置では幅Ｒの注目窓をまだずらせるかを判定しながらデータ符号系列上で１符号ずつずらしていき（ステップＳ２０４）、注目窓が設定できたなら、注目窓内の部分符号系列をＰ'とする（ステップＳ２０５）。なお、Ｐ'を [ｐ'1,ｐ'2,…,ｐ'R]とする。次に、Ｐ，Ｐ'とＲを既照合判定装置２０７と類似度判定装置２０９に供給する。そして、対応付けられる部分がなくなると、符号位置選択装置２０５にＲの減少を要求する。
【００６１】
一方、既照合判定装置２０７は、与えられたＰ'におけるデータ符号系列上の先頭の位置が未照合か否かを判定し（ステップＳ２０６）、その照合結果と、Ｒ、Ｐ、Ｐ'を照合装置２０８に供給する。
類似度判定装置２０９は、与えられたＲ、Ｐ、Ｐ'より、ｓ（ｐR，ｐ'R)をｐRとｐ'Rが同じ文字なら“１”、そうでないなら“０”とする。そして、ｓ（ｐR，ｐ'R)を照合要否判定装置２１０に供給する。
照合要否判定装置２１０は、与えられたｓ（ｐR，ｐ'R)が“０”より大きけれは照合要と判定、そうでなければ非照合とする（ステップＳ２０７）。そして、その照合結果を照合装置２０８に供給する。
【００６２】
照合装置２０８は、既照合判定装置２０７による判定結果が未照合で、かつ、照合要否判定装置２１０の判定結果が照合要の場合に照合を行い、Ｐ'のデータ符号系列上の先頭位置は既照合とする。そうでない場合、照合を行わず、対応付けを待つ（ステップＳ２０６，Ｓ２０７）。
照合（ステップＳ２０８）は以下の演算式（７）を求め、その値がθより大きいときPがP'のデータ符号系列上の先頭位置に検出されたとする。
【数６】
0003759438.tif 000007
なお、演算式（７）の計算において、ｉがＲになる前に累積値がθを越えた場合は、その時点で、演算式（７）の計算を中止し、ＰがＰ'のデータ符号系列上の先頭位置に検出されたとする。そして、照合を行った場合は照合回数を“１”増やす。この照合回数が“ｎ−ｍ＋１”回を越えた場合、すなわち、照合し得る全ての対応付けで照合を行った場合、本類似音楽検索装置は停止し、そうでない場合は次の対応付けを待つ（ステップＳ２１０）。
【００６３】
以上、本発明の他の実施形態について説明したが、対応付け装置２０６に類似度判定装置２０９と照合要否判定装置２１０の機能を加え、この対応付け装置２０６において、ｍ番目にｐRとの類似度が“０”より大きい文字をもつ位置にだけ、対応付けることも行える。
【００６４】
次に上記した本発明の他の実施形態についてその実験結果について説明する。図４に示す実施形態同様、従来技術によるＤＰマッチングとずらし照合を行う装置をパソコン上に実装して、その検出速度を計測、比較した。従来技術による実装におけるＤＰマッチングについては、この場合、演算式（７）を単純に計算することになる。実験では、約２０分の音響データから、約１５秒の音響の断片１００個を検索し、その検出にかかった時間（検出時間）を計測した。平均の検出時間は、上記実装例では８９ミリ秒、従来手法では３．４秒であり、約３８倍高速な検出が行えた。
【００６５】
なお、上記した本発明実施形態においては、符号系列入力装置１０１（２０１）、符号系列入力装置１０２（２０２）、パラメータｄ制御装置１０３、符号位置選択装置１０４（２０５）、対応付け装置１０５（２０６）、類似度判定装置１０６（２０９）、照合要否判定装置１０７（２１０）、照合装置１０８（２０８）、文字間類似度表入力装置１０９、既照合判定装置１１０（２０７）、部分系列選択装置２０３、部分系列検出装置２０５のそれぞれで実行される手順をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより本発明における類似部分系列検出装置における各機能が実行されるものとする。ここでいうコンピュータシステムとは、ＯＳや周辺機器等のハードウエアを含むものである。
【００６６】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のシステムやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００６７】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００６８】
以上、この発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【００６９】
【発明の効果】
以上説明のように本発明によれば、目的符号系列と、より長いデータ符号系列の符号系列が与えられたとき、データ符号系列中の目的符号系列に類似した部分系列の場所を探し出すのに、照合の際、検索対象位置の符号系列が照合済みか否かを判定した後に照合を行なうことにより、照合回数を減らすことと照合を効率的に行うことができ、結果的に高速な類似部分系列検出処理を行うことができる。
なお、本発明は、目的符号系列と、より長いデータ符号系列の２つの符号系列が与えられたとき、データ符号系列中の目的符号系列に類似した部分系列の場所を探し出すときに使用されるものであり、例えば類似音響信号検出に利用することができる。具体的に、大量の音楽の音響信号からなる音楽データベースにおいて、音楽を時系列の音響信号を順次符号化した符号系列すなわちデータ符号系列として蓄積しており、あるお気に入りの楽曲の１フレーズを同様に符号化し、これを目的符号系列として類似部分系列検出を行うことで、お気に入りの楽曲と類似する音楽、例えば別の編曲、別奏者、ライブ版等の検索が可能になる。また、従来、ＭＩＤＩデータ等を対象とした鼻歌検索などは従来から知られているが、本発明では、自分で歌った歌や鼻歌を符号系列化し目的符号系列とし、上記の音響信号による音楽データベースに対するた歌声や鼻歌による音楽検索も可能になる。本発明は、音楽情報のみならず、映像情報やその他時系列情報にも同様に応用可能である。
【図面の簡単な説明】
【図１】  ＤＰマッチングの概念を説明するために引用した図である。
【図２】  本発明により実現される照合の高速化を概念的に説明するために引用した図である。
【図３】  本発明により実現される照合の高速化を概念的に説明するために引用した図である。
【図４】  本発明における類似部分系列検出装置の一実施形態をブロック図で示したものである。
【図５】  図４に示す本発明一実施形態の動作をフローチャートで示した図である。
【図６】  本発明における類似部分系列検出装置の一実施形態をブロック図で示したものである。
【図７】  図６に示す本発明一実施形態の動作をフローチャートで示した図である。
【符号の説明】
１０１（２０１）…符号系列入力装置、１０２（２０２）…符号系列入力装置、１０３…パラメータｄ制御装置、１０４（２０５）…符号位置選択装置、１０５（２０６）…対応付け装置、１０６（２０９）…類似度判定装置、１０７（２１０）…照合要否判定装置、１０８（２０８）…照合装置、１０９…文字間類似度表入力装置、１１０（２０７）…既照合判定装置、２０３…部分系列選択装置、２０４…部分系列検出装置
【図１】
0003759438.tif 000008
【図２】
0003759438.tif 000009
【図３】
0003759438.tif 000010
【図４】
0003759438.tif 000011
【図５】
0003759438.tif 000012
【図６】
0003759438.tif 000013
【図７】
0003759438.tif 000014