[강좌]Lucene Index File Format-3

작성일자 글쓴이

텀 사전(Term Dictionary)
텀 사전은 두개의 파일로 구성된다:

1) 텀 정보 파일 또는 .tis 파일

<구조 요약>
TermInfoFile (.tis)–> TIVersion, TermCount, IndexInterval, SkipInterval, TermInfos

<각 인자별 자료형 정의>
TIVersion –> UInt32

TermCount –> UInt64

IndexInterval –> UInt32

SkipInterval –> UInt32

TermInfos –> <TermInfo>^TermCount

TermInfo –> <Term, DocFreq, FreqDelta, ProxDelta, SkipDelta>

Term –> <PrefixLength, Suffix, FieldNum>

Suffix –> String

PrefixLength, DocFreq, FreqDelta, ProxDelta, SkipDelta
–> VInt

이 파일은 텀(Term)에 의해 정렬이 된다. 필드명(필드명은 FieldNum으로 알 수 있다.)에 의해서 처음 정렬이 되고, 내부적으로는 텀텍스트에 의해 정렬이 완료가 되는 것이다.

TIVersion은 현재 루씬 인덱스 파일포멧의 버전을 명시한다. 루씬 1.4일경우 -2

IndexInterval, SkipInterval은 인덱싱을 효율적으로 하기위한 인덱스 옵션중에 하나로서 자세한 설명은 나중에 하도록 하겠다.

Term정보는 내부적으로 알파벳 순으로 정렬이 되어 있기 때문에 Prefix를 공유할 가능성이 매우 많다. 따라서 PrefixLength라는 인자를 두고 쓰게된다. 만일 먼저번 term텍스트가 “bone”이고 그 다음에 오는 텍스트가 “boy”라면 PrefixLength는 2가 되고 Suffix는 “y”가 된다.

FieldNum은 .fdt파일에서 정보를 가져온다.

DocFreq는 해당 텀을 포함한 문서의 갯수이다.

FreqDelta는 .frq파일안에서의 현 텀정보의 위치를 저장한다. 그런데, 이것은 이전 텀의 위치정보를 현 텀의 위치정보값에서 뺀 값을 저장한다. (저장공간의 효율성을 추구한다.) TermInfosWriter클래스의 add메서드를 참고바람.

ProxDelta는 .prx파일안에서의 현 텀정보의 문서내 위치정보를 저장한다. 이것 역시 이전 텀의 위치정보와 현 텀의 위치정보값을 뺀 값을 저장한다. 역시  TermInfosWriter클래스의 add메서드를 참고바람.

SkipDelta는 .frq파일내의 해당텀의 SkipData의 위치정보를 저장한다. 다음 강좌에 나오겠지만 .frq파일은 TermFreqs와 SkipData로 구성된다. 그런데 TermFreqs정보의 길이를 알수 있는 방법이 필요한것이고 SkipData로의 random access하기 위한 정보로 SkipDelta라는 정보를 저장하게 된다. 그래서 SkipDelta는 해당 텀에서의 TermFreqs가 시작한 이후에 SkipData가 나오기까지의 바이트크기를 의미하고 다른 더 쉬운 말로는 TermFreq데이터의 길이라고 말할 수 있다.

TermCount라는건 Term Text에 따른 독창적인 값을 의미하는게 아니다. ‘auther’필드에 ‘John’이 나오고 ‘title’필드에 ‘John’이 나온다고 해서 TermCount에서 1개의 텀으로 갯수를 세는게 아니다. 엄연히 2개의 텀으로 인식이 되고 관리가 된다. 이것은 .frq파일과 .prx파일에서도 동일하다.

2) 텀 정보 인덱스 파일, 또는 .tii 파일.

우~ 이 파일 역시 문서만으로도 부족해서 소스코드를 분석해 봤다. 이야~ 정말 이해하고 나니 아름다운(?) 코드였다. 이걸 보시는 분들 중에서 내용이 좀 약하다거나 뭐 이해가 안간다 하시는 분들은 TermInfosWriter 클래스에서 add메서드를 꼭 참고하시길 바란다. (물론 이 add메서드를 보려면 봐야될게 한두개가 아니지만…쩝)

