내가 이해한 색인 압축(index compression)

요즘 관심있게 보는 색인 압축 알고리즘은 다음 세가지이다.

 

simple-9

relative-10

carryover-12

 

뒤에 붙는 숫자는 32bit 안에 몇가지 방법으로 데이터가 들어가는지에 대한 것이고

각각의 이름은 상대적인 의미에서의 naming 같다.

 

 

simple-9의 경우 이전에 살펴본 적이 있기 때문에 굳이 여기서 다시 설명은 하지 않고 간단하게 이야기하면

앞에 4비트에 내가 앞으로 몇바이트씩 사용해서 데이터를 저장하겠다라고 지정하고 데이터를 입력하는 방식으로 세가지 방법중에 가장 간단한 방법이 되겠다.

 

참고적으로 세가지 알고리즘 모두 d-gap을 기본으로 한다.d -gap이란 데이터 사이의 차이를 의미하는것으로 첫번째 데이터가 10인데 두번째 데이터가 12이면 차이는 2가 되고 12를 모두 저장하지 않고 차이값만 저장하는 것을 의미한다.

 

 

relative-10은 앞의 simple-9에서 4bit head를 구성하는것을 조금더 비트를 줄여서 2bit에 저장하는것이다.

2비트로는 4가지를 표현할수 있는데 (00 01 10 11)  쉽게 이야기 하면, 자신의 위치에서 조금더 큰 데이터를 저장하는 앞의 세가지로 데이터를 표현할수 있는지 확인해보고 안되면 가장 큰 값으로 데이터를 저장하겠다라는 의미이다. 그래서 4가지 값으로 표현이 가능한다.

 

마지막으로 carryover-12는 relative-10에서 버리는 비트가 있는데 이 비트까지 아낌없이 이용하겠다는 의미이다.

 

relative-10의 경우

2비트를 헤드로 사용하니까 데이터 영역이 30바이트가 된다.

1비트  , 30개

2비트  , 15개

3비트  , 10개

4비트  , 7개   - 2비트 사용하지 않음

5비트  , 6개

6비트  , 5개

7비트  , 4개   - 2비트 사용하지 않음

10비트, 3개

15비트, 2개 

30비트, 1개

 

지금 기억하기로는 이정도 였던것 같은데

relative-10의 경우 4비트로 저장할때와 7비트로 저장할때 마지막 2비트씩을 사용하지 못하였다.

이런 단점을 극복하기 위해 나온것이 carryover-12이고 남는 2비트에 head값을 쓰는데 사용하는 방식이다.

물론 relative-10보다 압축율을 더 좋고 계산시간은 조금더 사용하는것을 예상해볼수 있다.

 

 

 

첨언 --

 

relative-10이 2bit를 헤더로 사용한다고 했는데

2비트로 가능한것은 relative-10에서 헤더는 앞부분과의 차이값만을 저장하기 때문이다.

( 이동 가능한 head가 총 3가지 이다. 마지막은 무조건 30bit를 저장할수 있는 header j)