(57)【要約】【課題】データを構成するブロックごとの詳細な比較を速やかに行なうことを目的とする。【解決手段】少なくとも１つ以上のブロックからなる第１のデータと、少なくとも１つ以上のブロックからなる第２のデータと、を比較するデータ比較装置であって、第１のデータを構成する各ブロックの第１のハッシュデータ系列と、第２のデータを構成する各ブロックの第２のハッシュデータ系列と、を記憶する記憶手段と、記憶手段に記憶されている、第１のデータを構成する各ブロックの第１のハッシュデータ系列と、第２のデータを構成する各ブロックの第２のハッシュデータ系列と、をＤＰマッチングによって比較する比較手段を有することによって課題を解決する。【選択図】図５
2007280254.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つ以上のブロックからなる第１のデータと、少なくとも１つ以上のブロックからなる第２のデータと、を比較するデータ比較装置であって、
前記第１のデータを構成する各ブロックの第１のハッシュデータ系列と、前記第２のデータを構成する各ブロックの第２のハッシュデータ系列と、を記憶する記憶手段と、
前記記憶手段に記憶されている、前記第１のデータを構成する各ブロックの第１のハッシュデータ系列と、前記第２のデータを構成する各ブロックの第２のハッシュデータ系列と、をＤＰマッチングによって比較する比較手段を有することを特徴とするデータ比較装置。
【請求項２】
データを構成するブロックから一方向性関数を用いてハッシュ値のデータ系列を求めるデータ系列算出手段を更に有し、
前記比較手段は、前記データ系列算出手段において算出され、前記記憶手段に記憶された、前記第１のハッシュデータ系列と、前記第２のハッシュデータ系列と、をＤＰマッチングによって比較することを特徴とする請求項１に記載のデータ比較装置。
【請求項３】
前記記憶手段は、前記第１のデータと、前記第１のハッシュデータ系列とを、及び前記第２のデータと、前記第２のハッシュデータ系列とを、それぞれ関連付けて記憶することを特徴とする請求項１又は２に記載のデータ比較装置。
【請求項４】
少なくとも１つ以上のブロックからなる第１のデータと、少なくとも１つ以上のブロックからなる第２のデータと、を比較するデータ比較装置におけるデータ比較方法であって、
前記第１のデータを構成する各ブロックの第１のハッシュデータ系列と、前記第２のデータを構成する各ブロックの第２のハッシュデータ系列と、をＤＰマッチングによって比較する比較ステップを有することを特徴とするデータ比較方法。
【請求項５】
請求項４に記載のデータ比較方法をコンピュータに実行させることを特徴とするプログラム。
【請求項６】
請求項５に記載のプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ比較装置及びデータ比較方法に関する。
【背景技術】
【０００２】
例えば、ＭＳ−ＤＯＳ（登録商標）のオペレーティングシステムにおいては、ファイル比較コマンドのＦＣコマンドを実行させることによって、２つのデータが一致するか否かを確認することができる。
【０００３】
しかし、ＦＣコマンドによっては、２つのファイル（データ）が、どのくらい一致しているかは確認することができない。第１のデータが、Ａ、Ｂ、Ｃ、Ｄの４つのブロックに別れ、第２のデータが、Ａ、Ｂ、Ｃ、Ｘ、Ｄの５つのブロックに別れているデータの比較を考えてみる。ＦＣコマンドでは、両者のデータのＡ、Ｂ、Ｃ、Ｄのブロックが一致し、第２のデータのＣのブロックと、Ｄのブロックと、の間にＸなるブロックが挿入されていることを発見することはできない。
【０００４】
一方、Ｖｉｓｕａｌ  Ｓｔｕｄｉｏ（登録商標）に付属のＷｉｎｄｉｆｆによれば、Ａ、Ｂ、Ｃ、Ｄのブロックの一致を確認でき、Ｘのブロックが、Ｃのブロックと、Ｄのブロックとの間に追加されていることを発見することができる。
【０００５】
また、特許文献１には、パターン認識における類似度を求める技術が開示されている。
【０００６】
【特許文献１】特開平４−３２３６９８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
Ｗｉｎｄｉｆｆによれば長さのことなる一般のデータ比較をブロックごとの一致まで検査できるが、このようなＤＰマッチングではデータ量が大きくなると処理時間が極めて長くなる問題があった。ここで、ＤＰマッチングとは、Ｄｙｎａｍｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ（動的計画法）によるマッチング手法のことである。
【０００８】
近年、デジタル技術の発展により、デジタルテレビジョンの放送が開始され、また、ＤＬＮＡ等のホームネットワークの標準化に適合したオーディオ・ビジュアルのネットワーク対応製品が販売されるようになった。ここで、ＤＬＮＡとは、Ｄｉｇｉｔａｌ  ｌｉｖｉｎｇ  Ｎｅｔｗｏｒｋ  Ａｌｌｉａｎｃｅの略である。これらのホームネットワークでは、デジタルテレビ等の大きな動画データが家庭内に蓄積され、コピー、編集等が行われるようになってくる。そうすると、類似の動画データが増え、これらを整理し、不要なデータは削除する必要が生じる。そのためには、大きな動画データ同士の類似度を速やかに求める技術が必要となる。
【０００９】
本発明はこのような問題点又は要求に鑑みなされたもので、データを構成するブロックごとの詳細な比較を速やかに行なうことを目的とする。
【課題を解決するための手段】
【００１０】
そこで、前記問題を解決するため、本発明は、少なくとも１つ以上のブロックからなる第１のデータと、少なくとも１つ以上のブロックからなる第２のデータと、を比較するデータ比較装置であって、前記第１のデータを構成する各ブロックの第１のハッシュデータ系列と、前記第２のデータを構成する各ブロックの第２のハッシュデータ系列と、を記憶する記憶手段と、前記記憶手段に記憶されている、前記第１のデータを構成する各ブロックの第１のハッシュデータ系列と、前記第２のデータを構成する各ブロックの第２のハッシュデータ系列と、をＤＰマッチングによって比較する比較手段を有することを特徴とする。
【００１１】
係る構成とすることにより、データを構成するブロックごとの詳細な比較を速やかに行なうことができる。なお、記憶手段とは、例えば、後述するＨＤＤ４０６等に対応する。
【００１２】
また、前記問題を解決するため、本発明は、データ比較方法、プログラム及び記憶媒体としてもよい。
【発明の効果】
【００１３】
本発明によれば、データを構成するブロックごとの詳細な比較を速やかに行なうことができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施形態について図面に基づいて説明する。
【００１５】
ＭＰＥＧ１のデータ構造は、フレームの集合であり、可変長ブロック構造となっている。ここで、ＭＰＥＧ１は、Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ１の略である。ＭＰＥＧ１に限らずマルチメディアデータは、全て可変長ブロック構造となっている。図１は、マルチメディアデータのデータ構造の一例を示す図である。図１のマルチメディアデータは、ブロックの集合であり、各ブロックはブロック長と、ブロックデータと、からなっている。但し、ブロックデータの長さが所定の約束で決まっている場合は、ブロック長のフィールドは必ずしも必要ではない。
【００１６】
データ比較装置は、ハッシュデータ作成部を備えており、各ブロックデータから、ＭＤ５等の一方向性ハッシュ関数により、１２８ビット（＝１６バイト）のハッシュ値を作成し、図２に示すようなブロックの順序と等しく並べたハッシュデータを作る。図２は、ハッシュデータの一例を示す図である。
【００１７】
データ比較装置は、図２に示されるハッシュデータを、図１のマルチメディアデータの本体データの先頭に接続して、図３のようにハッシュ付データを作成する。図３は、ハッシュ付きデータの一例を示す図である。
【００１８】
但し、データ比較装置は、ハッシュデータを、本体データと合体させる必要はなく、本体データと対応付ける対応テーブルを別途用意して、本体データとは別にハッシュデータを管理するようにしてもよい。但し、以下では説明の簡略化のため、データ比較装置は、マルチメディアデータを、ハッシュ付データに変換して管理するものとして説明を行なう。但し、このことは本発明の実施を制限するものではない。
【００１９】
図４は、データ比較装置の一例のハードウェア構成図である。４０１は、データやアドレス信号を伝えるバスである。４０２は、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。４０３は、ＢＩＯＳ等の基本的なプログラムやデータを記憶するＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）である。４０４は、プログラムの作業領域としてＣＰＵ４０２に利用されるＲＡＭ（Ｒａｎｄａｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。４０５は、ハードディスク装置を制御するＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）コントローラである。
【００２０】
４０６は、データやオペレーティングシステム、データ比較プログラムを記憶するＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。４０７は、データ比較装置をＤＴＶ（Ｄｉｇｉｔａｌ  Ｔｅｌｅｖｉｓｉｏｎ）と接続するためのＤＴＶインターフェースである。４０８は、データ比較装置をホームネットワークと接続するためのＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。
【００２１】
データ比較装置は、ＤＴＶインターフェース４０７によってＤＴＶと接続されており、ＤＴＶで受信した番組をＭＰＥＧ２の形式で、ハードディスク装置４０６に記憶させることができる。また、データ比較装置は、ＮＩＣ４０８によって、ＴＣＰ／ＩＰを用いてホームネットワークと接続されている。このホームネットワークには、ＤＬＮＡの標準仕様に準拠した他のＡＶ（オーディオ／ビジュアル）機器が接続されており、これらのＡＶ機器によりＨＤＤ４０６に記憶された番組等のコンテンツを再生することができるようになっている。
【００２２】
つまり、データ比較装置には、ＮＩＣ４０８を介して、他のＡＶ機器から色々なマルチメディアデータのコンテンツを転送され、記憶される。いわば、データ比較装置は、コンテンツの記憶保管サーバとしての役割を担う。
【００２３】
ＮＩＣ４０８を介してデータ比較装置が受信したコンテンツは、図１の形式をしている。データ比較装置は、ブロックごとにＭＤ５等の一方向性関数を用いて１２８ビットのハッシュ値を作成し、図２に示すようなハッシュデータを作成する。そして、データ比較装置は、図３に示すようなハッシュ付データを作成し、ＨＤＤ４０６内に記憶し、管理する。
【００２４】
データ比較装置は、ＨＤＤ４０６の利用効率を上げるために、類似のデータは、１つだけ残し、余分な類似データを削除する。そのためには、マルチメディアデータの類似度を比較するデータ比較機能が必要となる。データ比較装置は、このデータ比較機能に対応するデータ比較プログラムをＨＤＤ４０６に保持している。
【００２５】
ホームネットワークに接続されているＡＶ機器は、ＨＤＤ４０６内に記憶されてあるコンテンツのリストを表示させることができる。ＡＶ機器を利用するユーザは、リスト内の任意の２つのコンテンツを指定し、データ比較の指示をリモコン等において行う。すると、その指示コマンドがＮＩＣ４０８を介してＣＰＵ４０２に伝わり、指定された２つのコンテンツのデータ比較が、データ比較プログラム（又はＣＰＵ４０２がデータ比較プログラムを実行すること）によってなされ、類似度が計算される。なお、以下では説明の簡略化のため、ＣＰＵ４０２ではなく、データ比較プログラムが処理を行うものとして説明を行なう。
【００２６】
データ比較プログラムにおいて計算された類似度は、ＮＩＣ４０８を介して、ＡＶ機器に伝送され、表示出力される。データ比較プログラムは、ＤＰマッチングの方法を用いたハッシュデータの比較を行うことによって、ハッシュ付データの形式で保管されている２つのコンテンツを比較する（後述する図５等参照）。データ比較プログラムが、ハッシュデータの比較を行なうことにより、コンテンツ本体データの各ブロックの比較がなされ、コンテンツ本体データの類似度が求まる。コンテンツＡと、コンテンツＢと、の比較において、一致したブロックの個数をＮ、一致しなかったコンテンツＡのブロック数をＮＡ個、一致しなかったコンテンツＢのブロック数をＮＢ個とする。すると、データ比較プログラムは、類似度を、２Ｎ×１００／（２Ｎ＋ＮＡ＋ＮＢ）として計算する。
【００２７】
図５は、ＤＰマッチングによる比較処理の一例を示すフローチャートである。図５において、ＡＨは、コンテンツＡのハッシュデータであり、ＢＨは、コンテンツＢのハッシュデータである。以下の説明において、ｉは、ハッシュデータＡＨを位置付けするカウンター、ｊは、ハッシュデータＢＨを位置付けするカウンターである。
【００２８】
ここで、図６は、データＸと、データＹと、をＤＰマッチングして比較した結果の一例を示す図である。図の斜線で示したブロックＸ１、Ｘ３、Ｘ５、Ｘ７と、ブロックＹ１、Ｙ３、Ｙ５、Ｙ７と、がそれぞれ一致している。各ブロックは、一致しているハッシュ値の連続となっている。
【００２９】
ステップ５０１において、データ比較プログラムは、カウンターｉと、ｊと、をゼロクリアする。ステップ５０２において、データ比較プログラムは、ＤＰマッチングのループ処理の開始にあたり、比較すべきデータが、残っていないか否かを判定する。データ比較プログラムは、前回一致したブロックの最終位置がデータサイズを超えてないか否かで、比較すべきデータが、残っていないか否かを判定する。データ比較プログラムは、比較すべきデータが残っていないと判定すると、ステップ５０７に進み、比較すべきデータが残っていると判定すると、ステップ５０３に進む。
【００３０】
ステップ５０３において、データ比較プログラムは、カウンターｉから開始するＡＨのハッシュ値系列と、最長に一致するＢＨのハッシュ値系列と、の検索を、カウンターｊから開始する。なお、この検索は、カウンターｉが初期値から、初期値＋所定値ＭＡＸＧＡＰになるまで行う。ここで、所定値ＭＡＸＧＡＰは、図６の不一致ブロックＸ２、Ｘ４、Ｘ６、Ｘ８、Ｙ２、Ｙ４、Ｙ６、Ｙ８の理論上の最大値であって、所定値ＭＡＸＧＡＰの長さ以内に最長一致が必ず見つかるはずと、考えられる数値である。ＭＡＸＧＡＰは、例えば、予め定められていてもよいし、データ比較プログラムが、比較するデータからその値を算出し、設定するようにしてもよい。
【００３１】
ステップ５０４において、データ比較プログラムは、ステップ５０３で見つかった最長一致ブロックの長さが所定値ＭＩＮＳＥＧ以上かどうかを判定する。ここで、所定値ＭＩＮＳＥＧというのは、この数値の長さ以上の一致したブロックでないと一致とはみなさないという最小値である。ＭＩＮＳＥＧは、例えば、予め定められていてもよいし、データ比較プログラムが、比較するデータからその値を算出し、設定するようにしてもよい。
【００３２】
データ比較プログラムは、最長一致の長さが所定値ＭＩＮＳＥＧよりも小さいと判定すると、カウンターｊにＢＨのデータサイズを設定してステップ５０２に戻る。一方、データ比較プログラムは、最長一致の長さが所定値ＭＩＮＳＥＧ以上であると判定すると、ステップ５０５に進む。
【００３３】
ステップ５０５において、データ比較プログラムは、一致したブロックの位置と、長さと、をブロックテーブルに登録する。続いて、ステップ５０６において、データ比較プログラムは、カウンターｊを最長一致の長さ分だけ増分して、ステップ５０２に戻る。
ステップ５０７において、データ比較プログラムは、登録されたブロックの情報（位置と、長さと）を出力する。このようにして、図６のような比較結果を生じさせるＤＰマッチングによるハッシュ値の比較が可能となる。図７、８、９に、データ比較プログラムをＣ言語でコーディングした例を示す。
【００３４】
以上、本実施形態によれば、データを構成するブロックごとの詳細な比較を速やかに行なうことができる。ブロック長の平均の大きさを１ｋバイトとすれば、比較すべきハッシュ値は１２８ビット＝１６バイトである。したがって、本実施形態によれば比較するデータが１６÷１０００＝約２％に減るので、マルチメディデータ本体をそのまま比較するよりも処理時間が例えば５０分の１以下になる。
【００３５】
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【図面の簡単な説明】
【００３６】
【図１】マルチメディアデータのデータ構造の一例を示す図である。
【図２】ハッシュデータの一例を示す図である。
【図３】ハッシュ付きデータの一例を示す図である。
【図４】データ比較装置の一例のハードウェア構成図である。
【図５】ＤＰマッチングによる比較処理の一例を示すフローチャートである。
【図６】データＸと、データＹと、をＤＰマッチングして比較した結果の一例を示す図である。
【図７】データ比較プログラムをＣ言語でコーディングした一例を示す図（その１）である。
【図８】データ比較プログラムをＣ言語でコーディングした一例を示す図（その２）である。
【図９】データ比較プログラムをＣ言語でコーディングした一例を示す図（その３）である。
【符号の説明】
【００３７】
４０１  バス
４０２  ＣＰＵ
４０３  ＲＯＭ
４０４  ＲＡＭ
４０５  ＨＤＤコントローラ
４０６  ＨＤＤ
４０７  ＤＴＶ  Ｉ／Ｆ
４０８  ＮＩＣ
【図１】
2007280254.tif 000003
【図２】
2007280254.tif 000004
【図３】
2007280254.tif 000005
【図４】
2007280254.tif 000006
【図５】
2007280254.tif 000007
【図６】
2007280254.tif 000008
【図７】
2007280254.tif 000009
【図８】
2007280254.tif 000010
【図９】
2007280254.tif 000011