基于原始字节的GIF编码器：小图正常大图失败，疑LZW实现有误

AI 小北

2026-8-25

GIF编码器LZW压缩实现问题：小图正常大图异常

我正在编写一个通过写入原始字节生成GIF文件的编码器，参考了W3C的GIF89a规范文档以及维基百科的GIF条目。我的代码在处理小尺寸图片时可以正常工作，但处理稍大的图片时会失败。我猜测可能是LZW压缩算法的实现存在错误，但无法定位问题所在。

注：该编码器用于特定场景，因此部分代码直接写入常量（除非错误出在头部区域）。

编码器代码

class GifWriter(object):
    def __init__(self, output):
        self.out = open(output, 'wb')
    
    def writeHeader(self, width, height, bpp=4):
        self.bpp = max(min(bpp,8),1)
        
        self.out.write(b'GIF89a')
        self.out.write(width.to_bytes(2,byteorder='little'))
        self.out.write(height.to_bytes(2,byteorder='little'))
        b = 0xf0 + (self.bpp-1)
        self.out.write(b.to_bytes(1,byteorder='big'))
        self.out.write(b'\x00\x00')
    
    def writeApplicationExtensionLoop(self, loopCount=0):
        self.out.write(b'\x21\xFF\x0B')
        self.out.write(b'\x4E\x45\x54\x53\x43\x41\x50\x45\x32\x2E\x30')
        self.out.write(b'\x03\x01\x00\x00')
        self.out.write(b'\x00')
    
    # rgbIntArr = [r0, g0, b0, r1, g1, b1, ...]
    # 0 <= r*,g*,b* <= 255
    def writePalette(self, rgbIntArr):
        palette = np.empty((len(rgbIntArr)//3,3))
        i = 0
        for c in rgbIntArr:
            self.out.write(c.to_bytes(1,byteorder='big'))
            palette[i//3][i%3] = c
            i+=1
        self.paletteTree = scipy.spatial.KDTree(palette,copy_data=True)
    
    # image.shape = (w,h,3)
    def writeImage(self, image, delay):
        image = image[:,:,0:3]
    
        #Graphics Control Extension
        self.out.write(b'\x21\xF9\x04')
        self.out.write(b'\x00') #Packed Fields
        self.out.write(delay.to_bytes(2,byteorder='little')) #Delay time (1/100)
        self.out.write(b'\x00') #Transparent Color Index (not used)
        self.out.write(b'\x00') #Terminator
        
        #Image Descriptor
        self.out.write(b'\x2C') #Seperator
        self.out.write(b'\x00\x00\x00\x00') #Top Left Corner
        self.out.write(image.shape[1].to_bytes(2,byteorder='little')) #Width
        self.out.write(image.shape[0].to_bytes(2,byteorder='little')) #Height
        self.out.write(b'\x00') #Packed Fields
        
        
        #Image Data
        self.out.write(self.bpp.to_bytes(1,byteorder='big')) #LZW Minimum Code Size
        
        maxLen = 1
        currCode = 2**self.bpp+2
        dict = {}
        for i in range(16):
            dict[chr(i)] = i
        dict[chr(2**self.bpp+1)] = 2**self.bpp
        dict[chr(2**self.bpp+2)] = 2**self.bpp+1
        dataStr = chr(2**self.bpp+1) + "".join([chr(item) for item in self.paletteTree.query(image)[1].flatten()]) + chr(2**self.bpp+2)
        ind = 0
        
        bufferInd = 0
        buffer = bytearray(255)
        acc = 0x0
        accInd = 0      
        
        while ind < len(dataStr):
            for j in range(maxLen,0,-1):
                if ind+j <= len(dataStr) and dataStr[ind:ind+j] in dict and currCode < 2**12:
                    acc += dict[dataStr[ind:ind+j]] << accInd
                    accInd += (currCode-1).bit_length()
                    out.append(dict[dataStr[ind:ind+j]])
                    if accInd > 7:
                        buffer[bufferInd] = acc & 0xff
                        acc = acc >> 8
                        accInd -= 8
                        bufferInd += 1
                        if bufferInd == 255:
                            bufferInd = 0
                            self.out.write(b'\xff')
                            self.out.write(buffer)
                    
                    if not dataStr[ind:ind+j+1] in dict and ind != 0 and ind != len(dataStr)-1:
                        dict[dataStr[ind:ind+j+1]] = currCode
                        currCode += 1
                        maxLen = j+1
                    ind += j
        if accInd > 0:
            buffer[bufferInd] = acc & 0xff
            bufferInd += 1
        if bufferInd > 0:
            self.out.write(bufferInd.to_bytes(1,byteorder='big'))
            self.out.write(buffer[:bufferInd])
        
        self.out.write(b'\x00')
        
    def close(self):
        self.out.write(b'\x3B')
        self.out.close()

使用示例

import numpy as np

## Example 1
gif = GifWriter('e1.gif')
gif.writeHeader(3,5)

colors = [0x00,0x00,0x00,0xff,0xff,0xff]
a = np.empty((42))
a[0::3] = np.linspace(255,0,15)[:-1]
a[1::3] = np.linspace(255,0,15)[:-1]
a[2::3] = 0
for b in a.tolist():
    colors.append(int(b))
gif.writePalette(colors)

gif.writeApplicationExtensionLoop()

data = np.asarray([[[0x00,0x00,0x00],[0xff,0xff,0xff],[0xff,0xff,0xff]] , [[0xff,0xff,0xff],[0x00,0x00,0x00],[0xff,0xff,0xff]] , [[0xff,0xff,0x00],[0xdd,0xdd,0x00],[0xbb,0xbb,0x00]] , [[0x99,0x99,0x00],[0x77,0x77,0x00],[0x55,0x55,0x00]] , [[0x33,0x33,0x00],[0x11,0x11,0x00],[0x00,0x00,0x00]]])
gif.writeImage(data,100)
gif.close();


## Example 2
N = 5
gif = GifWriter('e2.gif')
gif.writeHeader(N,N)

colors = [0x00,0x00,0x00,0xff,0xff,0xff]
a = np.empty((42))
a[0::3] = np.linspace(255,0,15)[:-1]
a[1::3] = np.linspace(255,0,15)[:-1]
a[2::3] = 0
for b in a.tolist():
    colors.append(int(b))
gif.writePalette(colors)
gif.writeApplicationExtensionLoop()

data = np.empty((N,N,3))

data[:,:,0] = (np.flip(np.linspace(0,1,N))*np.ones((N,1)))*255
data[:,:,1] = (np.flip(np.linspace(0,1,N))*np.ones((N,1)))*255
data[:,:,2] = 0

data = data.astype(int)
gif.writeImage(data,100)
gif.close();

示例1可正常输出GIF文件，但示例2输出异常，实际效果与预期不符。以下是十六进制dump：

十六进制Dump

Example 1:
           00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

00000000   47 49 46 38 39 61 03 00 05 00 F3 00 00 00 00 00  GIF89a....ó.....
00000010   FF FF FF FF FF 00 EC EC 00 DA DA 00 C8 C8 00 B6  ......ìì.ÚÚ.ÈÈ.¶
00000020   B6 00 A3 A3 00 91 91 00 7F 7F 00 6D 6D 00 5B 5B  ¶.££..⌂⌂.mm.[[
00000030   00 48 48 00 36 36 00 24 24 00 12 12 00 21 FF 0B  .HH.66.$$....!..
00000040   4E 45 54 53 43 41 50 45 32 2E 30 03 01 00 00 00  NETSCAPE2.0.....
00000050   21 F9 04 00 64 00 00 00 2C 00 00 00 00 03 00 05  !ù..d...,.......
00000060   00 00 04 0A 10 84 09 82 20 06 A5 D5 1E 88 00 3B  ...... .¥Õ..;

Example 2:
           00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

00000000   47 49 46 38 39 61 05 00 05 00 F3 00 00 00 00 00  GIF89a....ó.....
00000010   FF FF FF FF FF 00 EC EC 00 DA DA 00 C8 C8 00 B6  ......ìì.ÚÚ.ÈÈ.¶
00000020   B6 00 A3 A3 00 91 91 00 7F 7F 00 6D 6D 00 5B 5B  ¶.££..⌂⌂.mm.[[
00000030   00 48 48 00 36 36 00 24 24 00 12 12 00 21 FF 0B  .HH.66.$$....!..
00000040   4E 45 54 53 43 41 50 45 32 2E 30 03 01 00 00 00  NETSCAPE2.0.....
00000050   21 F9 04 00 64 00 00 00 2C 00 00 00 00 05 00 05  !ù..d...,.......
00000060   00 00 04 0C 50 98 D4 80 4C 55 CC 66 0D 05 B7 46  ....PÔLUÌf..·F
00000070   00 3B                                            .;

问题分析与修正

你的LZW压缩实现存在多个关键错误，导致大图处理失败：

1. CLEAR/END码初始化与使用错误

GIF的LZW规范中：

CLEAR码值为2^bpp（比如bpp=4时为16）
END码值为2^bpp + 1（比如bpp=4时为17）
图像数据必须以CLEAR码开头，END码结尾

你的代码中错误地将END码作为起始码，还使用了不存在的码作为结束码，且字典中CLEAR和END码的映射完全搞反。

2. 未定义变量`out`

代码中out.append(dict[dataStr[ind:ind+j]])里的out从未定义，会抛出NameError，直接删除这行即可。

3. 码长计算逻辑错误

你用(currCode-1).bit_length()计算当前码的长度，这会在码表达到阈值时出错。正确的做法是跟踪当前码长，初始为bpp+1，当currCode达到2^current_code_len时，码长加1（最大到12位）。

4. 码表满时未重置

当currCode达到2^12（4096）时，必须发送CLEAR码，重置字典、码长和currCode，否则后续编码会超出12位限制。

5. 新码添加条件错误

你限制ind !=0才能添加新码，这会导致第一个图像码无法扩展字典，影响压缩逻辑，应该移除该限制，只要不是最后一个字符即可。

修正后的LZW编码部分代码

替换writeImage方法中的Image Data部分：

#Image Data
self.out.write(self.bpp.to_bytes(1,byteorder='big')) #LZW Minimum Code Size

clear_code = 2 ** self.bpp
end_code = clear_code + 1
current_code_len = self.bpp + 1  # 初始码长为bpp+1
max_code = 2 ** current_code_len

# 初始化字典
code_dict = {}
for i in range(2 ** self.bpp):
    code_dict[chr(i)] = i
code_dict[chr(clear_code)] = clear_code
code_dict[chr(end_code)] = end_code

curr_code = end_code + 1
data_str = chr(clear_code) + "".join([chr(item) for item in self.paletteTree.query(image)[1].flatten()]) + chr(end_code)
ind = 0

buffer_ind = 0
buffer = bytearray(255)
acc = 0x0
acc_bits = 0      

while ind < len(data_str):
    # 查找最长匹配的字符串
    match_len = 0
    for j in range(min(len(data_str)-ind, current_code_len), 0, -1):
        substr = data_str[ind:ind+j]
        if substr in code_dict:
            match_len = j
            break
    
    if match_len == 0:
        match_len = 1  # 至少匹配单个字符
    
    code = code_dict[data_str[ind:ind+match_len]]
    # 将码写入缓冲区
    acc |= code << acc_bits
    acc_bits += current_code_len
    
    while acc_bits >= 8:
        buffer[buffer_ind] = acc & 0xff
        acc >>= 8
        acc_bits -= 8
        buffer_ind += 1
        if buffer_ind == 255:
            self.out.write(b'\xff')
            self.out.write(buffer)
            buffer_ind = 0
    
    # 添加新码到字典（如果不是最后一个字符，且码表未满）
    if ind + match_len < len(data_str) and curr_code < 4096:
        new_substr = data_str[ind:ind+match_len+1]
        if new_substr not in code_dict:
            code_dict[new_substr] = curr_code
            curr_code += 1
            # 检查是否需要增加码长
            if curr_code >= max_code and current_code_len < 12:
                current_code_len += 1
                max_code = 2 ** current_code_len
    
    # 处理码表满的情况
    if curr_code >= 4096:
        # 发送CLEAR码
        acc |= clear_code << acc_bits
        acc_bits += current_code_len
        while acc_bits >= 8:
            buffer[buffer_ind] = acc & 0xff
            acc >>= 8
            acc_bits -= 8
            buffer_ind += 1
            if buffer_ind

基于原始字节的GIF编码器：小图正常大图失败，疑LZW实现有误

编码器代码 #

使用示例 #

十六进制Dump #

问题分析与修正 #

1. CLEAR/END码初始化与使用错误 #

2. 未定义变量out #

3. 码长计算逻辑错误 #

4. 码表满时未重置 #

5. 新码添加条件错误 #

修正后的LZW编码部分代码 #