Efficient Grammar Compression via RLZ-based RePair

이 논문은 메모리 효율성이 낮은 기존 RePair 알고리즘의 단점을 보완하면서도 동일한 문법 구조를 생성하기 위해 RLZ 파싱을 기반으로 한 새로운 압축 기법인 RLZ-RePair 를 제안합니다.

핵심

1. 문제 상황: 도서관이 너무 붐벼요! 📚💥

우리가 가지고 있는 텍스트 데이터 (예: 수백만 개의 바이러스 유전자 서열) 는 마치 거대한 도서관에 쌓인 책들 같습니다. 이 책들을 더 작게 만들기 위해 RePair라는 아주 유명한 정리법이 있습니다.

• RePair의 방식: "가장 자주 나오는 두 글자 조합 (예: 'AA'나 'TG') 을 찾아서, 그걸 하나의 새로운 기호 (예: '4') 로 바꿔버리는 것"입니다.
  • 예: AA가 100 번 나오면, AA를 4로 바꾸고 4가 100 번 나오는 것으로 처리합니다. 이렇게 하면 책이 훨씬 작아집니다.
• 문제점: RePair 는 도서관의 모든 책을 한 번에 테이블 위에 펼쳐놓고 가장 자주 나오는 조합을 찾아야 합니다. 책이 너무 많으면 (데이터가 너무 크면) 테이블이 꽉 차서 (메모리 부족) 작업을 멈추게 됩니다.

2. 대안: 레퍼런스 (Reference) 를 활용하다 🗺️

반면, RLZ라는 다른 방법은 "이미 정리된 참고용 책 (Reference)"을 하나 가져옵니다. 그리고 새로 들어온 책들은 "참고용 책의 5 페이지부터 10 페이지까지 복사한 것"이라고만 적어둡니다.

• 장점: 메모리를 거의 쓰지 않습니다.
• 단점: 책의 구조를 깊이 있게 분석하지 못해, RePair 만큼 작게 압축하지 못합니다.

3. 새로운 해결책: RLZ-RePair (두 마리 토끼를 잡다) 🐇🐇

이 논문은 **"RLZ 의 가벼운 메모리 사용법 + RePair 의 강력한 압축력"**을 합친 RLZ-RePair를 제안합니다.

🎨 비유: 거대한 벽돌 벽을 정리하는 방법

가정해 보세요. 거대한 벽돌 벽 (데이터) 이 있고, 그 벽돌들이 반복되는 패턴으로 쌓여 있습니다.

1. 기존 RePair (무식하게 다 뜯기): 벽돌 하나하나를 모두 바닥에 내려놓고, "어떤 벽돌 조합이 가장 많이 반복되나?"를 찾아서 붙입니다. 벽돌이 너무 많으면 바닥이 꽉 차서 작업이 불가능해집니다.
2. RLZ-RePair (지도 보고 작업하기):
   • 먼저, 벽돌의 **대부분이 이미 있는 '참고용 벽돌 지도 (Reference)'**에서 가져온 것임을 확인합니다.
   • 이제 바닥에 모든 벽돌을 내려놓을 필요가 없습니다. **지도 (Reference)**만 가지고 있으면 됩니다.
   • 지도에서 "여기서 AA 조합이 가장 많이 반복되네?"라고 찾으면, 지도 위의 AA를 4로 바꿉니다.
   • 마법 같은 점: 지도를 바꿨으니, 그 지도를 참조하고 있던 나머지 벽돌들도 자동으로 4로 변합니다!
   • 주의할 점: 가끔 벽돌이 지도의 경계를 넘나드는 경우가 있습니다. 그럴 때는 그 부분만 따로 떼어내어 (Explicit Phrase) 수동으로 정리한 뒤, 지도를 수정합니다.

4. 이 기술의 놀라운 성과 🏆

연구팀은 SARS-CoV-2 (코로나 바이러스) 유전자 데이터와 인간 염색체 데이터를 가지고 실험했습니다.

