패턴 매칭 장치는 위에서 보았던 KMP의 유한 상태 장치처럼 현재 상태에 따라 다음에 어떤 것을 해야할 지 그림으로 표현한 장치이다.
패턴 매칭 장치는 다음과 같은 장치들로 구성되어 있다.
이때 이 장치를 정규 표현식을 참고해 다음과 같은 방법으로 연결하여 새로운 장치를 생성할 수 있다.
(논리합의 경우 표현할 때, 2개의 추가적인O를 사용하였고, ) (폐포의 경우 표현할 때, 1개의 추가적인O를 사용한 것을 유의하자.)
예를들어(A*B+AC)D의 정규 표현식은 다음과 같이 나타낼 수 있다.
(정리한 결과)
3) 패턴 매칭 장치의 배열
1. 번호를 붙인다.
(검은색 노드는 각각 매칭 장치의 시작과 끝 노드이다.)
배열에 기록한다
ch[i] : i번 노드에 위치한 문자를 기록한 배열
next[i] : i번 노드에서 갈 수 있는 노드를 기록한 배열들 (여러곳을 갈 수 있을 경우 여러개의 배열을 사용해 나타낸다.)
4) 매칭 동작 과정
Deque(Double Ended Queue)
우리는 Deque를 사용해 매칭 과정의 정보를 저장해야 한다. 이 Deque은 특별한 점이 하나 더 있는데 뒤에서는 삭제가 발생하지 않는다는 점이다.
(참고: 앞 부분과 뒷 부분을+기호로 나눈다.)
동작 규칙 : 검사를 시작할 때 먼저 시작 노드 다음의 값을 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부분을 검사할 경우
