Bioinformatics/Algorithms34 쉬프트-OR 문자열 검색 알고리즘의 설명(Shift OR Algorithm) 본 문서는 러시아어로 쓰인 http://habrahabr.ru/post/132128/의 내용의 구글 번역한 후 내용을 이해할 수 있도록 편역한 것이다. 1. 개요 최근에 나는 쉬프트-OR(http://en.wikipedia.org/wiki/Bitap_algorithm) 알고리즘을 이해해야만 했다. 이 알고리즘은 문자열의 부분 문자열을 찾도록 해준다. 이 알고리즘에 대한 분석 결과에 따라서, 나는 이 알고리즘이 어떻게 나의 알고리즘보다 빠르게 동작하는 지 누군가 이해하는데 도움을 줄거라는 기대하에 이 알고리즘에 대해서 쓰려고 마음먹었다. 실제로, "평범한 비교"와 비교하여 이 알고리즘의 주요한 차이점은, 이 알고리즘이 논리 연산에 기반을 두고 있다는 점이다. 소위 말하는 논리 곱(http://en.wiki.. 2012. 12. 29. 퍼지 문자열 검색(Fuzzy string search) 본 문서는 http://ntz-develop.blogspot.de/2011/03/fuzzy-string-search.html의 내용을 번역한 글이다. 원본 문서는 http://habrahabr.ru/post/114997/인 듯 하다. 관련 소스 코드는 https://github.com/polovik/Algorithms/blob/master/bitap.py에 있다. 소개 퍼지 검색 알고리즘(또한, 유사성 검색 알고리즘으로 알려짐)들은 철자 검사기와 구글(Google)과 얀덱스(Yandex) 완성된 검색 엔진의 근본을 이루고 있다. 예를 들어, 이 알고리즘들은 "당신은 ...을 말하려고 하는가요?" 함수를 제공하는데 이용되어져 왔다. 이 글에서, 나는 다음 개념, 방법, 그리고 알고리즘들을 설명할 것이다.:.. 2012. 12. 28. Morphing Match Chain(MMC) 본 문서는 현존하는 압축 프로그램 중 가장 빠른 것으로 보이는 LZ4 알고리즘에 대한 이해를 위해서 해당 알고리즘 저자의 블로그의 내용을 번역한 것이다. 원문은 아래 링크에 있다. http://fastcompression.blogspot.de/p/mmc-morphing-match-chain.html 소개 MMC(Morphing Match Chain)은 2010년 11월에, LZ 압축을 위한 향상된 검색 알고리즘을 위해 개발되었다. 시작은 간단한 해시 체인 방법에서였다. 그것은 여기 포럼 글(http://encode.ru/threads/1155-A-new-match-searching-structure?p=22901&viewfull=1#post22901)에 소개되었고, 새로운 알고리즘으로 선언되었다. (MM.. 2012. 12. 12. GenomeMapper 그래프 구조 본 내용은 내 동료 Jorg의 diploma thesis의 내용 중 일부를 번역한 것이다. 그래프 구조 이전에 설명했듯이, 지놈 서열은 블록들에 저장된다. 여러 개의 블록으로 분기해 확장되어나가는 서열들을 검색하기 위해서, 연결되어 있는 블록들에 대한 연결 정보를 가지고 있어야 한다. 이런 목적으로, 각 블록 테이블 요소는 양 인접한 블록들의 블록 수를 저장한다. 그런 까닭에, 이 구조는 그래프로 해석될 수 있다. 각 블록은 정점(vertex)으로, 그리고 그 연결은 에지(edge)로 해석된다. 지놈은 이제 염기 문자열들을 포함하고 있을 뿐 아니라, 서로 연결된 블록의 문자열들을 포함하고 있다(그림 2.3 (A)). 그림 2.3. 블록들을 포함하는 그래프 구조로 각 블록은 최대 256개의 염기를 저장한다.. 2012. 11. 29. 이전 1 ··· 3 4 5 6 7 8 9 다음
