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 的核心逻辑，实际应用时需根据具体场景调整细节。
