Quelle est la meilleure façon de compresser une liste de chaînes similaires mais non identiques?

StackOverflow https://stackoverflow.com//questions/9653793

Question

Dites, j'ai un certain nombre de chaînes qui sont assez similaires mais non absolument identiques.

Ils peuvent différer plus ou moins, mais on peut voir la similitude par l'œil nu.

Toutes les longueurs sont égales, chacune est de 256 octets. Le nombre total de chaînes est inférieur à 2 ^ 16.

Quelle serait la meilleure méthode de compression pour un tel cas?

Mise à jour ( FORMAT DE DONNÉES ):

Je ne peux pas partager les données mais je peux le décrire assez près de la réalité:

Imaginez la notation (comme Logo Language) qui est la séquence de commandes pour certains périphériques de déplacement et de dessin dans le plan. Comme: 

U12 - move up 12 steps
D64 - move down 64 steps
C78 - change drawing color to 78
P1  - pen down (start drawing)

et ainsi de suite.

Le vocabulaire complet de cette langue ne dépasse pas la taille de l'alphabet anglais.

La chaîne décrit alors une image entière: "u12c6p1l74d74r74u74p0 ....".

Imaginez maintenant la classe de dix mille enfants qui ont été racontés d'attirer une image très spécifique avec l'aide de cette langue: comme le drapeau de leur pays. Nous obtiendrons 10 km de chaînes qui sont toutes différentes et toutes semblables à la fois.

Notre tâche consacre la totalité du groupe de cordes aussi bonnes que possible.

Ma suspicion ici est qu'il existe un moyen d'exploiter cette similitude et cette longueur commune des cordes, tandis que Huffman E.G. ne l'utilisera pas explicitement.

Était-ce utile?

La solution

Pourriez-vous nous dire quelles sont les données?Peut-être comme une séquence d'ADN?Comme

AGCTGTGCGAGAGAGAGCGGTGGGGG ...

GGCTGTGCGAGCGAGAGCGGTGGGG ...

CGCTGTGAGAGNGAGAGCGGTGGG ...

NGCTGTGCGAGAGAGAGCGGTGGGG ...

GGCTGTGCGAGTGAGAGCGGTGGGG ...

... ...

? Peut-être, ou pas.Quoi qu'il en soit, voici deux niveaux ou deux façons de penser:

  1. Codage Huffman: Réf.Wikipedia par vous-même

  2. Stringologie: Réf. http://books.google.com.hk/books/about/Jewels_of_stringology.html?id=9ndohjxtiYyc

    Je pense qu'il est facile de résoudre votre problème mais difficile à choisir le meilleur moyen.Vous pouvez concevoir plusieurs méthodes pour comparer en utilisant http://fr.wikipedia.org/wiki/data_Compression et plus d'outils.

Autres conseils

Puisque vous avez une largeur de fixation de 256 octets et c'est une puissance de 2, j'essaierais une transformation du roue de terre ou un algorithme de déplacement à l'avant avec cette taille ou peut-être le double de cette taille.Ensuite, vous pouvez essayer un code Huffman.Peut-être que vous pouvez essayer une courbe de Hilbert sur 256 octets, puis un BWT et MFT?

"Le nombre total de chaînes est inférieur à 2 ^ 16."C'est un petit nombre délimité, qui rend votre travail très facile: pourquoi ne conservez-vous pas une table de recherche (table de hachage) de toutes les cordes déjà observées.Vous pouvez ensuite convertir toutes les lignes de 256 octets en un indice de deux octets dans cette table de recherche.

Vous avez ensuite une séquence d'entiers de 16 bits.Ces entiers contiendront des motifs tels que "après la descente du stylo, il y a une chance de 90% que la commande suivante commence à dessiner".Si les données contiennent des modèles tels que ceci, PPM est votre choix.7-Zip possède une implémentation de haute qualité de PPM.Vous pouvez le choisir à l'aide de l'interface graphique ou de la cmd-ligne.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top