(57)【特許請求の範囲】
【請求項１】
整列済みの複数の要素を含む第１のデータ源から読み出した第１の要素と、整列済みの複数の要素を含む第２のデータ源から読み出した第２の要素と、を第１の比較演算子及び前記第１の比較演算子と異なる第２の比較演算子により順次比較判定する第１の比較部と、
前記第１の要素と前記第２の要素とを前記第１の比較演算子及び前記第２の比較演算子により順次比較判定すると共に、前記第１の比較演算子及び前記第２の比較演算子による比較順序が前記第１の比較部と異なる第２の比較部と、
前記第１の比較部及び前記第２の比較部の何れかにより前記第１の要素と前記第２の要素とが同一でないと判定された場合に、前記第１の比較部及び前記第２の比較部の何れかが直前に実行した比較判定と同一の比較判定を先に行う比較部を前記第１の比較部及び前記第２の比較部から選択する選択部と、
前記第１の比較部及び前記第２の比較部の何れかにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、当該同一と判定された同一要素を出力する出力部と、
前記出力部が前記同一要素を出力した場合は、前記第１のデータ源及び前記第２のデータ源から次の要素を各々読み出すと共に、前記選択部により前記第１の比較部及び前記第２の比較部のうち一方の比較部が選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち一方のデータ源から次の要素を読み出し、前記選択部により前記第１の比較部及び前記第２の比較部のうち他方の比較部が選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち他方のデータ源から次の要素を読み出す読み出し部と、
を含む共通要素抽出装置。
【請求項２】
前記第１の要素と前記第２の要素とが同一であるか否か又は同一でないか否かを比較判定する第３の比較演算子と、前記第１の比較演算子及び前記第２の比較演算子のうち一方の比較演算子と、により前記第１の要素と前記第２の要素とを順次比較判定する第３の比較部をさらに備え、
前記選択部は、前記第３の比較部により前記第１の要素と前記第２の要素とが同一でないと判定された場合に、前記第１の比較部又は前記第２の比較部を選択すると共に、前記第３の比較部により前記第１の要素と前記第２の要素とが同一であると判定された場合に、前記第３の比較部を選択し、
前記出力部は、前記第１の比較部、前記第２の比較部、及び前記第３の比較部から選択された比較部により前記第１の要素と前記第２の要素とが同一であると判定された場合に、当該同一と判定された同一要素を出力する
請求項１記載の共通要素抽出装置。
【請求項３】
複数の前記請求項１又は請求項２記載の共通要素抽出装置を多段接続した共通要素抽出装置。
【請求項４】
２段目以降の前記共通要素抽出装置に、前段の前記共通要素抽出装置から出力された前記同一要素と、データ源から出力された要素と、が入力されるように、複数の前記共通要素抽出装置を多段接続した
請求項３記載の共通要素抽出装置。
【請求項５】
１段目に２つのデータ源からの各要素が入力される前記共通要素抽出装置が複数設けられ、２段目以降の前記共通要素抽出装置に、前段の２つの前記共通要素抽出装置から各々出力された前記同一要素が各々入力されるように、複数の前記共通要素抽出装置を多段接続した
請求項３記載の共通要素抽出装置。
【請求項６】
コンピュータが、
整列済みの複数の要素を含む第１のデータ源から読み出した第１の要素と、整列済みの複数の要素を含む第２のデータ源から読み出した第２の要素と、を第１の比較演算子及び前記第１の比較演算子と異なる第２の比較演算子により順次比較判定する第１の比較ステップと、
前記第１の要素と前記第２の要素とを前記第１の比較演算子及び前記第２の比較演算子により順次比較判定すると共に、前記第１の比較演算子及び前記第２の比較演算子による比較順序が前記第１の比較ステップと異なる第２の比較ステップと、
前記第１の比較ステップ及び前記第２の比較ステップの何れかにより前記第１の要素と前記第２の要素とが同一でないと判定された場合に、前記第１の比較ステップ及び前記第２の比較ステップの何れかが直前に実行した比較判定と同一の比較判定を先に行う比較ステップを前記第１の比較ステップ及び前記第２の比較ステップから選択する選択ステップと、
前記第１の比較ステップ及び前記第２の比較ステップの何れかにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、当該同一と判定された同一要素を出力する出力ステップと、
前記出力ステップが前記同一要素を出力した場合は、前記第１のデータ源及び前記第２のデータ源から次の要素を各々読み出すと共に、前記選択ステップにより前記第１の比較ステップ及び前記第２の比較ステップのうち一方の比較ステップが選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち一方のデータ源から次の要素を読み出し、前記選択ステップにより前記第１の比較ステップ及び前記第２の比較ステップのうち他方の比較ステップが選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち他方のデータ源から次の要素を読み出す読み出しステップと、
を含む処理を実行する共通要素抽出方法。
【請求項７】
コンピュータに、
整列済みの複数の要素を含む第１のデータ源から読み出した第１の要素と、整列済みの複数の要素を含む第２のデータ源から読み出した第２の要素と、を第１の比較演算子及び前記第１の比較演算子と異なる第２の比較演算子により順次比較判定する第１の比較ステップと、
前記第１の要素と前記第２の要素とを前記第１の比較演算子及び前記第２の比較演算子により順次比較判定すると共に、前記第１の比較演算子及び前記第２の比較演算子による比較順序が前記第１の比較ステップと異なる第２の比較ステップと、
前記第１の比較ステップ及び前記第２の比較ステップの何れかにより前記第１の要素と前記第２の要素とが同一でないと判定された場合に、前記第１の比較ステップ及び前記第２の比較ステップの何れかが直前に実行した比較判定と同一の比較判定を先に行う比較ステップを前記第１の比較ステップ及び前記第２の比較ステップから選択する選択ステップと、
前記第１の比較ステップ及び前記第２の比較ステップの何れかにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、当該同一と判定された同一要素を出力する出力ステップと、
前記出力ステップが前記同一要素を出力した場合は、前記第１のデータ源及び前記第２のデータ源から次の要素を各々読み出すと共に、前記選択ステップにより前記第１の比較ステップ及び前記第２の比較ステップのうち一方の比較ステップが選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち一方のデータ源から次の要素を読み出し、前記選択ステップにより前記第１の比較ステップ及び前記第２の比較ステップのうち他方の比較ステップが選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち他方のデータ源から次の要素を読み出す読み出しステップと、
を含む処理を実行させるための共通要素抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
開示の技術は共通要素抽出装置、共通要素抽出方法、及び共通要素抽出プログラムに関する。
【背景技術】
【０００２】
複数のイベントストリームからタイムスタンプ等が同じイベントを抽出するデータ分析として、例えばＰＯＳ（Point Of Sale）のバスケット分析、プローブデータの軌跡分析、感染症の分析、ＳＮＳ（Social Networking Service）分析等がある。
【０００３】
このようなデータ分析を行うには、分析対象である複数のデータ源を昇順又は降順に整列し、整列済みの複数のデータ源から同じ値のデータを抽出する。例えば２つのデータ源から同じ値のデータを抽出する場合、データ源の先頭から順に、２つのデータの大小比較を行い、同じ値のデータを出力する。
【０００４】
具体的には、図３８に示すような共通要素抽出処理によって２つのデータ源から同じデータを抽出することができる。同図は、データ源Ｘ＝｛Ｘ［０］、Ｘ［１］、・・・、Ｘ［ｎ］｝とデータ源Ｙ＝｛Ｙ［０］、Ｙ［１］、・・・、Ｙ［ｍ］｝を先頭から順次入力して大小比較を行い、同じ値のデータを出力する処理である。なお、ｎ，ｍは自然数である。
【０００５】
まず、ステップ２００では、データ源Ｘ用のカウンタｉ、データ源Ｙ用のカウンタｊを‘０’に初期化する。
【０００６】
ステップ２０２では、カウンタｉがｎより小さく且つカウンタｊがｍより小さいか否かを判定する。そして、カウンタｉがｎより小さく且つカウンタｊがｍより小さい場合にはステップ２０４へ移行し、そうでない場合には本ルーチンを終了する。
【０００７】
ステップ２０４では、Ｘ［ｉ］がＹ［ｊ］より小さいか否かを判定し、Ｘ［ｉ］がＹ［ｊ］より小さい場合はステップ２１２へ移行してカウンタｉをインクリメントする。一方、Ｘ［ｉ］がＹ［ｊ］より小さくない場合には、ステップ２０６へ移行する。
【０００８】
ステップ２０６では、Ｘ［ｉ］がＹ［ｊ］がより大きいか否かを判定し、Ｘ［ｉ］がＹ［ｊ］より大きい場合にはステップ２１４へ移行してカウンタｊをインクリメントする。一方、Ｘ［ｉ］がＹ［ｊ］より大きくない場合、すなわちＸ［ｉ］とＹ［ｊ］が同一の場合には、ステップ２０８へ移行してデータＸ［ｉ］を出力する。そして、ステップ２１０へ移行してカウンタｉをインクリメントし、続いてステップ２１４へ移行してカウンタｊをインクリメントする。
【０００９】
例えば図３９に示すような整列済みのデータ源Ｘ、Ｙについて図３８に示す処理を実行すると、データ源Ｘの要素とデータ源Ｙの要素とが同じ値となる｛１、９、１４、１９｝が出力される。
【００１０】
このように、図３８に示す処理は、データ源Ｘの要素とデータ源Ｙの要素との大小関係によって３通りの処理を実行する処理と言える。すなわち、データ源Ｘの要素がデータ源Ｙの要素より小さいか否かの比較判定処理を行い、データ源Ｘの要素がデータ源Ｙの要素よりも小さい場合には、データ源Ｘの次の要素を読み込む。また、データ源Ｘの要素がデータ源Ｙの要素よりも小さくない場合、データ源Ｘの要素がデータ源Ｙの要素より大きいか否かの比較判定処理を行い、データ源Ｘの要素がデータ源Ｙの要素よりも大きい場合には、データ源Ｙの次の要素を読み込む。一方、データ源Ｘの要素がデータ源Ｙの要素よりも大きくない場合、すなわちデータ源Ｘの要素とデータ源Ｙの要素とが同じである場合には、処理ｃを実行してデータ源Ｘの要素（＝データ源Ｙの要素）を出力する。そして、データ源Ｘの次の要素及びデータ源Ｙの次の要素を読み込む。
【００１１】
従って、データ源Ｘの要素がデータ源Ｙの要素よりも小さくない場合が連続する場合、ステップ２０４、２０６の２回の比較判定処理が繰り返されることとなり、処理時間が増加してしまう。例えば図４０に示すように、データ源Ｘの要素がデータ源Ｙの要素よりも小さい範囲Ｓ１では、図３８に示すステップ２０４の１回の比較判定処理だけでよい。一方、データ源Ｘの要素がデータ源Ｙの要素よりも小さくない範囲Ｓ２では、図３８に示すステップ２０４、２０６の２回の比較判定処理が必要となる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特表２００７−５３１９４８号公報
【非特許文献】
【００１３】
【非特許文献１】"Fast Sorted-Set Intersection using SIMD Instructions.", B.Schlegel,T.Willhalm,W.Lehner, In Proceedings of the Second International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS 2011), September, 2011, Seattle, WA, USA
【発明の概要】
【発明が解決しようとする課題】
【００１４】
このように、従来の図３８に示す処理では、データ源Ｘの要素がデータ源Ｙの要素よりも小さくない範囲が多くなるほど処理時間が増加する。このため、例えばデータの出現時刻に偏りがあるセンサーが出力したデータの出現時刻を要素とする整列済みの複数のデータ源の共通要素を出力したい場合、無駄な比較処理が多くなり処理時間が増大する、という問題があった。
【００１５】
開示の技術は、整列済みのデータ源から共通要素を抽出する際に処理時間が増大するのを抑制することが目的である。
【課題を解決するための手段】
【００１６】
開示の技術は、第１の比較部は、整列済みの複数の要素を含む第１のデータ源から読み出した第１の要素と、整列済みの複数の要素を含む第２のデータ源から読み出した第２の要素と、を第１の比較演算子及びこれと異なる第２の比較演算子により順次比較判定する。第２の比較部は、前記第１の要素と前記第２の要素とを前記第１の比較演算子及び前記第２の比較演算子により順次比較判定すると共に、前記第１の比較演算子及び前記第２の比較演算子による比較順序が前記第１の比較部と異なる。選択部は、第１の比較部及び第２の比較部の何れかにより第１の要素と第２の要素とが同一でないと判定された場合に、直前に実行した比較判定と同一の比較判定を先に行う比較部を第１の比較部及び第２の比較部から選択する。出力部は、前記第１の比較部及び前記第２の比較部の何れかにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、当該同一と判定された同一要素を出力する。読み出し部は、前記出力部が前記同一要素を出力した場合は、前記第１のデータ源及び前記第２のデータ源から次の要素を各々読み出す。また、出力部は、前記選択部により前記第１の比較部及び前記第２の比較部のうち一方の比較部が選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち一方のデータ源から次の要素を読み出す。また、出力部は、前記選択部により前記第１の比較部及び前記第２の比較部のうち他方の比較部が選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち他方のデータ源から次の要素を読み出す。
【発明の効果】
【００１７】
開示の技術は、整列済みのデータ源から共通要素を抽出する際に処理時間が増大するのを抑制することができる、という効果を有する。
【図面の簡単な説明】
【００１８】
【図１】第１実施形態に係る共通要素抽出装置の機能ブロック図である。
【図２】第１実施形態に係る共通要素抽出装置として機能するコンピュータの概略ブロック図である。
【図３】第１実施形態に係る共通要素抽出処理の一例を示すフローチャートである。
【図４】データ源の一例を示す図である。
【図５】データ源の各要素の比較結果について説明するための図である。
【図６】共通要素抽出処理の比較処理の処理順序について説明するための図である。
【図７】データ源の各要素の比較結果について説明するための図である。
【図８】共通要素抽出処理の比較処理の処理順序について説明するための図である。
【図９】データ源の各要素の比較結果について説明するための図である。
【図１０】共通要素抽出処理の比較処理の処理順序について説明するための図である。
【図１１】データ源の各要素の比較結果について説明するための図である。
【図１２】データ源の各要素の比較結果について説明するための図である。
【図１３】データ源の各要素の比較結果について説明するための図である。
【図１４】共通要素抽出処理の比較処理の処理順序について説明するための図である。
【図１５】データ源の各要素の比較結果について説明するための図である。
【図１６】共通要素抽出処理の比較処理の処理順序について説明するための図である。
【図１７】データ源の各要素の比較結果について説明するための図である。
【図１８】データ源の各要素の比較結果について説明するための図である。
【図１９】共通要素抽出処理の比較処理の処理順序について説明するための図である。
【図２０】データ源の各要素の比較結果について説明するための図である。
【図２１】データ源の各要素の比較結果について説明するための図である。
【図２２】データ源の共通要素の抽出結果について説明するための図である。
【図２３】比較装置Ｓの概念図である。
【図２４】比較装置Ｔの概念図である。
【図２５】データ源の各要素の比較回数について説明するための図である。
【図２６】第２実施形態に係る共通要素抽出装置の機能ブロック図である。
【図２７】第２実施形態に係る共通要素抽出装置として機能するコンピュータの概略ブロック図である。
【図２８】第２実施形態に係る共通要素抽出処理の一例を示すフローチャートである。
【図２９】第２実施形態に係る共通要素抽出処理の一例を示すフローチャートである。
【図３０】第３実施形態に係る共通要素抽出装置の機能ブロック図である。
【図３１】第３実施形態に係る共通要素抽出装置の機能ブロック図である。
【図３２】データ源の各要素の１処理当たりの比較回数の期待値の実験結果を示す図である。
【図３３】データ源の各要素の要素数と共通要素抽出処理の計算時間との関係を示す図である。
【図３４】実験に用いたデータ源の一例を示す図である。
【図３５】データ源の各要素のブロック長と共通要素抽出処理の計算時間との関係を示す図である。
【図３６】データ源の各要素のブロック長について説明するための図である。
【図３７】図３５の一部拡大図である。
【図３８】従来例に係る共通要素抽出処理の一例を示すフローチャートである。
【図３９】従来例に係るデータ源の共通要素の抽出結果について説明するための図である。
【図４０】従来例に係るデータ源の各要素の比較回数について説明するための図である。
【発明を実施するための形態】
【００１９】
以下、図面を参照して開示の技術の実施形態の一例を詳細に説明する。
【００２０】
（第１実施形態）
【００２１】
図１には、本第１実施形態に係る共通要素抽出装置１０が示されている。共通要素抽出装置１０は、整列済みの２つのデータ源の各要素を順次比較して同一の要素を抽出する装置である。
【００２２】
図１に示すように、共通要素抽出装置１０は、第１の比較部１２、第２の比較部１４、選択部１６、出力部１８、及び読み出し部２０を備えている。
【００２３】
第１の比較部１２は、整列済みの複数の要素を含む第１のデータ源Ｘから読み出した第１の要素Ｘ［ｉ］と、整列済みの複数の要素を含む第２のデータ源Ｙから読み出した第２の要素Ｙ［ｊ］と、を第１の比較演算子及び第２の比較演算子により順次比較判定する。なお、ｉ＝０〜ｎでｎは自然数、ｊ＝０〜ｍでｍは自然数である。また、本実施形態では、第１の比較演算子及び第２の比較演算子は、大小比較を行う比較演算子であり、一例として“＜”、“＞”が用いられる。
【００２４】
第２の比較部１４は、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とを第１の比較演算子及び第２の比較演算子により順次比較判定する。また、第２の比較部１４は、第１の比較演算子及び第２の比較演算子による比較順序が第１の比較部１２と異なる。すなわち、第１の比較部１２が、第１の比較演算子、第２の比較演算子の順に第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とを比較判定する場合、第２の比較部１４は、第２の比較演算子、第１の比較演算子の順に第１の要素Ｘ［ｉ］と第２の要素とを比較判定する。
【００２５】
選択部１６は、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とが同一であると判定されなかった場合に、直前に実行された比較判定と同一の比較判定を先に行う比較部を第１の比較部１２及び第２の比較部１４から選択する。
【００２６】
出力部１８は、第１の比較部１２及び第２の比較部１４の何れかにより第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とが同一であると判定された場合に、当該同一と判定された同一要素を出力する。
【００２７】
読み出し部２０は、第１の読み出し部２０Ｘ及び第２の読み出し部２０Ｙを備えている。第１の読み出し部２０Ｘは、出力部１８が同一要素を出力した場合は第１のデータ源Ｘから次の要素を読み出すと共に、選択部１６により第１の比較部１２が選択された場合は、第１のデータ源Ｘから次の要素を読み出す。第２の読み出し部２０Ｙは、出力部１８が同一要素を出力した場合は第２のデータ源Ｙから次の要素を読み出すと共に、選択部１６により第２の比較部１４が選択された場合は、第２のデータ源Ｙから次の要素を読み出す。
【００２８】
共通要素抽出装置１０は、例えば図２に示すコンピュータ６０で実現することができる。コンピュータ６０はＣＰＵ６２、メモリ６４、不揮発性の記憶部６６を備え、これらはバス６７を介して互いに接続されている。
【００２９】
また、記憶部６６はＨＤＤ(Hard Disk Drive)やフラッシュメモリ等によって実現できる。記録媒体としての記憶部６６には、コンピュータ６０を共通要素抽出装置１０として機能させるための共通要素抽出プログラム６８が記憶されている。ＣＰＵ６２は、共通要素抽出プログラム６８を記憶部６６から読み出してメモリ６４に展開し、共通要素抽出プログラム６８が有するプロセスを順次実行する。
【００３０】
共通要素抽出プログラム６８は、第１の比較プロセス７０、第２の比較プロセス７２、選択プロセス７４、出力プロセス７６、第１の読み出しプロセス７８、及び第２の読み出しプロセス８０を有する。
【００３１】
ＣＰＵ６２は、第１の比較プロセス７０を実行することで、図１に示す第１の比較部１２として動作する。また、ＣＰＵ６２は、第２の比較プロセス７２を実行することで、図１に示す第２の比較部１４として動作する。また、ＣＰＵ６２は、選択プロセス７４を実行することで、図１に示す選択部１６として動作する。またＣＰＵ６２は、出力プロセス７６を実行することで、図１に示す出力部１８として動作する。またＣＰＵ６２は、第１の読み出しプロセス７８を実行することで、図１に示す第１の読み出し部２０Ｘとして動作する。またＣＰＵ６２は、第２の読み出しプロセス８０を実行することで、図１に示す第２の読み出し部２０Ｙとして動作する。
【００３２】
これにより、共通要素抽出プログラム６８を実行したコンピュータ６０が、共通要素抽出装置１０として機能することになる。なお、共通要素抽出プログラム６８は開示の技術における共通要素抽出プログラムの一例である。
【００３３】
なお、共通要素抽出装置１０は、例えば半導体集積回路、より詳しくはＡＳＩＣ(Application Specific Integrated Circuit)等で実現することも可能である。
【００３４】
次に第１実施形態の作用を説明する。共通要素抽出装置１０に対して共通要素抽出処理の実行が指示されると、図３に示す共通要素抽出処理が実行される。なお、本実施形態では、一例として第１の比較演算子を“＜”、第２の比較演算子を“＞”とする。
【００３５】
図３に示す共通要素抽出処理は、データ源Ｘ＝｛Ｘ［０］、Ｘ［１］、・・・、Ｘ［ｎ］｝とデータ源Ｙ＝｛Ｙ［０］、Ｙ［１］、・・・、Ｙ［ｍ］｝を先頭から順次入力して大小比較を行い、共通要素、すなわち同一の要素を出力する処理である。
【００３６】
まず、ステップ１００では、第１の読み出し部２０Ｘが、データ源Ｘ用のカウンタｉを‘０’に初期化すると共に、第２の読み出し部２０Ｙが、データ源Ｙ用のカウンタｊを‘０’に初期化する。
【００３７】
ステップ１０２では、第１の読み出し部２０Ｘが、カウンタｉがｎより小さいか否かを判定すると共に、第２の読み出し部２０Ｙが、カウンタｊがｍより小さいか否かを判定する。そして、カウンタｉがｎより小さく且つカウンタｊがｍより小さい場合にはステップ１０４へ移行し、カウンタｉがｎ以上又はカウンタｊがｍ以上となった場合には、本ルーチンを終了する。すなわち、データ源Ｘ及びデータ源Ｙの少なくとも一方から全ての要素を読み出した場合には本ルーチンを終了する。
【００３８】
ステップ１０４では、第１の読み出し部２０Ｘが、データ源Ｘから第１の要素Ｘ［ｉ］を読み出すと共に、第２の読み出し部２０Ｙが、データ源Ｙから第２の要素Ｙ［ｊ］を読み出す。そして、第１の比較部１２が、第１の比較演算子“＜”により、Ｘ［ｉ］がＹ［ｊ］より小さいか否かを判定し、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さくない場合はステップ１０６へ移行する。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さい場合は、選択部１６がステップ１１２へ移行させる。
【００３９】
ステップ１１２では、第１の読み出し部２０Ｘが、カウンタｉをインクリメントする。
【００４０】
ステップ１０６では、第１の比較部１２が、第２の比較演算子“＞”により、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きいか否かを判定し、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きくない場合はステップ１０８へ移行する。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きい場合は、選択部１６がステップ１１４へ移行させる。
【００４１】
ステップ１０４で第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さくないと判定され、且つ、ステップ１０６で第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きくないと判定された場合、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］は同一である。
【００４２】
従って、ステップ１０８では、出力部１８が、第１の要素Ｘ［ｉ］（＝第２の要素Ｙ［ｊ］）を出力する。
【００４３】
ステップ１１０では、第１の読み出し部２０Ｘがカウンタｉをインクリメントする。そして、選択部１６がステップ１１４へ移行させる。
【００４４】
ステップ１１４では、第２の読み出し部２０Ｙがカウンタｊをインクリメントする。
【００４５】
ステップ１１６では、ステップ１０２と同様に、第１の読み出し部２０Ｘが、カウンタｉがｎより小さいか否かを判定すると共に、第２の読み出し部２０Ｙが、カウンタｊがｍより小さいか否かを判定する。そして、カウンタｉがｎより小さく且つカウンタｊがｍより小さい場合にはステップ１１８へ移行し、カウンタｉがｎ以上又はカウンタｊがｍ以上となった場合には、本ルーチンを終了する。
【００４６】
ステップ１１８では、第２の比較部１４がステップ１０６と同様の比較判定を行う。すなわち、第２の比較部１２が、第２の比較演算子“＞”により、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きいか否かを判定する。そして、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きくない場合はステップ１２０へ移行する。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きい場合は、選択部１６がステップ１１４へ移行させる。
【００４７】
ステップ１２０では、第２の比較部１４がステップ１０４と同様の比較判定を行う。すなわち、第２の比較部１４が、第１の比較演算子“＜”により、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さいか否かを判定する。そして、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さくない場合はステップ１２２へ移行する。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さい場合は、選択部１６がステップ１１２へ移行させる。
【００４８】
ステップ１１８で第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きくないと判定され、且つ、ステップ１２０で第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さくないと判定された場合、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］は同一である。
【００４９】
従って、ステップ１２２では、出力部１８が、第１の要素Ｘ［ｉ］（＝第２の要素［ｊ］）を出力する。
【００５０】
ステップ１２４では、第２の読み出し部２０Ｙがカウンタｊをインクリメントする。そして、選択部１６がステップ１１２へ移行させる。
【００５１】
このように、ステップ１０４で第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さいと判定された場合は、選択部１６は、その後再びステップ１０４の比較判定が行われるように、ステップ１１２へ移行させる。
【００５２】
また、ステップ１０６で第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きいと判定された場合は、選択部１６は、その後ステップ１０６と同様の比較判定を行うステップ１１８の比較判定が行われるように、ステップ１１４へ移行させる。
【００５３】
また、ステップ１１８で第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きいと判定された場合は、選択部１６は、その後再びステップ１１８の比較判定が行われるように、ステップ１１４へ移行させる。
【００５４】
また、ステップ１２０で第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さいと判定された場合は、選択部１６は、その後ステップ１２０と同様の比較判定を行うステップ１０４の比較判定が行われるように、ステップ１１２へ移行させる。
【００５５】
すなわち、選択部１６は、第１の比較部１２及び第２の比較部１４によって第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］と同一でないと判定された場合は、直前に実行した比較判定と同一の比較判定を先に行う比較部を第１の比較部１２及び第２の比較部１４から選択する。
【００５６】
これにより、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さい状態が続く場合は、第１の比較部１２によりステップ１０４の比較判定が繰り返される。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きい状態が続く場合は、第２の比較部１４によりステップ１１８の比較判定が繰り返される。すなわち、第１の比較部１２によりステップ１０４、１０６の２回の比較判定が行われるのは、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］が同一の場合だけとなる。同様に、第２の比較部１４によりステップ１１８、１２０の２回の比較判定が行われるのは、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］が同一の場合だけとなる。
【００５７】
次に、図４に示すようなデータ源Ｘ及びデータ源Ｙに対して図３の処理を実行した場合に、第１の比較部１２及び第２の比較部１４において比較判定処理が何回実行されるかについて説明する。
【００５８】
まず、図５の四角で囲まれたデータ、すなわちデータ源Ｘから先頭のデータである第１の要素Ｘ［０］＝１、データ源Ｙから先頭の要素である第２の要素Ｙ［０］＝１が読み出される。この場合、図６の矢印Ａ１で示す処理順序で処理が実行される。この場合、ステップ１０４、１０６の２回の比較判定処理が実行されるため、第１の要素Ｘ［０］と第２の要素Ｙ［０］が同一であると判定され、共通要素として第１の要素Ｘ［０］＝１が出力される。
【００５９】
そして、図７に示すように、データ源Ｘの次の第１の要素Ｘ［１］＝３、データ源Ｙの次の第２の要素Ｙ［１］＝８が読み出され、図８の矢印Ａ２で示す処理順序で処理が実行される。この場合、ステップ１１８、１２０の２回の比較判定処理が実行され、第１の要素Ｘ［１］が第２の要素Ｙ［１］よりも小さいと判定される。
【００６０】
次に、図９に示すように、データ源Ｘの次の第１の要素Ｘ［２］＝４が入力され、図１０の矢印Ａ３で示す処理順序で処理が実行される。この場合、ステップ１０４の１回の比較判定処理が実行され、第１の要素Ｘ［２］が第２の要素Ｙ［１］よりも小さいと判定される。
【００６１】
次に、図１１に示すように、データ源Ｘの次の第１の要素Ｘ［３］＝５が読み出され、図１０の矢印Ａ３で示す処理順序で処理が実行される。この場合、ステップ１０４の１回の比較判定処理が実行され、第１の要素Ｘ［３］が第２の要素Ｙ［１］よりも小さいと判定される。
【００６２】
次に、図１２に示すように、データ源Ｘの次の第１の要素Ｘ［４］＝７が読み出され、図１０の矢印Ａ３で示す処理順序で処理が実行される。この場合、ステップ１０４の１回の比較判定処理が実行され、データ源Ｘの要素がデータ源Ｙの要素よりも小さいと判定される。
【００６３】
次に、図１３に示すように、データ源Ｘの次の第１の要素Ｘ［５］＝９が読み出され、図１４の矢印Ａ４で示す処理順序で処理が実行される。この場合、ステップ１０４、１０６の２回の比較判定処理が実行され、第１の要素Ｘ［５］が第２の要素Ｙ［１］よりも大きいと判定される。
【００６４】
次に、図１５に示すように、データ源Ｙの次の第２の要素Ｙ［２］＝９が読み出され、図１６の矢印Ａ５で示す処理順序で処理が実行される。この場合、ステップ１１８、１２０の２回の比較判定処理が実行され、第１の要素Ｘ［５］が第２の要素Ｙ［２］と同一であると判定され、共通要素としてＸ［５］＝９が出力される。
【００６５】
次に、図１７に示すように、データ源Ｘの次の第１の要素Ｘ［６］＝１４、データ源Ｙの次の第２の要素Ｙ［３］＝１０が読み出され、図１４の矢印Ａ４で示す処理順序で処理が実行される。この場合、ステップ１０４、１０６の２回の比較判定処理が実行され、第１の要素Ｘ［６］が第２の要素Ｙ［３］よりも大きいと判定される。
【００６６】
次に、図１８に示すように、データ源Ｙの次の第２の要素Ｙ［４］＝１１が読み出され、図１９の矢印Ａ６で示す処理順序で処理が実行される。この場合、ステップ１１８の１回の比較判定処理が実行され、第１の要素Ｘ［６］が第２の要素Ｙ［４］よりも大きいと判定される。
【００６７】
次に、図２０に示すように、データ源Ｙの次の第２の要素Ｙ［５］＝１２が読み出され、図１９の矢印Ａ６で示す処理順序で処理が実行される。この場合、ステップ１１８の１回の比較判定処理が実行され、第１の要素Ｘ［６］が第２の要素Ｙ［５］よりも大きいと判定される。
【００６８】
次に、図２１に示すように、データ源Ｙの次の第２の要素Ｙ［６］＝１４が読み出され、図１６の矢印Ａ５で示す処理順序で処理が実行される。この場合、ステップ１１８、１２０の２回の比較判定処理が実行され、第１の要素Ｘ［６］が第２の要素Ｙ［６］と同一であると判定され、共通要素としてＸ［６］＝１４が出力される。
【００６９】
以下同様の処理を繰り返すことにより、図２２に示すように、データ源Ｘとデータ源Ｙの共通要素である｛１，９，１４，１９｝が出力される。
【００７０】
図３に示す処理のうち、ステップ１０２〜１１２の処理は、図２３に示すように、データ源Ｘの第１の要素Ｘ［ｉ］とデータ源Ｙの第２の要素Ｙ［ｊ］との大小関係によって３通りの処理ａ、ｂ、ｃを実行する比較装置Ｓと言える。すなわち、データ源Ｘの第１の要素Ｘ［ｉ］とデータ源Ｙの第２の要素Ｙ［ｊ］とを第１の比較演算子“＜”により比較判定し、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］よりも小さい場合には、処理ａとしてデータ源Ｘの次の第１の要素を読み込む。また、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］よりも小さくない場合、さらに第２の比較演算子“＞”により第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とを比較判定する。そして、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］よりも大きい場合には、処理ｂとしてデータ源Ｙの次の第２の要素を読み込む。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］よりも大きくない場合には、すなわち第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］と同一である場合には、処理ｃとして第１の要素Ｘ［ｉ］（＝第２の要素Ｙ［ｊ］）を出力する。そして、データ源Ｘの次の第１の要素及びデータ源Ｙの次の第２の要素を読み込む。
【００７１】
また、図３に示す処理のうち、ステップ１１４〜１２４の処理は、図２４に示すように、データ源Ｘの第１の要素Ｘ［ｉ］とデータ源Ｙの第２の要素Ｙ［ｊ］との大小関係によって３通りの処理ａ、ｂ、ｃを実行する比較装置Ｔと言える。すなわち、データ源Ｘの第１の要素Ｘ［ｉ］とデータ源Ｙの第２の要素Ｙ［ｊ］とを第２の比較演算子“＞”により比較判定し、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］よりも大きい場合には、処理ｂとしてデータ源Ｙの次の第２の要素を読み込む。また、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］よりも大きくない場合、さらに第１の比較演算子“＜”により第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とを比較判定する。そして、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］よりも小さい場合には、処理ａとしてデータ源Ｘの次の第１の要素を読み込む。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］よりも小さくない場合には、すなわち第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］と同一である場合には、処理ｃとして第１の要素Ｘ［ｉ］（＝第２の要素Ｙ［ｊ］）を出力する。そして、データ源Ｘの次の第１の要素及びデータ源Ｙの次の第２の要素を読み込む。
【００７２】
このように、第１の比較部１２が実行するステップ１０４、１０６の比較判定処理と、第２の比較部１４が実行するステップ１１８、１２０の比較判定処理は、第１の比較演算子“＜”及び第２の比較演算子“＞”による比較判定処理の順序が逆となっている。そして、第１の比較部１２及び第２の比較部１４によって第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］と同一でないと判定された場合は、直前に実行した比較判定と同一の比較判定を行う比較部が第１の比較部１２及び第２の比較部１４から選択される。
【００７３】
これにより、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さい状態が続く場合は、第１の比較部１２によりステップ１０４の比較判定処理が繰り返される。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より大きい状態が続く場合は、第２の比較部１４によりステップ１１８の比較判定処理が繰り返される。そして、第１の比較部１２によりステップ１０４、１０６の２回の比較判定が行われるのは、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］が同一の場合だけとなる。同様に、第２の比較部１４によりステップ１１８、１２０の２回の比較判定が行われるのは、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］が同一の場合だけとなる。このため、図２５に示すように、データ源Ｘの第１の要素がデータ源Ｙの第２の要素よりも小さい範囲Ｓ１では、図３に示すステップ１０４の１回の比較判定処理が実行される。また、データ源Ｘの要素がデータ源Ｙの要素よりも大きい場合が連続する範囲Ｔ１では、図３に示すステップ１１８の１回の比較判定処理が実行される。従って、例えば第１の要素が連続して出現した後、第２の要素が連続して出現するような、要素の出現に偏りがあるデータ源の共通要素を抽出する場合、無駄な比較判定処理を少なくすることができ、処理時間が増大するのを抑制することができる。
【００７４】
（第２実施形態）
【００７５】
次に開示の技術の第２実施形態について説明する。なお、第１実施形態と同一の部分には同一の符号を付して説明を省略し、第１実施形態と異なる部分についてのみ説明する。
【００７６】
図２６には、第２実施形態に係る共通要素抽出装置１０Ａが示されている。第２実施形態に係る共通要素抽出装置１０Ａは、第１実施形態に係る共通要素抽出装置１０と異なるのは、第３の比較部２２が設けられている点である。
【００７７】
第３の比較部２２は、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とが同一であるか否か又は同一でないか否かを比較判定する第３の比較演算子と、第１の比較演算子又は第２の比較演算子と、により第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とを順次比較判定する。例えば第１の比較演算子を“＜”、第２の比較演算子を“＞”とした場合、第３の比較演算子は“＝”が用いられる。
【００７８】
選択部１６は、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とが同一であると判定されなかった場合に、第１の比較部１２又は第２の比較部１４を選択する。また、選択部１６は、第３の比較部２２により第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とが同一であると判定された場合に、第３の比較部２２を選択する。
【００７９】
出力部１８は、第１の比較部１２、第２の比較部１４、及び第３の比較部２２から選択された比較部により第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とが同一であると判定された場合に、当該同一と判定された同一要素を出力する。
【００８０】
共通要素抽出装置１０Ａは、例えば図２７に示すコンピュータ６０Ａで実現することができる。コンピュータ６０Ａが図２に示すコンピュータ６０と異なるのは、記憶部６６に記憶された共通要素抽出プログラム６８Ａが第３の比較プロセス７３を有する点である。ＣＰＵ６２は、第３の比較プロセス７３を実行することで、図２６に示す第３の比較部２２として動作する。これにより、共通要素抽出プログラム６８Ａを実行したコンピュータ６０Ａが、共通要素抽出装置１０Ａとして機能することになる。なお、共通要素抽出プログラム６８Ａは開示の技術における共通要素抽出プログラムの一例である。
【００８１】
次に第２実施形態の作用として、第２実施形態に係る共通要素抽出処理について図２８を参照して説明する。なお、第１実施形態で説明した共通要素抽出処理(図３参照)と異なる部分についてのみ説明する。
【００８２】
図２８に示す共通要素抽出処理では、図３に示した共通要素抽出処理に対してステップ１３０〜１３４の処理が追加されている。
【００８３】
ステップ１３０は、ステップ１０２、１１６と同様の処理である。すなわち、第１の読み出し部２０Ｘが、カウンタｉがｎより小さいか否かを判定すると共に、第２の読み出し部２０Ｙが、カウンタｊがｍより小さいか否かを判定する。そして、カウンタｉがｎより小さく且つカウンタｊがｍより小さい場合にはステップ１３２へ移行し、カウンタｉがｎ以上又はカウンタｊがｍ以上となった場合には、本ルーチンを終了する。すなわち、データ源Ｘ及びデータ源Ｙの少なくとも一方から全ての要素を読み出した場合には本ルーチンを終了する。
【００８４】
ステップ１３２では、第３の比較部２２が、第３の比較演算子“＝”により、Ｘ［ｉ］がＹ［ｊ］と同一であるか否かを判定する。そして、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］と同一である場合は、選択部１６がステップ１０８へ移行させる。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］と同一でない場合には、ステップ１３４へ移行する。
【００８５】
ステップ１３４では、第３の比較部２２が、第１の比較演算子“＜”により、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さいか否かを判定する。そして、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さい場合は、選択部１６がステップ１１２へ移行させる。一方、第１の要素Ｘ［ｉ］が第２の要素Ｙ［ｊ］より小さくない場合は、選択部１６がステップ１１４へ移行させる。
【００８６】
これにより、第１の要素Ｘ［ｉ］と第２の要素Ｙ［ｊ］とが同一の状態が続く場合は、第３の比較部２２によりステップ１３２の比較判定処理が繰り返される。従って、第１の要素と第２の要素とが同一の状態が連続するものを含むデータ源の共通要素を抽出する場合に、無駄な比較判定処理を少なくすることができ、処理時間が増大するのを抑制することができる。
【００８７】
なお、本実施形態では、第１の比較演算子を“＜”、第２の比較演算子を“＞”、第３の比較演算子を“＝”とした場合について説明したが、図２９に示すように、第１の比較演算子を“≦”、第２の比較演算子を“≧”、第３の比較演算子を“≠”としてもよい。この場合、図２９に示すように、ステップ１０４、１０６、１１８、１２０の各比較判定の対象が図２８と逆になり、ステップ１０４、１０６、１１８、１２０、１３２の各比較判定結果に応じた分岐先が図２８と逆になる。
【００８８】
（第３実施形態）
【００８９】
次に開示の技術の第３実施形態について説明する。第３実施形態では、複数の共通要素抽出装置を多段接続した共通要素抽出装置について説明する。
【００９０】
図３０には、複数の共通要素抽出装置１０を多段接続した共通要素抽出装置５０を示した。同図では、一例として共通要素抽出装置１０を３段接続した例を示した。同図に示すように、共通要素抽出装置５０は、１段目の共通要素抽出装置には、データ源Ｄ１、Ｄ２の各要素が入力される。また、２段目の共通要素抽出装置１０には、１段目の共通要素抽出装置１０から出力されたデータ源Ｄ１、Ｄ２の共通要素（同一データ）と、データ源Ｄ３の要素が入力される。３段目の共通要素抽出装置１０には、２段目の共通要素抽出装置１０から出力されたデータ源Ｄ１〜Ｄ３の共通要素と、データ源Ｄ４の要素が入力される。
【００９１】
このように、共通要素抽出装置５０は、２段目以降の共通要素抽出装置１０に、前段の共通要素抽出装置１０から出力された同一要素と、データ源から出力された要素と、が入力されるように、複数の共通要素抽出装置１０を多段接続した構成となっている。このように、２段目以降の共通要素抽出装置１０の一方の入力には、前段の共通要素抽出装置１０から出力された同一要素が入力されるため、要素数が少ない。このため、２段目以降の共通要素抽出装置１０で比較するデータ源の要素数が偏るため、無駄な比較判定処理を更に少なくすることができ、処理時間が増大するのを更に抑制することができる。
【００９２】
また、図３１には、複数の共通要素抽出装置１０を多段接続した他の例を示した。同図に示す共通要素抽出装置５２は、１段目の一方の共通要素抽出装置１０には、データ源Ｄ１、Ｄ２の各要素が入力される。また、１段目の他方の共通要素抽出装置１０には、データ源Ｄ３、Ｄ４の各要素が入力される。また、２段目の共通要素抽出装置１０には、１段目の一方の共通要素抽出装置１０から出力されたデータ源Ｄ１、Ｄ２の共通要素と、１段目の他方の共通要素抽出装置１０から出力されたデータ源Ｄ３、Ｄ４の共通要素と、が入力される。
【００９３】
このように、共通要素抽出装置５２は、１段目に２つのデータ源からの各要素が入力される共通要素抽出装置１０が複数設けられている。そして、２段目の共通要素抽出装置１０に、前段の２つの共通要素抽出装置１０から各々出力された同一要素が各々入力されるように、複数の共通要素抽出装置１０を多段接続した構成となっている。
【００９４】
なお、上記では複数の共通要素抽出装置１０を多段接続する場合について説明したが、複数の共通要素抽出装置１０Ａを多段接続した構成としてもよい。また、共通要素抽出装置１０と共通要素抽出装置１０Ａが混在した構成としてもよい。
【００９５】
また、上記各実施形態では、データ源の各要素が昇順に整列済みの場合について説明したが、データ源の各要素が降順に整列済みであってもよい。また、一つのデータ源に同じ値の要素が含まれていても良い。
【００９６】
また、上記では開示の技術に係る共通要素抽出プログラムの一例である共通要素抽出プログラムが記憶部６６に予め記憶（インストール）されている態様を説明したが、これに限定されるものではない。開示の技術に係る画像処理プログラムは、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の記録媒体に記録されている形態で提供することも可能である。
【００９７】
本明細書に記載された全ての文献、特許出願及び技術規格は、個々の文献、特許出願及び技術規格が参照により取り込まれることが具体的かつ個々に記された場合と同程度に、本明細書中に参照により取り込まれる。
【００９８】
以上の実施形態に関し、更に以下の付記を開示する。
【００９９】
（付記１）
コンピュータが、
整列済みの複数の要素を含む第１のデータ源から読み出した第１の要素と、整列済みの複数の要素を含む第２のデータ源から読み出した第２の要素と、を第１の比較演算子及び前記第１の比較演算子と異なる第２の比較演算子により順次比較判定する第１の比較ステップと、
前記第１の要素と前記第２の要素とを前記第１の比較演算子及び前記第２の比較演算子により順次比較判定すると共に、前記第１の比較演算子及び前記第２の比較演算子による比較順序が前記第１の比較ステップと異なる第２の比較ステップと、
前記第１の比較ステップ及び前記第２の比較ステップの何れかにより前記第１の要素と前記第２の要素とが同一であると判定されなかった場合に、前記第１の比較ステップ及び前記第２の比較ステップの何れかが直前に実行した比較判定と同一の比較判定を先に行う比較ステップを前記第１の比較ステップ及び前記第２の比較ステップから選択する選択ステップと、
前記第１の比較ステップ及び前記第２の比較ステップの何れかにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、当該同一と判定された同一要素を出力する出力ステップと、
前記出力ステップが前記同一要素を出力した場合は、前記第１のデータ源及び前記第２のデータ源から次の要素を各々読み出すと共に、前記選択ステップにより前記第１の比較ステップ及び前記第２の比較ステップのうち一方の比較ステップが選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち一方のデータ源から次の要素を読み出し、前記選択ステップにより前記第１の比較ステップ及び前記第２の比較ステップのうち他方の比較ステップが選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち他方のデータ源から次の要素を読み出す読み出しステップと、
を含む処理を実行する共通要素抽出方法。
（付記２）
前記第１の要素と前記第２の要素とが同一であるか否か又は同一でないか否かを比較判定する第３の比較演算子と、前記第１の比較演算子及び前記第２の比較演算子のうち一方の比較演算子と、により前記第１の要素と前記第２の要素とを順次比較判定する第３の比較ステップをさらに備え、
前記選択ステップは、前記第３の比較ステップにより前記第１の要素と前記第２の要素とが同一であると判定されなかった場合に、前記第１の比較ステップ又は前記第２の比較ステップを選択すると共に、前記第３の比較ステップにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、前記第３の比較ステップを選択し、
前記出力ステップは、前記第１の比較ステップ、前記第２の比較ステップ、及び前記第３の比較ステップから選択された比較ステップにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、当該同一と判定された同一要素を出力する
付記１記載の共通要素抽出方法。
（付記３）
コンピュータに、
整列済みの複数の要素を含む第１のデータ源から読み出した第１の要素と、整列済みの複数の要素を含む第２のデータ源から読み出した第２の要素と、を第１の比較演算子及び前記第１の比較演算子と異なる第２の比較演算子により順次比較判定する第１の比較ステップと、
前記第１の要素と前記第２の要素とを前記第１の比較演算子及び前記第２の比較演算子により順次比較判定すると共に、前記第１の比較演算子及び前記第２の比較演算子による比較順序が前記第１の比較ステップと異なる第２の比較ステップと、
前記第１の比較ステップ及び前記第２の比較ステップの何れかにより前記第１の要素と前記第２の要素とが同一であると判定されなかった場合に、前記第１の比較ステップ及び前記第２の比較ステップの何れかが直前に実行した比較判定と同一の比較判定を先に行う比較ステップを前記第１の比較ステップ及び前記第２の比較ステップから選択する選択ステップと、
前記第１の比較ステップ及び前記第２の比較ステップの何れかにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、当該同一と判定された同一要素を出力する出力ステップと、
前記出力ステップが前記同一要素を出力した場合は、前記第１のデータ源及び前記第２のデータ源から次の要素を各々読み出すと共に、前記選択ステップにより前記第１の比較ステップ及び前記第２の比較ステップのうち一方の比較ステップが選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち一方のデータ源から次の要素を読み出し、前記選択ステップにより前記第１の比較ステップ及び前記第２の比較ステップのうち他方の比較ステップが選択された場合は、前記第１のデータ源及び前記第２のデータ源のうち他方のデータ源から次の要素を読み出す読み出しステップと、
を含む処理を実行させるための共通要素抽出プログラム。
（付記４）
前記第１の要素と前記第２の要素とが同一であるか否か又は同一でないか否かを比較判定する第３の比較演算子と、前記第１の比較演算子及び前記第２の比較演算子のうち一方の比較演算子と、により前記第１の要素と前記第２の要素とを順次比較判定する第３の比較ステップをさらに備え、
前記選択ステップは、前記第３の比較ステップにより前記第１の要素と前記第２の要素とが同一であると判定されなかった場合に、前記第１の比較ステップ又は前記第２の比較ステップを選択すると共に、前記第３の比較ステップにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、前記第３の比較ステップを選択し、
前記出力ステップは、前記第１の比較ステップ、前記第２の比較ステップ、及び前記第３の比較ステップから選択された比較ステップにより前記第１の要素と前記第２の要素とが同一であると判定された場合に、当該同一と判定された同一要素を出力する
付記３記載の共通要素抽出プログラム。
【実施例】
【０１００】
以下、開示の技術の効果を確認するために実施された実験の結果を説明する。この実験では、図３２に示すように、２つのデータ源の要素の出現の仕方が異なる５パターンについて、図３８に示す従来の共通要素抽出処理（従来）及び図３に示す共通要素抽出処理（開示の技術）を行い、１処理あたりの比較回数の期待値を求めた。
【０１０１】
まず、要素の出現が一様に密の２つのデータ源の場合（パターン１）、要素の出現が一様に疎の２つのデータ源の場合（パターン２）、従来及び開示の技術では期待値は変わらなかった。従って、従来に対する開示の技術の比較回数の比は１であった。
【０１０２】
また、要素の出現が非対称の２つのデータ源の場合（パターン３）、従来では、期待値が１又は２であり、開示の技術では期待値は１であった。従って、従来に対する開示の技術の比較回数の比は１又は０．５であった。
【０１０３】
また、連続した要素が交互に出現する２つのデータ源の場合（パターン４）、従来では、期待値が１．５であり、開示の技術では期待値は１であった。従って、従来に対する開示の技術の比較回数の比は０．６６であった。
【０１０４】
また、要素が交互に出現する２つのデータ源の場合（パターン５）、従来では、期待値が１．５であり、開示の技術では期待値は２であった。従って、従来に対する開示の技術の比較回数の比は１．３３であった。
【０１０５】
このように、パターン４が１処理あたりの比較回数の期待値が最も小さくなることが判った。
【０１０６】
また、図３３には、０以上で且つ１００万未満の整数からランダムに予め定めた個数の数字を選択して作成した整列済みのデータ源Ｘ、Ｙに対し、従来及び開示の技術の共通要素抽出処理を実行した場合における計算時間の結果を示した。なお、用いたデータ源Ｘ、Ｙは、図３４に示すように、データ源Ｙの要素数がデータ源Ｘの要素数よりも大きいデータ源である。また、データ源Ｘ、Ｙの何れかの要素数が１万以下の場合、計算時間が短いため、定数倍して表示している。同図では、データ源Ｘ、Ｙの要素数が共に１万の場合は１０倍（＊１）、データ源Ｘ、Ｙの要素数の一方が１万、他方が１００の場合は１００倍（＊２）、データ源Ｘ、Ｙの要素数が共に１００の場合は１００倍（＊３）している。
【０１０７】
図３３に示すように、データ源Ｙの要素数がデータ源Ｘの要素数よりも多い領域Ｒでは、開示の技術の方が従来よりも計算時間を大幅に短縮できることが判った。これは、データ源Ｙの要素数が多く、データ源Ｘの要素よりもデータ源Ｙの要素の方が小さい場合が多いため、図３のステップ１１８の比較処理が繰り返されるためである。
【０１０８】
また、図３５には、１から２００万までの数字が、図３６に示すように一定回数（ブロック長）毎に交互に出現する同一要素数のデータ源Ｘ、Ｙに対し、従来及び開示の技術の共通要素抽出処理を実行した場合における計算時間の結果を示した。また、図３７には、図３５のうち、ブロック長が１〜１０の場合の拡大図を示した。図３５に示すように、ブロック長が長くなるほど、開示の技術の方が従来と比較して計算時間が短くなるのが判る。このように、上記のパターン３やパターン４、特にパターン４の場合に、共通要素抽出処理の計算時間を従来と比較して大幅に短縮できることが判った。
【符号の説明】
【０１０９】
１０、１０Ａ、５０、５２      共通要素抽出装置
１０Ａ      共通要素抽出装置
１２  第１の比較部
１４  第２の比較部
１６  選択部
１８  出力部
２０  読み出し部
２２  第３の比較部
６０、６０Ａ      コンピュータ
６８、６８Ａ      共通要素抽出プログラム
【図１】
0005862418.tif 000002
【図２】
0005862418.tif 000003
【図３】
0005862418.tif 000004
【図４】
0005862418.tif 000005
【図５】
0005862418.tif 000006
【図６】
0005862418.tif 000007
【図７】
0005862418.tif 000008
【図８】
0005862418.tif 000009
【図９】
0005862418.tif 000010
【図１０】
0005862418.tif 000011
【図１１】
0005862418.tif 000012
【図１２】
0005862418.tif 000013
【図１３】
0005862418.tif 000014
【図１４】
0005862418.tif 000015
【図１５】
0005862418.tif 000016
【図１６】
0005862418.tif 000017
【図１７】
0005862418.tif 000018
【図１８】
0005862418.tif 000019
【図１９】
0005862418.tif 000020
【図２０】
0005862418.tif 000021
【図２１】
0005862418.tif 000022
【図２２】
0005862418.tif 000023
【図２３】
0005862418.tif 000024
【図２４】
0005862418.tif 000025
【図２５】
0005862418.tif 000026
【図２６】
0005862418.tif 000027
【図２７】
0005862418.tif 000028
【図２８】
0005862418.tif 000029
【図２９】
0005862418.tif 000030
【図３０】
0005862418.tif 000031
【図３１】
0005862418.tif 000032
【図３２】
0005862418.tif 000033
【図３３】
0005862418.tif 000034
【図３４】
0005862418.tif 000035
【図３５】
0005862418.tif 000036
【図３６】
0005862418.tif 000037
【図３７】
0005862418.tif 000038
【図３８】
0005862418.tif 000039
【図３９】
0005862418.tif 000040
【図４０】
0005862418.tif 000041