[algorithm] lucene은 문서를 어떻게 색인합니까?

Program / 글쓴이

Lucene에 대한 문서를 읽었습니다. 또한이 링크 ( http://lucene.sourceforge.net/talks/pisa ) 의 문서를 읽었습니다 .

Lucene이 문서를 색인화하는 방법을 정말로 이해하지 못하고 Lucene이 색인화에 사용하는 알고리즘을 이해하지 못합니까?

위의 링크에서 Lucene은 색인 생성에이 알고리즘을 사용한다고 말합니다.

  • 증분 알고리즘 :
    • 세그먼트 인덱스 스택 유지
    • 들어오는 각 문서에 대한 색인 생성
    • 스택에 새 인덱스 푸시
    • b = 10을 병합 인자로 둡니다. M = 8
for (size = 1; size < M; size *= b) {
    if (there are b indexes with size docs on top of the stack) {
        pop them off the stack;
        merge them into a single index;
        push the merged index onto the stack;
    } else {
        break;
    }
}

이 알고리즘은 최적화 된 인덱싱을 어떻게 제공합니까?

Lucene은 인덱싱을 위해 B- 트리 알고리즘 또는 이와 유사한 다른 알고리즘을 사용합니까? 아니면 특정 알고리즘이 있습니까?

답변

여기에 상당히 좋은 기사가 있습니다 : https://web.archive.org/web/20130904073403/http://www.ibm.com/developerworks/library/wa-lucene/

2014 년 12 월 편집 : 원본이 삭제되어 보관 된 버전으로 업데이트되었습니다. 아마도 가장 최근의 대안은 http://lucene.apache.org/core/3_6_2/fileformats.html입니다.

http://lucene.apache.org/core/4_10_2/core/org/apache/lucene/codecs/lucene410/package-summary.html#package_description에 더 최신 버전이 있지만 정보가 적은 것 같습니다. 더 오래된 것보다.

간단히 말해서, lucene이 문서를 색인화하면 문서를 여러 용어로 나눕니다. 그런 다음 각 용어가 포함 된 문서와 연관된 색인 파일에 용어를 저장합니다. 해시 테이블과 비슷하다고 생각할 수 있습니다.

용어는 각 단어를 어근 형태로 추출하는 분석기를 사용하여 생성됩니다. 영어에서 가장 널리 사용되는 형태소 분석 알고리즘은 Porter 형태소 분석 알고리즘입니다. http://tartarus.org/~martin/PorterStemmer/

쿼리가 실행되면 인덱스를 작성하는 데 사용 된 동일한 분석기를 통해 처리 된 다음 인덱스에서 일치하는 용어를 조회하는 데 사용됩니다. 그러면 쿼리와 일치하는 문서 목록이 제공됩니다.

답변

간단히 말해서 Lucene은 디스크의 Skip-Lists 를 사용하여 반전 된 인덱스를 빌드 한 다음 FST ( 유한 상태 변환기)를 사용하여 인덱스 된 용어 에 대한 매핑을 메모리에 로드합니다 . 그러나 Lucene 은 Lucene의 인덱싱 시스템을 직접 만든 Michael McCandless가 설명한대로 모든 인덱싱 된 용어를 RAM에로드하지 않습니다 (필수) . Skip-Lists를 사용하면 인덱스를 한 적중에서 다른 적중으로 순회 할 수 있으므로 집합 및 특히 범위 쿼리가 가능합니다 (B- 트리와 매우 유사 함). 그리고 Skip-Lists 색인화에 대한 Wikipedia 항목은 Lucene의 Skip-List 구현이 다중 레벨 이라고 불리는 이유를 설명 합니다.Skip-List-본질적으로 O(log n)조회를 가능하게합니다 (다시 말하지만 B- 트리와 매우 유사 함).

따라서 Skip-List 데이터 구조를 기반으로하는 반전 된 (용어) 인덱스 가 문서에서 빌드되면 인덱스가 디스크에 저장됩니다. 그런 다음 Lucene 은 Morfologick에서 느슨하게 영감 을 받은 FST 구현에서 Finite State Transducer에 해당 용어를로드합니다 (이미 말했듯이, 아마도 일부만) .

Michael McCandless (또한)는 Lucene이 (최소 비순환) FST 를 사용하여 Lucene이 메모리에 저장하는 용어를 SortedMap<ByteSequence,SomeOutput>. 이 매핑의 메모리 사용이 부선 형적으로 증가하도록 FST가 바이트 시퀀스 [즉, 색인 된 용어]를 압축하는 방법). 그리고 그는 Lucene이 사용 하는 특정 FST 알고리즘을 설명하는 논문도 지적합니다 .

