Lucen 색인 파일 구조

Contents

문서를 파싱해서 색인으로할 단어의 목록을 만드는건 그리 어려운일이 아니라고 생각된다. 그러나 빠른 검색을 위한 색인 DB포맷을 만드는건 쉬운일이 아니며, 고려해야할 사항들이 많다. 수천만개의 색인 단어에서 원하는 단어를 찾아내어서 가중치 별로 순위를 매긴다거나 boolean, fuzzy, 문장, grouping, field 등의 다양한 검색의 지원을 고려해야 한다. 현재 lucene이 지원하는 검색의 종류에 대해서는 Lucene 검색 및 쿼리문서를 참고하기 바란다.

참고한 할 문서는 아래와 같다.

• lucene Index file format
• Introduction to Text Indexing with Apache Jakarta Lucene
• A tutorail Introduction to full-text Indexing In Java

Lucene 1.9 버전에 정의되어 있는 색인파일에 대해서 알아본다.

Lucene 인덱스의 기본적인 요소는 document, field 와 term으로, 색인은 연속된 이들의 요소를 가지고 있다.

• document : 필드의 연속
• field : term이 속한 영역의 연속된 정보
• Term : 문자열

하나의 동일한 Term이라 할지라도 field가 다르면 서로 다른 Term으로 인식된다. 예를들어 linux 라는 Temr이 있을 때, 문서의 title에서의 linux와 본문에서의 linux는 다른 것으로 인식된다. 이렇게 색인을 함으로써, 검색에서 영역(field)별 검색이 가능하도록 한다. 결국 Term은 <field,term>의 형식으로 저장된다. 색인은 Term기반으로 만들어지며, 효과적인 검색이 가능하도록 구성되어야 한다. Lucene의 인덱스는 indverted index구조를 사용한다. 이것은 term이 키가 되고, document의 정보가 value가 되는 list구조다. 최초 term을 얻어올 때는 document로 부터 term의 목록을 얻어올 것이므로 <document, term>의 리스트가 될 것이다. 이게 <term, document>의 형식으로 역변환 되기 때문에, invert indexing 이라고 한다.

Lucene는 term이 발견된 영역에 따라서 field를 구분해서 저장한다. 다른 말로 Lucene는 Term기반으로 색인을 할때, 각 field별로 tokenized해서 색인을 만든다. 하나의 document가 있다면 title, content, site, anchor등으로 분류해서 색인을 만든다.

Lucene 색인은 segment(multiple sub-indexs)의 조합이다. 각각의 세그먼트는 완전히 독립된 색인을 가지고 있다.

1. 새로운 문서가 추가되면 새로운 segment를 만든다.
2. 기존의 segment와 결합(Merging)한다.

검색기는 다중의 segments에 있는 다수의 색인을 검색하게 된다. 어떤 경우 색인은 여러개의 segment의 조합으로 결정될 수도 있다.

내부적으로 Lucene는 각 문서를 가리키기 위해서 일련의 숫자로된 document number(이하 숫자)를 할당한다. 가장 먼저 추가된 document에는 0이 부여되고, 이후 추가될때 마다 1씩 증가한다.

document를 가리키는 숫자이기 때문에 변경되면 안될거 같지만, document number는 변경이 된다. document number는 다음과 같은 경우에 변경이 된다.

• 각각의 segment내에는 유일한 숫자만이 존재한다.
• 문서가 삭제되면 숫자에 틈이 생길 것이다. 이러한 빈틈은 segment가 합쳐질때 삭제됨으로써 조절된다. 세그먼트가 합쳐지게 되면, 완전히 연속된 일련의 숫자를 가지게 된다. database에서 Vacum작업을 거쳐서 delete된 레코드를 없애주는 것과 같은 이치라고 볼 수 있다.

각각의 segement 색인은 아래의 요소를 관리한다.

