Lucene PostingsFormat 한눈에 보기

NoCoDe·2021년 10월 28일
lucene검색엔진
0

번역 출처 - https://github.com/mocobeta/lucene-postings-format

이 페이지는 Apache Lucene 의 기본 PostingsFormat - 역 색인(인덱스)를 저수준 바이너리 형식으로 표현하여 한눈에 볼 수 있도록 고급사용자를 위해 작성되었습니다.

NOTE: 이 내용은 Lucene 릴리스 버전이 아닌 특정 개정판(커밋)과 관련이 있습니다. 비정기적으로 업데이트되며, 아주 미세한 부분도 생략되는 경우가 많습니다. 더 자세한 내용 및 최신 정보는 공식 문서 또는 소스 코드(후자가 가장 좋습니다)를 참조하십시오.

개요

PostingsFormat (즉, 역 인덱스) 은 대략 두 가지 구성 요소, 즉 용어사전(Term dictionary)과 해당 용어를 포함하는 문서들의 집합 (Posting list)으로 구성 됩니다.

  1. 용어사전(Term dictionary)은 다음의 파일로 구성됩니다:
  2. Postings list는 다음의 파일로 구성됩니다 :

Term Metadata

term metadata 형식 (.tmd file).

+--------+-----------+------------+------------+-----+-----------------+----------------+--------+
| Header | NumFields | FieldStats | FieldStats | ... | TermIndexLength | TermDictLength | Footer |
+--------+-----------+------------+------------+-----+-----------------+----------------+--------+
                     |------- ( # of fields ) -------|
  • Header (CodecHeader)
  • NumFields (VInt) : 인덱스의 모든 필드 수.
  • FieldStats : 필드 레벨 통계 및 메타 데이터.
  • TermIndexLength (Long) : Term Index 전체 길이.
  • TermDictLength (Long) : Term Dictionary 전체 길이.
  • Footer (CodecFooter)

FieldStats

+-------------+----------+----------------+----------+-------------------+--
| FieldNumber | NumTerms | RootCodeLength | RootCode | SumTotalTermFreq? |
+-------------+----------+----------------+----------+-------------------+--

--+------------+----------+---------------+---------+---------------+---------+--
  | SumDocFreq | DocCount | MinTermLength | MinTerm | MaxTermLength | MaxTerm |
--+------------+----------+---------------+---------+---------------+---------+--

--+--------------+-----------+-------------+
  | IndexStartFP | FSTHeader | FSTMetadata |
--+--------------+-----------+-------------+
  • FieldNumber (VInt) : 필드 번호.
  • NumTerms (VLong) : 필드의 고유 용어 수.
  • RootCodeLength (VInt): RootCode의 길이 .
  • RootCode (Bytes) :
  • SumTotalTermFreq (VLong): TF(term frequencies)의 전체 합계 ; 문서 ID만 색인하는 경우 생략.
  • SumDocFreq (VLong) : 문서 빈도(DF)의 합계.
  • DocCount (VInt) : 이 필드가 포함된 문서의 수.
  • MinTermLength (VInt) : MinTerm의 길이.
  • MinTerm (Bytes): 이 필드에 포함된 최소(첫 번째) 용어.
  • MaxTermLength (VInt): MaxTerm의 길이.
  • MaxTerm (Bytes): 이 필드에 포함된 최대(마지막) 용어.
  • IndexStartFP (VLong): 이 필드에 해당하는 Term Index에 대한 파일 포인터.
  • FSTHeader (CodecHeader)
  • FSTMetadata

Term Dictionary

term dictionary 형식. (.tim file)

+--------+-----------+-----------+-----------+-----+--------+
| Header | NodeBlock | NodeBlock | NodeBlock | ... | Footer |
+--------+-----------+-----------+-----------+-----+--------+
         |------------ ( # of blocks ) ------------|
  • Header (CodecHeader)
  • NodeBlock : 블록 단위로 정리된 용어 데이터.
  • Footer (CodecFooter)

NodeBlock

+-------------+--------------+--------+---------------------+---------------
| BlockHeader | SuffixLength | Suffix | SuffixLengthsLength | SuffixLengths 
+-------------+--------------+--------+---------------------+---------------

--+-------------+-----------+-----------+-----------+-----
  | StatsLength | TermStats | TermStats | TermStats | ... 
--+-------------+-----------+-----------+-----------+-----
                |------------- ( # of terms ) ------------

--+----------------+--------------+--------------+--------------+-----+
  | MetadataLength | TermMetadata | TermMetadata | TermMetadata | ... |
--+----------------+--------------+--------------+--------------+-----+
--|                |----------------- ( # of terms ) -----------------|
  • BlockHeader (VInt) : 블록 메타데이터 (예: 블록에 포함된 항목 수).
  • SuffixLength (VLong) : Suffix의 길이.
  • Suffix (Bytes): 블록에 포함된 모든 용어들을 결합한 접미사.
  • SuffixLengthsLength (VInt) : SuffixLengths의 길이.
  • SuffixLengths (Byte) or Bytes) : 블록에 포함된 모든 용어의 접미사 길이.
  • StatsLength (VInt) : TermStats의 전체 길이.
  • TermStats : 용어 레벨 통계.
  • MetaLength (VInt) : TermMetadata의 전체 길이 .
  • TermMetadata

TermStats

+-----------------+---------+----------------+
| SingletonCount? | DocFreq | TotalTermFreq? |
+-----------------+---------+----------------+
  • SingletonCount (VInt) : 용어 앞에 오는 싱글톤 용어의 수 (DF==1, TTF==1) .
  • DocFreq (VInt) : 용어의 문서 빈도.
  • TotalTermFreq (VLong) : 용어의 전체 TF(term frequency); 문서 ID만 색인하는 경우 생략.

TermMetadata

TBD

Term Index

Term index file 형식. (.tip file)

+--------+----------+----------+----------+-----+--------+
| Header | FSTIndex | FSTIndex | FSTIndex | ... | Footer |
+--------+----------+----------+----------+-----+--------+
         |---------- ( # of fields ) -----------|
  • Header (CodecHeader)
  • FSTIndex (Bytes) : 필드 당 바이너리 인코딩 된 FST 인덱스.
  • Footer (CodecFooter)

Frequencies and Skip data

Document and term frequencies file 형식. (.doc file)

+--------+------------------------+------------------------+-----+--------+
| Header | (TermFreqs, SkipData?) | (TermFreqs, SkipData?) | ... | Footer |
+--------+------------------------+------------------------+-----+--------+
         |------------------- ( # of terms ) --------------------|
  • Header (CodecHeader)
  • TermFreqs : 문서 ID 델타 및 용어 빈도.
  • SkipData : 빠른 검색을 위한 스킵(Skip) 리스트 데이터.
  • Footer (CodecFooter)

TermFreqs

+-------------------------------+-------------------------------+-----
| (PackedDocDelta, PackedFreq?) | (PackedDocDelta, PackedFreq?) | ... 
+-------------------------------+-------------------------------+-----
|------------------------- ( # of doc blocks ) -----------------------

--+-------------------+-------------------+-------------------+-----+
  | (DocDelta, Freq?) | (DocDelta, Freq?) | (DocDelta, Freq?) | ... |
--+-------------------+-------------------+-------------------+-----+
--|------------------- (# of remaining docs ) ----------------------|
  • PackedDocDelta (PackedInts) : 블록 압축된 문서 ID의 델타.
  • PackedFreq (PackedInts) : 블록 압축된 TF(term frequencies)의 델타. 용어 출현 위치를 색인하지 않을 때는 생략.
  • DocDelta (VInt) : 문서 ID의 델타.
  • Freq (VInt) : TF(term frequencies)의 델타; 문서 ID만 색인하는 경우 생략.

SkipData

+------------------------------+------------------------------+-----+-----------+
| (SkipLevelLength, SkipLevel) | (SkipLevelLength, SkipLevel) | ... | SkipDatum |
+------------------------------+------------------------------+-----+-----------+
|------------------- ( # of skip levels - 1 ) ----------------------|
  • SkipLevelLength (VLong) : SkipLevel의 길이.
  • SkipLevel
  • SkipDatum : level 0의 Skip datum.

SkipLevel

+-----------+-------------------------------+-------------------------------+-----+
| SkipDatum | (SkipDatum, ChildSkipLevelFP) | (SkipDatum, ChildSkipLevelFP) | ... | 
+-----------+-------------------------------+-------------------------------+-----+
            |--- ( maximum number of skip level for the number of docs seen ) ----|
  • SkipDatum
  • ChildSkipLevelFP (VLong) : 하위 skip level data에 대한 파일 포인터.

SkipDatum

+--------------+----------------+-----------------+---------------------+---------------------+-----------------+--
| SkipDocDelta | SkipDocFPDelta | SkipPosFPDelta? | SkipPosBlockOffset? | SkipPayBlockLength? | SkipPayFPDelta? |
+--------------+----------------+-----------------+---------------------+---------------------+-----------------+--

--+--------------+--------+--------+--------+-----+
  | ImpactLength | Impact | Impact | Impact | ... |
--+--------------+--------+--------+--------+-----+
                 |------- ( # of impacts ) -------|
  • SkipDocDelta (VInt) : 각 블록의 마지막 문서 ID의 델타.
  • SkipDocFPDelta (VLong) : .doc 파일에 있는 각 블록의 파일 포인터.
  • SkipPosFPDelta (VLong) : .pos 파일에 있는 각 관련 블록의 파일 포인터; 용어 출현 위치를 색인하지 않을 때는 생략.
  • SkipPosBlockOffset (VInt) : .pos 파일의 관련 블록 내부 오프셋 값; 용어 출현 위치를 색인하지 않을 때는 생략.
  • SkipPayBlockLength (VInt) : .pay 파일에 있는 각 관련 블록의 페이로드 길이 합계; 용어 출현 위치를 색인하지 않을 때는 생략.
  • SkipPayFPDelta (VLong) : .pay 파일의 각 관련 블록의 파일 포인터; 오프셋/페이로드가 인덱싱되지 않은 경우 생략.
  • ImpactLength (VInt) : Impacts의 전체 길이 .
  • Impact : 빠른 Top-k 검색을 위한 추가 데이터(competitive frequency and norm data).

Impact

+----------------------+-----------------------+
| CompetitiveFreqDelta | CompetitiveNormDelta? |
+----------------------+-----------------------+
  • CompetitiveFreqDelta (VInt)
  • CompetitiveNormDelta (ZLong)

Positions

positions file 형식. (.pos file)

+--------+---------------+---------------+---------------+-----+--------+
| Header | TermPositions | TermPositions | TermPositions | ... | Footer |
+--------+---------------+---------------+---------------+-----+--------+
         |------------------- ( # of terms ) ------------------|
  • Header (CodecHeader)
  • TermPositions : 용어 위치 데이터. 고정 크기의 블록 압축 부분과 나머지 부분으로 구성.
  • Footer (CodecFooter)

TermPositions

+----------------+----------------+-----+------------------+------------------+-----+
| PackedPosDelta | PackedPosDelta | ... | ResidualPosDelta | ResidualPosDelta | ... |
+----------------+----------------+-----+------------------+------------------+-----+
|---------- ( # of pos blocks ) --------|------- ( # of remaining positions ) ------|
  • PackedPosDelta (PackedInts) : 블록 압축된 문서 ID의 델타.
  • ResidualPosDelta : VInt로 인코딩된 나머지 위치의 델타.

ResidualPosDelta

+----------+----------------+----------+--------------+---------------+
| PosDelta | PayloadLength? | Payload? | OffsetDelta? | OffsetLength? |
+----------+----------------+----------+--------------+---------------+
  • PosDelta (VInt) : delta 위치.
  • PayloadLength (VInt) : Payload 길이; 페이로드가 색인되지 않은 경우 생략.
  • Payload (Bytes) : Payload 데이터; 페이로드가 색인되지 않은 경우 생략.
  • OffsetDelta (VInt) : 시작 오프셋 델타; 문자 오프셋이 색인되지 않은 경우 생략.
  • OffsetLength (VInt) : offset 길이 (종료 문자 오프셋에서 시작 문자 오프셋을 뺀 것); 문자 오프셋이 색인되지 않은 경우 생략.

Payloads and Offsets

payloads and offsets file 형식. (.pay file)

+--------+-------------------------------+------------------------------+-----+--------+
| Header | (TermPayloads?, TermOffsets?) | (TermPayloads?, TermOffsets) | ... | Footer |
+--------+-------------------------------+------------------------------+-----+--------+
         |---------------------- ( # of terms ) ------------------------------|
  • Header (CodecHeader)
  • TermPayloads : Payload 데이터; 페이로드가 색인되지 않은 경우 생략.
  • TermOffsets : Offsets 데이터; 문자 오프셋이 색인되지 않은 경우 생략.
  • Footer (CodecFooter)

TermPayloads

+--------------------------------------------------------+--------------------------------------------------------+-----+
| (PackedPayloadLengths, SumPayloadLengths, PayloadData) | (PackedPayloadLengths, SumPayloadLengths, PayloadData) | ... |
+--------------------------------------------------------+--------------------------------------------------------+-----+
|------------------------------------------- ( # of pos blocks ) -------------------------------------------------------|
  • PackedPayloadLengths (PackedInts) : 블록 압축된 페이로드 길이.
  • SumPayloadLengths (VInt) : 이 블록의 페이로드 길이 합계.
  • PayloadData (Bytes) : 이 블록의 모든 페이로드를 결합한 데이터.

TermOffsets

+------------------------------------------+------------------------------------------+-----+
| (PackedOffsetDelta, PackedOffsetLengths) | (PackedOffsetDelta, PackedOffsetLengths) | ... |
+------------------------------------------+------------------------------------------+-----+
|----------------------------------- ( # of pos blocks ) -----------------------------------|
  • PackedOffsetDelta (PackedInts) : 블록 압축된 시작 문자 오프셋의 델타.
  • PackedOffsetLengths (PackedInts) : 블록 압축된 문자 오프셋 길이(종료 문자 오프셋에서 시작 문자 오프셋을 뺀 것).
profile
NoCoDe
Search engine developer / platform architect - software engineer
이전 포스트

elasticsearch : payload-score-query Plugin 개발 기록

다음 포스트

Nori에서 사용자 정의 사전을 사용하는 방법 (How to use a custom dictionary in Nori) - Elasticsearch 8.0 이하

0개의 댓글