js 实现 lzw

LZW 压缩算法实现

LZW（Lempel-Ziv-Welch）是一种无损数据压缩算法，适用于文本和图像数据。以下是 JavaScript 实现 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;
}

解压缩函数

解压缩过程将编码数组还原为原始字符串：

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] !== undefined) {
            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);

注意事项

压缩后的输出是数字数组，实际应用中可能需要进一步编码为字节流。对于大文件，需考虑内存管理和分块处理。JavaScript 的字符串处理基于 UTF-16，对于二进制数据需使用 TypedArray 进行优化。

性能优化

对于大型数据，可采用以下优化策略：

• 动态调整字典大小限制
• 使用更高效的数据结构存储字典（如 Trie 树）
• 实现流式处理避免内存溢出

该实现展示了 LZW 的核心逻辑，实际应用时需根据具体场景调整细节。