青少年编程与数学 02-016 Python数据结构与算法 30课题、数据压缩算法 ...

课题摘要:
先容一些常见的数据压缩算法，并提供更详细的Python代码实现。
  

---

一、无损压缩算法

1. Huffman编码

Huffman编码是一种基于字符频率的编码方法，通过构建一棵Huffman树来天生每个字符的唯一编码。
详细代码示例（Python）：

1. import heapq
2. from collections import defaultdict, Counter
4. class Node:
5.     def __init__(self, char, freq):
6.         self.char = char
7.         self.freq = freq
8.         self.left = None
9.         self.right = None
11.     def __lt__(self, other):
12.         return self.freq < other.freq
14. def build_huffman_tree(frequency):
15.     heap = [Node(char, freq) for char, freq in frequency.items()]
16.     heapq.heapify(heap)
17.    
18.     while len(heap) > 1:
19.         left = heapq.heappop(heap)
20.         right = heapq.heappop(heap)
21.         merged = Node(None, left.freq + right.freq)
22.         merged.left = left
23.         merged.right = right
24.         heapq.heappush(heap, merged)
25.    
26.     return heap[0]
28. def generate_codes(node, prefix="", code_dict=None):
29.     if code_dict is None:
30.         code_dict = {}
31.     if node is not None:
32.         if node.char is not None:
33.             code_dict[node.char] = prefix
34.         generate_codes(node.left, prefix + "0", code_dict)
35.         generate_codes(node.right, prefix + "1", code_dict)
36.     return code_dict
38. def huffman_encode(s):
39.     frequency = Counter(s)
40.     huffman_tree = build_huffman_tree(frequency)
41.     huffman_codes = generate_codes(huffman_tree)
42.     encoded_string = ''.join(huffman_codes[char] for char in s)
43.     return encoded_string, huffman_codes
45. def huffman_decode(encoded_string, huffman_codes):
46.     reverse_dict = {code: char for char, code in huffman_codes.items()}
47.     current_code = ""
48.     decoded_string = ""
49.     for bit in encoded_string:
50.         current_code += bit
51.         if current_code in reverse_dict:
52.             decoded_string += reverse_dict[current_code]
53.             current_code = ""
54.     return decoded_string
56. # 示例
57. s = "this is an example for huffman encoding"
58. encoded_string, huffman_codes = huffman_encode(s)
59. print("Encoded string:", encoded_string)
60. print("Huffman dictionary:", huffman_codes)
61. decoded_string = huffman_decode(encoded_string, huffman_codes)
62. print("Decoded string:", decoded_string)

复制代码

2. Lempel-Ziv-Welch (LZW) 编码

LZW编码是一种基于字典的压缩算法，通过动态构建字典来编码重复的字符串。
详细代码示例（Python）：

1. def lzw_encode(s):
2.     dictionary = {chr(i): i for i in range(256)}
3.     w = ""
4.     result = []
5.     for c in s:
6.         wc = w + c
7.         if wc in dictionary:
8.             w = wc
9.         else:
10.             result.append(dictionary[w])
11.             dictionary[wc] = len(dictionary)
12.             w = c
13.     if w:
14.         result.append(dictionary[w])
15.     return result
17. def lzw_decode(encoded):
18.     dictionary = {i: chr(i) for i in range(256)}
19.     w = chr(encoded.pop(0))
20.     result = [w]
21.     for k in encoded:
22.         if k in dictionary:
23.             entry = dictionary[k]
24.         elif k == len(dictionary):
25.             entry = w + w[0]
26.         result.append(entry)
27.         dictionary[len(dictionary)] = w + entry[0]
28.         w = entry
29.     return ''.join(result)
31. # 示例
32. s = "TOBEORNOTTOBEORTOBEORNOT"
33. encoded = lzw_encode(s)
34. print("Encoded:", encoded)
35. decoded = lzw_decode(encoded)
36. print("Decoded:", decoded)

复制代码

3. Run-Length Encoding (RLE)

RLE是一种简单的无损压缩算法，通过将连续重复的字符替换为字符和重复次数的组合。
详细代码示例（Python）：