• Field name. 색인에서 사용되는 필드이름의 목록을 가지고 있다.
• Sotred Field values. 필드는 나름대로의 속성을 가지고 있다. 필드의 요소가 될 수 있는 url, content, site등은 나중에 문서를 평가할 때, 다른 영향을 줄 수 있기 때문이다. 이들 정보는 각 문서에 대해서 속성(필드)-값의 형태로 저장이된다. 이들 값은 문서를 평가할때 사용된다.
• Term dictionary. 모든 문서의 색인된 필드에서 사용된 모든 단어를 가지고 있는 사전이다. 이 사전은 또한 문서가 가지고 있는 단어의 갯수와 각단어의 출편빈도를 저장한 데이터파일의 포인터, 단어의 문서에서의 위치정보를 가지고 있는 데이터파일의 포인터를 가지고 있다.
• Term Frequency data. 사전에 있는 단어가 각각의 모든 문서에서 얼마나 자주 출현하는지와 얼마나 많은 문서에서 출현하고 있는지에 대한 정보.
• Term Proximity data. 사전에 있는 단어가 문서의 어느곳에 위치하는지에 대한 정보
• Nomalization factors. 문서의 각필드가 가지는 고유 값으로, 문서를 평가할 때 사용된다.
• Term Vectors. 각 문서의 필드에서 문자와 문자의 빈도수가 구성되는데, 이를 Term Vector이라고 한다. 방향(문자)와 크기(빈도수)로 구성되기 때문에 벡터가 된다.
• Deleted documents. 문서가 삭제되었는지를 측정하기 위한 옵션 데이터.

이들 색인의 관리 요소에 대한 자세한 설명은 별도의 장을 할애하도록 하겠다.

8bit로 이루어진 데이터 타입으로 파일은 연속된 바이트 형태로 접근할 수 있다. 모든 데이터 타입의 기본이 되며, 다른 데이터 타입들도 byte데이터타입을 확장한 형태로 사용한다. 파일은 기본 데이터 타입을 바이트로 사용하기 때문에 byte_order(:12)에 독립적이다. 32-bit unsigned inteter로 4바이트로 이루어진다. 상위 바이트가 먼저 출현한다. 32-bit unsigned inteter로 8바이트로 이루어진다. 상위 바이트가 먼저 출현한다. 가변형의 데이터를 타입을 정의하기 위해서 사용한다. 그렇다면 더 읽어야될 데이터가 있는지 없는지를 판단할 수 있어야 하는데, 이를 위해서 바이트의 상위 1bit를 측정값으로 사용한다. 예를 들자면 첫번째 바이트에서는 127(01111111)까지가 저장되고, 두번째 바이트는 128에서 16383까지가 저장되는 방식이다.

