비트맵 알고리즘

Bitap algorithm

비트맵 알고리즘(Shift-or, shift-and 또는 Baeza-Yates-Gonnet 알고리즘이라고도 함)은 대략적인 문자열 매칭 알고리즘이다.알고리즘은 주어진 텍스트가 주어진 패턴과 "대략적으로 동일한" 하위 문자열을 포함하고 있는지 여부를 알려준다. 여기서 대략적인 동등성은 레벤스테인 거리에 따라 정의된다. 하위 문자열과 패턴이 서로 주어진 거리 k 내에 있으면 알고리즘은 이들을 동등하다고 간주한다.알고리즘은 패턴의 각 요소에 대해 1비트를 포함하는 비트마스크 집합을 미리 계산하는 것으로 시작한다.그러면 대부분의 작업을 매우 빠른 비트 연산으로 할 수 있다.

비트맵 알고리즘은 Udi Manber, Sun Wu, Burra Gopal이 작성한 Unix 유틸리티 agrep의 기본 알고리즘 중 하나로 가장 잘 알려져 있다.Manber와 Wu의 원본 논문은 일반적인 정규 표현식의 퍼지 일치를 다루기 위해 알고리즘의 확장을 제공한다.

알고리즘이 요구하는 데이터 구조 때문에 일정한 길이(일반적으로 해당 기계의 단어 길이) 미만의 패턴에서 가장 잘 수행되며, 작은 알파벳보다 입력을 선호하기도 한다.그러나 일단 주어진 알파벳과 단어 길이 m에 대해 구현되면, 그것의 실행 시간은 완전히 예측 가능하다 – 텍스트의 구조나 패턴에 상관없이 O(mn) 운영으로 실행된다.

정확한 스트링 검색을 위한 비트맵 알고리즘은 1964년[1][2] 바린트 뫼몰키에 의해 발명되었고 R. K에 의해 확장되었다.1977년[3] 샤야마순다르(Syamasundar)가 리카르도 배자-예이츠(Ricardo Baeza-Yates)와 개스톤 곤넷(Gaston Gonnet[4])에 의해 재창조되기 전인 1989년(제1저자 박사논문의[5] 한 장)에는 등장인물, 와일드카드, 미스매치 등을 다루도록 확장되기도 했다.1991년에는 맨버와 우에 의해 삽입과 삭제(완전한 퍼지 문자열 검색)도 처리하도록 확장되었다.이 알고리즘은 후에 1996년에 Baeza-Yates와 Navarro에 의해 개선되었다.[8]

정확한 검색

정확한 문자열 검색을 위한 비트맵 알고리즘은 일반적으로 다음과 같이 유사하다.

알고리즘 bitap_search 입력: 문자열로서의 텍스트. 문자열로서의 패턴.출력: m = 0이면 문자열 m := 길이(패턴)를 반환한 다음 /* 비트 배열 R. */ R := 새 배열[m+1]을 초기화하십시오. 초기에는 i := 0의 경우 0 R[0] : 1; i < 길이(텍스트); i += 1 do /* 비트 배열을 업데이트하십시오.*/ k :=m; k ≥ 1; k -= 1 do R[k] := R[k - 1] & (text[i] = 패턴[k - 1]) R[m]이면 반환(텍스트 + i - m) + 1 return null

비트맵은 위의 프로그램의 다음과 같은 수정에서와 같이 단순한 비트 와이즈 연산에 대한 자연스러운 매핑에서 잘 알려진 다른 문자열 검색 알고리즘과 구별된다.이 구현에서 역직관적으로 각 비트는 값이 0인 비트는 일치를 나타내고, 값이 1인 비트는 일치를 나타낸다.0과 1에 대한 직관적인 의미론으로는 동일한 알고리즘을 쓸 수 있지만, 그 경우 우리는 내측 루프에 다른 명령을 도입하여 설정을 해야 한다.R = 1. 이 구현에서 우리는 왼쪽 변위 값이 오른쪽의 0으로 이동한다는 사실을 이용하는데, 이것은 정확히 우리가 필요로 하는 행동이다.

또한 당사가 요구하는 사항도 통지하십시오.CHAR_MAX변환하기 위해 추가 비트마스크(text[i] == pattern[k-1])비트와이즈 운영의 일반 구현 조건.따라서 비트맵 알고리즘은 더 작은 알파벳을 통한 입력에 적용될 때 더 좋은 성능을 발휘한다. 

 #include < 현악기>h>  #include <limits.h>    경시하다 마를 뜨다 *bitap_bitwise_search(경시하다 마를 뜨다 *문자 메시지를 보내다, 경시하다 마를 뜨다 *무늬를 넣다)  {      인트로 m = 끈적끈적하게 하다(무늬를 넣다);      서명이 없는 장기의 R;      서명이 없는 장기의 패턴_마스크[CHAR_MAX+1];      인트로 i;        만일 (무늬를 넣다[0] == '\0') 돌아오다 문자 메시지를 보내다;      만일 (m > 31) 돌아오다 "패턴이 너무 길어!";         /* 비트 어레이 R */ 초기화      R = ~1;        /* 패턴 비트마스크 초기화 */      을 위해 (i=0; i <= CHAR_MAX; ++i)          패턴_마스크[i] = ~0;      을 위해 (i=0; i < m; ++i)          패턴_마스크[무늬를 넣다[i]] &= ~(1UL << i);        을 위해 (i=0; 문자 메시지를 보내다[i] != '\0'; ++i) {          /* 비트 어레이 업데이트 */          R = 패턴_마스크[문자 메시지를 보내다[i]];          R <<= 1;            만일 (0 == (R & (1UL << m)))              돌아오다 (문자 메시지를 보내다 + i - m) + 1;      }        돌아오다 NU LL;  }