• 메모리 사용량: 기존 RePair 는 100GB 이상의 메모리가 필요해서 실패했지만, RLZ-RePair 는 **80% 이상 적은 메모리 (약 17GB)**로 성공했습니다.
• 압축률: 메모리는 아끼면서도, 결과물은 기존 RePair 가 만든 것과 거의 똑같이 작고 효율적이었습니다. (다른 대안 방법들보다 더 작은 파일 크기를 냅니다.)
• 속도: 메모리 절약 덕분에 큰 데이터를 다룰 수 있게 되었으며, 속도는 기존 방법보다 약간 느리지만 감당할 만한 수준입니다.

5. 한 줄 요약 💡

"RLZ-RePair 는 거대한 데이터를 다룰 때, 모든 것을 메모리에 올리는 무식한 방법 대신, '참고 지도'를 활용해서 효율적으로 정리하면서도, 결과물은 최고 수준으로 압축하는 똑똑한 기술입니다."

이 기술 덕분에 앞으로는 수백 기가바이트 (GB) 나 되는 거대한 유전체 데이터나 웹 데이터도, 일반 서버에서 충분히 압축하고 분석할 수 있게 될 것입니다.

기술 요약

1. 문제 제기 (Problem)

• RePair 의 한계: RePair 는 인접한 두 심볼 (Bigram) 을 가장 빈번하게 발생하는 순서대로 치환하여 문법 (CFG) 을 생성하는 강력한 오프라인 압축 알고리즘입니다. 그러나 이 방법은 전체 텍스트를 메모리에 로드해야 하므로, 대규모 데이터셋 (예: 게놈 시퀀스) 에서는 메모리 사용량이 입력 크기의 수 배에 달해 실행이 불가능하거나 매우 느려집니다.
• 기존 확장 방법의 결함: Gagie et al. 과 Kim et al. 이 제안한 BigRePair 나 Re2Pair 와 같은 기존 확장 방법들은 rsync 스타일 파싱이나 재귀적 프리픽스 프리 파싱을 사용하여 메모리 효율을 높였습니다. 하지만 이러한 방법은 초기 파싱 단계에서 임의의 구획을 나누기 때문에, 구획 경계를 가로지르는 빈번한 서브스트링을 감지하지 못합니다. 결과적으로 생성된 문법은 원래 RePair 가 생성하는 최적의 계층적 구조를 반영하지 못하며, 이론적 보장이 깨집니다.

2. 방법론 (Methodology: RLZ-RePair)

저자들은 RLZ (Relative Lempel-Ziv) 파싱의 확장성과 RePair의 구조적 정확성을 결합한 RLZ-RePair 알고리즘을 개발했습니다.

• 기본 원리:

  1. RLZ 파싱: 입력 텍스트 $T$를 참조 문자열 $R$에 대해 RLZ 방식으로 파싱합니다. 이때 텍스트는 참조 문자열의 부분 문자열을 가리키는 '구 (Phrase)'들의 시퀀스로 변환됩니다.
  2. 비대칭 처리: 참조 문자열 $R$과 파싱된 구들의 시퀀스를 메모리에 로드합니다. $R$이 입력보다 훨씬 작기 때문에 메모리 사용량을 크게 줄일 수 있습니다.
  3. Bigram 교체 전략:
     • 구 내부 (Within Phrase Boundaries): 가장 빈번한 Bigram 이 $R$ 내에서 발생하고, 해당 구간이 비명시적 구 (Non-explicit Phrase, 즉 $R$의 구간을 가리키는 구) 로 완전히 덮여 있다면, $R$ 내에서만 해당 Bigram 을 치환합니다. $R$의 변경은 이를 가리키는 모든 구에 자동으로 전파되므로, 실제 텍스트 전체를 스캔할 필요가 없습니다.
     • 구 경계 및 부분 겹침 (Boundary Constraints): Bigram 이 구의 경계를 가로지르거나 $R$의 구간과 부분적으로 겹치는 경우, 해당 경계 심볼들을 '명시적 구 (Explicit Phrase)'로 분리하여 처리합니다. 이는 비명시적 구의 무결성을 해치지 않도록 보장합니다.
  4. 데이터 구조: 효율적인 업데이트를 위해 최대 힙 (Max-heap), 증강된 동적 암시적 구간 트리 (Augmented dynamic implicit interval tree), 해시 테이블 등을 사용하여 Bigram 빈도수와 구의 경계를 관리합니다.