중요한 개념은 이 파일이 소스코드에 명시된 IndexInterval(initial값은 128로 정해져 있다.)번째의 텀에대한 정보만을 tii파일에 저장을 한다. 물론 tis파일에서의 위치 정보도 그때 함께 저장을 한다. 이 파일은 검색시 메모리에 모두 올라가게끔 되어 있고, 목적은 tis파일에 대한 random access를 하기 위함이다. 128이 정해진 값인데 이 값을 적게한다면 인덱스 수치가 올라가서 메모리 사용량이 증가가 될것이고 그렇지만 검색 속도는 빨라질 것이다. 128보다 크가한다면 그와 반대의 결과가 나오겠다.

이 파일은 기본적으로 tis파일과 구조가 같지만, 단 한가지 정보가 추가가 된다. 뭐냐면 tis에 대한 인덱스 파일이기 때문에 tis파일에 대한 인덱스 정보가 필요한 것이다. 소스코드에서는 128번째마다 정보가 추가되기 때문에 128번째 텀 정보가 추가될때 tii파일이 만들어지고 이에 따른 1)텀 위치정보(tis파일)파일 포인터를 저장하고 있다가 256번째 텀이 추가될때 현재의 파일 포인터로 이전 1)번 포인터정보와의 차이를 저장하고 있는것이다. 그래서 검색시 빠른 메모리 연산을 통해 128의 간격 사이에 원하는 텀이 있는지 없는지 판단을 할 수 있는것이다. 만일 텀이 있다고 판단 되면(판단은 FieldNum과 알파벳 순서로 정렬된 term텍스트값으로 판단을 하게될 것이다.- 이 부분에 대해서는 tis파일의 구조를 잘 살펴보면 알 수 있을것이다.) 그 시작 파일 포인터로 부터 검색을 시작해 나가는 것이다. 정확히 random access는 아니라고 생각되지만 random access를 하기위한 노력으로는 생각이 된다.ㅋ~ 오늘 강좌중에서 백미에 해당하는 부분이고 더 자세히 알고 싶으신 분은 꼭 소스코드를 보길 바란다.(좀 헷갈리지만 볼만은 하다.ㅋ)

<구조 요약>
TermInfoIndex (.tii)–> TIVersion, IndexTermCount, IndexInterval, SkipInterval, TermIndices

<각 인자별 자료형 정의>
TIVersion –> UInt32

IndexTermCount –> UInt64

IndexInterval –> UInt32

SkipInterval –> UInt32

TermIndices –> <TermInfo, IndexDelta>^IndexTermCount

IndexDelta –> VLong

여기서 IndexTermCount는 총 텀 갯수를 IndexInterval로 나눈 몫이 될 것이다.  위에서 주구장창 설명했던 부분이 바로 IndexDelta이다.다른곳은 별 문제 없을 듯하다. 그리고 TermInfo는 위 tis파일에서 설명한 구조 그대로의 정보임을 명심하라.

빈도(Frequencies)

뭐 이것은 정보검색에서 색인구조를 조금만 본 사람이면 다 알 수 있는 파일이다. 바로 Term Frequency(T.F)정보는 저장하는 .frq파일이다.

<구조 요약>
FreqFile (.frq) –> <TermFreqs, SkipData>^TermCount

<각 인자별 자료형 정의>
TermFreqs –> <TermFreq>^DocFreq

TermFreq –> DocDelta, Freq?

SkipData –> <SkipDatum>^(DocFreq/SkipInterval)

SkipDatum –> DocSkip,FreqSkip,ProxSkip

DocDelta,Freq,DocSkip,FreqSkip,ProxSkip –> VInt

TermFreqs 의 정렬 순서는 tis파일과 같다. (Field name에 정렬되고 Term Text에 의해 다시 내부 정렬된다)

