【手続補正書】
【提出日】平成15年11月14日(2003.11.14)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力装置を介して提供される、ある目的符号系列に類似した符号系列を、コンピュータにより、より長い符号系列であるデータ符号系列中において検出する類似部分系列検出方法であって、前記目的符号系列中のある一つの未選択の符号位置を順次選択する符号位置選択過程と、前記符号位置選択過程による選択結果を用いて、前記目的符号系列を前記データ符号系列中に位置付ける対応付け過程と、前記対応付けた位置が既に照合済の位置か否かを判定する既照合判定過程と、前記対応付けた位置において、前記選択された符号位置に対する前記データ符号系列中の符号との類似度を判定する類似度判定過程と、前記類似度判定結果に基づき、その位置での照合の要否を判定する照合要否判定過程と、前記照合要となった位置において類似しているか否かを判定して当該位置を照合済とし、前記データ符号系列の各符号位置において、前記目的符号系列に類似しているか否かを判定し、前記目的符号系列に類似した符号系列を前記データ符号系列中において検出する照合過程とを備えたことを特徴とする類似部分系列検出方法。
【請求項２】
それぞれの符号α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，…について、当該符号を並ベて得られる列である符号系列の各符号を順に書き下した場合、［α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 ]とし、ＰとＰ'の間の類似度を、ｘ＋ｙ＜ｄの時は、[ｐ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，…について、当該符号を並ベて得られる列である符号系列の各符号を順に書き下した場合、［α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,ｐ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]とし、対応づけられたデータ符号系列中の部分系列Ｐ’を[ｐ'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,ｐ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]とし、対応づけられたデータ符号系列中の部分系列Ｐ'を[ｐ'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,ｐ2,…,ｐn]とし、パラメータｄ制御装置１０３、符号位置選択装置１０４、対応付け装置１０５に供給する。一方、符号系列入力装置１０２は、ファイルからデータ符号系列を読み込む。読み込んだデータ符号系列Ｔを[ｔ1,ｔ2，…,ｔn]とし、パラメータｄ制御装置１０３、対応付け装置１０５に供給する。


【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００５０
【補正方法】変更
【補正の内容】
【００５０】
文字間類似度表入力装置１０９は、文字間類似度表をファイルから読み込む。文字間類似度表は、文字間の類似度が書き込まれたファイルであり、この表が類似度判定装置１０６、照合装置装置１０８により参照される。パラメータｄ制御装置１０３は、パラメータｄの値を“２”にセットし（ステップＳ１０１）、ｄ≦ｍ＋ｍ'かを判定し、ここで、条件が成立したらならパラメータｄを符号位置選択装置１０４に入力して待ち状態となる（ステップＳ１０２）。その後は、対応付け装置１０５からのパラメータｄの増加要求があると、パラメータｄを“１”増やし（ステップＳ１０７）、ステップＳ１０２の判定を繰り返す。なお、ステップＳ１０２において、パラメータｄ≦ｍ＋ｍ'が不成立の場合、本類似音楽検索装置は停止する。符号位置選択装置１０４は、パラメータｄを入力とし、ｓmaxu＝ｍ＋ｍ'＋２−dとして計算し（ステップＳ１０３）、ｓmaxu＞θを判定し（ステップＳ１０４）、ここで条件が不成立の場合類似音楽装置を停止させ、条件成立の場合は、ｉ＝１とする（ステップＳ１０５）。そして、ｉ≦ｄ−１、かつ、ｉ≦ｍか否かを判定し（ステップＳ１０６）、条件成立の場合、ｉとｄを対応付け装置１０５に入力して待ち状態になる。条件不成立の場合は、パラメータｄ制御装置１０３にパラメータｉの増加要求を出し、処理を終了する。


