알고리즘 13강 (스트링 알고리즘)

학습개요

1. 지난 시간에 이어 스트링 매칭 알고리즘을 하나 더 살펴본 후, 이번 시간과 다음 시간에 걸쳐 데이터 압축에 대해 살펴본다. 우선 보이어-무어 알고리즘이 스트링 매칭 문제를 해결하는 방법에 대해서 학습하고, 이후 데이터 압축의 개념과 함께 데이터 압축 알고리즘의 하나인 RLE에 대해서 학습한다.

 학습목표

1. 보이어-무어 알고리즘의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
2. 데이터 압축과 관련된 개념을 이해하고 설명할 수 있다.
3. RLE 알고리즘의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.

 주요용어

1. 보이어-무어 (Boyer-Moore) 알고리즘
   패턴 내의 문자들의 관계를 이용하여 매칭 시 중복된 비교를 줄이며 패턴을 찾는 방법으로, 패턴의 뒷부분부터 문자를 비교
2. 데이터 압축 (data compression)
   주어진 데이터를 보다 적은 공간을 사용하여 표현하는 것
3. 무손실 (lossless) 압축
   압축된 데이터로부터 원래의 데이터를 완벽하게 복원할 수 있는 압축 방법
4. 손실 (lossy) 압축
   압축된 데이터로부터 원래의 데이터를 완벽하게 복원할 수 없는 압축 방법
5. 인코딩 (encoding)
   원래의 데이터를 압축된 데이터로 변환하는 것
6. 디코딩 (decoding)
   압축된 데이터를 압축되지 않은 데이터로 변환하는 것
7. RLE (Run Length Encoding)
   스트링에서 동일 문자가 연속해서 나타나는 것을 그 문자와 반복 횟수로 압축하는 방법

정리하기

1. 보이어-무어 알고리즘
    ⦁ 패턴 내의 문자들의 관계를 이용하여 매칭 시 중복된 비교를 줄이며 패턴을 찾는 방법
    ⦁ 텍스트의 첫 위치에서 패턴의 뒷부분부터 문자 비교
    ⦁ 불일치가 발생하거나 매치를 찾으면 불일치 문자 방법과 일치 접미부 방법 중 더 많이 이동시키는 값으로 패턴을 텍스트의 다음 위치로 옮김
   - 불일치 문자 방법 → 불일치한 텍스트의 문자가 패턴에서 가장 마지막에 나타나는 위치로 패턴을 이동
   - 일치 접미부 방법 → 일치한 서브스트링에 대해 접두부와 접미부의 최대 일치 정보만큼 패턴을 이동
    ⦁ 전처리 → 불일치 문자 방법과 일치 접미부 방법을 위한 정보를 구함
    ⦁ 전처리에 O(m)
    ⦁ 매칭은 최악에 O(nm), 최선에 O(n/m)
2. 데이터 압축의 기본 개념
    ⦁ 주어진 데이터를 보다 적은 공간을 사용하여 표현하는 것
    ⦁ 무손실 압축 → 압축된 데이터로부터 원래의 데이터를 완벽하게 복원할 수 있는 압축 방법
   - 종류 → RLE, 허프만 코딩, LZ77 등
    ⦁ 손실 압축 → 압축된 데이터로부터 원래의 데이터를 완벽하게 복원할 수 없는 압축 방법
   - 종류 → JPEG 표준, MPEG 표준 등
    ⦁ 인코딩 → 원래의 데이터를 압축된 데이터로 변환하는 것
    ⦁ 디코딩 → 압축된 데이터를 압축되지 않은 데이터로 변환하는 것
3. RLE
    ⦁ 스트링에서 동일 문자가 연속해서 나타나는 것을 그 문자와 반복 횟수로 압축하는 방법
    ⦁ 인코딩 예 → aaaaabb → (a,5) (b,2)
    ⦁ 디코딩 예 → (a,5) (b,2) → aaaaabb
    ⦁ 성능 → O(n)