[알고리즘] 스트링 처리 알고리즘 | 패턴 매칭 알고리즘

패턴 매칭 알고리즘

이 알고리즘은 정해진 문자를 찾는것이 아니라 특정 패턴의 문자를 찾는 알고리즘이다.

1) 정규 표현식

(아래의 표현식 이외에도 수많은 식들이 있는데 이는 구글링을 통해 참고하자.)

1. AB
   : AB를 찾는다.

1. A+B
   : A또는 B를 찾는다.

1. ()*
   : ()안의 문자들이 0번 이상 나타나는 경우를 찾는다.

1. ?
   : 해당 자리에 어떤 문자라도 들어올 수 있다. (0개 또는 1개)

---

(예시)

• ?*(ie+ei)?* : ie 또는 ei를 갖고 있는 모든 단어
• (1+01)*(0+1) : 두개의 0이 연속적으로 나오지 않는 0과 1로 이루어진 문자열

2) 패턴 매칭 장치 그리기

패턴 매칭 장치는 위에서 보았던 KMP의 유한 상태 장치처럼 현재 상태에 따라 다음에 어떤 것을 해야할 지 그림으로 표현한 장치이다.

---

패턴 매칭 장치는 다음과 같은 장치들로 구성되어 있다.

이때 이 장치를 정규 표현식을 참고해 다음과 같은 방법으로 연결하여 새로운 장치를 생성할 수 있다.

(논리합의 경우 표현할 때, 2개의 추가적인 O를 사용하였고, )
(폐포의 경우 표현할 때, 1개의 추가적인 O를 사용한 것을 유의하자.)

---

예를들어 (A*B+AC)D의 정규 표현식은 다음과 같이 나타낼 수 있다.

---

(정리한 결과)

3) 패턴 매칭 장치의 배열

1. 번호를 붙인다.

(검은색 노드는 각각 매칭 장치의 시작과 끝 노드이다.)

---

1. 배열에 기록한다
   

   

   • ch[i]
     : i번 노드에 위치한 문자를 기록한 배열
   • next[i]
     : i번 노드에서 갈 수 있는 노드를 기록한 배열들
     (여러곳을 갈 수 있을 경우 여러개의 배열을 사용해 나타낸다.)

4) 매칭 동작 과정

1. Deque(Double Ended Queue)

우리는 Deque를 사용해 매칭 과정의 정보를 저장해야 한다.
이 Deque은 특별한 점이 하나 더 있는데 뒤에서는 삭제가 발생하지 않는다는 점이다.

---

(참고: 앞 부분과 뒷 부분을 +기호로 나눈다.)

1. 동작 규칙
   : 검사를 시작할 때 먼저 시작 노드 다음의 값을 Deque의 앞부분에 넣는다.
   : 그 후 Deque.front를 다음과 같은 기준으로 검사한다.
   • ch[Deque.front]가 존재할 경우
     : 해당 문자와 현재 검사하고 있는 문자가 일치할 경우,
     -> next[Deque.front]를 Deque.back에 Enqueue하고 해당 값을 Queue에서 삭제한다.
     : 해당 문자와 현재 검사하고 있는 문자가 일치하지 않을 경우,
     -> Deque.front를 삭제한다.

   ---

   • ch[Deque.front]가 존재하지 않을 경우
     -> next[Deque.front]를 Deque.front에 Enqueue하고 해당 값은 Queue에서 삭제한다.

   ---

   • Deque.front가 존재하지 않을 경우
     (Deque.front가 +인 경우)
     -> Deque를 뒤집어 준다.
     -> 검사하는 문자를 다음 문자로 바꾼다.

   ---

   • Deque.front와 Deque.Back모두 존재하지 않을 경우
     : 매칭 실패
   • Deque.front가 0일 경우
     : 매칭 성공

5) 예시

1. 검사 성공 예시

위에서 구한 (A*B+AC)D의 패턴 매칭 장치의 배열을 활용해 Text의 ABD부분을 검사할 경우

---

2. 검사 실패 예시

위에서 구한 (A*B+AC)D의 패턴 매칭 장치의 배열을 활용해 Text의 ADC부분을 검사할 경우