Bonjour,

je tente en ce moment de coder un compresseur lzss, mais j'ai une question sur la fin du fichier.

D'après ce que j'ai compris, le principe consiste a mettre 1 octet de flag (donc 8 "1" ou "0") chaque 0 indiquant que le(s) prochain(s) octet(s) contiennent la taille et la position des données à répéter dans le buffer et chaque 1 indiquant que le prochain octet est un octet de données.

Problème: comment faire si notre nombre d'instructions n'est pas multiple de 8? on a donc un octet de flag incomplet? on rajoute des espaces à la fin du fichier?

Merci d'avance de votre aide, j'espère avoir été clair...

Je n'ai jamais codé le lzss. En quel langage l'as-tu écrit?
J'ai trouvé ce lien. J'espère qu'il va répondre à ta question.
https://compression.fiches-horaires.net/la-compression-sans-perte/lz77-et-lzss-les-algorithmes-a-fenetre-glissante/

Bonjour,

merci pour ta réponse! Je programme en python.

En fait j'ai suivi le tuto vers lequel tu me rediriges  mais il ne propose que de coder un décompresseur, et j'ai essayé de programmer un compresseur: tout marche sauf ce point. Voici mon code si ca peut aider:

def compresseur_lzss(octets_a_compresser: bytes) -> bytes:
  ma_position_source = 0
  pos_ecr_buffer = 4078
  octets_compresses = b''
  ring_buffer = bytearray(b' ' * 4096)
  octet_de_flag = ''
  sequence_de_donnees_correpondant_au_flag = b''
  while ma_position_source < len(octets_a_compresser):
    conc_2_buffer = bytes(ring_buffer) * 2
    if octets_a_compresser[ma_position_source:ma_position_source + 3] in conc_2_buffer and min(18, len(octets_a_compresser) - ma_position_source)>=3:
      octet_de_flag = "0" + octet_de_flag
      flag = False
      for taille in range(3, min(18, len(octets_a_compresser) - ma_position_source) + 1):
        if flag:
          continue
        test_sequence = octets_a_compresser[ma_position_source:ma_position_source + taille + 1]
        if test_sequence not in conc_2_buffer or taille == min(18, len(octets_a_compresser) - ma_position_source):
          position = conc_2_buffer.index(test_sequence[:-1])
          ring_buffer[pos_ecr_buffer:pos_ecr_buffer + taille] = ring_buffer[position:position + taille]
          position = hex(position).strip("0x")
          position = "0"*(3-len(position)) + position
          sequence_de_donnees_correpondant_au_flag += bytes.fromhex(position[1:]+position[:1]\
          +hex(taille-3)[2:]) #premier octet: 8 bits les moins signifiants de position
          pos_ecr_buffer += taille
          pos_ecr_buffer %= 4096
          flag = True
          ma_position_source += taille
    else:
      octet_de_flag = "1" + octet_de_flag
      sequence_de_donnees_correpondant_au_flag += bytes([octets_a_compresser[ma_position_source]])
      ring_buffer[pos_ecr_buffer%4096] = octets_a_compresser[ma_position_source]
      ma_position_source += 1
      pos_ecr_buffer += 1
      pos_ecr_buffer %= 4096
    if len(octet_de_flag) == 8:
      octets_compresses += bytes([int('0b' + octet_de_flag, 2)])
      octets_compresses += sequence_de_donnees_correpondant_au_flag
      octet_de_flag = ''
      sequence_de_donnees_correpondant_au_flag= b''
  if len(octet_de_flag)!=8:
    nb_fake_bytes_to_add = (8-len(octet_de_flag))
    octet_de_flag += '1' * nb_fake_bytes_to_add
    octets_compresses += bytes([int('0b' + octet_de_flag, 2)])
    octets_compresses += sequence_de_donnees_correpondant_au_flag
    octets_compresses += b'\x20' * nb_fake_bytes_to_add
  return octets_compresses

Du coup ça ne répond pas à ma question...

Une autre idée?

Merci d'avance

EDIT: Il y a d'autres choses qui ne marchent pas très bien mais c'est pas très grave...

-
Edité par the-cellist 8 mai 2021 à 21:56:01

J'ai fait un copier-coller de ton code et j'ai ajouté les quelques lignes qui suivent.
Pour tester si ça marche vraiment, il faut comparer la chaîne d'entrée de la compression avec la chaîne de sortie de la décompression.
Bien sûr, il faut que ce soit de même type.
-
inline="aaaabbbbc"
print(len(inline))
outline=compresseur_lzss(bytes(inline,encoding='utf-8'))
print(len(outline))
print(*[hex(i)[-2:] for i in outline])
-
9                                                                                                                      
18                                                                                                                     
ff 61 61 61 61 62 62 62 62 ff 63 20 20 20 20 20 20 20

Même si je ne comprend pas complètement l'algorithme, voici mon idée:
Si la longueur du dernier bloc est de 8, pas de problème.
Si elle est inférieure à 8, ce bloc est forcément différent des autres.
Tu complètes le byte position/taille et tu ajoutes les bytes restants.
Pour décompresser, tu vérifies toujours qu'il reste au moins 8 bytes à décompresser (plus le contrôle position/taille).
Si oui, tu fais comme d'habitude.
Sinon, tu traites le byte position/taille et tu ajoutes tout simplement les bytes suivants à la suite dans la séquence.

Merci beaucoup!

Je pense que c'est une bonne solution, je ferme le sujet.

Merci encore pour ton aide