Bioinformatics61 FM-Index와 역방향 검색(Backwards Search) 본 문서는 http://www.alexbowe.com/fm-indexes-and-backwards-search-32172의 내용을 편역 하였다. 또한, 위키피디아(http://en.wikipedia.org/wiki/FM-index)의 내용을 일부 번역하였다. BWT에 대한 내용은 다음글(http://juggernaut.tistory.com/entry/%EB%B2%84%EB%A1%9C%EC%9A%B0%EC%A6%88%ED%9C%A0%EB%9F%AC-%EB%B3%80%ED%99%98BWT-BurrowsWheeler-transform)을 참고하기 바란다. FM-색인 FM 색인은 문자열에 대해서 BWT를 수행함으로써 얻어질 수 있다. BWT를 수행하게 되면, 행렬의 열은 기본적으로 정렬된 문자열의 접미사가 되고.. 2012. 11. 24. 버로우즈-휠러 변환(BWT, Burrows-Wheeler transform) 이 변환은 블록 정렬 압축으로 불리지만, 실제로는 데이터를 압축하지는 않고 변환만 수행한다. Michael Burrows 씨와 David Wheeler 씨가 켈리포니아의 DEC System Research Center에서 일하면서 고안한 것이다. 이 변환을 수행하게 되면 같은 문자들이 묶여서 반복되는 양상의 문자열이 생성된다. 마찬가지로 데이터의 크기를 줄이지 않지만 비슷한 의미를 가진 전향(MTF, Move To Front) 변환 등과 함께 사용되고 최종적으로는 반복 길이 부호화 인코딩(RLE, Run Length Encoding)과 같은 알고리즘을 이용하여 데이터를 압축하는데 사용되기도 한다. 큰 상관은 없는 이야기이지만, 문자열을 전향 변환으로 처리하는 과정에서 데이터의 반복이 지역적 상관도를 가지.. 2012. 11. 22. 접미사 배열(Suffix Array) 접미사 배열은 접미사 트리의 공간 소모량을 줄이기 위해 고안된 데이터 구조이다. 이 데이터 구조는 아리조나 대학의 Udi Manber 씨와 Gene Myers 씨에 의해서 1989년 5월에 제안되었다.다음은 해당 논문의 연결이다.http://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC8QFjAA&url=http%3A%2F%2Fwebglimpse.net%2Fpubs%2Fsuffix.pdf&ei=5vytUPW1DsK1tAa214HYDA&usg=AFQjCNFj4JQQ2S1vdKZ09py7_SLZ45m_SA&sig2=b_RSaBtaOhl2V_yGzA2gHw 이 데이터 구조는 기본적으로 다음과 같이 생성된다.주어진 문자열에 대.. 2012. 11. 22. 접미사 트라이(Suffix Trie) 본 문서는 다음 내용을 편역 하였다. Suffix array - a contest approach - CS 97SI(http://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCoQFjAA&url=http%3A%2F%2Fcs97si.stanford.edu%2Fsuffix-array.pdf&ei=69ytUIj-DMbvsga-7oH4Dg&usg=AFQjCNHjS8jTxKaXGR8cgK7bedDyIzDCpg&sig2=j7FsJb7lmcZ6bLFY9o_zkw) 소개트라이(trie)는 접미사 트리(Suffix Tree)의 일반화된 개념이다. 트라이는 문자열을 저장하기 위한 트리이다. 트라이의 각 노드는 주어진 문자열에서 사용된 문자.. 2012. 11. 22. 이전 1 ··· 12 13 14 15 16 다음