【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
待ち状態では、対応付け装置１０５からｉの増加要求を受けとると、ｉを１増やし（ステップＳ１１４）、ｉ≦ｄ−１、かつ、ｉ≦ｍか否かを判定する（ステップＳ１０６）。対応付け装置１０５は、入力されたiにより、ｊ＝ｄ−ｉとし（Ｓ１０８）、目的符号系列をデータ符号系列に対応付ける。本装置では、長さｍ'の注目窓をまだずらせるか否か判定しながらデータ符号系列上で１符号ずつずらしていき（ステップＳ１００）、注目窓が設定できたなら、注目窓内の部分符号系列をＰ'とする（ステップＳ１１０）。ここで、Ｐ’を[ｐ’1,ｐ’2,…,ｐ’m']とする。そして、Ｐ，ｄ，Ｐ’のデータ符号系列中での位置情報と、ｉ，ｊを既照合判定装置１１０と類似度判定装置１０６に供給する。そして、対応付けられる部分がなくなると、符号位置選択装置１０４にｉの増加要求を出す。


【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
次に本発明の他の実施形態について説明する。この実施形態は、特定の音響信号をより長い音響信号から検出する音響検出システムに採用したものである。この実施形態では、検出したい音響信号を符号系列化したものを目的符号系列、同様により長い音響信号を符号系列化したものをデータ符号系列とする。ここでは、文字間の類似度は２つの文字が一致する場合のみ１、一致しない場合は０である。そして、目的符号系列Ｐを[ｐ1,ｐ2,…,ｐm]とし、データ符号系列Ｔを[ｔ1,ｔ2,…,ｔn]としたとき、目的符号系列との類似度が類似閾値θより大きい、長さｍの部分系列の、データ符号系列での位置を出力する。なお、ここで類似度は、注目する部分系列Ｐ’を[ｐ’1,ｐ’2,…,ｐ’m]としたとき、以下の演算式（６）とする。
【数５】
2003050823.tif 000001
これは、従来技術であるＤＰマッチングにおいて、マッチングを行なう二つの系列の長さを等しいとし、そして、ｉh−ｊh≦ｒで表される整合窓についてｒ＝０とした場合と考えられる。


【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００５９
【補正方法】変更
【補正の内容】
【００５９】
部分系列選択装置２０３は、Ｒmin＝θ＋１とし、Ｐの部分系列Ｐpar＝[ｐ1,ｐ2,…,ｐmin]を選択し（ステップＳ２０１）、部分系列検出装置２０４に供給する。部分系列検出装置２０４は、ＰparをＢＭ法等の完全一致の文字列探索によりデータ符号系列のＰparを検出する。ＢＭ法については、「野下浩平、高岡忠雄、町田元（編）、基本的算法、岩波講座、情報科学１０、岩波書店１９８３年発行」に開示されており、完全一致の文字列照合を行う方法である。そして、Ｐparが検出されたデータ符号系列上の位置において、Ｐが検出されたとし、データ符号系列上の該位置は既照合とする（ステップＳ２０２）。そして、制御を符号位置選択装置２０５に移す。


【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
符号位置選択装置２０５は、Ｒ＝ｍとし（ステップＳ２０３）、Ｒ＞ｍminの間（ステップＳ２１１）、Ｒを１減らしながら（ステップＳ２０９）、順次、対応付け装置に２０６にＲを供給する。Ｒ≦ｍminになると、本音響検出システムを停止させる。対応付け装置２０６は、入力されたＲにより、目的符号系列をデータ符号系列に対応付ける。本装置では幅Ｒの注目窓をまだずらせるかを判定しながらデータ符号系列上で１符号ずつずらしていき（ステップＳ２０４）、注目窓が設定できたなら、注目窓内の部分符号系列をＰ'とする（ステップＳ２０５）。なお、Ｐ'を [ｐ'1,ｐ'2,…,ｐ'R]とする。次に、Ｐ，Ｐ'とＲを既照合判定装置２０７と類似度判定装置２０９に供給する。そして、対応付けられる部分がなくなると、符号位置選択装置２０５にＲの減少を要求する。