lz78/lz_78_xor.py

   1 import sys
   2 import struct
   3
   4 ########################################################################################
   5 # python lz_78_xor.py <d/c> <caminho_para_o_ficheiro_original>
   6 #
   7 # c: comprimir
   8 # d: descomprimir
   9 #
  10 # Os ficheiros gerados ficarão na mesma pasta que o script
  11 ########################################################################################
  12
  13 def xor(bitstream, largura, altura):
  14     matriz = []
  15     for i in range(altura):
  16         linha = [int(b) for b in bitstream[i * largura : (i + 1) * largura]]
  17         matriz.append(linha)
  18
  19     nova_imagem = ""
  20     # A primeira linha mantém-se igual (não tem linha anterior)
  21     nova_imagem += "".join(map(str, matriz[0]))
  22
  23     for i in range(1, altura):
  24         nova_linha = []
  25         for j in range(largura):
  26             res = matriz[i][j] ^ matriz[i-1][j]
  27             nova_linha.append(str(res))
  28         nova_imagem += "".join(nova_linha)
  29
  30     return nova_imagem
  31
  32 def descodificar_xor(bitstream_transformado, largura, altura):
  33     matriz_temp = []
  34     for i in range(altura):
  35         linha = [int(b) for b in bitstream_transformado[i * largura : (i + 1) * largura]]
  36         matriz_temp.append(linha)
  37
  38     matriz_original = []
  39
  40     matriz_original.append(matriz_temp[0])
  41
  42     for i in range(1, altura):
  43         linha_recuperada = []
  44         for j in range(largura):
  45             pixel_original = matriz_temp[i][j] ^ matriz_original[i-1][j]
  46             linha_recuperada.append(pixel_original)
  47         matriz_original.append(linha_recuperada)
  48
  49     bitstream_final = ""
  50     for linha in matriz_original:
  51         bitstream_final += "".join(map(str, linha))
  52
  53     return bitstream_final
  54
  55 def lz78_compression(image):
  56     dictionary = {
  57         0: ""
  58     }
  59
  60     output = []
  61
  62     symbol = ""
  63
  64     for i in image:
  65         if (symbol + i) in dictionary.values():
  66             symbol += i
  67         else:
  68             if symbol == "":
  69                 output.append([0, i])
  70                 dictionary[len(dictionary)] = i
  71             else:
  72                 output.append([list(dictionary.keys())[list(dictionary.values()).index(symbol)], i])
  73                 dictionary[len(dictionary)] = symbol + i
  74             symbol = ""
  75
  76     if symbol != "":
  77         idx = list(dictionary.keys())[list(dictionary.values()).index(symbol)]
  78         output.append([idx, ""])
  79
  80     return output, dictionary
  81
  82 def lz78_decompression(compressed_image):
  83     dictionary = {
  84         0: ""
  85     }
  86
  87     output = ""
  88
  89     for i in compressed_image:
  90         output += dictionary.get(i[0]) + i[1]
  91         dictionary[len(dictionary)] = dictionary.get(i[0]) + i[1]
  92
  93     return output
  94
  95 def clean_image_data(image_data):
  96
  97     clean_text = ""
  98
  99     for line in image_data:
 100         line = line.strip()
 101         line = line.replace(" ", "")
 102         if not line or line.startswith('#'):
 103             continue
 104         clean_text += line
 105
 106     return clean_text
 107
 108 def chunkstring(string, length):
 109     return [string[i : length+i] for i in range(0, len(string), length)]
 110
 111 #Comprimir
 112 if sys.argv[1] == "c":
 113
 114     with open(sys.argv[2], "r") as image:
 115         lines = image.readlines()
 116         image_size = lines[1].split()
 117
 118         if lines[0].strip() != 'P1':
 119             raise ValueError("This is not a pbm file")
 120
 121         clean_text = clean_image_data(lines[2:]) #Limpa os espaços em branco para comprimir melhor
 122
 123         clean_text = xor(clean_text, int(image_size[0]), int(image_size[1]))
 124
 125         output, dic = lz78_compression(clean_text)
 126
 127         print(f"Output: {output}\n")
 128         print(f"Dictionary: {dic}")
 129
 130         #Compressão em texto (human-readable)
 131         with open(sys.argv[2] + "_compressed", "w") as save_file:
 132             save_file.write(f"{output} \n{image_size[0]} {image_size[1]}")
 133
 134         #Compressão em binário (compressão "a sério")
 135         with open(sys.argv[2] + ".bin", "wb") as save_file:
 136             largura = int(image_size[0])
 137             altura = int(image_size[1])
 138             save_file.write(struct.pack('II', largura, altura))
 139
 140             for indice, simbolo in output:
 141                 simbolo_byte = ord(simbolo) if simbolo != "" else 0
 142                 save_file.write(struct.pack('HB', indice, simbolo_byte))
 143 #Descomprimir
 144 elif sys.argv[1] == "d":
 145
 146     #Descomprimir do ficheiro de texto
 147     with open(sys.argv[2] + "_compressed", "r") as image:
 148         lines = image.readlines()
 149
 150         compressed_image = eval(lines[0])
 151         image_size = lines[1]
 152         largura = int(lines[1].split(" ")[0])
 153         altura = int(lines[1].split(" ")[1])
 154
 155         output = lz78_decompression(compressed_image)
 156
 157         output = descodificar_xor(output, largura, altura)
 158
 159         chuncked_output = chunkstring(output, largura)
 160
 161         with open(sys.argv[2] + "_decompressed", "w") as save_file:
 162             save_file.write(f"P1\n{image_size}\n")
 163             for line in chuncked_output:
 164                 save_file.write(f"{line}\n")
 165
 166     #Descomprimir do binário
 167     with open(sys.argv[2] + ".bin", "rb") as image:
 168         header = image.read(8)
 169         largura, altura = struct.unpack('II', header)
 170
 171         compressed_image_bin = []
 172         while True:
 173             chunk = image.read(3)
 174             if not chunk:
 175                 break
 176             indice, simbolo_byte = struct.unpack('HB', chunk)
 177             simbolo = chr(simbolo_byte) if simbolo_byte != 0 else ""
 178             compressed_image_bin.append([indice, simbolo])
 179
 180         output = lz78_decompression(compressed_image_bin)
 181
 182         output = descodificar_xor(output, largura, altura)
 183
 184         chuncked_output = chunkstring(output, largura)
 185
 186         with open(sys.argv[2]+ "_bin_decompressed", "w") as save_file:
 187             save_file.write(f"P1\n{largura} {altura}\n")
 188             for line in chuncked_output:
 189                 save_file.write(f"{line}\n")