VInt를 사용하는 이유는 데이터의 양을 줄이기 위함이다. Lucene는 Java의 modified [http:http://en.wikipedia.org/wiki/UTF-8#Modified_UTF-8 UTF-8 encoding] 를 이용해서 unicode를 지원한다. Lucene는 Vint 타입을 이용해서 문자 데이터를 다룬다.

여기에서는 하나의 색인을 구성하기 위해서 필요한 파일들에 대해서 알아보도록 하겠다. 색인이 있는 세그먼트의 정보를 가지고 있는 info 파일로 파일의 이름은 segments이다. 여기에는 관련된 세그먼트의 목록과 각 세그먼트의 크기를 가지고 있다.

Format	Uint32
NameCounter	Uint32
SegCounter	Uint32
SegSize	Uint32
Format	Uint32
Format	Uint32
Version	Uint64
SegName	String

• Version : Uint
• SegName

색인에 대해서 동시에 여러개의 프로세스가 접근할 수 있으므로, 이를 제어하기 위한 목적으로 사용한다. commit.lock파일이 생겼다면, 이건 프로세스가 segments파일과 색인파일을 다시 쓰고 있음을 의미한다. write.lock파일이 생성되어 있다면, 색인이 추가되거나 제거되었음을 의미한다.

deletable 파일에는 더이상 사용되지 않는 색인에 대한 정보가 들어간다.

필드의 이름이 저장된 파일로 확장자는 .fnm이다. 여기에는 FieldsCount, FieldName, FieldBits등의 정보가 들어간다. 2개의 파일로 이루어진다.

1. 필드 색인을 가지고 있는 .fdx 파일. 여기에는 각 문서에서 필드데이터의 포인터를 가지고 있다. 하나의 문서가 n개의 필드 데이터를 가지고 있다면 Unit64데이터가 n*8 만큼 저장될 것이다.
2. 필드 데이터를 포한 .fdt파일. 여기에는 tokenized 된 각 필드의 정보가 들어간다.

term dictonary는 2개의 파일로 이루어진다.

1. term infos 혹은 tis 파일

|| TermCount || UInt64 ||

IndexInterval	UInt32
SkipInterval	Uint32
TermInfos	<TermInfo>
TermInfo	<Term, DocFreq, FreqDelta, ProxDelta, SkipDelta>
Term	PrefixLength, Suffix, FieldNum
Suffix	String

이 파일은 단어를 저장되며, 사전순으로 정렬되어 있다.

• DocFreq : 단어를 포함한 문서의 갯수
• FreqDelta : .frq파일에는 단어가 어느 문서에 포함되어 있는지 정보를 가지고 있다. FreqDelta는 해당 단어가 시작하는 .frq에서의 위치정보를 가지고 있다.
• ProxDelta : 해당 단어가 문서의 어느위치에 있는지에 대한 정보를 가진다. 이 정보는 검색결과에 대한 요약정보를 보여주기 위해서 중요하게 사용된다.

term info index 혹은 tii파일 tis 파일은 텀의 갯수만큼의 크기를 가지게 될 것이다. 그렇기 때문에 비록 정렬되어 있다고 하더라도, 특정 단어에 대한 정보를 찾으려면 많은 시간이 소모될 수 밖에 없다. tii파일은 tis파일에 대한 random access가 가능하도록 색인 정보를 가지고 있다. 예를 들자면 tii파일은 모든 단어의 정보를 저장하는 대신에 256개씩 마다의 단어와 해당단어의 tis위치에 대한 정보를 가진다. 그렇다면 검색하고자 하는 어떤 단어가 주어졌을때 tii에서 해당 단어보다 한단계 더 작은 단어를 찾아내고, 해당 단어의 tis에서의 위치를 가져온다음 tis파일에서 동일한 단어가 나올때까지 선형검색을 해나가면 될것이다. 이런 식으로 검색 속도를 크게 절약할 수 있다.

Frequencies

.frq 파일은 각 단어를 포함한 모든 문서의 목록을 가지고 있다. 여기에는 <document number, Term #>이 들어가게 된다.

Positions

.prx 파일은 각단어가 문서의 어느위치에서 발견되고 있는지에 대한 정보를 가지고 있다. 단어의 문서에서의 위치는 가장 마지막에 발견된 단어의 위치에서이 차이다. 예를 들어 linux란 단어가 1000번 문서에서 1, 8, 20, 22 에서 발견이 되었다면, 1, 7, 12, 2 이런식으로 위치정보가 들어가게 된다.

Normalization Factors

문서의 각 필드에 대한 정규화 값을 가지며 .f[0-9]*의 확장자를 가진다. 여기에 있는 값들은 문서의 score를 계산할때 곱해지게 된다.

deleted Documents

.del 파일이며, 세그먼트에 삭제된 문서가 존재할 경우에 생성된다. 각 비트가 문서에 대응되며, 1로 세팅될 경우 지워진 것으로 판단한다. 예를 들어 .del파일에 0x00과 0x02 두개의 바이트가 있다면 9번째 문서가 지워졌음을 의미한다.

+-- doc number 0
|
0 0 0 0 0 0 0 0    0 1 0 0 0 0 0 0
                     |
                     +-- doc number 9