LZW压缩算法原理及MATLAB实现教程

LZW文档压缩

LZW压缩（LZW compression）是一种由Abraham Lempel、Jacob Ziv和Terry Welch发明的基于表查寻算法把文件压缩成小文件的无损压缩方法。

算法通过建立字典，实现字符重用与编码，LZW的一个特点是压缩后的编码是自解释 (self-explaining) 的。即字典是不会被写进压缩文件，解压缩时可以通过编码后的数据生成字典。 LZW编码算法流程： 步骤1： 开始时的词典包含所有可能的根(Root)，而当前前缀P是空的； 步骤2： 当前字符(C) ：=字符流中的下一个字符； 步骤3： 判断缀-符串P+C是否在词典中  (1) 如果“是”：P ：= P+C // (用C扩展P) ；  (2) 如果“否” ① 把代表当前前缀P的码字输出到码字流; ② 把缀-符串P+C添加到词典; ③ 令P ：= C //(现在的P仅包含一个字符C); 步骤4： 判断码字流中是否还有码字要译  (1) 如果“是”，就返回到步骤2；  (2) 如果“否” ① 把代表当前前缀P的码字输出到码字流; ② 结束。 LZW解码算法流程： 解压步骤如下： (1)译码开始时Dictionary包含所有的根。 (2)读入在编码数据流中的第一个码字 cW(它表示一个Root)。 (3)输出String.cW到字符数据流Charstream。 (4)使pW=cW 。 (5)读入编码数据流的下一个码字cW。 (6)目前在字典中有String.cW吗? YES：1)将String．cW输出给字符数据流； 2)使P=String.pW； 3)使C=String.cW的第一个字符； 4)将字符串P+C添加进Dictionray。 NO ：1)使P=String.pW ； 2)使C=String.pW的第一个字符； 3)将字符串P+C输出到字符数据流并将其添加进Dictionray(现在它与cW相一致)。 (7)在编码数据流中还有Codeword吗? YES：返回(4)继续进行译码。 NO：结束译码[4]   （以上摘录自百度百科）

MATLAB 代码：LZW文本压缩

clc;clear;fclose('all');

%读取文件为字符串

fid = fopen('test.txt');

str = fscanf(fid,'%s');

fclose(fid);

%LZW编码解码

data_en = LZWenco( str );%编码后的数据

data_deco = LZWdeco(data_en);%解码后数据

function [ str_en ] = LZWenco( str )

% 拓展ascii的LZW编码

% 输入为字符串，输出为16位无符号整型数组

table = cell(1,256); 

for i=1:256 

    table{i}=char(i-1); %码表初始化

end 

str_en = [];

P = [];

for i=1:length(str) %遍历字符串

    C=str(i); 

    if ismember([P C],table)

        P = [P C];

    else

        [~,Index] = ismember(P,table);

        str_en = [str_en Index-1];    %如果缀-符在表中不存在，输出前缀

        table{end+1}=[P C];     %把缀-符串添加到表格中

        P = C;                  %令P=C

    end 

end

[~,Index] = ismember(P,table);

str_en = [str_en Index-1]; %最后把缓存在前缀里面的数据输出

str_en = uint16(str_en);

end

function [ str_de ] = LZWdeco( data_en )

%LZW 解码程序

%输入为压缩后的uint16数组

table = cell(1,256); 

for i=1:256 

    table{i}=char(i-1); %码表初始化

end

cW = data_en(1);

str_de = table{cW+1};

for i=2:length(data_en) %遍历数组

    pW = cW;

    cW = data_en(i);

    if cW<length(table) %在字典内

        str_de = [str_de table{cW+1}]; %解码输出cW

        P = table{pW+1};

        C = table{cW+1}(1);

        table{end+1} = [P C]; %增加字典映射P+C

    else

        P = table{pW+1};

        C = table{pW+1}(1);

        table{end+1} = [P C];

        str_de = [str_de table{end}];

    end

end

end

以上代码适用于通信领域，将输入数据简单替换也可以适用于图像压缩。