1. def rle_encode(s):
2.     if not s:
3.         return ""
4.    
5.     result = []
6.     prev_char = s[0]
7.     count = 1
8.    
9.     for char in s[1:]:
10.         if char == prev_char:
11.             count += 1
12.         else:
13.             result.append((prev_char, count))
14.             prev_char = char
15.             count = 1
16.     result.append((prev_char, count))
17.    
18.     return ''.join([f"{char}{count}" for char, count in result])
20. def rle_decode(encoded):
21.     result = []
22.     i = 0
23.     while i < len(encoded):
24.         char = encoded[i]
25.         count = int(encoded[i+1])
26.         result.append(char * count)
27.         i += 2
28.     return ''.join(result)
30. # 示例
31. s = "AAAABBBCCDAA"
32. encoded = rle_encode(s)
33. print("Encoded:", encoded)
34. decoded = rle_decode(encoded)
35. print("Decoded:", decoded)

复制代码

二、有损压缩算法

1. JPEG压缩（有损）

JPEG是一种广泛利用的图像压缩标准，通常用于有损压缩。虽然JPEG压缩的实现较为复杂，但可以利用Python的Pillow库来处置惩罚JPEG图像。
详细代码示例（Python）：

1. from PIL import Image
3. # 压缩图像
4. def compress_image(input_path, output_path, quality=85):
5.     image = Image.open(input_path)
6.     image.save(output_path, "JPEG", quality=quality)
8. # 示例
9. compress_image("input.jpg", "output.jpg", quality=50)

复制代码

2. DEFLATE（ZIP压缩）

DEFLATE是一种结合了LZ77算法和Huffman编码的压缩算法，广泛用于ZIP文件格式。
详细代码示例（Python）：

1. import zlib
3. def deflate_compress(data):
4.     compressed_data = zlib.compress(data.encode())
5.     return compressed_data
7. def deflate_decompress(compressed_data):
8.     decompressed_data = zlib.decompress(compressed_data)
9.     return decompressed_data.decode()
11. # 示例
12. data = "this is an example for deflate compression"
13. compressed_data = deflate_compress(data)
14. print("Compressed data:", compressed_data)
15. decompressed_data = deflate_decompress(compressed_data)
16. print("Decompressed data:", decompressed_data)

复制代码

3. Brotli

Brotli是一种现代的压缩算法，结合了多种压缩技术，提供比DEFLATE更好的压缩率。
详细代码示例（Python）：

1. import brotli
3. def brotli_compress(data):
4.     compressed_data = brotli.compress(data.encode())
5.     return compressed_data
7. def brotli_decompress(compressed_data):
8.     decompressed_data = brotli.decompress(compressed_data)
9.     return decompressed_data.decode()
11. # 示例
12. data = "this is an example for brotli compression"
13. compressed_data = brotli_compress(data)
14. print("Compressed data:", compressed_data)
15. decompressed_data = brotli_decompress(compressed_data)
16. print("Decompressed data:", decompressed_data)

复制代码

4. LZMA

LZMA是一种高效的压缩算法，广泛用于7z文件格式。
详细代码示例（Python）：

1. import lzma
3. def lzma_compress(data):
4.     compressed_data = lzma.compress(data.encode())
5.     return compressed_data
7. def lzma_decompress(compressed_data):
8.     decompressed_data = lzma.decompress(compressed_data)
9.     return decompressed_data.decode()
11. # 示例
12. data = "this is an example for lzma compression"
13. compressed_data = lzma_compress(data)
14. print("Compressed data:", compressed_data)
15. decompressed_data = lzma_decompress(compressed_data)
16. print("Decompressed data:", decompressed_data)

复制代码

5. Zstandard (Zstd)

Zstd是一种现代的压缩算法，结合了高压缩率和快速解压缩的特点。
详细代码示例（Python）：

1. import zstandard
3. def zstd_compress(data):
4.     compressed_data = zstandard.compress(data.encode())
5.     return compressed_data
7. def zstd_decompress(compressed_data):
8.     decompressed_data = zstandard.decompress(compressed_data)
9.     return decompressed_data.decode()
11. # 示例
12. data = "this is an example for zstd compression"
13. compressed_data = zstd_compress(data)
14. print("Compressed data:", compressed_data)
15. decompressed_data = zstd_decompress(compressed_data)
16. print("Decompressed data:", decompressed_data)

复制代码

总结

这些数据压缩算法在不同的场景下具有各自的优势和适用性。无损压缩算法如Huffman编码、LZW编码和RLE适用于需要完全恢复原始数据的场景，而有损压缩算法如JPEG压缩则适用于对数据质量要求不高的场景。根据具体需求选择符合的压缩算法可以有效节省存储空间和传输带宽。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。