当前位置：首页 > JavaScript

js 实现 lzw

2026-03-14 09:20:08JavaScript

LZW 压缩算法简介

LZW（Lempel-Ziv-Welch）是一种无损数据压缩算法，广泛应用于 GIF 图像格式和 Unix 的 compress 命令中。其核心思想是通过动态构建字典表，将重复出现的字符串替换为更短的编码。

LZW 压缩实现步骤

初始化一个字典，包含所有可能的单字符作为键，并为每个键分配一个唯一的编码。

function compress(input) {
    const dictionary = {};
    const result = [];
    let nextCode = 256;

    for (let i = 0; i < 256; i++) {
        dictionary[String.fromCharCode(i)] = i;
    }

    let current = '';
    for (const char of input) {
        const combined = current + char;
        if (combined in dictionary) {
            current = combined;
        } else {
            result.push(dictionary[current]);
            dictionary[combined] = nextCode++;
            current = char;
        }
    }

    if (current !== '') {
        result.push(dictionary[current]);
    }

    return result;
}

LZW 解压实现步骤

初始化字典与压缩时一致，但需要通过编码反向重建字符串。

js 实现 lzw

function decompress(compressed) {
    const dictionary = {};
    let nextCode = 256;

    for (let i = 0; i < 256; i++) {
        dictionary[i] = String.fromCharCode(i);
    }

    let current = String.fromCharCode(compressed[0]);
    let result = current;

    for (let i = 1; i < compressed.length; i++) {
        const code = compressed[i];
        let entry;
        if (code in dictionary) {
            entry = dictionary[code];
        } else if (code === nextCode) {
            entry = current + current[0];
        } else {
            throw new Error('Invalid compressed data');
        }

        result += entry;
        dictionary[nextCode++] = current + entry[0];
        current = entry;
    }

    return result;
}

使用示例

const original = "TOBEORNOTTOBEORTOBEORNOT";
const compressed = compress(original);
const decompressed = decompress(compressed);

console.log("Original:", original);
console.log("Compressed:", compressed);
console.log("Decompressed:", decompressed);
console.log("Match:", original === decompressed);