[압축 알고리즘] LZ77 구현

압축 알고리즘을 Node.js로 구현해 봤습니다.

Node.js의 Buffer와 LCS알고리즘을 사용하여 구현했습니다.

 

LZ77 구현

Search buffer size와 Look ahead buffer size는 임의의 값이 아닌 Deflate 알고리즘의 Spec인 32KB와 258을 사용했습니다.

 

소스코드는 다음과 같습니다.

const KILO_BYTE = 1024;
const SEARCH_BUFFER_SIZE = KILO_BYTE * 32;
const LOOK_AHEAD_BUFFER_SIZE = 258;

class LZ77 {
  private searchBufferSize;
  private lookAheadBufferSize;

  constructor(
    searchBufferSize = SEARCH_BUFFER_SIZE,
    lookAheadBufferSize = LOOK_AHEAD_BUFFER_SIZE,
  ) {
    this.searchBufferSize = searchBufferSize;
    this.lookAheadBufferSize = lookAheadBufferSize;
  }

  compress(input: Buffer): Buffer {
    const output: number[] = [];

    let position = 0;

    while (position < input.length) {
      const match = this.findLongestMatch(input, position);

      if (match.length > 0) {
        const nextPosition = position + match.length;
        const nextChar = nextPosition < input.length ? input[nextPosition] : 0;

        const encodedOffset = this.encodeToTwoBytes(match.offset);
        const encodedLength = this.encodeToTwoBytes(match.length);

        output.push(
          encodedOffset[0],
          encodedOffset[1], 
          encodedLength[0], 
          encodedLength[1], 
          nextChar,
        );
        position = nextPosition + 1;
      } else {
        output.push(0, 0, 0, 0, input[position]);
        position++;
      }
    }

    return Buffer.from(output);
  }

  decompress(input: Buffer): Buffer {
    const output: number[] = [];

    let i = 0;

    while (i < input.length) {
      const offsetHigh = input[i++];
      const offsetLow = input[i++];
      const lengthHigh = input[i++];
      const lengthLow = input[i++];
      const nextChar = input[i++];

      const offset = this.decodeFromTwoBytes(offsetHigh, offsetLow);
      const length = this.decodeFromTwoBytes(lengthHigh, lengthLow);

      if (length > 0) {
        const startPoint = output.length - offset;
        for (let j = 0; j < length; j++) {
          output.push(output[startPoint + j]);
        }
      }

      if (nextChar !== 0 || i < input.length) {
        output.push(nextChar);
      }
    }

    return Buffer.from(output);
  }

  private findLongestMatch(
    input: Buffer,
    position: number,
  ): { offset: number; length: number } {
    const searchStartPosition = Math.max(0, position - this.searchBufferSize);
    const match = { offset: 0, length: 0 };

    for (let i = searchStartPosition; i < position; i++) {
      let length = 0;

      while (
        position + length < input.length &&
        i + length < position &&
        input[i + length] === input[position + length] &&
        length < this.lookAheadBufferSize
      ) {
        length++;
      }

      if (length > match.length) {
        match.offset = position - i;
        match.length = length;
      }
    }

    return match;
  }

  private encodeToTwoBytes(num: number) {
    return [(num >> 8) & 0xff, num & 0xff];
  }

  private decodeFromTwoBytes(high: number, low: number) {
    return (high << 8) | low;
  }
}

export default LZ77;

 

 

근데 구현하다가 문제가 발생해서 해당 문제에 대해 공유를 해보려고 합니다.

 

‼️ 문제 발생?

원래의 구현에서는 offset과 length를 1바이트로 인코딩했습니다.

 

짧은 텍스트를 가진 파일을 압축/압축해제 후 원본과 대조하는  테스트를 진행했을 때는 정상적으로 작동했습니다.

하지만 긴 텍스트를 가지고 테스트했을 때, 압축 해제 후 텍스트가  원본과 일치하지 않는 문제가 발생했습니다. 

 

원인을 분석해 보니 offset과 length의 최댓값 때문이었습니다.

LZ77 알고리즘에서:

- offset 최대값: SEARCH_BUFFER_SIZE = 32KB (32,768)

- length 최대값: LOOK_AHEAD_BUFFER_SIZE = 258  

 

그런데 압축 시 (offset, length, literal) 형태로 토큰화할 때,  각 값을 1바이트(0-255 범위)에 저장했습니다.  

 

긴 파일에서 offset이나 length가 255를 초과하면 바이트 오버플로우가  발생해 값이 잘못 저장되었습니다.  

 

예를 들어:

- offset = 300 → 1바이트 저장 시 44로 변환 (300 % 256)

- 압축 해제 시 44 위치를 참조 → 엉뚱한 데이터 복사  

 

이를 수정하기 위해 offset과 length를 2바이트(big-endian)로 인코딩하여  최대 65,535까지 표현 가능하도록 수정했습니다.

private encodeToTwoBytes(num: number) {
return [(num >> 8) & 0xff, num & 0xff];
}

private decodeFromTwoBytes(high: number, low: number) {
return (high << 8) | low;
}