carryover12.pdf

                              NUMBER OF              LENGTH OF                     NUMBER OF

 SELECTOR             CODES                     EACH CODE (BITS)         UNUSED BITS

 a                             30                            1                                    0

 b                             15                            2                                    0

 c                             10                            3                                    0

 d                             7                              4                                   2

 e                             6                              5                                   0

 f                              5                              6                                   0

 g                             4                              7                                   2

 h                             3                              10                                 0

 i                              2                              15                                 0

 j                              1                              30                                 0

TABLE-1

 

                                                                    possible next selector values

Current selector          a             b             c             d             e              f            g            h              i               j

a                               0             1             2                                                                                                      3

b                               0             1             2                                                                                                      3

c                                             0             1              2                                                                                       3

d                                                            0             1             2                                                                         3

e                                                                          0             1               2                                                         3

f                                                                                          0              1             2                                           3

g                                                                                                        0             1              2                            3

h                                                                                                                       0             1               2            3

i                                                                                                                        0             1               2            3

j                                                                                                                        0             1               2            3

 

TABLE-2

 

 relative-10은 TABLE-1에서처럼 총 10개의 selector가 존재한다.

 

그래서 이름이 relative-10이다.

 

그럼 relative가 의미하는 것은  selector를 선택할때 이전에 선택했던 selector를 기준으로 상대적인 거리를 계산하여 기록하기 때문에 붙여진 이름이다.

예를 들면 이전 selector가 c이었다면 현재 selector로 될수 있는 후보는 b ,c, d, j 이다.

다시 말하면 최대 경우는 수는 4가 되고 이 4를 저장하기 위해 2bit를 사용한다.

 

전체 진행 과정을 예를 들어 설명 하면 다음과 같다.

 

입력되는 포스팅값이 다음과 같이 주어졌다고 가정하자

 1, 3, 9 , 11 ,12, 14

초기 selector를 선택하고 시작할수도 있으나, 여기서는 a를 초기 selector로 하겠다.

-- 데이터를 압축하여 저장할때 기본적으로 데이터 사이의 차이를 저장한다. 차이를 저장하므로써 저장할 수가 작아지기 때문에 효율적으로 데이터 압축이 진행될수 있다. (이것을 보통은 data gap 줄여서 D-gap이라 부른다)

 

a selector가 기본적으로 바뀔수 있는 selector은 a, b, c, j 이다( TABLE-2 참조) 

초기 값이 1, 3, 9, 11, 12, 14 라면 차이값으로 다시 변환하면 아래와 같다.

1, 2, 6, 2, 1, 2

첫번째 숫자 1는 a selector로 저장할수 있기 때문에 selector는 여전히 a이다.

두번째 숫자 2는 a selector로 저장할수 없기 때문에 a보다 큰 selector b를 선택한다.

selector b는 2를 담을수 있기  때문에 현재 selector는 b이다.

세번째 숫자 6은 b selector로 저장할수 없기 때문에 b보다 큰 selector c를 선택한다.

selector c도 6을 담을수 없기 때문에 selector는 마지막 가능한 selector인 j로 이동한다.

 

selector  j는 하나의 데이터만을 저장할수 있기 때문에 첫번째 숫자 1을 저장한

 

여기부터는 다시 위의 과정을 반복한다. 단 j selector에서는 selector가 아래로 이동한다.

2는 selector j로 담기에는 너무 크기 때문에 아래 selector로 이동한다

 selector i 는 2를 담기에는 너무 크기 때문에 아래 selector로 이동한다.

 selector h 는 2를 담기에는 너무 크기 때문에 아래 selector로 이동한다.

 selector g 는 2를 담기에는 너무 크지만 selector에서 이동할수 있는 최대 범위 이기 때문에

더이상의 selector를 아래로 이동하진 못한다.

세번째 숫자 6은  selector g로 저장할수 있기 때문에 현재 selector는 g이다.

세번째 숫자 2은  selector g로 저장할수 있기 때문에 현재 selector는 g이다.

세번째 숫자 1은  selector g로 저장할수 있기 때문에 현재 selector는 g이다.

세번째 숫자 2은  selector g로 저장할수 있기 때문에 현재 selector는 g이다.

 

 

 위와 같은 방식으로 selector는 이전 selector를 기준으로 TABLE-2를 참조하여 이동할수 있다,

selector j일 경우에만 아래(table-2 기준으로 왼쪽)로 이동하고 모든 경우는 위로(table-2기준으로 오른쪽)만 이동한다.

이런 방법으로 위에 든 예처럼 "1, 3, 9 , 11 ,12, 14"은 interger 변수 2개로 모두 표현할수 있다. 

 

 

 

 

 

 

 

 

이 글은 스프링노트에서 작성되었습니다.

'검색' 카테고리의 다른 글

LSH(Locality sensitive hashing)  (0) 2008.10.07
베이지안 정리(Bayes' theorem)  (2) 2007.06.13
끝음절 차트  (0) 2007.06.13
다음 검색에 대한 오해?(google...)  (0) 2007.01.06
Posted by 고요한하늘
,