반전 지수

Inverted index

컴퓨터 과학에서 반전 인덱스(게시 목록, 게시 파일 또는 반전 파일이라고도 함)는 표 또는 문서 또는 문서 세트(문서에서 콘텐츠로 매핑되는 순방향 인덱스와 대조적으로 이름 지정)에 단어 또는 숫자와 같은 콘텐츠에서 해당 위치로 매핑되는 데이터베이스 인덱스입니다.반전 색인의 목적은 문서가 데이터베이스에 추가될 때 처리량이 증가하여 빠른 전체 텍스트 검색을 가능하게 하는 것입니다.반전된 파일은 인덱스가 아닌 데이터베이스 파일 자체일 수 있습니다.문서 검색 [1]시스템에서 가장 많이 사용되는 데이터 구조이며, 검색 엔진 등에서 대규모로 사용됩니다.또한 ADABAS, DATACOM/DB 및 Model 204를 비롯한 여러 주요 범용 메인프레임 기반 데이터베이스 관리 시스템에서 역목록 아키텍처를 사용했습니다.

반전 인덱스의 주요 변형은 두 가지가 있습니다.레코드 수준의 반전 색인(또는 반전 파일 색인 또는 반전 파일)에는 각 단어의 문서에 대한 참조 목록이 들어 있습니다.단어 수준 반전 색인(또는 전체 반전 색인 또는 반전 목록)에는 문서 [2]내 각 단어의 위치가 추가로 포함됩니다.후자의 양식은 더 많은 기능(구 검색 등)을 제공하지만 더 많은 처리 능력과 공간이 필요합니다.

적용들

반전 인덱스 데이터 구조는 일반적인 검색 엔진 인덱싱 알고리즘의 중심 구성 요소입니다.검색 엔진 구현의 목표는 쿼리 속도를 최적화하는 것입니다. 즉, 단어 X가 발생하는 문서를 찾는 것입니다.문서당 단어 목록을 저장하는 순방향 인덱스가 개발되면 다음으로 반전 인덱스를 개발합니다.순방향 색인을 쿼리하려면 일치하는 문서를 확인하기 위해 각 문서와 각 단어에 대해 순차적으로 반복해야 합니다.이러한 쿼리를 수행하기 위한 시간, 메모리 및 처리 리소스가 기술적으로 항상 현실적인 것은 아닙니다.순방향 인덱스에 문서당 단어를 나열하는 대신 단어당 문서를 나열하는 역색인 데이터 구조를 개발한다.

반전 인덱스를 생성하면 이제 반전 인덱스의 단어 ID로 점프하여 쿼리를 해결할 수 있습니다(임의 액세스를 통해).

컴퓨터 이전 시대에는 중요한 책과 일치하는 것을 수동으로 조립했습니다.이것들은 실질적으로 역지표였고, 그에 수반되는 소량의 해설은 생산하는데 엄청난 노력이 필요했다.

생물정보학에서 반전지수는 배열된 DNA의 짧은 조각의 배열 조합에서 매우 중요하다.파편의 출처를 찾는 한 가지 방법은 참조 DNA 염기서열과 대조하여 파편을 찾는 것입니다.(시퀀스된 DNA와 참조 DNA의 차이 또는 오류로 인해) 소수의 불일치는 단편화(fragment)를 더 작은 조각으로 나누어 설명할 수 있습니다. 적어도 하나의 하위 조각이 참조 DNA 염기서열과 일치할 가능성이 높습니다.매칭은 참조 DNA 배열에서 특정 길이의 모든 서브스트링의 반전 인덱스를 구성해야 합니다.인간의 DNA는 30억 개 이상의 염기쌍을 포함하고 있기 때문에 모든 지수에 DNA 서브스트링과 지수 자체에 32비트 정수를 저장해야 하기 때문에 이러한 반전 지수에 대한 저장 요건은 아마도 수십 기가바이트가 될 것입니다.

압축

역사적 이유로, 역목록 압축과 비트맵 압축은 별도의 연구 라인으로 개발되었고, 나중에야 근본적으로 동일한 [3]문제를 해결하는 것으로 인식되었다.

「 」를 참조해 주세요.

참고 문헌

  • Knuth, D. E. (1997) [1973]. "6.5. Retrieval on Secondary Keys". The Art of Computer Programming (Third ed.). Reading, Massachusetts: Addison-Wesley. ISBN 0-201-89685-0.
  • Zobel, Justin; Moffat, Alistair; Ramamohanarao, Kotagiri (December 1998). "Inverted files versus signature files for text indexing". ACM Transactions on Database Systems. New York: Association for Computing Machinery. 23 (4): 453–490. doi:10.1145/296854.277632. S2CID 7293918.
  • Zobel, Justin; Moffat, Alistair (July 2006). "Inverted Files for Text Search Engines". ACM Computing Surveys. New York: Association for Computing Machinery. 38 (2): 6. doi:10.1145/1132956.1132959. S2CID 207158957.
  • Baeza-Yates, Ricardo; Ribeiro-Neto, Berthier (1999). Modern information retrieval. Reading, Massachusetts: Addison-Wesley Longman. p. 192. ISBN 0-201-39829-X.
  • Salton, Gerard; Fox, Edward A.; Wu, Harry (1983). "Extended Boolean information retrieval". Commun. ACM. ACM. 26 (11): 1022. doi:10.1145/182.358466. hdl:1813/6351. S2CID 207180535.
  • Information Retrieval: Implementing and Evaluating Search Engines. Cambridge, Massachusetts: MIT Press. 2010. ISBN 978-0-262-02651-2.

레퍼런스

  1. ^ Zobel, Moffat & Ramohanarao 1998
  2. ^ Baeza-Yates & Ribeiro-Neto 1999, 192 페이지
  3. ^ 왕지앙구, 린춘빈, 야니스 파파콘스탄티누, 스티븐 스완슨."비트맵 압축과 반전 리스트 압축". 2017.doi: 10.1145/3035918.3064007

외부 링크