TermFreq는 Document Number의 숫자에 따라 오름차순 정렬이 된다.

아까 전에 tis파일에서 TermCount값에 대한 설명을 못했는데, 여기서 설명한다. TermCount는 총 Term의 갯수를 의미한다. 여기서 Term은 중복되지 않는 개체를 의미하며 각 개체의 특징을 구별하는 인자는 FieldNum값과 Term Text 값이 된다. 따라서 같은 Term Text라도 해당되는 필드값에 따라 다른것으로 구분이 되는 것이다.

여기서 루씬이 색인 파일의 용량을 줄여볼라는 참 재밋는 데이터 압축(?) 방법이 나온다.
DocDelta라는 정보쪽을 보면 Freq?라는 부분이 붙어 있다. Freq? 정보는 나올수도 나오지 않을 수도 있다는 이야기이다. DocDelta는 document Number정보와 frequency정보를 둘 다 가지고 있는 격이다. 그러니까 예를 들어 설명하자면

7번 문서에 “검색”이라는 텀이 1번 출현하고 11번 문서에 3번이 출현한다면 TermFreqs의 시퀀스는 “15, 22, 3″으로 출력된다. 15라는 숫자에는 7번문서 번호와 1번이 출현한다는 정보를 가지고 있고 ’22, 3’에는 11번 문서에 3번 출현한다는 정보를 추출할 수 있다. 많은 색인어가 1번 출현하기 때문에 이런 방법은 큰 용량상의 잇점을 가져다 줄것이다. 15/2 를 하면 7.xxx 숫자가 나오고 여기서 정수만 추출해 7번 문서라는 정보를 알 수 있고 또한 15라는 숫자 자체를 ‘문서번호*2+1’의 값으로 계산해 DocDelta가 홀수이면 frequency값이 1임을 표현하게 한 것이다. 그러나 11번 문서는 3번이 출현함으로 ’11*2’를 써주고 그 값이 짝수임으로 추가로 VInt형 데이터를 한번 더 읽어들여 frequeny가 3임을 알 수 있는것이다. 

마지막으로 개인적인 생각은 n-gram으로 색인할 경우에 이 방법에 대한 효과는 더 커질 것이라는 생각을 해본다.

DocSkip은 SkipInterval번째의 문서번호를 저장한다. 여기서 문서번호라는건 이전 SkipInterval에서 문서번호와 현 SkipInterval의 문서번호와의 차이값이다. 만일 DocFreq=35이고 SkipInterval=16 이라면 이곳에는 15번째 문서번호와 31번째 문서번호정보를 포함하는  두곳의 SkipDatum이 존재한다.  여기서 첫번째 FreqSkip는 TermFreqs의 시작부분부터 16번째 SkipDatum이 시작되는 부분까지의 바이트수를 의미한다. 그리고 그 다음에는 16번째 SkipDatum이 시작되는 부분부터 32번째 SkipDatum이 시작되는 부분까지의 바이트수를 의미한다.
그리고 첫번째 ProxSkip은 Positions(.prx 파일 설명때 나옴)의 시작부분에서 16번째 SkipDatum이 시작되는 부분까지의 Positions까지의 바이트수를 의미한다. 또한 두번째 ProxSkip은 16번째 SkipDatum이 시작되는 부분에서부터 32번째 시작부분까지 Positions의 위치에 대한 바이트수를 저장하게 된다.

SkipDatum 정보는 d.f계산을 위함이나 .frq, .prx파일에 빠르게 접근하기 위해 따로 인덱스를 구성해놓은 의미를 가지고 있다. SkipInterval이 적을수록 많은 위치 정보가 입력이 가능해서 빠른 접근이 가능할것이다.

문서내 위치(Positions)
.prx파일은 문서내에서 term이 나타나는 위치에 대한 정보를 가지고 있는 파일이다.

<구조 요약>
ProxFile (.prx) –> <TermPositions>^TermCount

