Compression de séquence?

Question

ces derniers temps j'ai fait face à un problème qui me fait tellement confus, le problème est: je veux compresser une séquence de sorte qu'aucune information ne soit perdue, par exemple:

a, a, a, b -> a, b

a, b, a, a, c -> a, b, a, a, c (il ne peut pas être compressé en a, b, a, c car de cette façon nous perdons un , a)

Existe-t-il un algorithme pour faire une telle chose? quel est le nom de ce problème? est-ce la compression? ou autre chose? J'apprécierais vraiment toute aide Merci d'avance

Answer 1

À moins d'avoir à coder une solution vous-même, vous pouvez utiliser une bibliothèque de compression ZIP pour le langage de programmation que vous utilisez.

Et oui, c'est la compression de données.

Answer 2

RLE

Answer 3

Eh oui, la compression. Un algorithme simple serait encodage runlength. Il y a aussi la théorie de l'information, qui est la base des algorithmes de compression.

Théorie de l'information: Les entrées les plus communes devraient être plus courtes, ce qui raccourcirait la longueur de la phrase.

Donc, si vous le codage binaire, où la séquence 0101 est très commmon (environ 25% de l'entrée), puis une compression simple serait:

0101 = 0 
anything else = 1[original 4 bits] 

donc l'entrée: 0101 1100 0101 0101 1010 0101 1111 0101
Serait compressé à: 0 11100 0 0 11010 0 11111 0

C'est une compression de 32 bits -> 20 bits.

Une leçon importante: le choix de l'algorithme de compression dépend entièrement de l'entrée. Le mauvais algorithme et vous aurez probablement rendre les données plus longues.

Answer 4

Chaque algorithme qui est capable de transformer des données de manière à occuper moins de mémoire est appelé compression. Que ce soit sans perte ou avec perte.

par exemple. (Sous forme comprimée pour « exemple donné » :-))

Ce qui suit est AMHA la forme de simples, appelé le codage de longueur d'exécution, courte RLE:

a,a,a,b,c -> 3a,1b,1c 

Comme vous pouvez le voir tous les caractères suivants qui sont identiques sont compressés en un.

Vous pouvez également rechercher des motifs ultérieurs qui est beaucoup plus difficile:

a,b,a,b,a,c --> 2(a,b),1(a),1(c) 

Il y a beaucoup de sources documentaires et Web sur les algorithmes de compression, vous devez les utiliser pour obtenir une vue plus profonde.

Answer 5

Un autre bon algorithme est Lempel–Ziv–Welch

Je trouve merveilleux cette simple fonction LZW Javascript, des magiciens à 140 bytes of javascript:

function (
    a // String to compress and placeholder for 'wc'. 
){ 

    for (
     var b = a + "Ā", // Append first "illegal" character (charCode === 256). 
      c = [], // dictionary 
      d = 0, // dictionary size 
      e = d, // iterator 
      f = c, // w 
      g = c, // result 
      h; // c 

     h = b.charAt(e++); 
    ) 

     c[h] = h.charCodeAt(), // Fill in the dictionary ... 
     f = 1 + c[a = f + h] ? a : (g[d++] = c[f], c[a] = d + 255, h); // ... and use it to compress data. 

    return g // Array of compressed data. 

} 

Answer 6

Nous pouvons utiliser l'algorithme de compression LZW pour compresser les fichiers texte rapidement et efficacement par en utilisant des tables de hachage.