티스토리

바게의 정보검색
검색하기

블로그 홈

바게의 정보검색

searchall.tistory.com/m

바게소프트를 꿈꾸며...

구독자
0
방명록 방문하기
공지 바게의 정보검색은 모두보기

주요 글 목록

  • [박혜웅] Shift-Or Shift-Or 의 특징 비트병렬성을 기반으로, 머신의 처리단위(워드) 내부에서 비트연산 이용 머신의 처리 단위보다 패턴의 길이가 짧다면 효과적임 성능 전처리 시간,공간복잡도: O(m + ) 검색시 시간복잡도: O(n) Shift-Or 기본 개념 Shift-Or 설명 bit-mask table 가로: 패턴 세로: 패턴에 나타나는 문자종류 패턴에 해당하는 문자가 나타나는 곳만 0으로 세팅. Shift-Or 실행 Shift-Or 소스 int preSo(char *x, int m, unsigned int S[]) { unsigned int j, lim; int i; for (i = 0; i < ASIZE; ++i) S[i] = ~0; for (lim = i = 0, j = 1; i < m; ++i, j 1);.. 공감수 0 댓글수 0 2010. 3. 27.
  • [박혜웅] Knuth-Morris-Pratt(KMP) Knuth-Morris-Pratt 의 특징 패턴내에 반복되는 문자열이 있을 경우, 가장 크게 반복되는 처음 문자열과 윈도우에서 가장 마지막까지 일치했던 부분을 일치시킴(이동) BF에서는 윈도우 이동을 1씩 하지만, KMP에서는 그 이동크기를 최대화 함 일치하지 않은 문자가 발생할 경우, 일치했던 부분을 텍스트에 맞추도록 윈도우 이동 보통 BF보다 많이 빠르지는 않지만, 최악의 경우 길이 n의 텍스트 문자열에 대해 n번의 비교만 수행 성능( text의 길이: n , pattern의 길이 m) 시간 복잡도: O(2m+n) 전처리과정의 시간,공간 복잡도: O(m) 검색시 시간 복잡도: O(n+m) Knuth-Morris-Pratt 설명 텍스트와 패턴의 문자가 일치하지 않을 경우 틀린문자 이전에 텍스트와 패턴이.. 공감수 0 댓글수 0 2010. 3. 27.
  • [박혜웅] Karp-Rabin Karp-Rabin 의 특징 fingerprint 후 hash function 적용 h(k) = k mod q ( q>m, q=prime) 텍스트의 각 윈도우와 패턴에 대하여, 문자열을 십진수(또는 d진수)로 바꾸고 이를 해쉬값으로 변환하여 사용 예: 문자열 "12345" -> 숫자 12345 -> 해쉬값 5 h(x)= mod 5일 경우 성능 전처리과정 시간복잡도: O(m) 검색과정 최악의 시간복잡도: O(mn) 텍스트의 모든 윈도우의 해쉬값이 패턴의 해쉬값과 같을 경우 검색과정 예상 시간복잡도: O(m+n) 텍스트에서 n회 비교하고, 충돌이 없을 경우 발견된 위치에서 텍스트와 패턴이 일치하는지 m회 검증 대부분 해쉬값이 같지 않을 것이므로 일반적으로 O(m+n)일 확률이 높다. fingerprint의 .. 공감수 0 댓글수 0 2010. 3. 27.
  • [박혜웅] Brute Force(BF) Brute Force 의 특징 가장 간단한 문자열 탐색 알고리즘 텍스트에서 모든 가능한 위치에 패턴이 일치하는지 검사 전처리과정이 필요없음 문자가 불일치할때 마다, 텍스트에 대한 윈도우(window)는 왼쪽에서 오른쪽으로 1식 이동한다. 성능 text의 길이: n , pattern의 길이 m 시간복잡도: 평균 시간복잡도: O(n) 최악의 시간복잡도: O(nm) Brute Force 설명 Brute Force 의 실행 Brute Force 소스 void BF(char *x, int m, char *y, int n) { int i, j; /* Searching */ for (j = 0; j = m) OUTPUT(j); } } Brute Force 소스(개선버전) #define EOS '\0' void BF(.. 공감수 0 댓글수 0 2010. 3. 27.
  • [박혜웅] Boyer-Moore-Horspool Boyer-Moore-Horspool의 특징 Boyer-Moore의 2가지 shift 방법중 bad-character shift 만 이용한다. bad-character shift 는 알파벳이 패턴의 길이보다 클 때, 유용하다. Boyer-Moore-Horspool 의 개념 Boyer-Moore의 개념과 동일하며, good-suffix shift 만 사용하지 않는다. Boyer-Moore-Horspool 의 실행 Boyer-Moore-Horspool 의 소스 void HORSPOOL(char *x, int m, char *y, int n) { int j, bmBc[ASIZE]; char c; /* Preprocessing */ preBmBc(x, m, bmBc); /* Searching */ j = 0; .. 공감수 0 댓글수 0 2010. 3. 27.
  • [박혜웅] Boyer-Moore Boyer-Moore의 특징 윈도우는 왼쪽에서 오른쪽으로 이동하며, 패턴내에서 오른쪽에서 왼쪽으로 검사한다. 문자열이 불일치 할 때 대상 text에서 다음 비교를 위해서 이동할 위치를 최대화한 알고리즘이다. 성능 전처리시 공간복잡도 : O(m+) 검색시 시간복잡도: O(mn) 최악의 경우 비교회수: 3n 최상의 경우 비교회수: O(n/m) Boyer-Moore의 설명 일치하지 않는 문자가 나왔을 때 good-suffix shift 또는 bad-character shit 중 큰 값으로 윈도우를 이동한다. good-suffix shift 텍스트와 일치하는 문자열이 패턴에 2개이상 존재하는 경우 텍스트와 일치하는 문자열이 패턴에 1개만 존재하는 경우 bad-character shit 텍스트와 다른 문자가 패턴.. 공감수 0 댓글수 0 2010. 3. 27.
  • [박혜웅] 문자열 매칭 알고리즘(string matching algorithm)의 종류 참고 사이트: http://www-igm.univ-mlv.fr/~lecroq/string/ 참고 자료: 문자열 유한한 길이의 기호들. 가장 간단한 텍스트 모델 w=xyz에 대하여 (x,y,z,w 모두 문자열) x는 w의 접두어(prefix) y는 w의 접미어(suffix) xy는 w의 부문자열(substring) = 연속된 부분 문자열 xz는 w의 부분열(subsequence) = 비연속된 부분 문자열 문자열 사이의 유사성 해밍거리(hamming distance) 같은 문자길이의 두 문자열사이에 다른 문자의 수 (예) d(text, that) = 2 편집거리(edit distance) 한 문자열을 다른 문자열로 변환하기 위해 필요한 작업(입력/삭제/치환)의 최소 수 (예) d(text, tax) = 2 .. 공감수 0 댓글수 0 2010. 3. 27.
  • [박혜웅] 연속된 부분 문자열 (sistring) sistring(시스트링): 텍스트에 대하여, 시작점으로부터 오른쪽끝까지 연속된 substring(부문자열) Semi-Infinite string (반무한 문자열) sistring 은 시작위치(position) 으로 식별됨 text에서 sistring을 생성할 때, 문자,단어,문장,문단 중에서 하나를 선택하여 단위로 사용할 수 있음 주로 단어 단위로 사용(문자단위보다 저장공간이 20%로 감소) sistring 끼리의 비교 "A SA..." < "AMP...." < "E ST...." 공백이 가장 앞이며 나머지는 알파벳순으로 비교 sistring의 예 공감수 0 댓글수 0 2010. 3. 27.
  • [강한구] Shift or 비트로 and, or연산을 통해 문자열 매칭을 하는 알고리즘 이다. 예제를 통해 흐름을 파악해보자 원본 : GCATCGAGAGACGTACG 패턴 : GAGAGACG 우선 비트 마스크를 만든다. (비트마스크는 충분한 길이의 unsigned int형 배열로 선언) 패턴에 해당하지 않는것은 모두 1로 초기화해준다. 나중에 원본텍스트와 or연산시 패턴길이를 정해 주기위해서 lim이 비트마스크 만드는단계에서 필요하다. 패턴이 다섯글자면 하위 4비트를 0, 나머지를 1로 해준다. 예로든 패턴의 lim은 1111111~11110000000 동그라미를 보니 뭔가 감이 잡힌다. . . 우선, 가장 오른쪽 G부터 시작해서 가장 왼쪽 G까지 비트 0이 도달하게 되면 문자가 매칭되었다고 할수있다. 지금까지 매칭을 시작하기 위.. 공감수 0 댓글수 0 2009. 10. 10.
  • [강한구] Brute Force 가장 간단한 알고리즘이다. 만약 찾고자 하는 패턴은 ABTBA, 원본 텍스트는 AAABTABTBAB일 경우 다음과 같은 방법으로 문자열을 찾는다. 패턴의 첫 글자가 매칭되는것을 차례대로 검색하고, 첫글자가 매칭이 되었으면, 그 상태에서 다음글자 매칭, 중간에 글자 매칭이 실패했다면 다시 차례대로 패턴 첫글자부터 검색을 시작한다. 공감수 0 댓글수 0 2009. 10. 9.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.