정렬 인덱스 와 정렬 인덱스

역 배열 색인 (영어: Inverted index) 은 역방향 색인, 파일 삽입 또는 역방향 파일 이 라 고도 불 리 며 전체 텍스트 검색 에 저 장 된 단어 가 한 문서 나 한 문서 에 저 장 된 위 치 를 나타 내 는 데 사 용 됩 니 다.그것 은 문서 검색 시스템 에서 가장 자주 사용 하 는 데이터 구조 이다.
두 가지 서로 다른 역방향 색인 형식 이 있 습 니 다.
기 록 된 수평 역방향 색인 (또는 역방향 파일 색인) 은 단 어 를 참조 하 는 모든 문서 의 목록 을 포함 합 니 다.한 단어의 수평 역방향 색인 (또는 완전 역방향 색인) 은 각 단어 가 한 문서 에 있 는 위 치 를 포함한다.후자 의 형식 은 더 많은 호환성 (예 를 들 어 구문 검색) 을 제공 하지만 더 많은 시간 과 공간 이 필요 합 니 다.
정 열 색인 이란 색인 문서 에서 키워드 부터 내용 까지, 역 열 색인 은 반대로 키워드 부터 주파수, 위치, 디 렉 터 리 등 정 보 를 검색 하 는 데 사용 된다.인터넷 상의 데 이 터 는 양 이 무한 하여 충분 한 문 서 를 저장 할 수 없 기 때문에 정렬 색인 은 쓸모 가 크 지 않다.
두 가지 서로 다른 역방향 색인 형식 이 있 습 니 다.

기 록 된 수평 역방향 색인 (또는 역방향 파일 색인) 은 단 어 를 참조 하 는 모든 문서 의 목록 을 포함 합 니 다.

한 단어의 수평 역방향 색인 (또는 완전 역방향 색인) 은 각 단어 가 한 문서 에 있 는 위 치 를 포함한다.

우 리 는 아래 의 역방향 파일 색인 을 얻 을 수 있다.

{\displaystyleT_{0}=} "it is what it is"

{\displaystyleT_{1}=} "what is it"

{\displaystyleT_{2}=} "it is a banana"

"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}

검색 조건 "what", "is" 와 "it" 는 이 집합 에 대응 합 니 다.
coll
같은 문자 에 대해 우 리 는 문서 의 수량 과 현재 검색 한 단어 결과 로 구 성 된 쌍 의 데 이 터 를 얻 을 수 있 습 니 다.마찬가지 로 문서 수량 과 현재 검색 한 단어 결 과 는 0 에서 시작 합 니 다.그래서 "banana": {(2, 3)} '바나나' 는 세 번 째 문서 ({\ displaystyle T {2}}} T {2}) 에 있 고 세 번 째 문서 의 위 치 는 네 번 째 단어 (주 소 는 3) 입 니 다.

"a":      {(2, 2)}
"banana": {(2, 3)}
"is":     {(0, 1), (0, 4), (1, 1), (2, 1)}
"it":     {(0, 0), (0, 3), (1, 2), (2, 0)}
"what":   {(0, 2), (1, 0)}

