(57)【要約】【課題】データ配列１とデータ配列２のデータを比較する場合、データ配列１に含まれるデータ数が多くなるほど、比較を行う回数は多くなってしまうという問題があった。【解決手段】一致データ検出装置１００は、データ配列１のデータと一致するデータ配列２のデータを検出する装置であり、データ配列１は、複数の第１データから構成され、データ配列２は、複数の第２データから構成され、複数の第２データの最小値、複数の第２データの最大値、及びその他の第２データを含む。一致データ検出装置１００は、データ配列２から比較対象とする第２データを抽出する抽出部１１０と、最小値より小さい第１データと最大値よりを大きい第１データをデータ配列１から除外し、残りの第１データを、抽出部１１０がその他の第２データから抽出した第２データと比較して一致する第２データを出力する比較部１２０とを備える。【選択図】図１
2008197719.tif 000002
【特許請求の範囲】
【請求項１】
データ配列１及びデータ配列２を入力し、データ配列１のデータと一致するデータ配列２のデータを検出する一致データ検出装置であって、
前記データ配列１は、複数の第１データから構成され、
前記データ配列２は、複数の第２データから構成され、前記複数の第２データの最小値、前記複数の第２データの最大値、及びその他の第２データを含み、
前記データ配列２から比較対象とする第２データを抽出する抽出部と、
前記最小値より小さい第１データと前記最大値よりを大きい第１データを前記データ配列１から除外し、残りの第１データを、前記抽出部が前記その他の第２データから抽出した第２データと比較して一致する第２データを出力する比較部と、を備える一致データ検出装置。
【請求項２】
前記抽出部は、前記その他の第２データそれぞれを大きさに基づく順に前記比較部へ出力し、
前記比較部は、前記残りの第１データを大きさに基づく順に、前記抽出部が出力した第２データと比較し、比較結果に基づいて、比較対象とならない第１データを前記残りの第１データから除外し、続いて除外後の第１データを、前記比較部が出力する第２データと比較することを、前記除外後の第１データがなくなるまで繰り返すことを特徴とする請求項１記載の一致データ検出装置。
【請求項３】
前記データ配列１は、前記複数の第１データが昇順に配置された配列であり、
前記データ配列２は、配列の一番目に前記最小値、配列の二番目に前記最大値、配列の三番目以降にその他の第２データが昇順に配置された配列であり、
前記抽出部は、前記その他の第２データそれぞれを昇順に前記比較部へ出力し、
前記比較部は、前記残りの第１データを昇順に、前記抽出部が出力した第２データと比較し、前記第２データより小さい第１データを前記残りの第１データから除外し、続いて除外後の第１データを昇順に、前記比較部が出力する第２データと比較することを、前記除外後の第１データがなくなるまで繰り返すことを特徴とする請求項２記載の一致データ検出装置。
【請求項４】
前記データ配列２は、送信装置が各受信装置宛のＥＭＭ（Entitlement Management Messages：契約情報）を複数まとめて送信するＥＭＭセッションであり、
前記ＥＭＭセッションは、ＥＭＭの宛て先を識別するＣａｒｄＩＤを含み、前記ＣａｒｄＩＤが最小値のＥＭＭが一番目に配置され、前記ＣａｒｄＩＤが最大値のＥＭＭが二番目に配置され、ＣａｒｄＩＤが昇順になるようにその他のＥＭＭが三番目以降に配置されたＥＭＭの配列であり、
前記データ配列１は、自己を宛て先とするＣａｒｄＩＤが第１データとして昇順に配置された配列であり、
前記抽出部は、前記ＥＭＭからＣａｒｄＩＤを抽出して前記比較部へ出力し、
前記比較部は、前記データ配列１と、前記抽出部が出力したＣａｒｄＩＤとを比較し、一致したＣａｒｄＩＤを含むＥＭＭを出力することを特徴とする請求項１乃至３のいずれかに記載の一致データ検出装置。
【請求項５】
送信装置が各受信装置宛のＥＭＭを複数まとめて送信するＥＭＭセッションを受信する受信装置であって、
前記ＥＭＭセッションは、ＥＭＭの宛て先を識別するＣａｒｄＩＤを含み、前記ＣａｒｄＩＤが最小値のＥＭＭが一番目に配置され、前記ＣａｒｄＩＤが最大値のＥＭＭが二番目に配置され、ＣａｒｄＩＤが大きさに基づく順になるようにその他のＥＭＭが三番目以降に配置されたＥＭＭの配列であり、
前記ＥＭＭセッションを受信する受信部と、
自己宛のＥＭＭであることを示す複数の保持データを配置したデータ配列を保持する保持データ保持部と、
前記受信したＥＭＭの配列からＣａｒｄＩＤを抽出する抽出部と、
前記ＣａｒｄＩＤの最小値より小さい保持データと前記ＣａｒｄＩＤの最大値よりを大きい保持データを前記データ配列から除外し、残りのデータ配列を前記抽出部が出力したＣａｒｄＩＤと比較して一致するＣａｒｄＩＤを含むＥＭＭを出力する比較部と、を備えることを特徴とする受信装置。
【請求項６】
データ配列１及びデータ配列２を入力し、データ配列１のデータと一致するデータ配列２のデータを検出する一致データ検出方法であって、
前記データ配列１は、複数の第１データから構成され、
前記データ配列２は、複数の第２データから構成され、前記複数の第２データの最小値、前記複数の第２データの最大値、及びその他の第２データを含み、
前記データ配列２から比較対象とする第２データを抽出し、
前記最小値より小さい第１データと前記最大値よりを大きい第１データを前記データ配列１から除外し、
残りの第１データを前記抽出部が前記その他の第２データから抽出した第２データと比較して一致する第２データを出力する一致データ検出方法。
【請求項７】
データ配列１及びデータ配列２を入力し、データ配列１のデータと一致するデータ配列２のデータを検出する手順を計算機で実行させるための一致データ検出プログラムであって、
前記データ配列１は、複数の第１データから構成され、
前記データ配列２は、複数の第２データから構成され、前記複数の第２データの最小値、前記複数の第２データの最大値、及びその他の第２データを含み、
前記データ配列２から比較対象とする第２データを抽出する手順と、
前記最小値より小さい第１データと前記最大値よりを大きい第１データを前記データ配列１から除外する手順と、
残りの第１データを前記抽出部が前記その他の第２データから抽出した第２データと比較して一致する第２データを出力する手順と、を計算機上で実行させるための一致データ検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二つのデータ配列において、データ配列１に含まれるデータがもう一つのデータ配列２に含まれているかを検出する装置及び方法に関する。
【背景技術】
【０００２】
従来から、二つのデータ配列１、データ配列２を比較する処理では、データ配列１のうちのひとつのデータに対してデータ配列２の各データを比較する処理が行われていた。例えば、データ配列２が、１番目に最小値、２番目に最大値、３番目以降は残りのデータが昇順に配置されている配列の場合の処理について説明する。まず、データ配列１のデータひとつひとつに対してデータ配列２の先頭データと２番目のデータからデータ配列２に含まれている可能性があるかの判定を行い、可能性がない場合は次のデータ配列１のデータの判定を行う。これをデータ配列１のそれぞれのデータに対して行っていた。図１３から図１６に、従来の検出方法の具体例を示す。判定した結果、一致するデータが存在する可能性がある場合は、データ配列２の３番目以降のデータとデータ配列１のデータの比較を一つずつ行う(図１３、１４)。一致するデータが検出されるか、データ配列２のデータがデータ配列１のデータより大きくなると（図１５）、データ配列１の次のデータとの比較に進む。この動作を全てのデータ配列１のデータに対して行っていた（図１６）。
【０００３】
図１６の場合、データ配列１を昇順に比較していくことで前に比較していたデータ配列１のデータより現在比較しているデータ配列１のデータのほうが大きいこととなる。
そのため前のデータ配列１のデータよりも小さいデータ配列２のデータとは比較を行う必要がないのに比較しており処理時間、処理負荷がかかってしまっていた。具体的には、図１６の場合、データ配列２のデータ４１〜４９は、データ配列１の２番目のデータより小さく、データ配列１が昇順に並んでいる場合は、データ配列１の３番目のデータは、２番目のデータより大きいため、比較する必要がない。
【０００４】
また、図１３，１４に示すように、データ配列１のデータ一つ一つに対して範囲の確認（データ配列２の１番目の最小値と２番目の最大値との比較）を行っているため、範囲のチェックでもデータ配列１の要素数分は必ずチェックを行う必要が出てきてしまっていた。さらに、一般的に知られている２分検索法などの方法では、比較したいデータの位置が特定されている場合は有効であるが、特定されない場合には用いることが困難であった。例えば、特許文献１に開示されているＥＭＭ（Entitlement Management Messages：契約情報）のＣａｒｄＩＤ（カードＩＤ）の検索のような場合、比較したいＣａｒｄＩＤの位置を特定するためにはデータの先頭から解析する必要がある。図１７に、ＥＭＭのデータ内容の一例を示す。ＥＭＭのデータは、配列の数、要素の値を知るためには全てのデータを解析し、ＣａｒｄＩＤを抽出後に検索を行う必要がある。
【０００５】
このとき全てのデータを解析すると解析に時間がかかってしまい、先頭から解析しながら比較すると、データ配列１に含まれるデータの最大値より比較しているデータ配列２のデータが大きくなった場合に比較、解析を取りやめることができる。このため、２分検索法などの検索法を使用するとかえって余計に処理時間、処理負荷がかかってしまう恐れがある。また一度比較したいデータ（ＥＭＭの場合だとＣａｒｄＩＤ）を抜き出し保存するメモリが必要である。
【特許文献１】特開２００４−７８０９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
このように、データ配列１に含まれるデータがデータ配列２に含まれているデータと一致するかの判定を行う場合、データ配列１に含まれるデータ数が多くなるほど、比較を行う回数は多くなってしまうという問題があった。
【課題を解決するための手段】
【０００７】
本発明に係る一致データ検出装置の一態様は、データ配列１及びデータ配列２を入力し、データ配列１のデータと一致するデータ配列２のデータを検出する一致データ検出装置であって、前記データ配列１は、複数の第１データから構成され、前記データ配列２は、複数の第２データから構成され、前記複数の第２データの最小値、前記複数の第２データの最大値、及びその他の第２データを含み、前記データ配列２から比較対象とする第２データを抽出する抽出部と、前記最小値より小さい第１データと前記最大値よりを大きい第１データを前記データ配列１から除外し、残りの第１データを、前記抽出部が前記その他の第２データから抽出した第２データと比較して一致する第２データを出力する比較部と、を備える。
【０００８】
本発明に係る受信装置の一態様は、送信装置が各受信装置宛のＥＭＭを複数まとめて送信するＥＭＭセッションを受信する受信装置であって、前記ＥＭＭセッションは、ＥＭＭの宛て先を識別するＣａｒｄＩＤを含み、前記ＣａｒｄＩＤが最小値のＥＭＭが一番目に配置され、前記ＣａｒｄＩＤが最大値のＥＭＭが二番目に配置され、ＣａｒｄＩＤが大きさに基づく順になるようにその他のＥＭＭが三番目以降に配置されたＥＭＭの配列であり、前記ＥＭＭセッションを受信する受信部と、自己宛のＥＭＭであることを示す複数の保持データを配置したデータ配列を保持する保持データ保持部と、前記受信したＥＭＭの配列からＣａｒｄＩＤを抽出する抽出部と、前記ＣａｒｄＩＤの最小値より小さい保持データと前記ＣａｒｄＩＤの最大値よりを大きい保持データを前記データ配列から除外し、残りのデータ配列を前記抽出部が出力したＣａｒｄＩＤと比較して一致するＣａｒｄＩＤを含むＥＭＭを出力する比較部と、を備える。
【０００９】
本発明に係る一致データ検出方法の一態様は、データ配列１及びデータ配列２を入力し、データ配列１のデータと一致するデータ配列２のデータを検出する一致データ検出方法であって、前記データ配列１は、複数の第１データから構成され、前記データ配列２は、複数の第２データから構成され、前記複数の第２データの最小値、前記複数の第２データの最大値、及びその他の第２データを含み、前記データ配列２から比較対象とする第２データを抽出し、前記最小値より小さい第１データと前記最大値よりを大きい第１データを前記データ配列１から除外し、残りの第１データを前記抽出部が前記その他の第２データから抽出した第２データと比較して一致する第２データを出力する。
【００１０】
本発明に係る一致データ検出プログラムの一態様は、データ配列１及びデータ配列２を入力し、データ配列１のデータと一致するデータ配列２のデータを検出する手順を計算機で実行させるための一致データ検出プログラムであって、前記データ配列１は、複数の第１データから構成され、前記データ配列２は、複数の第２データから構成され、前記複数の第２データの最小値、前記複数の第２データの最大値、及びその他の第２データを含み、前記データ配列２から比較対象とする第２データを抽出する手順と、前記最小値より小さい第１データと前記最大値よりを大きい第１データを前記データ配列１から除外する手順と、残りの第１データを前記抽出部が前記その他の第２データから抽出した第２データと比較して一致する第２データを出力する手順と、を計算機上で実行させる。
【発明の効果】
【００１１】
本発明によれば、データ配列１に含まれるデータがデータ配列２に含まれているデータと一致するかの判定を行う場合、データ配列１に含まれるデータのうち判定に必要なデータの範囲をデータ配列２のデータに基づいて判断する。これにより、データ比較を行うデータ数を抑制することができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施形態について、図面を参照しながら説明する。説明の明確化のため、以下の記載及び図面は、適宜、省略、及び簡略化がなされている。各図面において同一の構成または機能を有する構成要素および相当部分には、同一の符号を付し、その説明は省略する。
【００１３】
実施形態１．
図１は、本発明に係る実施形態の一致データ検出装置の構成例を示すブロック図である。図１に示す一致データ検出装置１００は、データ配列１及びデータ配列２を入力し、データ配列１のデータと一致するデータ配列２のデータを検出する装置であり、抽出部（比較対象データ抽出手段）１１０と比較部（配列比較手段）１２０とを備える。
【００１４】
データ配列１は、複数の保持データ（複数の第１データ）から構成される。ここでは、データ配列１は、複数の保持データが昇順に配置されていることを前提とする。
データ配列２は、複数の比較データ（複数の第２データ）から構成され、複数の比較データの最小値、前記複数の比較データの最大値、及びその他の比較データを配置する配列である。ここでは、データ配列２は、配列の一番目に最小値、配列の二番目に最大値、配列の三番目以降にその他の比較データが昇順に配置された配列であることを前提とする。
【００１５】
抽出部１１０は、データ配列２から比較対象となる比較データを抽出する。
比較部１２０は、データ配列１とデータ配列２とのデータを比較し、一致するデータを出力する。比較部１２０は、昇順比較手段１２１と降順比較手段１２２とを含む。詳細な動作は後述する。
【００１６】
図２は、図１に示す一致データ検出装置が動作する環境の一例を示す図である。図２では、一致データ検出装置及び方法をプログラム（ここでは一致データ検出プログラム）で実現する場合を示し、プログラムが計算機上で動作する環境例を示している。ＣＰＵ（Central Processing Unit）５０１は、計算機全体を制御し、記憶媒体５０８に記憶するプログラムをメモリ５０２へダウンロードして実行させる。図２は、従って、プログラムをメモリ５０２へダウンロードした機能イメージ図でもある。データ配列１取得部５０３は、記憶媒体５０８の所定の領域に記憶（保持）するデータ配列１情報を取得し、メモリ５０２上で一致データ検出装置１００へ受け渡す。データ配列２は、外部からメモリ５０２へ入力される。データ配列１、データ配列２は、メモリ５０２へ一時的に記憶され、一致データ検出装置１００によって利用される。メモリ５０２は、例えばＲＡＭ（Random Access Memory）が用いられる。
【００１７】
ここで、本実施形態では、データ配列２は、配列の一番目に最小値、配列の二番目に最大値、配列の三番目以降にその他の比較データが昇順に配置された配列であることを前提としている。しかし、データの構成が不明な場合は、予めデータ配列２の構成を解析する必要がある。例えば、ＥＭＭのように、比較したいデータ位置が特定されていない場合はデータ配列２の解析が必要となる。解析に必要なプログラム（装置）は、記憶媒体５０８に保持し、ＣＰＵ５０１がメモリ５０２にダウンロードして、データ配列２を一致データ検出装置１００へ入力するときに解析する。また、データ配列１が昇順（降順）にソートされていない場合はあらかじめソートするためのソート用プログラム（例えば、保持データソート部）も必要となる。
【００１８】
続いて、一致データ検索装置の動作について説明する。図３〜図６は、本実施形態の一致データ検出装置１００の動作の一例を示すフローチャートである。図３は全体の動作、図４は比較データの最小値のとの比較、図５は比較データの最大値との比較、図６はその他の比較データとの比較を示している。データ配列１及びデータ配列２の取得方法等についてはここでは説明を省略する。また、図４〜図６中で「データ配列１」を「配列１」、「データ配列２」を「配列２」と記すことがある。
【００１９】
まず、全体の流れを説明する。一致データ検索装置１００は、データ配列（データ配列１、データ配列２）を入力する。データ配列１は比較部１２０へ、データ配列２は抽出部１１０へ入力される。データ配列１がソートされていない場合、比較部１２０は、昇順にソートを行う（Ｓ１１）。次に、一致データ検索装置１００は、データ配列２の最小値とデータ配列１のデータを比較する（Ｓ１２）。比較処理が終了した場合には（Ｓ１３でＹｅｓ）、比較部１２０は、比較結果を出力用のバッファへ出力する。比較処理が継続する場合（Ｓ１３でＮｏ）、一致データ検索装置１００は、データ配列２の最大値とデータ配列１のデータを比較する（Ｓ１４）。比較処理が終了した場合には（Ｓ１５でＹｅｓ）、比較部１２０は、比較結果を出力用のバッファへ出力する。
【００２０】
比較処理が継続する場合（Ｓ１５でＮｏ）、一致データ検索装置１００は、データ配列２のその他の比較データとデータ配列１のデータを比較する（Ｓ１６）。ステップＳ１４までの比較処理が終了した段階で、比較部１２０は、データ配列２の最小値より小さい保持データとデータ配列２の最大値よりを大きい保持データをデータ配列１から除外することになる。従って、比較部１２０は、ステップＳ１６の比較処理において、データ配列２の最小値より大きく、最大値より小さいデータ配列１の保持データについて、データ配列２の比較データと比較処理を実施する。比較処理終了後、比較部１２０は、比較処理結果を出力用バッファ（図１、２には図示していない）へ出力する。一致したデータがある場合は、一致したデータもしくは一致したデータを含むデータ配列２が出力され、一致したデータがなかった場合は、一致データなしを示すデータが出力される。
【００２１】
続いて、各比較処理の詳細な動作を説明する。まず、データ配列２の最小値との比較処理を、図４を用いて説明する。データ配列２の最小値との比較では、まず、抽出部１１０は、データ配列２の先頭の比較データ（比較データの最小値）を検索し、抽出する（Ｓ２１）。比較データの検索が必要ない場合（比較するデータの位置が特定できている場合、データが固定長の場合）は検索は行わなくてよい。すでに特定されている位置のデータを抽出する。比較部１２０（昇順比較手段１２１）は、抽出部１１０が抽出したデータ配列２の先頭の比較データ（データ配列２に含まれる最小の比較データ）とデータ配列１で比較対象となっているデータを先頭から昇順に比較する（Ｓ２２）。ここで比較対象となっているのは、データ配列１に含まれる複数の保持データとなる。比較した結果、一致した場合は（Ｓ２３でＹｅｓ）、比較部１２０は、その時点で比較処理を終了する（Ｓ２４）。比較部１２０は、一致したデータ配列２もしくは比較データを一致データ出力用メモリに出力する（Ｓ１７）。
【００２２】
比較した結果、一致しない場合（Ｓ２３でＮｏ）でかつデータ配列１のデータがデータ配列２の比較データより小さい場合は（Ｓ２５でＮｏ）、比較部１２０は、比較したデータ配列１の保持データを比較対象外とし、今回のデータ配列２との判定ではこれ以降比較しないように、データ配列１から除外する（Ｓ２６）。比較対象のデータ配列１がある場合（Ｓ２７でＹｅｓ）、ステップＳ２２へ戻り、データ配列１の比較対象を次の保持データへ順番に（昇順に）移し、比較処理を繰り返す。データ配列１に比較対象のデータがない場合（Ｓ２７でＮｏ）、一致データなしとして、比較処理を終了する（Ｓ２８）。また、比較した結果、一致しない場合（Ｓ２３でＮｏ）でかつデータ配列１のデータがデータ配列２の比較データより大きい場合は（Ｓ２５でＹｅｓ）、データ配列２に次の比較データがあるか確認し（Ｓ２９）、ある場合は（Ｓ２９でＹｅｓ）、比較部１２０は、次の比較処理へ移行（比較処理継続）するようにし（Ｓ３０）、ない場合は（Ｓ２９でＮｏ）、比較部１２０は、一致データなしとして、比較処理を終了する（Ｓ２８）。
【００２３】
次に、データ配列２の最大値との比較処理を、図５を用いて説明する。データ配列２の最大値との比較では、まず、抽出部１１０は、データ配列２の２番目の比較データ（比較データの最大値）を抽出する（Ｓ３１）。比較部１２０（降順比較手段１２２）は、抽出部１１０が抽出したデータ配列２の２番目（データ配列２に含まれる最大の比較データ）とデータ配列１で比較対象となっているデータを降順に比較する（Ｓ３２）。ここで比較対象となっているのは、データ配列２の最小値より小さい保持データをデータ配列１から除いた複数の保持データとなる。比較した結果、一致した場合は（Ｓ３３でＹｅｓ）、その時点でデータ比較処理を終了する（Ｓ３４）。比較部１２０は、一致したデータ配列２もしくは比較データを一致データ出力用メモリに出力する。
【００２４】
比較した結果、一致しない場合（Ｓ３３でＮｏ）でかつデータ配列１のデータがデータ配列２の比較データより大きい場合は（Ｓ３５でＮｏ）、比較部１２０は、比較したデータ配列１の保持データを比較対象外とし、今回の判定ではこれ以降比較しないように、データ配列１の保持データから除外する（Ｓ３６）。比較対象のデータ配列１がある場合（Ｓ３７でＹｅｓ），ステップＳ３２へ戻り、データ配列１の比較対象を次の保持データへ順番に（降順に）移し、比較処理を繰り返す。データ配列１に比較対象のデータがない場合（Ｓ３７でＮｏ）、一致データなしとして、比較処理を終了する（Ｓ３８）。比較した結果、一致しない場合（Ｓ３３でＮｏ）でかつデータ配列１のデータがデータ配列２の比較データより小さい場合は（Ｓ３５でＹｅｓ）、データ配列２に次の比較データがあるか確認し（Ｓ３９）、ある場合は（Ｓ３９でＹｅｓ）、比較部１２０は、次の比較処理へ移行（比較処理継続）するようにし（Ｓ４０）、ない場合は（Ｓ３９でＮｏ）、比較部１２０は、一致データなしとして、比較処理を終了する（Ｓ３８）。
【００２５】
次に、データ配列２のその他の比較データとの比較処理を、図６を用いて説明する。データ配列２の３番目以降のデータとの比較では、データ配列２の３番目以降のデータとデータ配列１のデータを昇順に比較していく。まず、抽出部１１０は、データ配列２の３番目の比較データを抽出する（Ｓ４１）。ここでは、データ配列２の３番目以降のデータは、昇順に配置されていることを前提としている。昇順になってない場合は、抽出部１１０において、データ配列２のその他の比較データを昇順に比較部１２０へ出力すればよい。比較部１２０（昇順比較手段１２１）は、抽出部１１０が抽出したデータ配列２の３番目とデータ配列１で比較対象となっているデータを昇順に比較する（Ｓ４２）。ここで比較対象となっているのは、データ配列２の最小値より小さい保持データと最大値より大きい保持データとをデータ配列１からを除いた複数の保持データとなる。比較した結果、一致した場合は（Ｓ４３でＹｅｓ）、その時点でデータ比較処理を終了する（Ｓ４４）。比較部１２０は、一致したデータ配列２もしくは比較データを一致データ出力用メモリに出力する。
【００２６】
比較した結果、一致しない場合（Ｓ４３でＮｏ）でかつデータ配列１のデータがデータ配列２の比較データより大きい場合は（Ｓ４５でＹｅｓ）、比較したデータ配列１の保持データを比較対象外とし、今回の判定ではこれ以降比較しないように、データ配列１保持データから除外する（Ｓ４６）。比較対象のデータ配列１がある場合（Ｓ４７でＹｅｓ），ステップＳ４２へ戻り、データ配列１の比較対象を次の保持データに順番に（昇順に）移し、比較処理を繰り返す。データ配列１に比較対象のデータがない場合（Ｓ４７でＮｏ）、一致データなしとして、比較処理を終了する（Ｓ４８）。比較した結果、一致しない場合（Ｓ４３でＮｏ）でかつデータ配列１のデータがデータ配列２の比較データより小さい場合は（Ｓ４５でＮｏ）、データ配列２に次の比較データがあるか確認し（Ｓ４９）、ある場合は（Ｓ４９でＹｅｓ）、ステップＳ４１へ戻る。抽出部１１０は、データ配列２の次の比較データの抽出を行い（Ｓ４１）、比較部１２０は、同様の比較処理を行う（Ｓ４２〜４５）。データ配列２の３番目以降のデータがなくなるまで、ステップＳ４９までの処理を比較データの昇順に繰り返す。ない場合は（Ｓ４９でＮｏ）、一致データなしとして、データ比較処理を終了する（Ｓ４８）。
【００２７】
以上の動作を具体的な値を用いて説明すると、まず図７のように、比較部１２０は、データ配列２の１番目のデータからデータ配列１からデータ配列２の最小値である４０以下のデータを比較対象外にし、データ配列２２番目のデータからデータ配列１からデータ配列２の最大値である７０以上のデータを比較対象外にする（図４のＳ２３からＳ２６及び図５のＳ３２からＳ３６の処理に相当）。次に図８のように、比較部１２０は、データ配列１の比較対象である保持データを昇順に比較していくため、まず５０をデータ配列２の３番目以降と比較していく（図６のＳ４２、４３、４５）。
【００２８】
このとき比較部１２０は、データ配列２の値が５０を超えるまではデータ配列２のデータの抽出を行い比較していき、５１となった時点でこれ以降５０はないので対象外とし（Ｓ４６）、次のデータ配列１のデータ（６０）へと比較対象を移し（Ｓ４７，４２）、データ配列２の５１からまた比較を行っていく（図９）（図６のＳ４５、４９、４１、４２、４３と繰り返す）。
【００２９】
これを繰り返し、図１０のように一致した場合、比較部１２０はデータを出力し、どれにも一致せずに全てのデータ配列１が対象外になるか、データ配列２が最後のデータまで行った場合は一致するデータなしとして、二つの配列のデータの比較処理を終了する。
【００３０】
上記説明したように、従来の技術ではデータ配列１を個別に考えて比較を行っていたため不要な部分の比較が発生していたが、本実施形態ではデータ配列１を昇順に比較していき、前に比較対象としていたデータ未満のデータ配列２のデータとは比較を行わないことで、不要な比較を行わないようになっている。
【００３１】
また、データ配列２の１番目（比較データの最小値）、２番目（比較データの最大値）から、データ配列１の保持データがデータ配列２に含まれるか判定する際にデータ配列を昇順（もしくは降順）に並べておくことで、一つ一つ判定していくのではなくデータ配列１全体で可能性のチェックを行い、データ配列２の１番目以上となったデータ配列１の保持データとデータ配列２の２番目以下となったデータ配列１の保持データの間にある数は全てデータ配列２に含まれる可能性があると判定することができる。従って、一つ一つ判定していくよりも処理が少なくてすむ。
【００３２】
さらに、比較していく際に比較対象とするデータ配列２のデータは先頭から取得していくため２分探索法のようにあらかじめ全てのデータを解析する必要がない。例えばデータ配列２の途中でそれ以降のデータを見る必要がなくなった場合にそれ以降のデータを抽出するための無駄な解析を行う必要がない。
【００３３】
また、本実施形態の方法ではデータ配列２のデータは１度次のデータへと比較の対象を移すとそれ以降今まで比較していたデータ配列２のデータは今後比較する必要はなくなるため２分探索法のように保存しておく必要がない。
以上説明したように、本実施形態によれば、比較対象とするデータ配列１のデータ数を抑制することができる。
【００３４】
実施形態２．
実施形態２では、実施形態１で説明した一致データ検出装置１００を、ＥＭＭの受信装置に適用する一態様を説明する。ＥＭＭの受信装置は、送信装置が各受信装置宛のＥＭＭを複数まとめて送信するＥＭＭセッションを受信する。ＥＭＭセッションは、ＥＭＭの宛て先を識別するＣａｒｄＩＤ（宛て先データ）を含む。ここでは、ＥＭＭセッションは、ＣａｒｄＩＤが最小値のＥＭＭが一番目に配置され、前記ＣａｒｄＩＤが最大値のＥＭＭが二番目に配置され、ＣａｒｄＩＤが大きさに基づく順になるようにその他のＥＭＭが三番目以降に配置されたＥＭＭの配列であることを前提とする。図１１は、ＥＭＭ受信器の構成例を示すブロック図である。ＥＭＭの受信装置では放送されたデータは図１１のような経路をたどる。
【００３５】
図１１に示す例では、一致データ検索装置１００はＥＭＭ解析部６０４に含まれる。図１２にＥＭＭ解析部及びＥＭＭ解析部が動作する環境の一例を示す。図１２では、Ｂ−ＣＡＳカードデータ取得部７０３、ＣａｒｄＩＤ照会プログラム７０６、ＣａｒｄＩＤソートプログラム７０７及び自己ＣａｒｄＩＤ情報７０８がＥＭＭ解析部６０４に含まれる構成となる。図１２は図２と同様に、一致データ検索装置及び方法をＣａｒｄＩＤ照会プログラムで実現する場合を示し、プログラムが計算機上で動作する環境例を示している。ＣａｒｄＩＤ照会プログラムは、図２に示す一致データ検出プログラムに相当し、同様の機能を有する。ＣＰＵ７０１は、記憶媒体７０９に記憶するプログラム（ＣａｒｄＩＤ照会プログラム７０６、ＣａｒｄＩＤソートプログラム７０７）をメモリ７０２へダウンロードして実行させる。ＣａｒｄＩＤ照会プログラムの構成は、図２で示した一致データ検出装置１００と同様である。
【００３６】
図１１、１２を用いてＥＭＭセッションを受信するときの受信装置６００の動作を説明する。放送されたストリームデータは放送受信部６０１で受信し、そのデータをフィルタリング部６０２でフィルタリングし、ＥＭＭセクションの取得を行う。取得されたＥＭＭセクションは、ＥＭＭセクションバッファ６０３に出力される。また、ＥＭＭセクションはセクションバッファ６０３からＥＭＭ解析部６０４へ出力される。ＥＭＭ解析部６０４では、あらかじめ、Ｂ−ＣＡＳカードデータ取得部７０３が自己ＣａｒｄＩＤをＢ−ＣＡＳカード６０５から取得する。ＣａｒｄＩＤソートプログラム７０７は、取得した自己ＣａｒｄＩＤを昇順（降順）にソートし、記憶媒体７０９の自己ＣａｒｄＩＤ情報７０８の領域に保存する。ＣａｒｄＩＤ照会プログラムは、保存していた自己ＣａｒｄＩＤとＥＭＭ解析部６０４に入力されてきたＥＭＭセクションを解析する。
【００３７】
ＣａｒｄＩＤ照会プログラムの構成は、図２で示した一致データ検出装置と同様であり、図２の抽出部１１０と比較部１２０が処理を実施する。自己ＣａｒｄＩＤは、データ配列１の保持データに相当する。また、ＥＭＭから抽出した自己ＣａｒｄＩＤは、データ配列２の比較データに相当する。また、解析の具体的な動作は、実施形態１で説明した一致データ検索装置の動作と同様である。ＣａｒｄＩＤ照会プログラムの構成は、図２で示した一致データ検出装置と同様であり、図２の抽出部１１０と比較部１２０が処理を実施する。自己ＣａｒｄＩＤは、データ配列１の保持データに相当する。また、ＥＭＭから抽出した自己ＣａｒｄＩＤは、データ配列２の比較データに相当する。
【００３８】
具体的には、ＣａｒｄＩＤ照会プログラムにおいて、抽出部１１０は、ＥＭＭセッションを解析して、ＣａｒｄＩＤを抽出する。比較部１２０は、抽出したＥＭＭセクションのＥＭＭに含まれるＣａｒｄＩＤと、自己ＣａｒｄＩＤとを比較する。比較部１２０は、比較した結果ＥＭＭセクション内に自己ＣａｒｄＩＤと一致するＣａｒｄＩＤが含まれていた場合は一致したＥＭＭもしくはＥＭＭセクションをＩＤ一致ＥＭＭセクション出力バッファ６０６に出力する。
【００３９】
このように、本発明の好適な実施形態によれば、一致データ検出装置において、次のような機能を実現することができる。（１）比較対象データの範囲のチェックをデータ配列１のデータ全体で行うようにする。（２）データ配列２の３番目以降との比較時に前のデータ配列１の比較対象のデータ未満のデータ配列２のデータとは比較しないようにする。（３）データ配列１のデータが全て対象外になったらそれ以降のデータ配列２の解析は行わないようにする。これにより、比較対象となるデータ数を抑制することにより、処理負荷を抑えること、あるいは、処理時間を短縮することができる。また、２分探索法と比べた場合は無駄なメモリの使用も抑えることができる。
【００４０】
なお、上記各実施形態ではデータ配列１、データ配列２の一部分は昇順にソートされている場合を前提として説明したが、降順にソートされている場合であっても、同様の処理が可能である。従って、データの値が大きい順または小さい順のいずれかの順番（大きさに基づく順）でソートされていれば、本発明を適用することは可能である。すなわち、比較部１２０は、抽出部１１０が出力した比較データと比較し、比較結果に基づいて、比較の対象とならない保持データを除外する。
【００４１】
また、上記各実施形態では、一致データ検出装置は、プログラムによって実現する場合を説明したが、これに限られるわけではなく、ハードウェア、あるいはハードウェアとソフトウェアとの組み合わせなどであってもよい。
【００４２】
さらに、本発明は上記に示す実施形態に限定されるものではない。本発明の範囲において、上記実施形態の各要素を、当業者であれば容易に考えうる内容に変更、追加、変換することが可能である。
【図面の簡単な説明】
【００４３】
【図１】本発明に係る実施形態の一致データ検出装置の構成例を示すブロック図である。
【図２】図１に示す一致データ検出装置が動作する環境の一例を示す図である。
【図３】実施形態１の一致データ検出装置の動作（全体）の一例を示すフローチャートである。
【図４】実施形態１の一致データ検出装置の動作（最小値との比較）の一例を示すフローチャートである。
【図５】実施形態１の一致データ検出装置の動作（最大値との比較）の一例を示すフローチャートである。
【図６】実施形態１の一致データ検出装置の動作（その他の比較データとの比較）の一例を示すフローチャートである。
【図７】実施形態１の検索方法の具体例を示す１番目の図である。
【図８】実施形態１の検索方法の具体例を示す２番目の図である。
【図９】実施形態１の検索方法の具体例を示す３番目の図である。
【図１０】実施形態１の検索方法の具体例を示す４番目の図である。
【図１１】ＥＭＭ受信器の構成例を示すブロック図である。
【図１２】ＥＭＭ解析部及びＥＭＭ解析部が動作する環境の一例を示す。
【図１３】従来の検索方法の具体例を示す１番目の図である。
【図１４】従来の検索方法の具体例を示す２番目の図である。
【図１５】従来の検索方法の具体例を示す３番目の図である。
【図１６】従来の検索方法の具体例を示す４番目の図である。
【図１７】ＥＭＭのデータ内容の一例を示す図である。
【符号の説明】
【００４４】
１００    一致データ検出装置
１１０    抽出部
１２０    比較部
１２１    昇順比較手段
１２２    降順比較手段
５０２    メモリ
５０３    データ配列１取得部
５０８    記憶媒体
６００    受信装置
６０１    放送受信部
６０２    フィルタリング部
６０３    セクションバッファ
６０４    解析部
６０５    カード
６０６    セクション出力バッファ
６０７    マスター鍵
６０８    ＥＣＭ復号
６０９    ワーク鍵
６１０    デスクランブル
６１１    視聴判定
６１２    契約情報
７０２    メモリ
７０３    カードデータ取得部
７０６    ＣａｒｄＩＤ照会プログラム
７０７    ＣａｒｄＩＤソートプログラム
７０８    自己ＣａｒｄＩＤ情報
７０９    記憶媒体
【図１】
2008197719.tif 000003
【図２】
2008197719.tif 000004
【図３】
2008197719.tif 000005
【図４】
2008197719.tif 000006
【図５】
2008197719.tif 000007
【図６】
2008197719.tif 000008
【図７】
2008197719.tif 000009
【図８】
2008197719.tif 000010
【図９】
2008197719.tif 000011
【図１０】
2008197719.tif 000012
【図１１】
2008197719.tif 000013
【図１２】
2008197719.tif 000014
【図１３】
2008197719.tif 000015
【図１４】
2008197719.tif 000016
【図１５】
2008197719.tif 000017
【図１６】
2008197719.tif 000018
【図１７】
2008197719.tif 000019