퍼지 검색

비트맵 알고리즘을 사용하여 퍼지 문자열 검색을 수행하려면 비트 배열 R을 두 번째 차원으로 확장해야 한다.텍스트의 길이에 따라 변하는 단일 배열 R을 갖는 대신에, 우리는 이제 K 구별 배열 R을1..k 갖게 되었다.배열 R은i 현재 문자열의 접미사와 i 이하 오류의 접미사를 일치시키는 패턴 접두사를 가지고 있다.이러한 맥락에서 "오류"는 삽입, 삭제 또는 대체일 수 있다. 이러한 작업에 대한 자세한 내용은 Levenshtein 거리를 참조하십시오.

아래 구현에서는 퍼지 비트맵 알고리즘을 사용하여 퍼지 매칭(최대 k개의 오류가 있는 첫 번째 매칭을 되돌림)을 수행한다.그러나 대체에만 주의를 기울일 뿐, 삽입이나 삭제에는 주의를 기울이지 않는다. 즉, 해밍 거리 k이다.이전과 마찬가지로 0과 1의 의미론도 종래의 의미와 반대로 되어 있다. 

 #include <stdlib.h>  #include < 현악기>h>  #include <limits.h>    경시하다 마를 뜨다 *bitap_bitwise_search(경시하다 마를 뜨다 *문자 메시지를 보내다, 경시하다 마를 뜨다 *무늬를 넣다, 인트로 k)  {      경시하다 마를 뜨다 *결과 = NU LL;      인트로 m = 끈적끈적하게 하다(무늬를 넣다);      서명이 없는 장기의 *R;      서명이 없는 장기의 패턴_마스크[CHAR_MAX+1];      인트로 i, d;        만일 (무늬를 넣다[0] == '\0') 돌아오다 문자 메시지를 보내다;      만일 (m > 31) 돌아오다 "패턴이 너무 길어!";        /* 비트 어레이 R */ 초기화      R = 만록의((k+1) * 의 크기 *R);      을 위해 (i=0; i <= k; ++i)          R[i] = ~1;        /* 패턴 비트마스크 초기화 */      을 위해 (i=0; i <= CHAR_MAX; ++i)          패턴_마스크[i] = ~0;      을 위해 (i=0; i < m; ++i)          패턴_마스크[무늬를 넣다[i]] &= ~(1UL << i);        을 위해 (i=0; 문자 메시지를 보내다[i] != '\0'; ++i) {          /* 비트 어레이 업데이트 */          서명이 없는 장기의 old_Rd1 = R[0];            R[0] = 패턴_마스크[문자 메시지를 보내다[i]];          R[0] <<= 1;            을 위해 (d=1; d <= k; ++d) {              서명이 없는 장기의 tmp = R[d];              /* 대체란 우리가 신경쓰는 모든 것이다 */              R[d] = (old_Rd1 & (R[d]   패턴_마스크[문자 메시지를 보내다[i]])) << 1;              old_Rd1 = tmp;          }            만일 (0 == (R[k] & (1UL << m))) {              결과 = (문자 메시지를 보내다+i - m) + 1;              부숴뜨리다;          }      }        무료의(R);      돌아오다 결과;  }

참고 항목

외부 링크 및 참조

  1. ^ Barlint Dömömölki, 구문 분석을 위한 알고리즘, 계산 언어학 3, 헝가리 과학 아카데미 페이지 29-46, 1964.
  2. ^ Balint Dömömölki, 생산 규칙에 기초한 범용 컴파일러 시스템, BIT 수치 수학, 8(4), 페이지 262–275, 1968. doi:10.1007/BF01933436
  3. ^ R. K.Shyamasundar, Dömölki의 알고리즘, International Journal of Computer Mathematics, 6(2)pp 105–114, 1977을 사용한 우선 순위 구문 분석.
  4. ^ 리카르도 배자 예이츠."효율적인 텍스트 검색"1989년 5월 캐나다 워털루 대학교 박사 논문.
  5. ^ 우디 만버, 선우 "오류로 빠른 텍스트 검색"기술 보고서 TR-91-11.1991년 6월, 투싼 아리조나 대학의 컴퓨터 과학 학부. (gziped PostScript)
  6. ^ 리카르도 배자 예이츠, 가스톤 H. 곤넷."문자 검색에 대한 새로운 접근 방식"ACM 통신, 35(10): 74–82, 1992년 10월.
  7. ^ 우디 만버, 선우 "오류 허용 가능한 빠른 텍스트 검색"ACM 통신, 35(10): 83–91, 1992년 10월, doi:10.1145/135239.135244.
  8. ^ R. Baeza-Yates와 G. Navarro.대략적인 문자열 일치를 위한 더 빠른 알고리즘.Dan Hirchsberg와 Gene Myers, 편집자, CPM'96, LNCS 1075, 1-23페이지, 어빈, CA, 1996년 6월.
  9. ^ G. Myers."동적 프로그래밍에 기반한 대략적인 문자열 일치를 위한 빠른 비트 벡터 알고리즘."ACM 46(3), 1999년 5월 395–415.
  10. libbitap, 대부분의 정규 표현식에 대해 알고리즘을 쉽게 확장할 수 있는 방법을 보여주는 무료 구현.위의 코드와 달리 패턴 길이에 제한을 두지 않는다.
  11. 리카르도 배자 예이츠, 베스티에 리바이로 네토현대 정보 검색.1999. ISBN0-201-39829-X.
  12. bitap.py - Wu-Manber 수정과 함께 Bitap 알고리즘의 Python 구현.