Trier les structures dans l'ordre de moindre changement

Question

Ceci est devenu incompréhensible. Je vais reformuler

Existe-t-il un algorithme ou une approche permettant de trier un tableau de manière à minimiser les différences entre les éléments successifs?

struct élément
{
uint32 positions[8];
}

Ces enregistrements ne sont pas sensibles à l'ordre.
Le format du fichier de sortie est défini comme suit :

byte  présent;  // chaque bit indiquant si la position[i] est présente
uint32 position0;
-- (seuls les bits définis dans Présent sont effectivement écrits dans le fichier).  
uint32 positionN;  // N est le nombre de bits définis dans "présent"
byte  prochainprésent;

Tous les enregistrements sont garantis comme étant uniques, donc un octet de 'présent' de 0 représente EOF. Le fichier est analysé en mettant à jour une structure "courante" avec les champs présents, et le résultat est ajouté à la liste.

Par exemple : { 1, 2, 3}, { 2, 3, 2}, { 4, 2, 3}
Serait : 111b 1 2 3 001b 4 111b 2 3 2
Économisant 2 nombres par rapport à l'approche non triée.

Mon objectif est de minimiser la taille du fichier de sortie.

Answer 1

Votre problème

Je pense que cette question devrait vraiment être étiquetée avec 'compression'.

Si je comprends bien, vous avez des enregistrements non ordonnés composés de huit entiers de 4 octets : 32 octets au total. Vous souhaitez stocker ces enregistrements avec une taille de fichier minimale, et avez décidé d'utiliser une forme de codage delta basé sur une distance de Hamming. Vous demandez comment trier au mieux vos données pour le schéma de compression que vous avez construit.

Vos hypothèses

D'après ce que vous nous avez dit, je ne vois pas de véritable raison pour laquelle vous devriez diviser vos 32 octets de la manière que vous avez décrite (à part le fait que les limites de mots sont pratiques)! Si vous récupérez les mêmes données, est-ce vraiment important si elles sont encodées en huit lots de 4 octets, ou en seize lots de 2 octets, ou en un énorme entier de 32 octets?

De plus, à moins qu'il y ait quelque chose dans le domaine du problème qui rende votre méthode préférée, votre meilleure option est probablement d'utiliser un schéma de compression éprouvé. Vous devriez pouvoir trouver du code déjà écrit, et vous obtiendrez de bonnes performances sur des données typiques.

Votre question

Revenons à votre question initiale, si vous voulez vraiment suivre cette voie. Il est facile d'imaginer choisir un enregistrement de départ (je ne pense pas que cela fera beaucoup de différence, mais cela a probablement du sens de choisir le plus 'petit' ou le plus 'grand'), et calculer la distance de Hamming par rapport à tous les autres enregistrements. Vous pourriez alors choisir celui avec la distance minimale à stocker ensuite, et répéter. De toute évidence, ceci est en O(n^2) par rapport au nombre d'enregistrements. Malheureusement, cet article (que je n'ai pas lu ou compris en détail) donne l'impression que calculer la distance de Hamming minimale d'une chaîne à un ensemble d'autres est intrinsèquement difficile, et n'a pas de très bonnes approximations.

Vous pourriez évidemment obtenir une meilleure complexité en triant vos enregistrements en fonction du poids de Hamming (qui revient au nombre de population de cet entier de 32 octets), ce qui est en O(n log(n)) par rapport au nombre d'enregistrements. Ensuite, utilisez un codage de différence sur le résultat. Mais je ne pense pas que cela fasse un schéma de compression terriblement efficace : les entiers de 0 à 7 pourraient finir par ressembler à quelque chose comme :

000, 100, 010, 001, 101, 011, 110, 111

0, 4, 2, 1, 5, 3, 6, 7

Cela nous ramène à la question que j'ai posée précédemment : êtes-vous sûr que votre schéma de compression est meilleur que quelque chose de plus standard pour vos données particulières?

Answer 2

Vous regardez une paire de sous-problèmes, définissant la différence entre les structures, puis le tri.

Je ne suis pas très clair sur votre description de la structure, ni sur la préférence des différences, mais je suppose que vous pouvez résoudre cela et calculer un score de différence entre deux instances. Pour les fichiers, il existe des algorithmes connus pour discuter de ces choses, comme celui utilisé dans diff.

Pour votre ordre, vous regardez un problème classique du problème du voyageur de commerce. Si vous triez quelques-unes de ces choses, c'est facile. Si vous en triez beaucoup, vous devrez vous contenter d'un tri 'suffisamment bon', à moins que vous ne soyez prêt à appliquer des connaissances spécifiques au domaine et de nombreux petits conseils du TSP à l'effort.