대부분의 데이터베이스는 (B +를) 사용하는 동안 루씬은, 건너 뛰기-목록을 사용하는 이유는 그 호기심을 위해 – 및 / 또는 (B)를 – 트리, 한 번 봐 걸릴 바로 SO 답변 이 질문에 (B-나무 대 건너 뛰기-목록)에 관한합니다. 그 대답은 상당히 훌륭하고 깊은 설명을 제공합니다. 본질적으로 인덱스의 동시 업데이트를 “더 적절하게”그렇게 만들지는 않습니다 (왜냐하면 B- 트리를 즉시 재조정하지 않기로 결정할 수 있기 때문입니다. Skip-List) 대신 Skip-Lists를 사용하면 밸런싱 작업 (지연 여부에 관계없이) 작업을 하지 않아도 됩니다. (궁극적으로) B- 트리가 필요로합니다 (사실 답변에서 알 수 있듯이 B- 트리와 [다단계] Skip-Lists 중 하나가 “올바른 작업”인 경우에는 성능 차이가 거의 없습니다.)

답변

색인 자체보다 색인 병합에 대한 질문이 더 많은 것 같습니다.

낮은 수준의 세부 정보를 무시하면 인덱싱 프로세스가 매우 간단합니다. Lucene은 문서에서 “역 인덱스”라고하는 것을 형성합니다. 따라서 텍스트가 “To be or not be”이고 id = 1 인 문서가 들어 오면 반전 된 인덱스는 다음과 같습니다.

[to] → 1
[be] → 1
[or] → 1
[not] → 1

이것은 기본적으로 단어에서 주어진 단어를 포함하는 문서 목록 에 대한 색인입니다 . 이 색인 (단어)의 각 줄을 게시 목록이라고합니다. 이 인덱스는 장기 저장소에 유지됩니다.

물론 실제로 상황은 더 복잡합니다.

  • Lucene은 주어진 특정 분석기에 따라 일부 단어를 건너 뛸 수 있습니다.
  • 언어의 유연성을 줄이기 위해 형태소 분석 알고리즘을 사용하여 단어를 사전 처리 할 수 ​​있습니다.
  • 게시 목록에는 문서의 식별자뿐만 아니라 문서 내 주어진 단어의 오프셋 (잠재적으로 여러 인스턴스) 및 기타 추가 정보가 포함될 수 있습니다.

기본적인 이해에 그렇게 중요하지 않은 더 많은 합병증이 있습니다.

하지만 Lucene 색인은 추가 전용 이라는 것을 이해하는 것이 중요 합니다 . 어느 시점에서 애플리케이션은 인덱스의 모든 변경 사항을 커밋 (게시)하기로 결정합니다. Lucene은 색인을 사용하여 모든 서비스 작업을 완료하고 닫으므로 검색에 사용할 수 있습니다. 커밋 후 인덱스는 기본적으로 변경 불가능합니다. 이 색인 (또는 색인 부분)을 세그먼트 라고 합니다 . Lucene이 쿼리 검색을 실행하면 사용 가능한 모든 세그먼트에서 검색합니다.

그래서 질문이 생깁니다. 이미 색인 된 문서를 어떻게 변경할 수 있습니까?

새 문서 또는 이미 인덱싱 된 문서의 새 버전은 새 세그먼트에서 인덱싱되고 소위 kill list를 사용하여 이전 세그먼트에서 무효화 된 이전 버전 입니다. Kill list는 변경 될 수있는 커밋 된 인덱스의 유일한 부분입니다. 짐작할 수 있듯이 오래된 인덱스에는 대부분 제거 된 문서가 포함될 수 있으므로 인덱스 효율성은 시간이 지남에 따라 떨어집니다.

병합이 시작되는 곳입니다. 병합 – 전체적으로보다 효율적인 인덱스를 만들기 위해 여러 인덱스를 결합하는 프로세스입니다. 병합 중에 기본적으로 발생하는 것은 라이브 문서가 새 세그먼트에 복사되고 이전 세그먼트가 완전히 제거되는 것입니다.

이 간단한 프로세스를 사용하여 Lucene은 검색 성능 측면에서 인덱스를 양호한 상태로 유지할 수 있습니다.

도움이되기를 바랍니다.

답변

그것은되는 인덱스를 반전 ,하지만 그것을 사용하는 구조 지정하지 않습니다.
lucene의 인덱스 형식 에는 완전한 정보가 있습니다.
‘파일 확장자 요약’으로 시작하십시오.

먼저 다양한 인덱스에 대해 이야기하고 있음을 알 수 있습니다. 엄밀히 말하면 B- 트리를 사용하는 것은 아니지만 유사점이 있습니다. 위의 구조는 나무와 비슷합니다.

답변