서브스크링지수

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "서브스트링 인덱스" – 뉴스 · 신문 · 도서 · 학자 · JSTOR (2021년 12월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

컴퓨터 과학에서 하위 문자열 지수는 하위 선형의 텍스트 또는 텍스트 수집에서 하위 문자열 검색을 제공하는 데이터 구조다.If you have a document ${\displaystyle S}$ of length ${\displaystyle n}$, or a set of documents ${\displaystyle D=\{S^{1},S^{2},\dots ,S^{d}\}}$ of total length ${\displaystyle n}$, you can locate all occurrences of a pattern ${\displaystyle P}$ in ${\displa$$ystyle o(n)}$ 시간$$.(Big O 표기법 참조)

전체 텍스트 색인이라는 문구는 텍스트의 모든 하위 문자열의 색인에도 자주 사용된다.그러나 반전 파일과 문서 검색과 같은 정규 단어 색인에도 사용되기 때문에 모호하다.전체 텍스트 검색을 참조하십시오.

하위 문자열 인덱스에는 다음이 포함된다.

• 접미사 트리
• 접미사 배열
• 텍스트의 모든 N-그램에 대한 반전 파일인 N-그램 인덱스
• 압축 접미사 배열^[1]
• FM-지수
• LZ-지수

참조