2D MxN グリッド (またはマトリックス) があります。行列のセルは整数を保持する場合があります。ゼロ以外の整数を含むセルは、入力されていると言われます。マトリックス内に取り込まれたセルのセットは、「構成」として知られています。
エンコードされた値 (一意の番号を生成する必要があります) を計算することにより、マトリックス内の構成を一意に識別できるようにするエンコードまたはハッシュ アルゴリズムを考え出します。
衝突はまったく望ましくないため、ハッシュよりもエンコードを好みます。
特定の構成の一意の「ID」を計算するために使用できるエンコードアルゴリズムを誰かが提案できますか?
一意のIDを生成する可能性が99.999999999％になるハッシュアルゴリズムを使用することをお勧めします。ほとんどのシナリオでは、10億分の1のハッシュごとに衝突が発生することは許容されます。私の提案は、CRCアルゴリズムを使用することです。これは、高度に分散されたハッシュのセットを生成し、衝突の発生率が比較的低いためです。
衝突があるかどうかは関係ありません。衝突が発生した場合でも、intごとに行列intをチェックし続けて、実際に類似しているかどうかを確認できます。
衝突が非常にまれに発生する限り、オーバーヘッドは0です。
したがって、ハッシュ関数は、すべてのintを足し合わせるのと同じくらい簡単です。これで十分な場合は、intの可能な値とその数によって異なります（したがって、マトリックス全体で1つまたは2つのセルのみに値がある場合、このハッシュは機能しません）
1と0の配列ですか？その配列の RLE または LZW 圧縮はどうですか?
正確な比較を可能にする表現は、構成を表現する一連のビットの最適な圧縮よりも優れたものにすることはできません。
MxN ブール値を整数で一意にエンコードする必要がある場合は、2 M*N値が必要です。プラットフォームの固定精度整数を使用して実現可能かどうかは、M と N のサイズによって異なります。そうでない場合は、ビット文字列または大きな整数を使用する必要があります。
元のデータは単なる 1 または 0 ではなく、任意の整数値であるため、ナイーブ マトリックスのナイーブ ビットストリング ID は の圧縮を提供し8 * sizeof ( matrix::cell_type )ます。スパース値用に最適化されたビット文字列の方が優れている可能性があります。スパース ビット文字列の適切な実装はデータを圧縮するため、これにより表現のストレージ スペースが削減され、要件である正確な比較が迅速に行われます。
パターンが特定のレベルまでまばらであることが保証されている場合、情報を圧縮して実行できる最適化がありますが、より多くの情報を提供する必要があります。
たとえば、スパース マトリックス表現 (バンド、対角線、行圧縮など) を使用しており、スパース マトリックス ストレージの内部にアクセスできる場合、圧縮されたビット文字列に自然かつ効率的にマップされます。
他の投稿を見ると、マトリックスはマトリックスとしてではなく、ゲームのグリッドとして使用されているようです。その場合、ビット文字列でランレングス圧縮を使用するのがおそらく最善です。これにより、別の有用なプロパティが得られます。構成が相互の翻訳であるマトリックスのエンコードされたビット文字列表現は、エンコーディングの最初の値のみが異なります。
何を達成したいのかは明確ではありませんが、カスタム ブルーム フィルターの実装が問題に適している可能性があります。
解決しようとしている問題に応じて、次のことが思い浮かびます。