반전 된 인덱스 저장

Question

역 색인 생성은 단어를 색인하는 좋은 방법이지만, 내가 혼란스럽게 생각하는 것은 검색 엔진이 실제로 이들을 저장하는 방법입니다. 예를 들어 'google'이라는 단어가 2, 4, 6, 8 번 문서에 서로 다른 빈도로 나타날 경우 어디에 저장해야합니까? 일대 다 관계가있는 데이터베이스 테이블이 데이터베이스 테이블을 저장하는 데 도움이 될 수 있습니까?

Answer 1

각 주요 검색 엔진에는 역 색인을 처리하는 자체 기술이 있습니다. 표준 관계형 데이터베이스 기술을 기반으로하지 않는 것이 적당합니다.

Google의 특정 사례에서 사용 된 현재 기술은 Fay Chang 외 2006 년에 Bigtable: A Distributed Storage System for Structured Data에 기술 된 BigTable 기술에서 파생 된 것으로 추측됩니다. 시스템이 그 이후로 진화했다는 것은 거의 의심의 여지가 없습니다.

Answer 2

완전한 목적의 SQL과 유사한 데이터베이스가이 용도로 사용되는 것은 거의 없습니다. 첫째, 색인 일 뿐이므로 역순환 색인이라고합니다. 각 항목은 단지 참조 용입니다. 비 관계형 데이터베이스와 키 값 저장소가 웹 기술과 관련하여 가장 많이 사용되는 주제로 등장했습니다.

• 쿼리 단어로 한 가지 방법으로 만 데이터에 액세스 할 수 있습니다. 이것이 색인이라고 불리는 이유입니다.
• 각 항목은 문서에 대한 참조 목록/배열/벡터이므로 해당 목록의 각 요소는 매우 작습니다. documentID를 저장하는 것 외의 다른 정보는 각 요소에 대해 tf-idf 점수를 저장하는 것입니다.

사용 방법 :

당신이 ("구글") 다음 당신이 회전이 단어를 문서화하는 역 색인에서 찾아 볼 단일 쿼리 단어가있는 경우 (2,4,6,8 귀하의 예에서). tf-idf 점수가있는 경우 결과를 정렬하여 가장 일치하는 문서를 먼저보고 할 수 있습니다. 그런 다음 문서 ID 2,4,6,8이 참조하는 문서를 찾아보고 해당 URL과 스 니펫 등을보고합니다. URL, 스 니펫 등은 다른 테이블이나 키 - 값 저장소에 저장하는 것이 가장 좋습니다.

여러 개의 검색어 ('google'및 'altavista')가있는 경우 두 검색어에 대해 II를 조사하면 두 개의 문서 ID 목록 (2,4,6,8 및 3,7, 8,11,19). 두 목록 중 교차점을 가져옵니다.이 경우 두 쿼리 단어가 모두 포함 된 문서 목록 인 (8)입니다.

Answer 3

전통적으로 역 색인은 파일에 직접 쓰여지고 어딘가에 디스크에 저장됩니다. 부울 검색 쿼리를 수행하려는 경우 (파일에 쿼리의 모든 단어가 포함되어 있든 없든) 게시물은 파일에 연속적으로 저장되어있는 것처럼 보일 수 있습니다.

Term_ID_1 : Frequency_N : Doc_ID_1, Doc_ID_2, Doc_ID_N.Term_ID_2 : Frequency_N : Doc_ID_1, Doc_ID_2, Doc_ID_N.Term_ID_N : Frequency_N : Doc_ID_1, Doc_ID_2, Doc_ID_N

용어 ID가 기간의 ID이고

주파수는 용어가 나타나는 문서의 수 (즉, 게시 목록의 길이)이며 문서 ID는 해당 용어가 포함 된 문서입니다.

색인과 함께 모든 위치에 파일이 있는지 알아야 매핑이 다른 파일의 어딘가에 저장되어야합니다. 예를 들어, term_id가 주어지면, 맵은 해당 인덱스를 포함하는 파일 위치를 리턴해야하며 그 위치로 탐색 할 수 있습니다. post에는 frequency_id가 기록되므로 파일에서 읽을 doc_ids의 수를 알 수 있습니다.또한 ID와 실제 용어/문서 이름 간의 매핑이 필요합니다.

작은 유스 케이스가있는 경우 게시 목록에 blob을 사용하고 쿼리 할 때 직접 교차를 처리하면 SQL을 사용하여이 작업을 수행 할 수 있습니다.

아주 작은 유스 케이스의 또 다른 전략은 용어 문서 행렬을 사용하는 것입니다.

Answer 4

가능한 해결 방법

한 가지 가능한 솔루션은 위치 인덱스를 사용하는 것입니다. 기본적으로 역 색인이지만 정보를 더 추가하여 색인을 추가합니다. Stanford NLP에서 자세한 내용을 볼 수 있습니다.

예에서는 단어 "안녕하세요"위치 (3,5,6,200) 및 (9,10) 각각에서, 문서 1 및도 3에 나타난 말한다.

• 기본 역 색인,

"hello" => [1,3]

• 첨자가 (우리가 각 문서에 대한 freqs이없는 참고 (주에는 단어 freqs을 찾을 수있는 방법도이 위치가 없습니다) 그러나 우리는 그 용어가 문서에 나타난 정확한 위치를 알고 있습니다.)

"hello" => [1:<3,5,6,200> , 3:<9,10>]

머리는 위로

은 인덱스는 이제 더 많은 크기를 취할 것인가? 내기!

그래서 색인을 압축하는 것이 좋습니다. 간격 인코딩을 사용하여 게시물 목록을 압축하는 여러 옵션과 일반 문자열 압축 알고리즘을 사용하여 사전을 압축하는 더 많은 옵션이 있습니다.

관련 독서는

Postings file compression

Dictionary compression