압축 접미사 배열

컴퓨터 과학에서 압축 서픽스^[1][2][3] 배열은 패턴 매칭을 위한 압축 데이터 구조입니다.압축된 접미사 배열은 접미사 ^[1][2]배열에서 개선된 일반적인 데이터 구조 클래스입니다.이러한 데이터 구조를 사용하면 인덱스가 비교적 작은 임의의 문자열을 빠르게 검색할 수 있습니다.

압축서픽스 배열은 알파벳 δ에서n글자의 텍스트 T가 주어졌을 때 T 내의 임의의 패턴 검색을 지원한다.입력 패턴 P가 m자일 경우 검색 시간은 일반적으로 O(m) 또는 O(m + log(n))입니다.${\displaystyle \mathrm{일반적}}$으로 사용되는 공간은 O${\displaystyle }$( n ${\displaystyle H_{}}$k${\displaystyle }$(${\displaystyle T}$ )${\displaystyle }$+ $o$ (${\displaystyle }$n$$){ $displaystyle$O ($nH$_ { k$}$ ( T )+$o ($n $)\}$ 입니다.${\displaystyle {여기}_{}}$서 H${\displaystyle {}_{}}$k (${\displaystyle T}$) \ $displaystyle H$_ { $k$} ( $T$)는$$ 텍스트T의 k차수의 경험적 엔트로피입니다.압축된 서픽스 배열을 구성하는 시간과 공간은 $보통{\displaystyle }$O (${\displaystyle n}$) \ $displaystyle$O ($n$ )$$。

압축된 서픽스^[1] 배열의 최초 인스턴스화에서는 O${\displaystyle (n}$ log${\displaystyle }$⁡ ${\displaystyle \sigma \mathrm{}}$ σ σ$$)${\displaystyle }$display ） { $display style$ O$(n,$ {\$log \Sigma$ }$$}비트를$$ 사용하는 $텍스트{\displaystyle }$ T의 크기에 비례하는 선형 공간 데이터 구조만을 사용하여 고속 패턴 매칭이 가능함을 보여줌으로써 오랜 미해결 문제를 해결했습니다.기존의 서픽스 배열 및 서픽스 트리에서는${\displaystyle }\delta {\displaystyle \mathrm{}}$ (${\displaystyle n}$ log$){$ $displaystyle \Omega (n,$ {\$log$ n$})$비트가$$ 사용되고 있습니다.이 비트는 상당히 큽니다.데이터 구조의 기본은 "네이버 함수"를 사용한 재귀적 분해입니다. 이를 통해 접미사 배열은 길이의 절반으로 표시됩니다.결과 접미사 배열이 선형 비트 수를 사용할 때까지 구성이 여러 번 반복됩니다.다음 연구에서는 실제 저장 공간이 0차 엔트로피와 관련이 있으며 인덱스가 자가 ^[4]인덱싱을 지원하는 것으로 나타났다.공간 경계가 더욱 개선되어 고차 엔트로피라는 궁극적인 목표를 달성했습니다. 압축은 인접 함수를 고차 콘텍스트로 분할하고 각 파티션을 웨이브릿 ^[3]트리로 압축함으로써 얻을 수 있습니다.공간 사용률은 다른 최첨단 ^[5]압축기와 매우 경쟁적이며 빠른 패턴 매칭을 지원합니다.

패턴 매칭을 위한 압축 접미사 배열 및 기타 압축 데이터 구조에 의해 이루어지는 메모리 액세스는 일반적으로 현지화되지 않기 때문에 이러한 데이터 구조를 외부 메모리에서 사용하기 위해 효율적으로 설계하는 것은 어려운 것으로 악명 높다.기하학적 이중성을 사용한 최근의 진보에서는 디스크에 의해 제공되는 블록 액세스를 활용하여 I/O^[6] 시간을 대폭 단축하고 외부 메모리의 압축된 서픽스 배열에 대해 잠재적으로 실용적인 검색 성능이 ^[7]입증되었습니다.

오픈 소스 구현

압축 서픽스 배열에는 몇 가지 오픈 소스 구현이 있습니다(아래 외부 링크 참조).Bowtie 및 Bowtie2는 바이오 정보학에서 사용하기 위한 읽기 정렬의 오픈 소스 압축 서픽스 배열 구현입니다.간결한 데이터 구조 라이브러리(SDSL)는 압축 접미사 배열을 포함한 다양한 압축 데이터 구조를 포함하는 라이브러리입니다.FEMTO는 외부 메모리용 압축 서픽스 배열의 구현입니다.또, 원래의 FM-index 실장 등, 다양한 실장이, Pizza & Chili Web 사이트(외부 링크 참조)로부터 입수할 수 있습니다.

「 」를 참조해 주세요.

• FM 색인
• 서픽스 배열

레퍼런스

외부 링크

구현:

• 보타이 및 보타이2
• 간결한 데이터 구조 라이브러리(SDSL)
• 펨토
• 피자&칠리 웹사이트