Bioinformatics/Algorithms34 일반화된 접미사 트리 구현(다중 시퀀스로 부터) Java 본 문서는 Bogdan Dorohonceanu씨와 Craig Nevill-Manning 교수님에 의해 2000년 7월 1일에 의해 쓰인 내용을 편역하였다. http://www.drdobbs.com/database/a-practical-suffix-tree-implementation/184404184?pgno=1 접미사 트리는 문자열 검색에 사용된다. 우리 저자들은 이론적으로 언급된 시간 복잡도를 유지하면서 최소한의 자원을 가지고 어떻게 일반화된 접미사 트리 자료 구조를 생성하는지 설명한다. 보그단씨는 대학원 조교이고, 크레이그씨는 Rutgers 대학교의 컴퓨터 과학과 교수님이시다. 그들은 각각 dbogdan@caip.rutgers.edu and nevill@cs.rutgers.edu 로 연락할 수 있다... 2013. 3. 28. 병렬 비트 카운팅(Parallel Bit Counting) 본 문서는 다음의 내용을 번역한 것이다. http://bits.stephan-brumme.com/countBits.html 001: unsigned int countBits(unsigned int x) 02: { 03: // count bits of each 2-bit chunk 04: x = x - ((x >> 1) & 0x55555555); 05: // count bits of each 4-bit chunk 06: x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 07: // count bits of each 8-bit chunk 08: x = x + (x >> 4); 09: // mask out junk 10: x &= 0xF0F0F0F; 11: // add al.. 2013. 1. 12. 두 양수를 유일한 양수키로 변경하기(캔터 쌍짓기 함수) 해시함수를 정의할 때, 두 양의 정수를 하나의 유일한 양의 정수로 변경하여 키값으로 사용을 하려고 할 때가 있다. 이 때 사용할 수 있는 것이 캔터 쌍짓기 함수(Cantor Pairing Function)이다. 이것은 다음과 같이 정의된다. 두 정수값 k1, k2를 입력하면 유일한 값이 결과로 나온다. public int cantorPairing(int k1, int k2) {return 1/2*(k1 + k2)*(k1 + k2 + 1) + k2;} 위와 같이 정의할 수 있을 것이다. 2013. 1. 8. 문자열 차이점 발견 전략(Diff Strategies) 본 문서는 http://neil.fraser.name/writing/diff/의 내용을 번역한 것입니다. 2006년 4월에 네일 프레서(Neil Fraser)에 의해서 두 문자열 간의 차이점을 계산하는 것은 많은 응용 프로그램의 중요 연산이다. 아래는 두 문자열 간의 차이점에 대한 간단한 예제이다. Text 1: Apples are a fruit.Text 2: Bananas are also fruit.Diff: AppleBananas are also fruit. 이 글은 차이 발견 알고리즘에 대한 문헌들을 조사하고, 그것들을 비교하고, 실제 활용엣 그들의 유용성을 증대시키기 위한 여러 기술들을 설명한다. 특별히, 우리는 선행 처리 최적화, 특정 작업을 위한 최적의 차이 발견 알고리즘의 선택, 그리고 사후.. 2012. 12. 29. 이전 1 2 3 4 5 6 7 8 9 다음