"what is it" 를 검색 하면 이 단어의 모든 단 어 를 얻 을 수 있 습 니 다. 각각의 결 과 는 문서 0 과 문서 1 입 니 다.그러나 이 구문 검색 의 연속 적 인 조건 은 문서 1 에서 만 얻 을 수 있다.
역방향 색인 데이터 구 조 는 전형 적 인 검색엔진 검색 알고리즘 의 중요 한 부분 이다.한 검색엔진 이 실행 하 는 목 표 는 검색 속 도 를 최적화 하 는 것 이다. 문서 에 나타 난 단 어 를 찾 는 것 이다.이전 에는 각 문 서 를 저장 할 단어 목록 을 색인 으로 개발 하고 있 었 으 며, 이어서 방향 을 바 꾸 어 역방향 색인 을 개발 하 였 다.색인 에 대한 조 회 는 모든 문서 의 질서 있 고 빈번 한 전문 조회 와 모든 단어 가 검사 문서 에서 이러한 조 회 를 검증 하 는 것 을 만족 시 킵 니 다.실제로 시간, 메모리, 프로세서 등 자원 의 제한 은 기술적 으로 정방 향 색인 을 실현 할 수 없다.정방 향 색인 을 대체 하 는 모든 문서 의 단어 목록 을 위해 검색 한 단어 마다 있 는 문서 의 목록 을 보 여 주 는 역방향 색인 데이터 구조 가 개발 되 었 습 니 다.역방향 색인 이 만들어 지면 서 현재 조 회 는 즉각 적 인 단어 표 시 를 통 해 결 과 를 신속하게 얻 을 수 있 습 니 다 (무 작위 저장 을 통 해).무 작위 저장 도 일반적으로 순서대로 저장 하 는 것 보다 빠르다 고 여 겨 진다.
구축 방법
단순 법
색인 구축 [4] 은 정렬 표 에서 후진 표 까지 의 구축 과정 에 해당 합 니 다.우리 가 웹 페이지 를 분석 한 후에 얻 은 것 은 웹 페이지 를 위주 로 하 는 색인 표 이다.색인 작성 이 완료 되면 역 배열 표를 받 아야 합 니 다. 구체 적 인 절 차 는 그림 과 같 습 니 다. 절차 설명 은 다음 과 같 습 니 다. 1) 문 서 를 단어 term 태그 라 고 분석 하고 2) hash 를 사용 하여 단어 term 3) 를 다시 만 듭 니 다. 단어 에 역 배열 목록 을 만 드 는 것 은 바로 문서 번호 DocID 입 니 다. 그의 정보 (예 를 들 어 단어 주파수, 단어 위치 등) 가 포함 되 어 있 지 않 습 니 다. 이것 이 바로 간단 한 색인 입 니 다.이 간단 한 색인 기능 은 수천 개의 문 서 를 색인 하 는 등 작은 데이터 에 사용 할 수 있다.그러나 이 는 두 가지 제한 이 있다. 1) 후진 표를 저장 할 충분 한 메모리 가 필요 하 다. 검색엔진 에 있어 서 모두 G 급 데이터 이다. 특히 규모 가 계속 커지 면 우 리 는 이렇게 많은 메모 리 를 제공 할 수 없다.2) 알고리즘 은 순서대로 실행 되 기 때문에 병행 처리 하기 어렵다.
합병 법
병합 법 [4], 즉 메모리 에 있 는 데 이 터 를 디스크 에 쓸 때마다 사전 을 포함 한 모든 중간 결과 정 보 를 디스크 에 기록 합 니 다. 그러면 메모리 의 모든 내용 이 비 워 지고 나중에 색인 을 만 들 면 모든 정액 메모 리 를 사용 할 수 있 습 니 다.병합 색인 병합 색인 그림 병합 설명도: 병합 절차: 1) 페이지 분석, 임시 후진 데이터 색인 A, B 생 성, 임시 후진 데이터 색인 A, B 가 메모리 에 가득 차 면 메모리 색인 A, B 를 임시 파일 에 기록 하여 임시 후진 파일 을 생 성 합 니 다. 2) 생 성 된 여러 임시 후진 파일 에 대해 다 중 병합 을 실행 하고 최종 후진 파일 을 출력 합 니 다.(inverted file). 통합 프로 세 스 통합 프로 세 스 색인 생 성 과정 에서 페이지 분석, 특히 중국어 단 어 는 주요 시간 비용 입 니 다. 알고리즘 의 두 번 째 단 계 는 상대 적 으로 빠 릅 니 다. 이렇게 알고리즘 을 만 드 는 최 적 화 는 중국어 단어 효율 에 집 중 됩 니 다.