• 핵심 아이디어: 참조 문자열 $R$에서 Bigram 을 교체하면, $R$을 참조하는 모든 구 (Phrase) 의 내용이 자동으로 업데이트된다는 점을 활용합니다. 이를 통해 전체 텍스트를 메모리에 올리지 않고도 RePair 와 동일한 문법 구조를 생성할 수 있습니다.

3. 주요 기여 (Key Contributions)

1. 정확한 RePair 문법 생성: 기존 확장 알고리즘 (BigRePair, Re2Pair) 이 구조적 정확성을 희생하는 반면, RLZ-RePair 는 표준 RePair 와 구조적으로 동일한 문법을 생성합니다. 이는 RePair 의 이론적 최적성 (예: 피보나치 문자열에 대한 최적성) 을 유지합니다.
2. 대규모 데이터 확장성: 참조 문자열의 크기에 비례하는 메모리 사용량으로, 기존 RePair 가 처리하지 못했던 수백만 개의 시퀀스나 수십 GB 규모의 데이터를 압축할 수 있습니다.
3. 효율적인 메모리 및 연산: 불필요한 Bigram 교체를 줄이고, 참조 문자열 내에서만 교체를 수행함으로써 메모리 사용량을 획기적으로 감소시켰습니다.

4. 실험 결과 (Results)

저자들은 SARS-CoV-2 게놈 (400,000 개) 과 인간 염색체 19 (1,024 개) 데이터를 사용하여 성능을 평가했습니다.

• SARS-CoV-2 데이터 (400,000 개 시퀀스, 약 11.9 GB):

  • 메모리: 표준 RePair (large_bal) 는 99.88 GB 를 사용했으나, RLZ-RePair (0.5% 참조) 는 17.17 GB만 사용했습니다 (82.8% 감소).
  • 속도: RLZ-RePair 는 RePair 보다 약 27.5% 느렸지만, 메모리 부족으로 실행이 불가능했던 RePair(default) 와 비교하면 실용적입니다.
  • 압축률: 생성된 문법의 크기와 규칙 수는 RePair 와 거의 동일했습니다 (약 20.48 MB). 반면 BigRePair 와 Re2Pair 는 더 많은 규칙을 사용하여 더 큰 파일 크기를 생성했습니다.

• 염색체 19 데이터 (1,024 개 시퀀스, 약 60.5 GB):

  • 성공적 압축: RePair 는 256 개 시퀀스 이상에서 메모리/시간 제한으로 실패했으나, RLZ-RePair 는 전체 1,024 개 시퀀스를 성공적으로 압축했습니다.
  • 메모리 효율: 256 개 시퀀스 기준 RLZ-RePair 는 RePair 대비 83.1% 적은 메모리를 사용했습니다.
  • 압축 품질: RLZ-RePair 와 RePair 는 15.13 GB 데이터를 69.02 MB 로 압축했으나, BigRePair 와 Re2Pair 는 각각 74.38 MB, 78.89 MB 로 더 큰 용량을 차지했습니다.

5. 의의 및 결론 (Significance)

• 실용성과 이론의 조화: RLZ-RePair 는 대규모 데이터 (특히 게놈 데이터) 에 대해 이론적으로 엄밀한 RePair 문법을 생성할 수 있는 최초의 확장 가능한 방법 중 하나입니다.
• 하위 작업의 신뢰성: 생성된 문법이 실제 데이터의 계층적 구조를 정확히 반영하므로, 패턴 매칭, 서브스트링 검색, 또는 머신러닝 토크나이저 등 하위 작업에서 신뢰할 수 있는 결과를 제공합니다.
• 미래 전망: 참조 문자열 (Reference) 선택 전략을 최적화하거나, 작은 구간을 가진 비명시적 구를 초기에 명시적으로 처리하는 등의 추가 연구를 통해 성능을 더욱 향상시킬 수 있는 가능성이 제시되었습니다.

결론적으로, 이 연구는 메모리 병목 현상을 해결하면서도 RePair 의 강력한 압축 성능과 구조적 무결성을 유지하는 획기적인 솔루션을 제시했습니다.