<각 인자별 자료형 정의>
TermPositions –> <Positions>^DocFreq

Positions –> <PositionDelta>^Freq

PositionDelta –> VInt

TermPositions는 텀text에 의해 정렬이 된다. (tis파일에 기반한 – 필드명에 의한 정렬과 텀 text에 의한 정렬)

Positions자체는 문서번호에 따른 오름차순으로 정렬이 된다. (.frq 파일에서 TermFreqs내의 TermFreq의 정렬순서와 같다.)

PositionDelta는 한 문서내에서 먼저번 나온 위치와 현 위치간의 차이값을 의미한다. (0이라면 문서에서 첫번째 값을 의미할것이다. )

예를들어 두개의 문서에서 term이 출현한다고 한다. 첫번째 문서에서는 네번째 텀으로 출현을 하고 두번째 문서에서는 5,9번째 텀에서 해당 텀이 출현 한다고 하면 TermPositions는 이렇게 구성이 될것이다.

“4, 5, 4”

“5,4”는 Freq개수만큼 존재하므로 T.F는 2가 되고, “4”는 한번 출현하므로 T.F는 1이 된다.

정규화 인자(Normalization Factors)
각 문서에는 각 인덱스된 필드를 위한 바이트가 할당된 정규화 파일이 있다. .f[0-9]*파일로서 이 파일은 각 문서마다의 해당 필드의 hits계산에 쓰일 인코딩된 값을 저장하고 있다.

<구조 요약>
Norms (.f[0-9]*) –> <Byte>^SegSize

각 바이트는 부동소수점 표현으로 부호화 된다. 3비트는 가수를 위한 공간이고, 5비트는 지수를 위한 공간으로 할당된다.

이런 바이트값은 아래와 같은 방법으로 IEEE single float 값으로 변환된다.

1. 0바이트이면 0 float값으로 변환
2. 0바이트가 아니라면 sign bit를 0으로 한다.
3. 실제 float지수로 만들기 위해 지수부분에 48을 더한다.
4. 가수의 3비트를 상위로 쉬프트 시키고 낮은 21비트는 0으로 만들어 버린다.

저장된 자료의 왜곡없이 프로그래밍 언어의 float형으로 변환시키기 위한 노력이다.

실제 DefaultSimilarity에서 Normalization Factors를 구하는 부분을 보자면 아래와 같은 코드를 형성한다.

(float)(1.0 / Math.sqrt(numTerms))

여기서 numTerms인자는 문서 하나가 추가될때 함께 추가되는 Field들에 포함되는 텀의 갯수를 의미한다. 그러니 필드 종류별로 .f[0-9]*까지의 파일들을 유지하는 것이다. 

이 정규화식을 잘 보면  0 < norm <= 1.0 의 값이 형성이 되고, 문서의 길이가 굉장히 짧을 경우 norm값은 최대 1.0이 나오는걸 알 수 있다. 메일링을 확인하면 Normalization Factor의 존재 의의는 짧은 문서와 긴 문서에서 색인어를 정규화 하기 위함인데 약간 이 부분에 대한 개인적인 연구가 필요할 듯 하다.(아직 왜 이런식을 쓰는지 이해가 되지는 않는다. 단지 0에서 1사이의 값을 구하기 위함인가?)

이번 강좌에서 중요한 부분은 IndexInterval을 이용한 검색 성능을 향상시킨 부분이다. 특히 tii파일을 이용하는 부분하고 한번 출현하는 term정보의 문서번호와 빈도수를 최소의 저장공간으로 저장하고자 하는 노력부분이 이번 강좌의 백미가 아니였을까 한다.(.frq 부분)그리고 또한 f[0-9]*파일에 ranking을 위해 계산해야될 값을들 저장하는것을 봤다, 아무래도 이 부분에 대한 정확한 이해는 Lucene의 Ranking알고리즘을 이해하고 난 다음이 아닐까 한다.

CC BY-NC 4.0 [강좌]Lucene Index File Format-3 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.