Modèles de codage dans un espace 2D (matrice)

Question

J'ai une grille MxN 2D (ou matrice). Les cellules de la matrice peuvent contenir un nombre entier. Une cellule avec un entier différent de zéro est dite remplie. L'ensemble des cellules peuplées dans la matrice est appelé "configuration". Je veux créer un algorithme de codage ou de hachage qui me permettra d'identifier de manière unique une configuration dans la matrice, en calculant sa valeur codée (qui devrait générer un nombre unique). Je préfère coder au hachage, car les collisions seront totalement indésirables. Est-ce que quelqu'un peut suggérer un algorithme de codage que je peux utiliser pour calculer un "id" unique pour une configuration donnée?

Answer 1

Donc c'est un tableau de 1 et 0? Que diriez-vous d'une compression RLE ou LZW de ce tableau?

Answer 2

Pour une représentation qui permet une comparaison exacte, il n'est pas possible de faire mieux qu'une compression optimale d'une séquence de bits qui représentent la configuration.

Si vous souhaitez que les valeurs booléennes MxN soient codées de manière unique dans un entier, vous avez besoin de 2 ^{valeurs M * N}. Que ce soit faisable en utilisant les entiers de précision fixe de votre plateforme dépend de la taille de M et N; Sinon, vous devrez utiliser une chaîne de caractères ou un grand nombre entier. Comme les données d'origine ont une valeur entière plutôt que 1 ou 0, un ID de chaîne binaire naïf d'une matrice naïve donnera une compression de 8 * sizeof (matrix::cell_type). Une chaîne de bits optimisée pour des valeurs éparses pourrait être meilleure. De bonnes implémentations de chaînes de bits fragmentées compressent les données, ce qui réduit l'espace de stockage de la représentation et permet une comparaison exacte rapide, qui sont les exigences.

Si les motifs sont garantis à un certain niveau, il y a des optimisations que vous pouvez faire en compressant l'information, mais vous devez donner plus d'informations. Par exemple, utilisez-vous une représentation matricielle fragmentée (en bandes, en diagonale, en ligne compressée, etc.) et avez accès aux composants internes de la matrice matricielle, puis mappez-la naturellement à une chaîne de bits compressée.

En regardant votre autre poste, il semble que la matrice est utilisée comme la grille d'un jeu plutôt que comme une matrice. Dans ce cas, il est probablement préférable d'utiliser une compression sur la chaîne de bits, car cela donne une autre propriété utile - la représentation codée de la chaîne binaire des matrices dont les configurations sont des translations ne différera que par la première valeur du codage.

Answer 3

On ne sait pas exactement ce que vous voulez réaliser, mais peut-être qu'un personnalisébloom filter pourrait être adapté à votre problème.

Answer 4

En fonction de ce problème que vous essayez de résoudre, le follwoing vient à l'esprit:

• utiliser une recherche-table pour associer des matrices ids largeur
• stocker uniquement les valeurs des champs peuplés; leur position dans la matrice peut être codée soit d'une valeur individuelle par champ ou à l'aide d'une image bitmap pour l'ensemble de matrice

Answer 5

Je suggère d'utiliser un algorithme de hachage qui aura une chance 99,999999999% de la génération d'un identifiant unique.Dans la plupart des scénarios, il est acceptable d'avoir une collision chaque milliardième hash. Ma suggestion est d'utiliser l'algorithme CRC, car il génère un ensemble de hachages hautement distribué et a un taux relativement faible de collisions.

Answer 6

Peu importe s'il y a une collision ou non. Même s'il y a une collision, vous pouvez continuer à vérifier la matrice int par int pour voir si elle est similaire.

Tant que les collisions se produisent très rarement les frais généraux est 0

donc une fonction de hachage pourrait être tout aussi simple que d'ajouter tous les int ensemble de. Si cela est suffisant, cela dépend des valeurs possibles des entiers et de leur nombre (si donc dans la matrice entière seulement 1 ou 2 cellules ont une valeur, ce hachage ne fonctionnera pas)