質問: バイナリデータの類似性の計算 私はここでファイルの類似性を決定することに関していくつかの質問を見ました、しかしそれらはすべて特定のドメイン(画像、音、テキストなど)にリンクされています。 解決策として提供される技術は、比較されるファイルの基礎となるファイルフォーマットの知識を必要とします。 私が探しているのは、この要件を持たない方法で、そこに含まれるデータの種類を理解する必要なしに任意のバイナリファイルを比較することができます。 つまり、私は、2つのファイルのバイナリデータの類似率を求めています。 あなたが取り組むためのもう少し詳細を与えるために、これは多くのことに潜在的に適用可能ですが、私は私が取り組んでいるという特定の問題を抱えています。 私は現在実用的な解決策も持っていますが、それが理想的だとは思いません。 比較方法と結果の保存に関しては、おそらく多くの最適化があります。 うまくいけば、ここの何人かの人々は私にいくつかの新しいアイデアを与えることができるでしょう。 2、3日後に私の現在の方法に関するいくつかの情報を編集するつもりですが、私はすでにそれをやっている方法をあなたに伝えることによって問題についての人々の考えを偏らせたくありません。 私が取り組んでいる問題は、ビデオゲームのromイメージのクローン検出です。 エミュレーションの経験がない人にとって、romはゲームカートリッジのデータのダンプです。 romの「クローン」は通常、同じゲームの修正版で、最も一般的なタイプは翻訳版です。 たとえば、nesのオリジナルの「ファイナルファンタジー」の日本語版と英語版はクローンです。 ゲームはほとんどすべての資産(スプライト、音楽など)を共有していますが、テキストは翻訳されています。 現在、さまざまなシステムのクローンのリストを管理するためのグループがいくつかありますが、私の知る限りでは、これはすべて手動で行われます。 私がやろうとしているのは、「これらは同じゲームのように見える」のではなく、データの類似性に基づいて、類似のromイメージを自動的かつ客観的に検出する方法を見つけることです。 クローンを検出する理由はいくつかありますが、主な動機の1つは solid compressionで使用することです。 これにより、すべてのゲームクローンをまとめて同じアーカイブに圧縮することができます。圧縮されたクローンセット全体では、個々のromの1つよりわずかに多くのスペースしか占有しないことがよくあります。 潜在的なアプローチを考え出す際に考慮すべきいくつかの懸念: romはシステムによってサイズが大きく異なります。 小規模なものもありますが、最近のシステムでは256mb以上の大規模なものがあります。 いくつかの(すべて?)システムは可能なサイズとして2のべき乗しか持っていません、これらのシステムのうちの1つの上の130mbのゲームは256mbのromを持っているでしょう、大部分は空です。 このため、ゲームバージョンがしきい値を超え、サイズの2倍のカートリッジを使用する必要がある場合、クローンによってはサイズが大きく異なることがあります。 現在多くのシステムには数千の既知のromがありますが、ほとんどのシステムではまだ新しいromが絶えずリリースされています。 古いシステムでさえも、頻繁に変更されたromを生成する主要なromハッキングコミュニティがあります。 考えられるromのすべてのペアについて類似性データを格納すると、一般的なシステムでは何百万行ものデータが生成されます。 5000個のromを持つシステムでは、2500万行の類似性データが必要になり、1つの新しいゲームでさらに5000行が追加されます。 処理の状態は回復可能でなければならないので、中断された場合は中断したところから再開できます。 どのような方法でも、多くの処理が必要になり、全体が1つのバッチで実行されると想定するのは安全ではありません。 新しいromはいつでも追加できます。そのため、このメソッドはすでに「完全」なセットを持っていると想定しないでください。 つまり、既存のすべてのromの類似性を把握した後でも、新しいromが追加された場合(これは以前の処理が完全に終了する前にも発生する可能性があります)。 (もしあれば)それはのクローンです。 より高い処理速度は(ある程度)正確さより優先されるべきです。 2つのromが94%または96%類似しているかどうかを知ることは特に重要ではありませんが、新しいromを以前のromと比較するのに1日の処理時間がかかる場合、プログラムはおそらく本当に完成しません。 取り組むのは興味深い問題でした。他の人々が思いつくことができるのを楽しみにしています。 あなたがこれ以上の詳細が欲しいなら私にコメントで知らせてください、そして私はそれらを供給しようとします。
回答: バイナリデルタ、またはバイナリデルタのアプリケーションから派生したインデックス(サイズなど)が必要なようです。 その後、このインデックスを実験的に決定したベースラインと比較して、それが「クローン」かどうかを判断できます。 圧縮とデルタ作成の間には多くの類似点があるので、現在の実装にそれほど遠くないと思います。 そうは言っても、データベース内のすべてのバイナリファイルのペアワイズ比較はおそらく法外に高価です(o(n ^ 2 ^)、私は思います)。 私は比較のために可能な候補を識別するための単純なハッシュを見つけようとします。 概念的にはspdenneとeduardが提案しているものと似ているものがあります。 つまり、すべての項目に1回適用できるハッシュを見つけ、そのリストをソートしてから、リスト内でハッシュが近い項目に対してより詳細な比較を使用します。 一般的な場合に有用なハッシュの構築は、数年間csで積極的に追求されている研究トピックです。 lshkitソフトウェアライブラリは、この種のアルゴリズムをいくつか実装しています。 インターネットでアクセス可能な論文 大規模ファイルシステムでの類似ファイルの検索テキストファイルの比較を目的としている可能性がありますが、可能性があります。あなたに役立つでしょう。 最新の論文http://www.sciencedirect.com/science?_ob=articleurl ただし、購読なしではアクセスできないようです。 他のリソースを閲覧するときには、おそらく locality sensitive hashingにあるウィキペディアの記事を便利に保管してください。 それらはすべてかなり技術的になっており、ウィキペディアのエントリ自体はかなり数学的なものです。 よりユーザーフレンドリーな代替手段として、あなたは acoustic fingerprintingの分野からいくつかのアイデア(あるいは実行可能ファイルさえ)を適用することができるかもしれません。 一般的なケースを放棄しても構わないと思っているのであれば、あなたのromだけに使える、はるかに単純な(そしてより速い)ドメイン固有のハッシュ関数を見つけることができるでしょう。 標準的な、または一般的なバイトシーケンスの配置とその近くの選択ビットの値を含む可能性があります。 私はあなたのバイナリフォーマットについてはあまり知りませんが、サウンド、イメージ、テキストなどの領域のようにファイル内のセクションの始まりを知らせるものを想像しています。 バイナリフォーマットは、ファイルの先頭近くにこの種のセクションのアドレスを格納することがよくあります。 また、最初のセクションのアドレスを既知の場所にそのサイズと共に格納する連鎖メカニズムも使用されています。 これにより、サイズなども含まれている次のセクションに移動できます。 ちょっと調べれば、あなたがまだそれに気付いていないのであれば、おそらく関連するフォーマットを見つけることができるでしょう。 ハッシュ関数がうまくいかない場合(またはメトリック/距離を定義するために何らかの入力を必要とする場合)、web上で利用可能なバイナリデルタアルゴリズムと実装がいくつかあります。 私が一番よく知っているのは、subversionのバージョン管理システムです。 バイナリファイルのリビジョンを効率的に保存するためにxdeltaと呼ばれるバイナリデルタアルゴリズムを使用します。 これを実装しているリポジトリ内のファイルへの直接リンクは次のとおりです。 xdelta.c。 おそらくこれをよりアクセスしやすくするツールがweb上にあります。