이원 문자열 매칭 알고리즘

Two-way string-matching algorithm
클래스문자열 검색 알고리즘
데이터 구조순서가 지정된 알파벳 문자열이 있는 문자열
최악의 경우 공연O(n)
베스트 케이스 공연O(n)
최악의 경우 공간 복잡성O(1)

컴퓨터 과학에서 양방향 문자열 매칭 알고리즘은 효율적인 문자열 검색 알고리즘으로, 전진하는 크누스-모리스-프라트 알고리즘과 후진하는 보이어-모어 문자열 검색 알고리즘의 조합으로 볼 수 있다.Maxime Crochemore와 Dominique Perrin은 1991년에 이 알고리즘을 발명했다.[1]사전 처리 시간은 바늘 크기에 선형이다.그것은 2n-m 비교에서 선형적으로 최악의 성능을 가진다.[2]브레슬라우어는 일정한 공간과 n+바닥(1+eps/2 × (n-m) 비교가 있는 것과 로그(m) 공간과 n+바닥(n-m) 비교가 적은 두 가지 개선점을 가지고 있다.[3]

KMP, BM과 마찬가지로 알고리즘은 패턴의 부분적인 반복 주기에 근거한 교대조정을 활용한다.그러나 바늘을 두 부분으로 분할(중요 인자화)하여 그렇게 하므로 사전 처리에서 하나의 값만 기억하면 된다.

알고리즘은 캐시 친화적이고 라이브러리 기능에 의해 대체될 수 있는 운영을 포함하고 있어 실제 조건에서 상당히 효율적인 것으로 간주된다.하위 문자열 함수의 mymmem 및 strstr 계열에 대한 glibc(그리고 파생된 newlib; str-way.h)와 musl 알고리즘으로 선택된다.[4][5][6]그러나 대부분의 고급 문자열 검색 알고리즘과 마찬가지로 건초더미와 바늘의 크기에 손익분기점이 있는 경향이 있는데, 그 이전에는 순진한 2차(메치-메컴) 구현이 더 효율적이다.[7]Glibc는 브레슬라우어 알고리즘을 두 가지 형태로 제공한다.[6]

임계 인자화

중요한 요소화를 정의하기 전에 다음을 정의해야 한다.[1]

  • 인자화: 끈은 두 부분으로 나눌 때 인자화된 것으로 간주된다.문자열 x가 두 부분(u, v)으로 분할되었다고 가정하면, (u, v)를 x。의 인수라고 한다.
  • 마침표: 문자열 x에 대한 마침표 p는 정수 0 < i - x - p, x[i] = x[i + p]의 값으로 정의된다.즉, "p는 거리 p에서 x의 두 글자가 항상 일치한다면 x의 기간이다."x의 최소 주기는 p(x)로 표시된 양의 정수다.
  • (u, v)의 반복은 다음과 같은 x의 하위 문자열이다.
    • w는 u의 접미사 또는 그 반대 방향이다.
    • w는 v의 접두사 또는 그 반대 방향이다.
    즉, w는 절단면 양쪽에서 발생하며 양쪽에서 오버플로가 발생할 수 있다.각각의 요소화에는 최소한 하나의 반복인 현악기가 있다.[2]
  • 국부 기간은 (u, v)에서 반복하는 길이를 말한다.(u, v)에서 가장 작은 국부 기간은 r(u, v)로 표시된다.모든 인자화의 경우 0 < r(u, v) ≤ x .
  • 임계 인자화는 r(u, v) = p(x)와 같은 x의 인자화(u, v)이다.순서 알파벳에서 길이 m의 바늘의 경우, 순서 ≤과 ≥[6]에 대해 정의된 순서의 최대 접미사 두 개 중에서 사전 편찬적으로 더 큰 것을 계산하여 2m 비교로 계산할 수 있다.

알고리즘

알고리즘은 사전 처리 단계로서 바늘의 임계 인자화에 의해 시작된다.이 단계는 주기적인 오른쪽 반의 지수(시작점)와 이 스트레칭의 기간을 산출한다.여기서의 접미사 계산은 저자의 공식에 따른다.그 대신에 더 느리지만 또한 선형 시간인 더 간단한 듀발 알고리즘을 사용하여 계산할 수 있다.[8] 

뒤집기 속기.cmp(a, b) 함수 a > b가 1을 반환하는 경우, a = b가 0을 반환하는 경우, 현재 알려진 기간 중 < b가 반환되는 함수 maxsuf(n, rev) l ← l ← l(n) p ← 1을 반환한다.k ← 주기 시험의 경우 1 지수, maxsuf 시험의 경우 0 < k <= 페이지 j ← 0 지수. maxsuf 시험의 경우 maxsuf 시험의 경우 0 지수.i ← -1 maxsuf의 제안된 시작 지수인 반면, rev cmpv ← -cmpv - -cmpv가 더 작으면 비교를 반전시킨다. 기간은 지금까지의 전체 접두사 입니다. j ← j + k k ← 1 p ← j - i 이외의 경우 cmpv = 0이면 - 계속 진행해야 한다. k = p. reset k. j ← j + p k ← 1 다른 k ← k + 1의 스트레칭 확인은 끝났다.접미사가 더 크다. 여기서부터 다시 시작. i ← j ← j + 1 p ← 1 k ← 1 return return [i, p] 함수 crit_fact(n) [idx1, per1] ← maxsuf(n, false) [idx2, true] idx1 > idx2 idx2가 반환되는 경우 [idx2, per1] 다른 반환

비교는 오른쪽에서 먼저 매칭한 다음, 일치하는 경우 왼쪽에서 매칭하는 방식으로 진행된다.선형 시간 건너뛰기는 기간을 사용하여 수행한다. 

함수 일치(n, h) nl ← len(n) hl ← len(h) [l, p] ← crit_fact(n) P ← {}의 일치 집합.접미사를 일치시킨다.memcmp와 같은 라이브러리 함수를 사용하거나, 자신만의 루프를 쓰십시오. n[0]인 경우...n[l] = n[l+1] ...n[l+p] P ← {} pos ← 0 s ← 0 TODO. 최소한 스킵을 넣는다.

참조

  1. ^ a b Crochemore, Maxime; Perrin, Dominique (1 July 1991). "Two-way string-matching" (PDF). Journal of the ACM. 38 (3): 650–674. doi:10.1145/116825.116845. S2CID 15055316.
  2. ^ a b "Two Way algorithm".
  3. ^ Breslauer, Dany (May 1996). "Saving comparisons in the Crochemore-Perrin string-matching algorithm". Theoretical Computer Science. 158 (1–2): 177–192. doi:10.1016/0304-3975(95)00068-2.
  4. ^ "musl/src/string/memmem.c". Retrieved 23 November 2019.
  5. ^ "newlib/libc/string/memmem.c". Retrieved 23 November 2019.
  6. ^ a b c "glibc/string/str-two-way.h".
  7. ^ "Eric Blake - Re: PATCH] Improve performance of memmem". Newlib mailing list.
  8. ^ Adamczyk, Zbigniew; Rytter, Wojciech (May 2013). "A note on a simple computation of the maximal suffix of a string". Journal of Discrete Algorithms. 20: 61–64. doi:10.1016/j.jda.2013.03.002.