当前位置：首页 > JavaScript

js 实现 lzw

2026-04-06 03:24:34JavaScript

LZW 算法简介

LZW（Lempel-Ziv-Welch）是一种无损数据压缩算法，广泛应用于 GIF 和 TIFF 文件格式中。其核心思想是将输入数据中的重复序列替换为字典中的索引，从而实现压缩。

LZW 压缩实现步骤

初始化一个字典，包含所有可能的单字符作为键，对应的值为索引。

function compress(input) {
    const dictionary = {};
    let nextCode = 256;
    for (let i = 0; i < 256; i++) {
        dictionary[String.fromCharCode(i)] = i;
    }

    let current = '';
    const result = [];
    for (const char of input) {
        const combined = current + char;
        if (dictionary.hasOwnProperty(combined)) {
            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) {
    let 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 (dictionary[code]) {
            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);