複数のタプルを対象に編集距離閾値τ正の整数を用いて類似結合処理を実行する結合処理装置において、前記各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に、共通する文字を持たないタプルのペアを編集距離計算対象から除外する結合処理手段、を備えることを特徴とする結合処理装置。複数のタプルを対象に編集距離閾値τ正の整数を用いて類似結合処理を実行する複数の結合処理装置と通信可能に接続されるデータ管理装置において、複数のタプルを格納するデータ格納手段と、前記複数の結合処理装置の中から、前記データ格納手段に格納される各タプルを処理させる結合処理装置を各タプルの分配先として決定する際に、当該各タプルの分配先を、各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に含まれる少なくとも1つの文字を、結合キー文字列の中の当該端部分に含む他のタプルと同じ分配先にそれぞれ決定し、かつ、各タプルの結合キー文字列の中の当該端部分に共通する文字を持たない他のタプルとは同じ分配先にならないようにそれぞれ決定するデータ分配手段と、を備えることを特徴とするデータ管理装置。少なくとも1つのデータ管理装置、及び、この少なくとも1つのデータ管理装置で保持される複数のタプルを対象に編集距離閾値τ正の整数を用いて類似結合処理を実行する複数の結合処理装置を含む文字列類似結合システムにおいて、前記少なくとも1つのデータ管理装置は、前記各タプルの結合キー文字列に関し、先頭文字からiiはτ1以下の正の整数の各々番目の文字から末尾文字までの末尾部分文字列と、残りの先頭部分文字列の文字列長と、タプル特定データとの組み合わせ、又は、末尾文字からi番目の文字から先頭文字までの先頭部分文字列と、残りの末尾部分文字列の文字列長と、タプル特定データとの組み合わせを含むキー情報タプルをτ1個それぞれ生成するキー情報生成手段と、前記キー情報生成手段により生成された各キー情報タプルに含まれる末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字に基づいて、当該各キー情報タプルの分配先を決定し、当該各キー情報タプルを、分配先として決定された各結合処理装置に各タプルのデータとしてそれぞれ分配するデータ分配手段と、を備え、前記複数の結合処理装置はそれぞれ、前記少なくとも1つのデータ管理装置から分配された複数のキー情報タプルを受信する受信手段と、前記受信手段により受信された複数のキー情報タプルのうち、前記末尾部分文字列の先頭文字又は前記先頭部分文字列の末尾文字が共通するキー情報タプル集合毎に、前記類似結合処理を実行する結合処理手段と、を備えることを特徴とする文字列類似結合システム。前記複数の結合処理装置はそれぞれ、前記受信手段により受信された複数のキー情報タプルの各ペアに関し、末尾部分文字列間又は先頭部分文字列間の編集距離を部分文字列編集距離としてそれぞれ算出し、算出された部分文字列編集距離が前記編集距離閾値τの条件を満たすキー情報タプルの各ペアに関し、当該部分文字列編集距離と、大きい方の先頭部分文字列の文字列長又は大きい方の末尾部分文字列の文字列長とを加算することにより、編集距離推定値をそれぞれ算出する推定値算出手段、を更に備え、前記結合処理手段は、前記推定値算出手段により算出された各編集距離推定値と前記編集距離閾値τとの比較結果に基づいて、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを特徴とする請求項3に記載の文字列類似結合システム。前記複数の結合処理装置はそれぞれ、前記受信手段により受信された複数のキー情報タプルに基づいて、前記先頭部分文字列又は前記末尾部分文字列の文字列長を重み値として管理するトライ木であって、前記末尾部分文字列又は前記先頭部分文字列がルートノードからエッジノードまでの枝にマッピングされたトライ木を構築するトライ木構築手段、を更に備え、前記結合処理手段は、前記トライ木構築手段により構築されたトライ木に含まれる各対象ノードに関し、対象ノードにより特定される文字列と他ノードで特定される文字列との間の編集距離と、対象ノード及び他ノードの重み値のうち大きい方の重み値とを加算することにより、他ノードのための編集距離推定値をそれぞれ算出し、当該編集距離推定値が前記編集距離閾値τの条件を満たす他ノードの情報及び当該編集距離推定値を含むリストを各対象ノードに関しそれぞれ設定し、エッジノードに設定されたリストに基づいて、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを特徴とする請求項3に記載の文字列類似結合システム。前記結合処理手段は、親ノードに設定されたリストに含まれる他ノードの情報に基づいて、各対象ノードの編集距離推定値の計算対象となる他ノードを選択する、ことを特徴とする請求項5に記載の文字列類似結合システム。前記トライ木構築手段は、同一のタプル特定データを持つ複数のキー情報タプルの前記末尾部分文字列又は前記先頭部分文字列を前記トライ木の1つの枝及び当該1つの枝の少なくとも1部分にマッピングし、前記トライ木のルートノードに、当該1つの枝の少なくとも1部分を特定するためのノードポインタを前記重み値と共に設定する、ことを特徴とする請求項5又は6に記載の文字列類似結合システム。前記少なくとも1つのデータ管理装置及び前記複数の結合処理装置と通信可能なシステム制御装置を更に含み、前記各結合処理装置の前記結合処理手段は、前記特定された各ペアに関し、タプル特定データのペア及び編集距離推定値を含む結果タプルをそれぞれ生成し、生成された各結果タプルをそれぞれ前記システム制御装置に送信し、前記システム制御装置は、前記複数の結合処理装置から送られた複数の結果タプルの中から同じタプル特定データのペアを含む重複結果タプルを検出し、検出された重複結果タプルの中から最小の編集距離推定値を持つ結果タプル以外の結果タプルを削除することにより、編集距離が前記編集距離閾値τの条件を満たすタプルのペアを決定する結果生成手段、を備えることを特徴とする請求項4から7のいずれか1項に記載の文字列類似結合システム。複数のタプルを対象に編集距離閾値τ正の整数を用いて実行される文字列類似結合方法において、少なくとも1つのコンピュータが、前記各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に、共通する文字を持たないタプルのペアを編集距離計算対象から除外する、ことを含む文字列類似結合方法。複数のタプルを対象に編集距離閾値τ正の整数を用いて文字列類似結合を少なくとも1つのコンピュータに実行させるプログラムにおいて、前記少なくとも1つのコンピュータに、前記各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に、共通する文字を持たないタプルのペアを編集距離計算対象から除外する結合処理手段、を実現させることを特徴とするプログラム。以下、本発明の実施の形態について説明する。なお、以下に挙げる各実施形態はそれぞれ例示であり、本発明は以下の各実施形態の構成に限定されない。[第1実施形態]第1実施形態における結合処理装置は、複数のタプルを対象に編集距離閾値τ正の整数、以降、単に閾値τとも表記するを用いて類似結合処理を実行する。この結合処理装置は、各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に、共通する文字を持たないタプルのペアを編集距離計算対象から除外する結合処理部を備える。従って、第1実施形態によれば、従来、類似結合処理の対象となるデータの全てのタプルペアを対象に編集距離の計算が行われていたところ、当該端部分に共通する文字を持たないタプルのペアを除外するため、従来に比べ、処理コストを削減し、システム全体での類似結合処理の時間を削減することができる。また、第1実施形態によれば、検出されるべきタプルのペアの取りこぼしは生じないため、適切な類似結合処理結果を出力することができる。以下、第1実施形態においてこのような作用効果を奏する理由について説明する。上述したように、類似結合処理では、処理対象となるデータにおける全てのタプルペアに関して、結合キーの編集距離の算出処理、編集距離と編集距離閾値τとの比較処理等が必要になる。例えば、入力データSと入力データRとの間の文字列類似結合は、全タプルペアの数は、入力データSのタプル数と入力データRのタプル数との乗算値となるため、膨大な処理時間を要する。そこで、第1実施形態は、編集距離を実際に計算する前に、編集距離が編集距離閾値τより大きくなるタプルペアを特定し、この特定されたタプルペアを類似結合処理の対象から除外する。これにより、編集距離計算等の対象とするタプルペアの数を削減することができるため、全体的な類似結合処理時間を軽減することができる。タプルs及びタプルrの各結合キー文字列の上記端部分に、共通する文字が1つも存在しない場合、当該端部分の文字数はτ1であるため、タプルs及びタプルrの編集距離は明らかに閾値τよりも大きくなる。例えば、タプルsの結合キー文字列がabcdefであり、タプルrの結合キー文字列がghidefであり、閾値τが2である場合、タプルsの端部分の文字列はabcであり、タプルrの端部分の文字列はghiであり、結果、両者間には共通する文字が存在しない。この時点で、タプルs及びタプルrの編集距離が閾値τを超えることは明らかであるため、タプルs及びタプルrのペアに関し編集距離を計算する必要がないことは容易に把握できる。なお、実際の編集距離も3である。従って、第1実施形態のように、当該端部分に共通する文字を持たないタプルのペアを編集距離計算対象から除外したとしても、検出されるべきタプルのペアの取りこぼしは生じず、適切な類似結合処理結果を出力することができる。一方、両者の当該端部分に共通する文字が1つでも存在すれば、編集距離が閾値τ以下となる可能性がある。そこで、第1実施形態における結合処理装置は、当該端部分に少なくとも1つの共通する文字を持つタプルのペアを編集距離計算の対象にすればよい。[第2実施形態]第2実施形態におけるデータ管理装置は、複数のタプルを対象に上記閾値τを用いて類似結合処理を実行する複数の結合処理装置と通信可能に接続される。このデータ管理装置は、複数のタプルを格納するデータ格納部と、前記データ格納部に格納される各タプルを処理させる結合処理装置を各タプルの分配先として決定する際に、各タプルの分配先を、各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に含まれる少なくとも1つの文字を、結合キー文字列の中の当該端部分に含む他のタプルと同じ分配先にそれぞれ決定し、かつ、各タプルの結合キー文字列の中の当該端部分に共通する文字を持たない他のタプルと同じ分配先とならないようにそれぞれ決定するデータ分配部と、を備える。第2実施形態におけるデータ管理装置では、データ格納部に格納され類似結合処理の対象となる各タプルが複数の結合処理装置の少なくとも1つにそれぞれ分配され、複数の結合処理装置で類似結合処理が並列に実行されることにより、文字列類似結合処理が高速化される。ここで、類似結合処理の対象となる複数のタプルは、1つのデータ管理装置のデータ格納部に格納される1つのタプル集合から抽出されてもよいし、1つのデータ管理装置のデータ格納部に格納される複数のタプル集合から抽出されてもよいし、複数のデータ管理装置のデータ格納部に格納される複数のタプル集合から抽出されてもよい。複数の結合処理装置で実行される類似結合処理には、上述のような周知の手法が利用されてもよい。ここで、各結合処理装置とは、類似結合処理を実行し得る単位を示しており、1つのコンピュータであってもよいし、1つのCPUCentralProcessingUnitであってもよい。よって、CPUを搭載する基板を複数備えるコンピュータの場合には、複数の結合処理装置は1台のコンピュータとして実現されてもよい。上記データ管理装置では、データ格納部に格納される各タプルの分配先は、各タプルの結合キー文字列の中の、先頭文字又は末尾文字からτ1番目までの端部分に含まれる少なくとも1つの文字を、結合キー文字列の中の当該端部分に含む他のタプルと同じ分配先にそれぞれ決定される。ここで、他のタプルとは、データ管理装置自身のデータ格納部に格納されるタプルであってもよいし、他のデータ管理装置により保持されるタプルであってもよい。結果として、1つの結合処理装置では、結合キー文字列の中の先頭文字からτ1番目までの端部分に共通する少なくとも1つの文字を持つタプルのペア、又は、結合キー文字列の中の末尾文字からτ1番目までの端部分に共通する少なくとも1つの文字を持つタプルのペアを対象に類似結合処理が行われる。一方、結合キー文字列の中の当該端部分に共通する文字を1つも持たないタプルの組み合わせは、同じ結合処理装置には分配されないため、編集距離計算の対象から除外されることになる。つまり、第2実施形態では、タプルの組み合わせが同じ結合処理装置に分配されるか否かにより、そのタプルの組み合わせが編集距離計算の対象とされるか否かが決まる。結果、第2実施形態によれば、第1実施形態と同様の効果を得ることができる。[第3実施形態]システム構成図1は、第3実施形態におけるシステムの構成例を概念的に示す図である。第3実施形態におけるシステム1は、システム制御装置10、データ管理装置201及び202、結合処理装置301、302、303及び304等を有する。以降、データ管理装置及び結合処理装置については、区別する必要のある場合を除き、データ管理装置20及び結合処理装置30と表記する。システム制御装置10は、類似結合処理の要求を受け、この要求に応じた類似結合処理を実行するために、データ管理装置20及び結合処理装置30を制御する。システム制御装置10は、各結合処理装置30からそれぞれ送られる結合結果を受け、最終的な文字列類似結合処理の結果を出力する。データ管理装置20は、結合処理対象となる少なくとも1つのデータタプル集合を管理する。第3実施形態では、データ管理装置201及び202はそれぞれデータを管理する。データ管理装置20は、第1実施形態と同様の考え方により自身で管理するデータを形成する各タプルの分配先をそれぞれ決め、決められた各分配先となる結合処理装置30に各タプルに関するデータを分配する。なお、具体的には、第3実施形態では、各タプルに関するデータとして、後述するSIPタプルが分配される。結合処理装置30は、データ管理装置20から分配されたデータに基づいて、編集距離が編集距離閾値τの条件を満たすタプルペアを特定し、その特定されたタプルペアに関するデータを結合結果としてシステム制御装置10に送る。システム制御装置10、データ管理装置20及び結合処理装置30は、ネットワーク7を介してそれぞれ通信可能に接続される。ネットワーク7は、インターネット等のような公衆網、WANWideAreaNetwork、LANLocalAreaNetwork、無線通信ネットワーク等である。なお、本実施形態は、各装置間が通信可能に接続されていれば、各装置間の通信プロトコル、ネットワーク形態等を限定しない。システム制御装置10、データ管理装置20及び結合処理装置30は、図1に示されるように、ハードウェア構成として、CPU2、RAMRandomAccessMemory2、ROMReadOnlyMemory、図示せず、ハードディスクHDD等のようなメモリ3、入出力インタフェースI/F4等をそれぞれ有する。これら各ハードウェア要素は例えばバス5により接続される。入出力I/F4は、ネットワーク7を介して他の装置と通信を実現し得るネットワークインタフェースを含む。本実施形態は、各装置のハードウェア構成を限定しない。また、本実施形態は、データ管理装置20及び結合処理装置30の台数を限定しない。結合処理対象のデータが1つのデータ管理装置20に保持される場合には、1つのデータ管理装置20が存在すればよい。結合処理装置30は、2台以上、かつ、入力データに出現する文字の種類数と等しい台数以下分、存在すればよい。この台数の根拠については後述する。装置構成以下、第3実施形態におけるシステム1を構成する各装置の詳細構成についてそれぞれ説明する。システム制御装置図2は、システム制御装置10の構成例を概念的に示すブロック図である。システム制御装置10は、図2に示されるように、要求制御部11、結果生成部12、結合結果格納部15等を有する。要求制御部11及び結果生成部12は、例えば、CPU2によりメモリ3に格納されるプログラムが実行されることで実現される。また、結合結果格納部15は、例えば、メモリ3上に実現される。要求制御部11は、文字列類似結合の処理要求を取得し、この処理要求の内容に基づき実行命令を生成し、入出力I/F4の通信インタフェースを介して当該実行命令をデータ管理装置20及び結合処理装置30へ送信する。ここで、当該処理要求は、結合処理対象となるデータを特定するためのデータ識別子と、その対象データの結合キー属性の情報と、閾値τとを含む。当該処理要求は、通信を介して外部の装置から取得されてもよいし、システム制御装置10のユーザインタフェース図示せずを介して入力されてもよい。データ管理装置20へ送られる上記実行命令は、上記処理要求に含まれていた各データ及び閾値τと共に、結合処理装置30のネットワークアドレス情報例えば、IPInternetProtocolアドレス及びポートを含む通信メッセージである。一方、結合処理装置30へ送られる上記実行命令は、データ識別子、閾値τ、結合処理装置30のネットワークアドレス情報例えば、IPアドレス、システム制御装置10のネットワークアドレス情報例えば、IPアドレス等を含む通信メッセージである。本実施形態は、この通信メッセージのフォーマットを限定しない。結合結果格納部15は、各結合処理装置30から送られる文字列類似結合の局所結合結果を格納する。結合処理装置30において編集距離が閾値τの条件を満たすと推定されたタプルのペアが存在する場合には、その局所結合結果には、局所結果タプルがそのペアの数分含まれる。局所結果タプルには、タプルのペアを特定するためのタプルポインタのペア及び編集距離推定値が含まれる。編集距離推定値は、結合処理装置30により算出される値であり、以降、局所編集距離とも表記される。この局所編集距離の詳細については後述する。タプルポインタは、システム1内で扱われる全タプルの中から1つのタプルを特定するための識別情報であり、タプル特定データと呼ぶこともできる。本実施形態では、タプルポインタは、或るタプル集合データの中で或るタプルを特定するためのタプル識別子と、そのタプル集合データを特定するためのデータ識別子とから形成される。なお、タプル識別子がシステム1内で扱われる全タプルに関しユニークに付される場合には、タプルポインタは、タプル識別子のみで形成されてもよい。結果生成部12は、入出力I/F4の通信インタフェースを介して各結合処理装置30から局所結合結果をそれぞれ取得する。結果生成部12は、取得された局所結合結果を結合結果格納部15に格納する際に、同じタプルポインタのペアを含む局所結果タプルを検出し、検出された局所結果タプルの中の最小の局所編集距離を持つ局所結果タプルのみを編集距離が前記編集距離閾値τの条件を満たすタプルのペアの情報として結合結果格納部15に格納する。データ管理装置図3は、データ管理装置20の構成例を概念的に示すブロック図である。データ管理装置20は、図3に示されるように、SIPタプル生成部21、データ分配部22、データ格納部25等を有する。SIPタプル生成部21及びデータ分配部22は、例えば、CPUによりメモリに格納されるプログラムが実行されることで実現される。また、データ格納部25は、例えば、メモリ上に実現される。データ格納部25は、データタプル集合とそのデータを特定するためのデータ識別子とを格納する。図20の例では、データ格納部25は、入力タプル集合S及び入力タプル集合Rの少なくとも1つと、その識別子S及びRの少なくとも1つを格納する。このように、データ格納部25は、データ識別子の異なる複数のデータを格納してもよい。SIPタプル生成部21は、入出力I/F4の通信インタフェースを介して、システム制御装置10から実行命令を受信し、当該実行命令に含まれるデータ識別子に対応するデータをデータ格納部25から抽出する。図20の例において、実行命令にデータ識別子Rが含まれている場合には、SIPタプル生成部21は、入力タプル集合Rの全タプルを抽出する。SIPタプル生成部21は、抽出されたデータに含まれる各タプルに関し、τ1個のSIPタプルをそれぞれ生成する。SIPタプルは、タプルの結合キー文字列に関し、先頭文字からiiはτ1以下の正の整数の各々番目の文字から末尾文字までの末尾部分文字列と、残りの先頭部分文字列の文字列長と、タプルポインタとの組み合わせ、又は、末尾文字から上記i番目の文字から先頭文字までの先頭部分文字列と、残りの末尾部分文字列の文字列長と、タプルポインタとの組み合わせである。各タプルの結合キーは、システム制御装置10から送られる実行命令に含まれる結合キー属性の情報により特定される。ここで、タプルsの結合キー文字列における、先頭文字から上記i番目の文字から末尾文字までの末尾部分文字列をst_iと表記し、残りの先頭部分文字列の文字列長を|sh_i|と表記し、タプルsのタプルポインタをs_ptrと表記すると、タプルsのSIPタプルは、<st_i、|sh_i|、s_ptr>と表記することができる。また、|sh_i|は、i-1と等しい。ここで、データ格納部25が図20に示される入力タプル集合Sを格納し、閾値τが2であり、データ識別子がSであり、結合キー属性が品番である場合に、タプル識別子が101のタプルsのSIPタプルは、以下のように生成される。この場合、タプルsの結合キー文字列はXWY-RS200である。SIPタプルi=1:<XWY-RS200、0、S:101>SIPタプルi=2:<WY-RS200、1、S:101>SIPタプルi=3:<Y-RS200、2、S:101>SIPタプルの他の態様、即ち、末尾文字から上記i番目の文字から先頭文字までの先頭部分文字列と、残りの末尾部分文字列の文字列長と、タプルポインタとの組み合わせである場合には、上記例のSIPタプルは、以下のように生成される。SIPタプルi=1:<XWY-RS200、0、S:101>SIPタプルi=2:<XWY-RS20、1、S:101>SIPタプルi=3:<XWY-RS2、2、S:101>なお、SIPタプルの態様は上記2つのうちのいずれの方法が利用されてもよい。このようにSIPタプルは、結合キーに関する情報を含むタプルであるため、キー情報タプルと呼ぶこともできる。これにより、SIPタプル生成部21は、キー情報生成部と呼ぶこともできる。データ分配部22は、SIPタプル生成部21により生成されたSIPタプル集合を受け、各SIPタプルの分配先を決定し、当該各SIPタプルを、分配先として決定された各結合処理装置30に、各タプルのデータとして、それぞれ分配送信する。データ分配部22は、各SIPタプルに含まれる末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字に基づいて、各SIPタプルの分配先を決定する。結果、当該先頭文字又は当該末尾文字が同じSIPタプルは、同じ結合処理装置30に分配される。例えば、データ分配部22は、1つの文字を入力して、結合処理装置301、302、303及び304のいずれか1つを特定し得る1つの数値を出力する関数ハッシュ関数等を用いて、各SIPタプルの分配先を決定する。データ分配部22は、決定された分配先の結合処理装置30のネットワークアドレスをシステム制御装置10から送られる実行命令に含まれるネットワークアドレス情報から特定し、対応するSIPタプルをその結合処理装置30に送信する。なお、或る文字から分配先を決定するための手法は、ハッシュ関数等のような関数を利用する形態に限定されない。ここで、末尾部分文字列の先頭文字は、結合キー文字列の中の先頭文字からτ1番目までの端部分に含まれるいずれか1つの文字となり、先頭部分文字列の末尾文字は、結合キー文字列の中の末尾文字からτ1番目までの端部分に含まれるいずれか1つの文字となる。よって、結合キー文字列における先頭文字又は末尾文字からτ1番目までの端部分に含まれる少なくとも1つの文字が共通するタプルs及びタプルrについては、タプルsに関するτ1個のSIPタプルと、タプルrに関するτ1個のSIPタプルとの全組み合わせペアのうち、1つ以上のペアが、同じ結合処理装置30に分配され、類似結合処理の対象とされる。なお、本実施形態では、当該端部分に共通する文字が1つも存在しないタプルs及びタプルrについては、同じ結合処理装置30に分配されてもよいし、異なる結合処理装置30に分配されてもよい。いずれの場合であっても、当該端部分に共通する文字が1つも存在しないタプルs及びタプルrについては、結合処理装置30において類似結合処理対象から除外される。結合処理装置図4は、結合処理装置30の構成例を概念的に示すブロック図である。結合処理装置30は、図4に示されるように、SIPタプル受信部31、結合処理部32、推定値算出部33、SIPタプル格納部35等を有する。SIPタプル受信部31、結合処理部32及び推定値算出部33は、例えば、CPUによりメモリに格納されるプログラムが実行されることで実現される。また、SIPタプル格納部35は、例えば、メモリ上に実現される。SIPタプル受信部31は、データ管理装置20から送られるSIPタプルを受信し、SIPタプル格納部35に格納する。SIPタプル格納部35は、SIPタプル受信部31により受信されたSIPタプルの集合を格納する。SIPタプル格納部35は、各SIPタプルに含まれる末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字が共通するSIPタプルを一つの集合として格納する。結合処理部32は、システム制御装置10から送られる実行命令を受信し、この実行命令に含まれる各種データを保持する。上述のように、この各種データには、データ識別子、閾値τ、データ管理装置20のネットワークアドレス情報例えば、IPアドレス、システム制御装置10のネットワークアドレス情報例えば、IPアドレス等が含まれる。結合処理部32は、上述のように保持されるデータを用いて、SIPタプル格納部35に格納されるSIPタプルを対象に類似結合処理を実行する。具体的には、結合処理部32は、末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字が共通する任意のSIPタプルの集合をSIPタプル格納部35から抽出し、抽出された末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字が共通する複数のSIPタプルの中の2つの全組み合わせ全ペアに関し、推定値算出部33に所定の処理を実行させる。ここで、類似結合処理が異なるタプル集合データ間の結合を対象とする場合には、結合処理部32は、抽出された末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字が共通する複数のSIPタプルの中のデータ識別子が異なる2つの全組み合わせ全ペアに関し、推定値算出部33に所定の処理を実行させる。当該データ識別子は、SIPタプルに含まれるタプルポインタから抽出される。これにより、結合キー文字列における先頭文字又は末尾文字からτ1番目までの端部分に共通する文字が存在しないタプルs及びタプルrについては、同じ結合処理装置30に分配されたとしても、類似結合処理対象から除外される。結合処理部32は、推定値算出部33から処理結果を取得し、取得された処理結果に基づいて、編集距離が閾値τの条件を満たすと推定されるSIPタプルのペアを特定する。推定値算出部33の処理結果としては、SIPタプルの各ペアに関する局所編集距離と、その編集距離が閾値τの条件を満たすか否かを示す情報が取得される。結合処理部32は、特定された各ペアに関し、タプルポインタのペア及び局所編集距離を含む局所結果タプルをそれぞれ生成し、生成された局所結果タプルを含む局所結合結果をそれぞれシステム制御装置10に送信する。推定値算出部33は、結合処理部32からSIPタプルのペア2つのSIPタプルを受けると、各SIPタプルに含まれる各末尾部分文字列又は各接頭部分文字列間の編集距離を算出する。算出された編集距離は、部分文字列編集距離と表記される。推定値算出部33は、算出された部分文字列編集距離が閾値τの条件を満たさない場合には、そのSIPタプルのペアの編集距離が閾値τの条件を満たさないことを示す処理結果を結合処理部32に返す。一方、推定値算出部33は、算出された部分文字列編集距離が閾値τの条件を満たす場合には、そのペアに関し、更に、当該部分文字列編集距離と、大きい方の先頭部分文字列の文字列長又は大きい方の末尾部分文字列の文字列長とを加算することにより、局所編集距離を算出する。推定値算出部33は、算出された局所編集距離と閾値τとを比較し、この比較結果を処理結果として結合処理部32に返す。具体的には、推定値算出部33は、局所編集距離が閾値τの条件を満たす場合には、局所編集距離と、そのSIPタプルのペアの編集距離が閾値τの条件を満たすことを示す情報とを処理結果として返す。一方、推定値算出部33は、局所編集距離が閾値τの条件を満たさない場合には、そのSIPタプルのペアの編集距離が閾値τの条件を満たさないことを示す処理結果を返す。ここで、上述のように部分文字列編集距離を用いて算出される局所編集距離と、結合キー文字列全体を用いて算出される通常の編集距離以降、真の編集距離と表記するとの関係について説明する。タプルxの結合キー文字列における、先頭文字からi-1番目の文字までの先頭部分文字列をxh_i、及びタプルyの先頭文字からj-1番目の文字までの先頭部分文字列をyh_jとそれぞれ表記し、残りの末尾部分文字列をxt_i及びyt_jと表記する。タプルxとタプルyの編集距離EDx、y、先頭部分文字列間の編集距離部分文字列編集距離EDxh_i、yh_j、及び、末尾部分文字列間の編集距離部分文字列編集距離EDxt_i、yt_jの間には、次のような関係が成立する。EDx、y≦EDxh_i、yh_jEDxt_i、yt_j式1また、EDx、yと結合キーの文字列長|x|及び|y|との間には、次の関係が成立する。なお、maxは、大きい方の値を返す関数である。EDx、y≦max|x|、|y|式2上記式1及び式2から、以下の式3及び式4が導かれる。EDx、y≦max|xh_i|、|yh_j|EDxt_i、yt_j式3EDx、y≦max|xt_i|、|yt_j|EDxh_i、yh_j式4上記式3及び式4のそれぞれの右辺は、推定値算出部33において、部分文字列編集距離を用いて算出される局所編集距離に対応する。タプルx及びタプルyに関するSIPタプルは、{2×τ1}個生成されるため、タプルx及びタプルyに関する局所編集距離は、複数生成される可能性がある。このように複数生成される局所編集距離の全てが、必ずしも真の編集距離と等しくなるわけではない。上記式3及び式4で示すように、局所編集距離は、真の編集距離の上限値を示すに過ぎないからである。そこで、局所編集距離は、編集距離推定値と呼ぶことができる。上記式3及び式4から、次の法則が成立する。max|xh_i|、|yh_j|EDxt_i、yt_j≦τただし、iは1以上τ1以下が成り立つ場合、EDx、y≦τである。式5max|xt_i|、|yt_j|EDxh_i、yh_j≦τただし、jは1以上τ1以下が成り立つ場合、EDx、y≦τである。式6上記法則式5および式6から、タプルx及びタプルyに関する局所編集距離が閾値τ以下であるとき、必ず真の編集距離もτ以下となることが分かる。これに加え、編集距離の一般的な性質から、真の編集距離が閾値τ以下であるならば、タプルx及びタプルyに関する複数の局所編集距離のうち最も小さい局所編集距離が、必ず真の編集距離と等しくなることが導ける。このような内容は、以下の定理として示すことができる。即ち、与えられた文字列x及びy間の編集距離EDx、yが編集距離閾値τ以下であるならば、次の条件を満たす正の整数のペア<i、j>が少なくとも1つ必ず存在する。1≦i≦τ1AND1≦j≦τ1ANDx[i]=y[j]AND{max|xh_i、yh_j|EDxt_i、yt_j=EDx、y}、又は、0≦|xs|-i1≦τ1AND0≦|ys|-j1≦τ1ANDx[i-1]=y[j-1]AND{max|xt_i、yt_j|EDxh_i、yh_j=EDx、y}ここで、xt_iは、文字列xの先頭文字からi番目の文字から末尾文字までの末尾部分文字列を示し、|xh_i|は、残りの先頭部分文字列の文字列長を示し、yt_jは、文字列yの先頭文字からj番目の文字から末尾文字までの末尾部分文字列を示し、|yh_j|は、残りの先頭部分文字列の文字列長を示す。また、x[i]は、文字列xの先頭文字からi番目の文字を示し、y[j]は、文字列yの先頭文字からj番目の文字を示し、|xs|は、文字列xの文字列長を示し、|ys|は、文字列yの文字列長を示す。上記の定理から、真の編集距離が閾値τ以下であるとき、SIPタプルから生成されるタプルx及びタプルyに関する複数の局所編集距離のうち最も小さい局所編集距離が、必ず真の編集距離と等しくなることが保証される。タプルx及びタプルyに関する局所編集距離は複数生成される可能性があるため、閾値τ以下となる局所編集距離も複数存在する可能性があるが、上述のように、システム制御装置10の結果生成部12において、局所編集距離を用いた局所結果タプルのフィルタリングが行われることで、真の編集距離を局所編集距離から容易に知ることが出来る。よって、本実施形態のように、真の編集距離の代わりに局所編集距離を用いて類似結合結果を得たとしても、正確な類似結合結果を得ることができる。動作例次に、第3実施形態におけるシステム1の動作例について説明する。図5は、第3実施形態におけるシステム1の全体的な動作の概要を示す図である。まず、システム制御装置10において、要求制御部11が文字列類似結合の処理要求を取得するS501。この処理要求には、結合処理対象となるデータを特定するためのデータ識別子例えば、S及びRと、その対象データの結合キー属性の情報例えば、品番と、編集距離閾値τが含まれる。要求制御部11は、取得された処理要求の内容に基づいて実行命令を生成し、生成された各実行命令を全てのデータ管理装置20及び全ての結合処理装置30に送るS502。当該実行命令を受信した各データ管理装置20は次のように動作する。SIPタプル生成部21が、当該実行命令に含まれるデータ識別子に対応するデータをデータ格納部25から抽出し、抽出されたデータに含まれる各タプルに関し、τ1個のSIPタプルをそれぞれ生成するS503。続いて、データ分配部22は、SIPタプル生成部21により生成されたSIPタプル集合を受け、各SIPタプルの分配先となる結合処理装置30を特定し、特定された各結合処理装置30に各SIPタプルをそれぞれ分配するS504。各SIPタプルを受信した各結合処理装置30は次のように動作する。SIPタプル受信部31が、データ管理装置20から送られるSIPタプルを受信し、受信されたSIPタプルを逐次、SIPタプル格納部35に格納する。対象となる全てのデータ管理装置20において分配が完了すると、各結合処理装置30は、結合処理対象となる全てのSIPタプルを完全に取得している。結合処理部32は、SIPタプル格納部35に格納されるSIPタプルを対象に類似結合処理を実行するS505。この類似結合処理では、各SIPタプルのペアに関し、部分文字列編集距離が算出され、この部分文字列編集距離に基づいて局所編集距離がそれぞれ算出される。結果、編集距離が閾値τの条件を満たすと推定されるSIPタプルのペアが特定される。結合処理部32は、特定された各ペアに関し、タプルポインタのペア及び局所編集距離を含む局所結果タプルをそれぞれ生成し、生成された局所結果タプルを含む局所結合結果をそれぞれシステム制御装置10に送信するS506。各結合処理装置30から局所結合結果を受信したシステム制御装置10では、結果生成部12が、同じタプルポインタのペアを含む局所結果タプルのうち最小の局所編集距離を持つもの以外を排除した後、当該局所結果タプルを結合結果格納部15に格納するS507。結果、システム制御装置10の結合結果格納部15に格納される局所結果タプルにより、編集距離閾値τの条件を満たすタプルのペアの情報を得ることができる。以下、図5に示されたステップのうち、S503、S505及びS507の動作について詳細に説明する。以下の説明では、図20の入力タプル集合データSを保持するデータ管理装置201が、結合処理対象としてデータ識別子S及びRが指定され、結合キー属性として品番が指定され、閾値τとして2が指定された実行命令をシステム制御装置10から受信する場合のデータ管理装置201の動作例について説明する。図6は、第3実施形態におけるデータ管理装置20の動作例を示すフローチャートである。図6には、上記S503における動作の詳細が示される。まず、SIPタプル生成部21は、システム制御装置10からの実行命令に含まれるデータ識別子Sに対応するデータSをデータ格納部25から抽出するS601。図20によれば、データ管理装置201のSIPタプル生成部21により、タプル識別子TIDが101から104である4つのタプルを含むデータSが抽出される。SIPタプル生成部21は、データSに未処理のタプルsが存在するか否かを判定するS602。未処理のタプルsが存在する場合S602;YES、SIPタプル生成部21は、タプルsに関し、タプルポインタs_ptr及び結合キー文字列長:|s|を取得するS603。図20の例において、タプル識別子TIDが101であるタプルが未処理である場合、取得されるタプルポインタs_ptrは、S:101であり、取得される結合キーは、XWY-RS200である。SIPタプル生成部21は、変数iに初期値1を設定するS604。SIPタプル生成部21は、結合キーの先頭文字からi番目の文字から末尾文字までの末尾部分文字列st_i、残りの先頭部分文字列の文字列長|sh_i|を取得するS605。ここで、末尾部分文字列st_iの文字列長は、|s|-i1であり、|sh_i|は、i-1で示される。SIPタプル生成部21は、これら取得されたデータを用いて、変数iに対するSIPタプル<st_i、|sh_i|、s_ptr>を生成するS605。続いて、SIPタプル生成部21は、生成されたSIPタプルを、文字s[i]に関するSIPタプル集合sip[s[i]]へ追加するS606。文字s[i]は、結合キーs[]例えば、XWY-RS200の先頭文字からi番目の文字、即ち、末尾部分文字列st_iの先頭文字に相当する。よって、SIPタプル集合sip[s[i]]は、末尾部分文字列st_iの先頭文字が共通するSIPタプルの集合となる。次に、SIPタプル生成部21は、sip[s[i]]に十分なSIPタプル例えば10個のSIPタプルが蓄積されているか否かを判定するS607。十分なSIPタプルが蓄積されていない場合S607;NO、SIPタプル生成部21は、変数iに1加算された値iがτ1以下であるか否かを判定するS610。iがτ1以下である場合S610;YES、SIPタプル生成部21は、1加算された変数iに関し、上述した処理S605及びS606を実行する。以降、SIPタプル生成部21は、iがτ1を超えるまで、上述した処理S605及びS606の実行を繰り返す。図7は、SIPタプルの生成例を概念的に示す図である。図7は、図20の例におけるデータSに含まれるタプル101に関し、上述のような処理により生成されたSIPタプルを示す。タプル101は、タプル識別子TIDが101であるタプルを示す。図7によれば、上記変数iが1の場合に生成されるSIPタプルが1行目に示され、上記変数iが2の場合に生成されるSIPタプルが2行目に示され、上記変数iが3の場合に生成されるSIPタプルが3行目に示される。そして、各SIPタプルは、SIPタプル集合sip[X]、sip[W]又はsip[Y]へそれぞれ追加される。SIPタプル生成部21は、十分なSIPタプルが蓄積されている場合S607;YES、その旨をデータ分配部22へ通知する。これにより、データ分配部22は、その通知の対象となるSIPタプル集合sip[s[i]]の分配先を決定するS608。例えば、データ分配部22は、文字s[i]を所定のハッシュ関数に与えることで得られるハッシュ値に対応する結合処理装置30を分配先に決定する。図8は、分配先の決定のために利用されるハッシュ関数の入出力の例を示す図である。図8の例では、出力される各ハッシュ値00、01、10、11に対応する結合処理装置301、302、303及び304がそれぞれ予め決められる。この例によれば、SIPタプル集合sip[X]については、ハッシュ値00に対応する結合処理装置301が分配先に決定され、SIPタプル集合sip[Y]については、ハッシュ値01に対応する結合処理装置302が分配先に決定され、SIPタプル集合sip[Z]については、ハッシュ値10に対応する結合処理装置303が分配先に決定され、SIPタプル集合sip[W]については、ハッシュ値11に対応する結合処理装置304が分配先に決定される。なお、文字に基づき或る1つの分配先を決める方法は、他の周知の方法が利用されてもよい。データ分配部22は、上述のように、末尾部分文字列st_iの先頭文字s[i]により決定された分配先となる結合処理装置30に、SIPタプル集合sip[s[i]]を送信するS608。正常に送信された場合には、データ分配部22は、SIPタプル集合sip[s[i]]を初期化空にするS609。SIPタプル生成部21は、iがτ1を超えた場合S610;NO、データSに未処理のタプルsが存在するか否かを再度判定するS602。未処理のタプルsが存在する場合にはS602;YES、その未処理のタプルsに関し、上述と同様に処理S603以降が実行される。図20の例によれば、入力タプル集合Sのタプル101、タプル102、タプル103及びタプル104に関しそれぞれ、SIPタプルが生成される。未処理のタプルsが存在しなくなるとS602;NO、SIPタプル生成部21は、実行命令に含まれる未処理の他のデータ識別子Sが存在するか否かを判定するS611。未処理の他のデータ識別子Sが存在する場合にはS611;YES、そのデータ識別子Sがデータ識別子Sに設定された後S612、上述と同様に処理S601以降が実行される。SIPタプル生成部21は、実行命令に含まれる未処理の他のデータ識別子が存在しないと判断するとS611;NO、未だ初期化されていない空になっていないSIPタプル集合sip[c]の送信をデータ分配部22へ依頼する。これにより、データ分配部22は、未だ空になっていないSIPタプル集合sip[c]の分配先を決定しS613、その決定された分配先の結合処理装置30へSIPタプル集合sip[c]を送信するS613。上述のような各データ管理装置20の処理が完了すると、図20の入力タプル集合データS及びRに関する各SIPタプルはそれぞれ図9A、図9B、図9C及び図9Dの例のように各結合処理装置30へ分配される。図9A、図9B、図9C及び図9Dは、図20の入力タプル集合S及びRに関するSIPタプルの分配例を示す図である。図9Aは、SIPタプル集合sip[X]を示し、図9Bは、SIPタプル集合sip[Y]を示し、図9Cは、SIPタプル集合sip[Z]を示し、図9Dは、SIPタプル集合sip[W]を示す。図8の例によれば、図9AのSIPタプル集合は、結合処理装置301へ分配され、図9BのSIPタプル集合は、結合処理装置302へ分配され、図9CのSIPタプル集合は、結合処理装置303へ分配され、図9DのSIPタプル集合は、結合処理装置304へ分配される。図10は、第3実施形態における結合処理装置30の動作例を示すフローチャートである。図10には、上記S505における動作の詳細が示される。各データ管理装置20において、実行命令に含まれる処理対象のデータ識別子の全てのSIPタプルの分配が完了すると、各結合処理装置30は、図10に示される処理を実行する。以下、図9AのSIPタプル集合が分配された結合処理装置301を例に挙げ、結合処理装置301の動作例を説明する。この場合、結合処理装置301では、SIPタプル格納部35に、図9AのSIPタプル集合が格納される。結合処理部32は、SIPタプル格納部35から、末尾部分文字列の先頭文字が共通するSIPタプルの集合を抽出するS1001。結合処理部32は、抽出されたSIPタプル集合の中の、タプルポインタから判別されるデータ識別子が異なる2つのSIPタプルの全ペアx、yを示す情報と共に、処理指示を推定値算出部33へ送る。推定値算出部33は、結合処理部32から送られた情報に基づいて、SIPタプルの全ペアx、yに関し、末尾部分文字列の編集距離EDx、yをそれぞれ計算するS1002。編集距離EDx、yは、一般的な周知の編集距離算出手法により算出されればよい。推定値算出部33は、算出された各部分文字列編集距離が閾値τ以下となるか否かをそれぞれ判定しS1003、部分文字列編集距離が閾値τ以下となる各ペアx、yに関し、局所編集距離をそれぞれ算出するS1003;YES、S1004。ここで、各ペアx、yに関する局所編集距離をLEDx、yとして示すと、局所編集距離の算出式は以下の式7のように示すことができる。LEDx、y=EDxt_i、yt_imax|xh_i|、|yh_i|式7更に、推定値算出部33は、部分文字列編集距離が閾値τ以下となる各ペアx、yに関し、算出された各局所編集距離を用いて結合処理判定をそれぞれ行うS1005。結合処理判定とは、局所編集距離が閾値τ以下となるか否かの判定である。即ち、以下の式8が判定される。LEDx、y≦τ式8図9Aの例において、タプル識別子がS:103であるSIPタプルS:103と、タプル識別子がR:203であるSIPタプルR:203とのペアに関する推定値算出部33の動作例は以下のとおりである。タプルS:103の末尾部分文字列xt_iはX-BB-KCであり、タプルR:203の末尾部分文字列yt_iはX-BB-KCである。また、タプルS:103の先頭部分文字列の文字列長|xh_i|は2であり、タプルR:203の先頭部分文字列の文字列長|yh_i|は2である。この場合、推定値算出部33は、タプルS:103及びタプルR:203のペアに関する部分文字列編集距離として、0ゼロを算出する。推定値算出部33は、部分文字列編集距離0が閾値τ2以下であるため、その部分文字列編集距離0と、大きい方の先頭部分文字列の文字列長2とを加算することにより、局所編集距離2を算出する。このときの算出式は以下の式9で示される。LEDS:103、R:203=EDX-BB-KC、X-BB-KCmax2、2=02=2式9推定値算出部33は、算出された局所編集距離2が閾値τ2以下であるため、結合処理判定の結果を真とする。このような推定値算出部33は、例えば、1つの関数validation関数として実現されてもよい。このとき、validation関数は、SIPタプルのペアにアクセスするためのアドレスを取得し、そのペアの局所編集距離と結合処理判定結果を示す情報とを返すように形成されればよい。結合処理部32は、SIPタプルの各ペアに関し、推定値算出部33から処理結果として局所編集距離及び結合処理判定結果をそれぞれ取得する。結合処理部32は、結合処理判定結果が真となるペアを特定し、特定された各ペアに関し、タプルポインタのペア及び局所編集距離を含む局所結果タプルをそれぞれ生成するS1006。結合処理部32は、生成された局所結果タプルを含む局所結合結果をシステム制御装置10に送信するS1006。結合処理部32は、局所結合結果をシステム制御装置10へ送信したS1006後、又は、部分文字列編集距離が閾値τ以下となるペアが存在しないと判断した場合S1003;NO、未処理の他のSIPタプル集合がSIPタプル格納部35内に存在するか否かを判定するS1007。結合処理部32は、未処理のSIPタプル集合が存在しない場合にはS1007;NO、処理を終了する。一方、結合処理部32は、未処理のSIPタプル集合が存在する場合にはS1007;YES、未処理のSIPタプルの先頭文字cを変数cに設定したS1008後、上述と同様に処理S1001以降を実行する。図11Aは、図9AのSIPタプル集合から算出される、部分文字列編集距離、局所編集距離及び局所結果タプルの例を示す図である。図11Bは、図9BのSIPタプル集合から算出される、部分文字列編集距離、局所編集距離及び局所結果タプルの例を示す図である。図11Cは、図9CのSIPタプル集合から算出される、部分文字列編集距離、局所編集距離及び局所結果タプルの例を示す図である。図11Dは、図9DのSIPタプル集合から算出される、部分文字列編集距離、局所編集距離及び局所結果タプルの例を示す図である。なお、図11A、図11B、図11C及び図11Dの各表における空欄は、部分文字列編集距離が閾値τを超えている、又は、局所編集距離が閾値τを超えているため処理が実行されなかった箇所を示す。図11Aの例によれば、SIPタプルの9つのペアに対して、3つの局所結果タプルが生成されている。図12は、第3実施形態におけるシステム制御装置10の動作例を示すフローチャートである。図12には、上記S507における動作の詳細が示される。結果生成部12は、各結合処理装置30から送られてくる各局所結合結果をそれぞれ受信するS1201。各居所結合結果にはそれぞれ局所結果タプルsがそれぞれ含まれている。結果生成部12は、受信された局所結果タプルsに含まれるタプルポインタのペアと同一のペアを含む局所結果タプルrを結合結果格納部15から抽出するS1201。続いて、結果生成部12は、受信された局所結果タプルsに含まれる局所編集距離led_sと、結合結果格納部15から抽出された局所結果タプルrに含まれる局所編集距離led_rとを取得するS1203。結果生成部12は、取得された局所編集距離led_sが同様に取得された局所編集距離led_rより小さいか否かを判定するS1204。結果生成部12は、局所編集距離led_sが局所編集距離led_rよりも小さい場合S1204;YES、結合結果格納部15から局所結果タプルrを削除し、代わりに局所結果タプルsを挿入するS1205。結果生成部12は、局所編集距離led_sが局所編集距離led_r以上である場合S1204;NO、何もしないで処理を終了する。ここで、図11A、図11B、図11C及び図11Dを参照すると、共通のタプルポインタのペアを含む複数の局所結果タプルが存在する。具体的には、タプルポインタペア<S:101、R:201>は、図11Aの1行目に示される局所結果タプル<<S:101、R:201>、1>、及び、図11Dの1行目に示される局所結果タプル<<S:101、R:201>、2>にそれぞれ含まれている。上述の図12に示されるシステム制御装置10の処理により、このような重複する局所結果タプルが除去される。図13は、システム制御装置10により得られる最終的な結合処理結果の例を示す図である。図13に示すように、重複する局所結果タプルについては、最小の局所編集距離を持つ局所結果タプルのみが残される。これにより、最終的に残された局所結果タプルに含まれる局所編集距離は、上述における真の編集距離と等しくなる。このことは、図13と図20の左下の表とを比較することにより証明することができる。図13と図20の左下の表を比較すると、本実施形態における文字列類似結合処理の結果が、図20の入力タプル集合S及びRを入力データとして品番属性を結合キー属性とした場合の既存の文字列類似結合処理結果と一致することが分かる。即ち、本実施形態によれば、編集距離を用いた文字列類似結合を適切に実行することができる。なお、上述の動作例では、SIPタプルが、末尾部分文字列と、残りの先頭部分文字列の文字列長と、タプルポインタとから形成される態様を例に挙げたが、当該SIPタプルは、装置構成の項で説明したように、先頭部分文字列と、残りの末尾部分文字列の文字列長と、タプルポインタとから形成される態様が利用されてもよい。この態様では、各SIPタプルは、先頭部分文字列の末尾文字からその分配先がそれぞれ決定され、局所編集距離は、先頭部分文字列間の編集距離と、大きい方の末尾部分文字列の文字列長とを加算することにより算出されればよい。第3実施形態における作用及び効果上述したように、第3実施形態では、データ管理装置20により、自身の保持するデータの各タプルの結合キー文字列に関し、先頭文字からiiはτ1以下の正の整数の各々番目の文字から末尾文字までの末尾部分文字列と、残りの先頭部分文字列の文字列長と、タプルポインタとの組み合わせ、又は、末尾文字からi番目の文字から先頭文字までの先頭部分文字列と、残りの末尾部分文字列の文字列長と、タプルポインタとから形成されるSIPタプルがτ1個それぞれ生成される。そして、各SIPタプルの分配先となる結合処理装置30が、各SIPタプルの末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字に応じて決定され、決定された結合処理装置30に各SIPタプルがそれぞれ分配される。これにより、第3実施形態では、各タプルに関し、最大で、τ1個の結合処理装置30が分配先として選出される。従って、第3実施形態によれば、ネットワーク7を流れる総通信量を小さく抑えることができる。具体的には、入力データS及びRに含まれる各タプル数をm及びnとすると、第3実施形態では、システム1全体の処理コストは、結合処理装置30の台数Nに依存されず、{τ×mn}となる。一方、従来の手法の処理コストは、N×mnとなる。従って、結合処理装置30の台数Nが大きく、かつ、閾値τが小さい程、第3実施形態は、従来手法よりも一層処理コストを抑えることができる。また、iの値が大きい程、SIPタプルのデータサイズは、完全な結合キー文字列のデータサイズよりも小さくなる。従って、第3実施形態は、完全な結合キー文字列を各結合処理装置30に送る必要のある従来手法に比べて、総通信量を抑えることができる。また、第3実施形態では、結合処理装置30により、複数のSIPタプルの各ペアに関し、末尾部分文字列間又は先頭部分文字列間の編集距離が部分文字列編集距離としてそれぞれ算出され、算出された部分文字列編集距離が閾値τ以下となるSIPタプルのペアがまず特定される。そして、この特定されたSIPタプルの各ペアに関し、当該部分文字列編集距離と、大きい方の先頭部分文字列の文字列長又は大きい方の末尾部分文字列の文字列長とを加算することにより、編集距離推定値がそれぞれ算出され、算出された各編集距離推定値が閾値τ以下となるSIPタプルのペアが特定される。更に、第3実施形態では、結合処理装置30により、特定されたSIPタプルの各ペアに関し、タプルポインタのペア及び局所編集距離を含む局所結果タプルが生成され、生成された各局所結果タプルがそれぞれシステム制御装置10へ送られる。システム制御装置10では、複数の結合処理装置30から送られた複数の局所結果タプルの中から同じタプルポインタのペアを含む重複結果タプルを検出し、検出された重複結果タプルの中から最小の編集距離推定値を持つ局所結果タプル以外が削除されることにより、編集距離が閾値τ以下となるタプルのペアが決定される。従って、第3実施形態によれば、部分文字列編集距離を算出するため、完全な結合キー文字列の編集距離を算出する従来手法に比べて、処理時間を短縮することができる。更に、第3実施形態のような分配手法を用いたとしても、上述の定理に示すように、タプルのペア<s、r>に対して、必ず1つ以上の結合処理装置30で真の編集距離EDs、rと値が等しくなる局所編集距離LEDs、rが算出されるため、取りこぼしなく結合処理が行われるように、処理対象データが分配される。更に、システム制御装置10による重複局所結果タプルの排除処理により、適切な文字列類似結合の結合結果を得ることができる。[第4実施形態]第4実施形態は、結合処理装置30における結合処理手法が第3実施形態と異なる。以下、第4実施形態におけるシステム1について第3実施形態と異なる内容を中心に説明し、第3実施形態と同じ内容については適宜省略する。図14は、第4実施形態における結合処理装置30の構成例を概念的に示すブロック図である。第4実施形態における結合処理装置30は、第3実施形態における推定値算出部33の代わりに、トライ木構築部37を更に有する。また、結合処理部32の処理が第3実施形態と異なる。第4実施形態における結合処理部32は、SIPタプル格納部35に格納されるSIPタプルを対象にトライ木を構築する処理をトライ木構築部37に実行させ、構築されたトライ木を辿ることにより局所結果タプルを生成する。結合処理部32は、第3実施形態と同様に、このように生成された局所結果タプルを含む局所結合結果をそれぞれシステム制御装置10に送信する。上記トライ木は、パトリシアトライに似た構造を有し、結合処理装置30のメモリ上に構築される。トライ木構築部37は、末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字が共通する各SIPタプル集合をSIPタプル格納部35から抽出し、抽出された各SIPタプル集合がマッピングされるトライ木をそれぞれ構築する。結合処理部32により構築されるトライ木は、SIPタプルを構成する末尾部分文字列又は先頭部分文字列、先頭部分文字列の文字列長又は末尾部分文字列の文字列長、及びタプルポインタの各情報をそれぞれ保持可能な構造を持つ。具体的には、当該トライ木では、SIPタプルの末尾部分文字列又は先頭部分文字列がルートノードからエッジノード葉ノードまでの枝パスにマッピングされ、各枝のエッジノードにはその枝にマッピングされたSIPタプルのタプルポインタが重みと共に付される。また、ルートノードには、末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字がラベルとして付され、子ノードのポインタのリストが重みと共に付される。このトライ木で利用される重みには、SIPタプルの先頭部分文字列の文字列長又は末尾部分文字列の文字列長が利用される。図15は、トライ木の構築例を概念的に示す図である。図15は、文字aを先頭文字又は末尾文字に持つ末尾部分文字列又は先頭部分文字列を含むSIPタプルの集合に関し構築されたトライ木tree_aの例を示す。このSIPタプル集合には、3種類の先頭部分文字列の文字列長0、1、2が含まれるため、ルートノード0:aには、3種類の重みが設定される。各子ノードポインタに重みがそれぞれ関連付けられている。なお、図15では、各ノードは、ノード番号とそのノードに付されたラベルとによりそれぞれ示されている。例えば、ノード2:aは、ノード番号が2であり、ラベルが文字aであるノードを示す。なお、図15では、ルートノードのノード番号は0に設定されている。以下、各ノードはノード番号のみを用いて示される。図15の例において、各枝とSIPタプルとの関係は以下のとおりである。文字列abaaは、ルートノード0、ノード1、ノード2及びノード3にマッピングされる。文字列acaaは、ルートノード0、ノード4、ノード5及びノード6にマッピングされる。文字列abcaaは、ルートノード0、ノード1、ノード7、ノード8及びノード9にマッピングされる。文字列acaは、ルートノード0、ノード10及びノード11にマッピングされる。文字列abcaaがマッピングされた枝のエッジノード9には、そのSIPタプルのタプルポインタs3が先頭部分文字列の文字列長0と共に付される。同様に、エッジノード6には、タプルポインタs2が先頭部分文字列の文字列長1と共に付され、エッジノード11には、タプルポインタs4が先頭部分文字列の文字列長2と共に付される。トライ木構築部37は、メモリ使用量を抑えるために、同一のタプルポインタを持つSIPタプルの末尾部分文字列又は先頭部分文字列を1つの枝にマッピングする。例えば、図15の文字列abaaと文字列aaとは同じタプルポインタs1を持つため、文字列abaaがマッピングされた枝の一部に文字列aaがマッピングされる。これは、一方の文字列は他方の文字列の部分文字列となるからである。従って、文字列aaは、ルートノード0及びノード3にマッピングされる。このとき、ルートノード0における重み2の子ノードポインタとしてノード3へのポインタ3:aが設定され、エッジノード3には、タプルポインタs1が重み0及び2と共に付される。なお、メモリ使用量を抑える必要がない場合には、同一のタプルポインタを持つSIPタプルの末尾部分文字列又は先頭部分文字列を異なる枝にマッピングするようにしてもよい。結合処理部32は、トライ木構築部37によりトライ木の構築処理が完了すると、構築されたトライ木を探索することにより、局所編集距離が閾値τ以下となる局所結果タプルの集合を取得する。結合処理部32は、トライ木の各ノードを順次訪問し、各ノードと類似している他のノードのリストアクティブリストを生成することで、当該局所結果タプルの集合を取得する。本実施形態では、アクティブリストには、類似する他のノードに関する、ノード番号、重み及び局所編集距離を含むノードタプルが格納される。結合処理部32によるトライ木の探索処理及び局所結果タプルの取得処理については後述する。動作例以下、第4実施形態におけるシステム1の動作例として、第3実施形態と異なる結合処理装置30における結合処理手法について説明する。図16は、結合処理装置30のトライ木の構築処理の例を示すフローチャートである。トライ木構築部37は、SIPタプル格納部35から、末尾部分文字列の先頭文字が共通するSIPタプルの集合を抽出するS1601。図16の例では、当該先頭文字がaのSIPタプル集合sip[a]が抽出される。図15の例によれば、例えば、SIPタプル<abaa、0、s1>が抽出される。トライ木構築部37は、SIPタプル集合sip[a]が抽出されると、トライ木を初期化するS1602。続いて、トライ木構築部37は、抽出されたSIPタプル集合sip[a]の中から、未処理のSIPタプルを取得するS1603。ここでは、SIPタプルに含まれる末尾部分文字列を文字列sと表記し、残りの先頭部分文字列の文字列長を長さplenと表記し、タプルポインタをpと表記する。トライ木構築部37は、当該先頭文字aのトライ木のルートノードが、重みplenが付された子ノードとしてラベルs[2]のノードndを持つか否かを判定するS1604。言い換えれば、トライ木構築部37は、当該ルートノードが、文字s[2]をラベルとして持つ子ノードのポインタが重みplenの子ノードポインタとして設定されているか否かを判定するS1604。文字s[2]とは、文字列sの先頭から2文字目の文字を意味する。図15の例によれば、ルートノード0に、文字babaaの2文字目をラベルとして持つ子ノードノード1のポインタ1:bが重み0の子ノードポインタとして設定されているか否かが判定される。トライ木構築部37は、既に子ノードを持つと判定するとS1604;YES、処理S1606を実行する。一方、トライ木構築部37は、該当する子ノードを持たないと判定するとS1604;NO、ラベルs[2]のノードndを新たに生成し、この生成された新たなノードndをルートノードの重みplenの子ノードに設定するS1605。図15の例によれば、ラベルbを持つノード1が生成され、ルートノードに、重み0及び子ノードポインタ1:bが設定される。トライ木構築部37は、変数iを3に設定し、変数parentをラベルs[2]のノードndに設定するS1606。続いて、トライ木構築部37は、変数iが文字列sの長さより大きくなるまでS1607、以下に説明する処理S1608からS1613を繰り返し実行する。処理S1608では、トライ木構築部37は、文字s[i]をラベルに持つノードndが変数parentに設定されているノードの子ノードに存在するか否かを判定する。この判定は、例えば、各ノードが持つ子ノードのポインタを用いて実行される。既に、ラベルs[i]のノードndが存在する場合にはS1608;YES、トライ木構築部37は、変数parentにラベルs[i]のノードndを設定しS1612、かつ、変数iに1加算したS1613後、S1607の判定を再度行う。一方、未だ、ラベルs[i]のノードndが存在しない場合にはS1608;NO、トライ木構築部37は、ラベルs[i]のノードndを新たに生成し、新たなノードndを変数parentに設定されているノードの子ノードに設定するS1609。図15の例によれば、ラベルaを持つノード2が生成され、ノード1に、子ノードポインタ2:aが設定される。続いて、トライ木構築部37は、文字s[i]の1つ前の文字s[i-1]から始まる末尾部分文字列を含むSIPタプルが存在し、かつ、当該文字s[i-1]がルートノードのラベルと等しいか否かを判定するS1610。具体的には、この判定は、図16に示すように、{pleni-2≦τ}かつs[i-1]=aが真か否かの判定である。この判定により、1つの枝にマッピングできる他のSIPタプルが存在するか否かが判定される。トライ木構築部37は、文字s[i]の1つ前の文字s[i-1]から始まる末尾部分文字列を含むSIPタプルが存在し、かつ、当該文字s[i-1]がルートノードのラベルと等しい場合にはS1610;YES、ルートノードの重みpleni-2の子ノードとしてノードndを追加するS1611。言い換えれば、トライ木構築部37は、当該ルートノードに、ラベルs[i]のノードndのポインタを重みpleni-2と共に設定する。図15の例によれば、文字列sがabaaである場合の処理S1609においてノード3が生成され、処理S1611において、ルートノードに、子ノードポインタ3:aが重み2と共に設定される。よって、この場合、文字列sがaaであるSIPタプルが処理対象とされた時には、既に、ルートノード0からノード3へのリンクは設定された状態となっている。以降、上述した処理S1612及びS1613が実行される。トライ木構築部37は、変数iが文字列sの長さより大きくなるS1607;YES、即ち、文字列sのトライ木へのマッピングが完了すると、ノードndにタプルポインタpを重みplenと共に設定するS1614。図15の例によれば、例えば、ノード3に、タプルポインタs1が重み0と共に設定される。なお、文字列sがaaであるSIPタプルが処理対象とされる場合には、ノード3に設定されたタプルポインタs1の重みとして重み2が追加される。続いて、トライ木構築部37は、SIPタプル集合sip[a]に未処理のSIPタプルtが存在するか否かを判定するS1615。未処理のSIPタプルtが存在する場合にはS1615;YES、トライ木構築部37は、処理対象のSIPタプルを示す変数tをtに設定したS1616後、再度、処理S1603以降を実行する。なお、未処理のSIPタプルtが存在しない場合にはS1615;NO、トライ木構築部37は処理を終了する。以上のような処理が実行されることにより、図15に示すようなトライ木が構築される。SIPタプル格納部35から、他の文字bが共通するSIPタプルの集合及び他の文字cが共通するSIPタプルの集合が抽出された場合にはS1601、文字b及び文字cに関する各トライ木がそれぞれ構築される。図17A及び図17Bは、文字b及び文字cに関する各トライ木の例を示す図である。結合処理部32は、トライ木構築部37における上述のようなトライ木の構築処理が完了すると、構築されたトライ木を探索することにより、局所編集距離が閾値τ以下となる局所結果タプルの集合を取得する。図18は、トライ木の探索処理の例を示すフローチャートである。結合処理部32は、各トライ木についてそれぞれ図18に示す処理を実行する。結合処理部32は、ルートノードに設定されている重みの中から、未処理の重みwを取得するS1801。更に、結合処理部32は、ルートノードに設定されている重みの中から、任意の重みw2を取得するS1802。結合処理部32は、重みwのルートノード以降、rootwと表記すると重みw2のルートノード以降、rootw2と表記するとの間の局所編集距離を算出するS1802。局所編集距離の算出手法は、第3実施形態と同様である。rootw及びrootw2は共に同じラベルを持つため、編集距離EDrootw、rootw2は0ゼロである。よって、rootwとrootw2との間の局所編集距離ledは、大きい方の重み値、即ち、先頭部分文字列又は末尾部分文字列の文字列長となる。結合処理部32は、rootw2をrootwのアクティブリストに追加するS1802。これにより、rootwのアクティブリストには、rootw2に関するノードタプルが設定される。このノードタプルは、ノード番号0、重みw2、及び、rootwとrootw2との間の局所編集距離を含む。ところで、ルートノード間の局所編集距離は、上述したとおり、大きい方の重み値となるため、必ず閾値τ以下となる。よって、処理S1802では、閾値τと局所編集距離とを比較することなく、rootw2に関するノードタプルがアクティブリストに追加される。次に、結合処理部32は、rootw2の子ノードnd2w2と、rootwとの間の局所編集距離ledを算出するS1803。ここで、ノード間の局所編集距離は、各ノードまでのパスにより形成される文字列間の編集距離に、大きい方の重み値が加算されることにより算出される。つまり、rootwとノードnd2w2との間の局所編集距離は、rootwのラベルに付された文字と、rootwのラベルとノードnd2w2のラベルとから形成される文字列との間の編集距離に、重みwと重みw2とのうち大きい方の重み値を加えた値となる。結合処理部32は、算出された局所編集距離ledが閾値τ以下であれば、rootwのアクティブリストにノードnd2w2を追加するS1803。これにより、rootwのアクティブリストには、ノードnd2w2に関するノードタプルが追加される。このノードタプルは、ノードnd2w2に関するノード番号、重みw2及び算出された局所編集距離ledを含む。なお、結合処理部32は、rootw2の子ノードnd2w2が複数存在する場合には、各子ノードについて処理S1803をそれぞれ実行する。また、結合処理部32は、ルートノードに複数の重みが設定されている場合には、各重みw2に関し、上述の処理S1802及びS1803を実行する。以上により、rootwのアクティブリストの生成が完了する。結合処理部32は、rootwの子孫ノードndwのアクティブリストも再帰的に順次生成する。まず、結合処理部32は、rootwの各子ノードndwをそれぞれ取得するS1804。結合処理部32は、取得された子ノードndwの親ノードのアクティブリストを取得しS1805、そのアクティブリストに設定されるノードanw3を取得するS1806。結合処理部32は、ノードndwとノードanw3との間の局所編集距離ledを算出し、算出された局所編集距離ledが閾値τ以下である場合には、ノードndwのアクティブリストにノードanw3を追加するS1807。更に、結合処理部32は、ノードanw3の各子ノードan_childw3とノードndwとの間の局所編集距離led2を算出し、算出された局所編集距離led2が閾値τ以下である場合には、ノードndwのアクティブリストにノードan_childw3を追加するS1808。結合処理部32は、ノードndwの親ノードのアクティブリストに、未処理のノードanw3が存在するか否かを判定するS1809。結合処理部32は、未処理のノードanw3が存在する場合にはS1809;YES、その未処理のノードanw3に関し、上述の処理S1806以降を実行する。結合処理部32は、未処理のノードanw3が存在しない場合にはS1809;NO、ノードndwにおける未処理の子ノードnd_childwが存在するか否かを判定するS1810。結合処理部32は、未処理の子ノードnd_childwが存在する場合にはS1810;YES、その未処理の子ノードnd_childwを処理対象のノードndwに設定してS1811、上述の処理S1805以降を実行する。結合処理部32は、未処理の子ノードnd_childwが存在しない場合にはS1810;NO、ルートノードに未処理の重みwが存在するか否かを判定するS1812。未処理の重みwが存在する場合にはS1812;YES、結合処理部32は、その未処理の重みに関し、上述の処理S1801以降を実行する。一方、未処理の重みwが存在しなければS1812;NO、結合処理部32は、処理を終了する。結合処理部32は、以上のような処理を実行することにより、トライ木の各ノードについてアクティブリストをそれぞれ生成する。図19は、アクティブリストの例を示す図である。図19は、図15の例に示す、文字aに関するトライ木tree_aにおける、重み0のルートノード、ノード1、ノード2及びノード3のアクティブリストを示す。図19における下線は、対応するノードがタプルポインタを所持することを示す。これにより、結合処理部32は、タプルポインタを所持するノード3のアクティブリストから、ノード3を含む、局所編集距離が閾値τ以下となるノードのペアを特定する。図19の例によれば、結合処理部32は、ノード3とノード3とのペア、ノード3とノード9とのペア、ノード3とノード6とのペアを得ることができる。結合処理部32は、このように特定されたノードのペアに関し、アクティブリスト内のノードタプルに基づいて、タプルポインタのペア及び局所編集距離を含む局所結果タプルを生成する。このようにして、結合処理部32は、全てのエッジノードのアクティブリストを利用することにより、局所結合結果を得ることができる。第4実施形態における作用及び効果第4実施形態では、結合処理装置30において、データ管理装置20から分配されるSIPタプルがトライ木にマッピングされる。当該トライ木では、SIPタプルに含まれる先頭部分文字列又は接尾部分文字列の文字列長が重みとして用いられ、重み毎に少なくとも1つの子ノードを持つルートノードが生成され、エッジノード葉ノードにはタプルポインタが重みと共に付される。そして、構築されたトライ木の各ノードに関しそれぞれ、親ノードのアクティブリストに基づいて選択された他のノードと当該ノードとの間の局所編集距離が算出され、算出された局所編集距離と閾値τとが比較される。結果、局所編集距離が閾値τ以下となる他のノードに関する情報が各ノードのアクティブリストに設定される。このように、第4実施形態によれば、トライ木の性質を利用して、親ノードのアクティブリストに基づいて各ノードの結合処理対象を選択することにより、局所編集距離を計算すべき対象を制限することができ、結果、結合処理の計算量を削減することができる。更に、第4実施形態によれば、末尾部分文字列又は先頭部分文字列を用いた局所編集距離の算出を採用するため、結合キー文字列全体を対象とした編集距離の算出を必要とする従来手法に比べて、処理コストを削減することができる。また、第4実施形態では、各ノードのアクティブリストには、当該ノードとの間の局所編集距離が閾値以下となる他ノードの情報、及び、その局所編集距離が設定される。よって、第4実施形態によれば、各エッジノードのアクティブリストを参照することにより、局所編集距離が閾値τ以下となる局所結果タプルを即座に取得することができる。[変形例]上述の各実施形態では、1つのタプルに対して、τ1個のSIPタプルが生成された。そして、1つのタプルから生成された複数のSIPタプルが、末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字が等しいために、同じ結合処理装置30へ分配される可能性がある。例えば、図9Cの例によれば、タプルポインタがR:203である2つのSIPタプルが同じ結合処理装置30に分配されている。この場合、結合処理装置30は、末尾部分文字列がZZX-BB-KCであり、先頭部分文字列の文字列長が0ゼロであるSIPタプルのみを得れば、そのSIPタプルから、末尾部分文字列がZX-BB-KCであり、先頭部分文字列の文字列長が1であるSIPタプルを自身で生成することができる。従って、データ管理装置20のSIPタプル生成部21は、末尾部分文字列の先頭文字が同じであるSIPタプルに関しては、残りの先頭部分文字列の文字列長が最も小さいSIPタプルのみを生成するようにしてもよい。この場合、結合処理装置30は、受信されたSIPタプルに基づいて、必要となる他のSIPタプルを生成するようにすればよい。図9Cの例によれば、データ管理装置20は、末尾部分文字列がZZX-BB-KCであり先頭部分文字列の文字列長が0ゼロであるSIPタプルを生成し、末尾部分文字列の先頭文字が同じになるSIPタプル末尾部分文字列がZX-BB-KCであり、先頭部分文字列の文字列長が1であるSIPタプルを生成しない。結合処理装置30は、このSIPタプルを受信した場合、文字列ZZX-BB-KCと、文字列長0と、閾値τとの関係から、データ管理装置20で生成されなかったSIPタプルが必要であると判断する。そこで、結合処理装置30は、末尾部分文字列がZX-BB-KCであり、先頭部分文字列の文字列長が1であるSIPタプルを生成した後、結合処理を開始する。このようにすれば、システム1内の通信コストを一層削減することができる。また、上述の各実施形態では、システム制御装置10の要求制御部11が処理要求を取得した後、要求制御部11により送られる実行命令に応じて、データ管理装置20がSIPタプルを分配し、結合処理装置30が処理を開始していた。他の態様として、処理要求が受け付けられる前に、データ管理装置20が所定条件を満たすSIPタプルを予め結合処理装置30へ分配しておくようにしてもよい。具体的には、編集距離閾値τに上限値max_τを設け、データ管理装置20は、当該閾値τが上限値である場合のSIPタプル1≦i≦max_τ1を生成し、予め分配する。システム制御装置10は、閾値τを含んだ処理要求を受け付けると、結合処理装置30のみに対して実行命令を出す。結合処理装置30は、予め分配されているSIPタプルのうち、先頭部分文字列又は末尾部分文字列の文字列長が閾値τ以下のSIPタプルのみを用いて、結合処理を実行する。このようにすれば、処理要求を受け付けてから結合処理結果を生成するまでの時間には、データ管理装置20から結合処理装置30への分配データ送信処理にかかる時間は含まれない。よって、処理要求を受け付けてから結合処理結果を生成するまでの時間を短縮することができる。このような態様は、多くの処理要求が短時間のうちに大量に舞い込むオンライン処理に好適である。[補足]上述の各実施形態及び変形例において実行される類似結合処理は、少なくとも1つのデータ管理装置20に格納されている少なくとも1つのデータSIPタプル集合であって処理要求で指定されたデータの中から、当該処理要求で指定された結合キー属性の文字列間の編集距離が閾値τの条件を満たすタプルのペアを検出していた。しかしながら、本発明に係る類似結合処理は、このような態様に限定されず、文字列類似検索処理の意をも包含する概念である。つまり、本発明に係る類似結合処理は、処理要求等で得られるクエリ文字列を1つのタプルとし、このクエリ文字列との間の編集距離が閾値τの条件を満たすタプルを、少なくとも1つのデータ管理装置20に格納されている少なくとも1つのデータの中から検索する処理であってもよい。この態様では、処理要求で指定されたデータを保持するデータ管理装置20は、上述の各実施形態及び変形例と同様に、SIPタプルを生成しかつ分配する。一方、クエリ文字列をシステム制御装置10から取得したデータ管理装置20は、このクエリ文字列に関するSIPタプルを生成しかつ分配する。クエリ文字列に関するSIPタプルを受信した結合処理装置30は、クエリ文字列に関するSIPタプルと、他のSIPタプルとのペアを対象に、上述の各実施形態及び変形例と同様の結合処理を実行すればよい。また、本発明に係る類似結合処理は、同じ意味を示すが表記が微妙に異なる文字列を検出するといった名寄せ技術をも含む概念である。また、上述の各実施形態及び変形例で示した文字列類似結合システム1は、複数の店舗をまたがる在庫検索システム等に適用することができる。このような態様によれば、商品名が店舗によって若干異なる場合にも、探したい商品を検出することができる。また、同じモデルの商品であっても色やサイズなどが違うことにより各商品に異なる品番が付く場合がある。このような場合でも、当該態様によれば、色やサイズが違う同じモデルの商品を検出することができる。なお、上述の説明で用いた複数のフローチャートでは、複数のステップ処理が順番に記載されているが、本実施形態で実行される処理ステップの実行順序は、その記載の順番に制限されない。本実施形態では、図示される処理ステップの順番を内容的に支障のない範囲で変更することができる。また、上述の各実施形態及び各変形例は、内容が相反しない範囲で組み合わせることができる。上記の各実施形態及び各変形例の一部又は全部は、以下の付記のようにも特定され得る。但し、各実施形態及び各変形例が以下の記載に限定されるものではない。付記1複数のタプルを対象に編集距離閾値τ正の整数を用いて類似結合処理を実行する結合処理装置において、上記各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に、共通する文字を持たないタプルのペアを編集距離計算対象から除外する結合処理手段を備えることを特徴とする結合処理装置。付記2複数のタプルを対象に編集距離閾値τ正の整数を用いて類似結合処理を実行する複数の結合処理装置と通信可能に接続されるデータ管理装置において、複数のタプルを格納するデータ格納手段と、上記複数の結合処理装置の中から、上記データ格納手段に格納される各タプルを処理させる結合処理装置を各タプルの分配先として決定する際に、各タプルの分配先を、各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に含まれる少なくとも1つの文字を、結合キー文字列の中の当該端部分に含む他のタプルと同じ分配先にそれぞれ決定し、かつ、各タプルの結合キー文字列の中の当該端部分に共通する文字を持たない他のタプルとは同じ分配先にならないようにそれぞれ決定するデータ分配手段と、を備えることを特徴とするデータ管理装置。付記3少なくとも1つのデータ管理装置、及び、この少なくとも1つのデータ管理装置で保持される複数のタプルを対象に編集距離閾値τ正の整数を用いて類似結合処理を実行する複数の結合処理装置を含む文字列類似結合システムにおいて、上記少なくとも1つのデータ管理装置は、上記各タプルの結合キー文字列に関し、先頭文字からiiはτ1以下の正の整数の各々番目の文字から末尾文字までの末尾部分文字列と、残りの先頭部分文字列の文字列長と、タプル特定データとの組み合わせ、又は、末尾文字からi番目の文字から先頭文字までの先頭部分文字列と、残りの末尾部分文字列の文字列長と、タプル特定データとの組み合わせを含むキー情報タプルをτ1個それぞれ生成するキー情報生成手段と、このキー情報生成手段により生成された各キー情報タプルに含まれる末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字に基づいて、当該各キー情報タプルの分配先を決定し、当該各キー情報タプルを、分配先として決定された各結合処理装置に各タプルのデータとしてそれぞれ分配するデータ分配手段と、を備え、上記複数の結合処理装置はそれぞれ、上記少なくとも1つのデータ管理装置から分配された複数のキー情報タプルを受信する受信手段と、この受信手段により受信された複数のキー情報タプルのうち、末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字が共通するキー情報タプル集合毎に、上記類似結合処理を実行する結合処理手段と、を備えることを特徴とする文字列類似結合システム。付記4上記複数の結合処理装置はそれぞれ、上記受信手段により受信された複数のキー情報タプルの各ペアに関し、末尾部分文字列間又は先頭部分文字列間の編集距離を部分文字列編集距離としてそれぞれ算出し、算出された部分文字列編集距離が上記編集距離閾値τの条件を満たすキー情報タプルの各ペアに関し、当該部分文字列編集距離と、大きい方の先頭部分文字列の文字列長又は大きい方の末尾部分文字列の文字列長とを加算することにより、編集距離推定値をそれぞれ算出する推定値算出手段を更に備え、上記結合処理手段は、上記推定値算出手段により算出された各編集距離推定値と上記編集距離閾値τとの比較結果に基づいて、編集距離が上記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを特徴とする付記3に記載の文字列類似結合システム。付記5上記複数の結合処理装置はそれぞれ、上記受信手段により受信された複数のキー情報タプルに基づいて、先頭部分文字列又は末尾部分文字列の文字列長を重み値として管理するトライ木であって、末尾部分文字列又は先頭部分文字列がルートノードからエッジノードまでの枝にマッピングされたトライ木を構築するトライ木構築手段、を更に備え、上記結合処理手段は、上記トライ木構築手段により構築されたトライ木に含まれる各対象ノードに関し、対象ノードにより特定される文字列と他ノードで特定される文字列との間の編集距離と、対象ノード及び他ノードの重み値のうち大きい方の重み値とを加算することにより、他ノードのための編集距離推定値をそれぞれ算出し、当該編集距離推定値が上記編集距離閾値τの条件を満たす他ノードの情報及び当該編集距離推定値を含むリストを各対象ノードに関しそれぞれ設定し、エッジノードに設定されたリストに基づいて、編集距離が上記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを特徴とする付記3に記載の文字列類似結合システム。付記6上記結合処理手段は、親ノードに設定されたリストに含まれる他ノードの情報に基づいて、各対象ノードの編集距離推定値の計算対象となる他ノードを選択する、ことを特徴とする付記5に記載の文字列類似結合システム。付記7上記トライ木構築手段は、同一のタプル特定データを持つ複数のキー情報タプルの末尾部分文字列又は先頭部分文字列を上記トライ木の1つの枝及び当該1つの枝の少なくとも1部分にマッピングし、上記トライ木のルートノードに、当該1つの枝の少なくとも1部分を特定するためのノードポインタを上記重み値と共に設定する、ことを特徴とする付記5又は6に記載の文字列類似結合システム。付記8上記少なくとも1つのデータ管理装置及び上記複数の結合処理装置と通信可能なシステム制御装置を更に含み、上記各結合処理装置の上記結合処理手段は、上記特定された各ペアに関し、タプル特定データのペア及び編集距離推定値を含む結果タプルをそれぞれ生成し、生成された各結果タプルをそれぞれ上記システム制御装置に送信し、上記システム制御装置は、上記複数の結合処理装置から送られた複数の結果タプルの中から同じタプル特定データのペアを含む重複結果タプルを検出し、検出された重複結果タプルの中から最小の編集距離推定値を持つ結果タプル以外の結果タプルを削除することにより、編集距離が上記編集距離閾値τの条件を満たすタプルのペアを決定する結果生成手段、を備えることを特徴とする付記4から7のいずれか1つに記載の文字列類似結合システム。付記9上記システム制御装置は、上記編集距離閾値τを含む処理要求を取得した後、上記複数の結合処理装置に処理の実行命令を送信する要求制御手段、を更に備え、上記少なくとも1つのデータ管理装置の上記キー情報生成手段は、予め決められた上記編集距離閾値τの上限値を上記編集距離閾値τと仮定して、上記各タプルの結合キー文字列に関する仮のキー情報タプルをそれぞれ生成し、上記少なくとも1つのデータ管理装置の上記データ分配手段は、上記処理要求が上記システム制御装置により取得される前に、上記各仮のキー情報タプルを各分配先の結合処理装置にそれぞれ分配する、ことを特徴とする付記3から8のいずれか1つに記載の文字列類似結合システム。付記10複数のタプルを対象に編集距離閾値τ正の整数を用いて実行される文字列類似結合方法において、少なくとも1つのコンピュータが、各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に、共通する文字を持たないタプルのペアを編集距離計算対象から除外する、ことを含む文字列類似結合方法。付記11複数のタプルを対象に編集距離閾値τ正の整数を用いて実行される文字列類似結合方法において、少なくとも1つのコンピュータが、上記各タプルの結合キー文字列に関し、先頭文字からiiはτ1以下の正の整数の各々番目の文字から末尾文字までの末尾部分文字列と、残りの先頭部分文字列の文字列長と、タプル特定データとの組み合わせ、又は、末尾文字からi番目の文字から先頭文字までの先頭部分文字列と、残りの末尾部分文字列の文字列長と、タプル特定データとの組み合わせを含むキー情報タプルをτ1個それぞれ生成し、上記生成された各キー情報タプルに含まれる末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字に基づいて、当該各キー情報タプルの分配先を決定し、当該各キー情報タプルを、分配先として決定された各対象コンピュータに各タプルのデータとしてそれぞれ分配し、上記各キー情報タプルの分配先として決定された対象コンピュータが、上記分配された複数のキー情報タプルを受信し、上記受信された複数のキー情報タプルのうち、末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字が共通するキー情報タプル集合毎に、類似結合処理を実行する、ことを含む文字列類似結合方法。付記12上記各キー情報タプルの分配先として決定された対象コンピュータが、上記受信された複数のキー情報タプルの各ペアに関し、末尾部分文字列間又は先頭部分文字列間の編集距離を部分文字列編集距離としてそれぞれ算出し、算出された部分文字列編集距離が上記編集距離閾値τの条件を満たすキー情報タプルの各ペアに関し、当該部分文字列編集距離と、大きい方の先頭部分文字列の文字列長又は大きい方の末尾部分文字列の文字列長とを加算することにより、編集距離推定値をそれぞれ算出し、上記算出された各編集距離推定値と上記編集距離閾値τとの比較結果に基づいて、編集距離が上記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを更に含む付記11に記載の文字列類似結合方法。付記13上記各キー情報タプルの分配先として決定された対象コンピュータが、上記受信された複数のキー情報タプルに基づいて、先頭部分文字列又は末尾部分文字列の文字列長を重み値として管理するトライ木であって、末尾部分文字列又は先頭部分文字列がルートノードからエッジノードまでの枝にマッピングされたトライ木を構築し、上記構築されたトライ木に含まれる各対象ノードに関し、対象ノードにより特定される文字列と他ノードで特定される文字列との間の編集距離と、対象ノード及び他ノードの重み値のうち大きい方の重み値とを加算することにより、他ノードのための編集距離推定値をそれぞれ算出し、当該編集距離推定値が上記編集距離閾値τの条件を満たす他ノードの情報及び当該編集距離推定値を含むリストを各対象ノードに関しそれぞれ設定し、エッジノードに設定されたリストに基づいて、編集距離が上記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを更に含む付記11に記載の文字列類似結合方法。付記14上記編集距離推定値を算出する際には、親ノードに設定されたリストに含まれる他ノードの情報に基づいて、各対象ノードの編集距離推定値の計算対象となる他ノードを選択する、ことを特徴とする付記13に記載の文字列類似結合方法。付記15上記トライ木を構築する際には、同一のタプル特定データを持つ複数のキー情報タプルの末尾部分文字列又は先頭部分文字列を上記トライ木の1つの枝及び当該1つの枝の少なくとも1部分にマッピングし、上記トライ木のルートノードに、当該1つの枝の少なくとも1部分を特定するためのノードポインタを上記重み値と共に設定する、ことを特徴とする付記13又は14に記載の文字列類似結合方法。付記16上記各キー情報タプルの分配先として決定された対象コンピュータが、上記特定された各ペアに関し、タプル特定データのペア及び編集距離推定値を含む結果タプルをそれぞれ生成し、上記生成された各結果タプルをそれぞれ他のコンピュータに送信し、上記他のコンピュータが、上記対象コンピュータから送られた複数の結果タプルの中から同じタプル特定データのペアを含む重複結果タプルを検出し、検出された重複結果タプルの中から最小の編集距離推定値を持つ結果タプル以外の結果タプルを削除することにより、編集距離が上記編集距離閾値τの条件を満たすタプルのペアを決定する、ことを更に含む付記12から15のいずれか1つに記載の文字列類似結合方法。付記17複数のタプルを対象に編集距離閾値τ正の整数を用いて文字列類似結合を少なくとも1つのコンピュータに実行させるプログラムにおいて、上記少なくとも1つのコンピュータに、上記各タプルの結合キー文字列の中の先頭文字又は末尾文字からτ1番目までの端部分に、共通する文字を持たないタプルのペアを編集距離計算対象から除外する結合処理手段、を実現させることを特徴とするプログラム。付記18複数のタプルを対象に編集距離閾値τ正の整数を用いて文字列類似結合を少なくとも1つのコンピュータに実行させるプログラムにおいて、少なくとも1つのコンピュータに、上記各タプルの結合キー文字列に関し、先頭文字からiiはτ1以下の正の整数の各々番目の文字から末尾文字までの末尾部分文字列と、残りの先頭部分文字列の文字列長と、タプル特定データとの組み合わせ、又は、末尾文字からi番目の文字から先頭文字までの先頭部分文字列と、残りの末尾部分文字列の文字列長と、タプル特定データとの組み合わせを含むキー情報タプルをτ1個それぞれ生成するキー情報生成手段と、このキー情報生成手段により生成された各キー情報タプルに含まれる末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字に基づいて、当該各キー情報タプルの分配先を決定し、当該各キー情報タプルを、分配先として決定された各対象コンピュータに各タプルのデータとしてそれぞれ分配するデータ分配手段と、を実現させ、上記各キー情報タプルの分配先として決定された対象コンピュータに、上記少なくとも1つのコンピュータから分配された複数のキー情報タプルを受信する受信手段と、この受信手段により受信された複数のキー情報タプルのうち、末尾部分文字列の先頭文字又は先頭部分文字列の末尾文字が共通するキー情報タプル集合毎に、前記類似結合処理を実行する結合処理手段と、を実現させることを特徴とするプログラム。付記19上記各キー情報タプルの分配先として決定された対象コンピュータに、上記受信手段により受信された複数のキー情報タプルの各ペアに関し、末尾部分文字列間又は先頭部分文字列間の編集距離を部分文字列編集距離としてそれぞれ算出し、算出された部分文字列編集距離が上記編集距離閾値τの条件を満たすキー情報タプルの各ペアに関し、当該部分文字列編集距離と、大きい方の先頭部分文字列の文字列長又は大きい方の末尾部分文字列の文字列長とを加算することにより、編集距離推定値をそれぞれ算出する推定値算出手段と、上記推定値算出手段により算出された各編集距離推定値と上記編集距離閾値τとの比較結果に基づいて、編集距離が上記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する結合処理手段と、を実現させることを特徴とする付記18に記載のプログラム。付記20上記各キー情報タプルの分配先として決定された対象コンピュータに、上記受信手段により受信された複数のキー情報タプルに基づいて、先頭部分文字列又は末尾部分文字列の文字列長を重み値として管理するトライ木であって、末尾部分文字列又は先頭部分文字列がルートノードからエッジノードまでの枝にマッピングされたトライ木を構築するトライ木構築手段と、上記トライ木構築手段により構築されたトライ木に含まれる各対象ノードに関し、対象ノードにより特定される文字列と他ノードで特定される文字列との間の編集距離と、対象ノード及び他ノードの重み値のうち大きい方の重み値とを加算することにより、他ノードのための編集距離推定値をそれぞれ算出し、当該編集距離推定値が上記編集距離閾値τの条件を満たす他ノードの情報及び当該編集距離推定値を含むリストを各対象ノードに関しそれぞれ設定し、エッジノードに設定されたリストに基づいて、編集距離が上記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する結合処理手段と、を実現させることを特徴とする付記18に記載のプログラム。付記21付記17から20のいずれか1つに記載のプログラムを記録したコンピュータが読み取り可能な記録媒体。この出願は、2011年2月2日に出願された日本出願特願2011-020374を基礎とする優先権を主張し、その開示の全てをここに取り込む。