알고리즘 : 패턴 매칭 알고리즘

패턴 매칭 알고리즘이란, 텍스트에서 원하는 문자 패턴을 찾아 내는 것입니다.

들어가기 전에, 정규식에 대해 간단히 소개하겠습니다.

---

정규식 (regex)

---

정규식이란, 세 가지 기본 연산들로 이루어진 심볼들의 스트링입니다.

여기서 심볼이란, 아래의 세 가지를 들 수 있습니다.

* : 앞의 문자 혹은 괄호 안의 문자들이 0번 이상 반복됨.
? : 어떤 문자와도 매칭됨. 조커.
+ : OR

그렇다면 이 심볼들이 어디에 사용되는지 정규식의 예를 살펴보겠습니다.

 

?*(ie+ei)?* : ie 또는 ei를 가지고 있는 모든 단어. 

                   - ???ie??? : billie eilish, kittie, ...

                   - ???ei??? : keith ape, weight, ...

(1+01)*(0+1) : 연속적으로 두개의 0이 나오지 않는 모든 이진수 스트링. 0, 1, 10, 11, 010, ...

---

패턴 매칭 장치

---

패턴 매칭 장치란, 패턴 매칭에 사용되는 장치 패턴을 일컫습니다.

그 전에 우선, 결정적 장치와 비결정적 장치에 대해 간단히 짚고 가겠습니다.

결정적(Deterministic) 장치는 각 단계의 상태 전이가 다음 입력될 문자에 의해 완전히 결정되는 것으로,

이전에 소개한 KMP 알고리즘의 유한 상태 장치가 이에 속합니다.

비결정적(Non-Deterministic) 장치는 이와 달리, 패턴 매칭에서의 예를 들면 패턴을 매칭하는 여러 가지 방법 중 장치가 올바른 방법을 찾아 나가는 것입니다.

 

그렇다면 이제 패턴 매칭 장치의 구성 요소를 보겠습니다.

먼저 접합 입니다. 두 장치가 단순 접합한 형태로, A와 C를 이으면 AC가 되는 것 뿐입니다.

다음으로 논리합입니다. 논리합은 앞서 설명한 정규식의 + 심볼과 같은 OR의 의미입니다.

다음은 폐포입니다. 폐포는 앞서 설명한 정규식의 * 심볼과 같은 반복의 의미입니다.

거치지 않는다면 파란색 화살표대로, 0번 이상 거친다면 빠져나갈 때 까지 붉은색 화살표를 따라 반복합니다.

이러한 장치들을 이용하여 (A*B+AC)D 라는 식을 패턴 매칭 장치로 나타내면 다음과 같습니다.

처음에 A* 가 폐포로 만들어지며, B가 그 뒤에 접합됩니다.

그러고선 + 연산자를 만나므로 논리합 장치의 머리 부분을 그리고, A 노드를 그립니다. C가 그 뒤에 단순 접합됩니다.

A*B와 AC의 논리합이므로 둘의 끝 부분을 논리합의 끝 부분으로 합치고, D 노드를 접합 하면 위와 같은 장치가 됩니다.

 

화살표를 따라 이동한다면, 다음과 같이 경로를 확인할 수 있습니다.

0 → 5 → 6 or 2

               6 → 7 → 8 → 9

               2 → 1 → 2 → 1 ...

               2 → 3 → 4 → 8 → 9

이러한 경로를 배열로 표현할 수 있습니다.

---

패턴 매칭 알고리즘

---

앞서 얻은 패턴 매칭 장치 또는 배열로 패턴 매칭 알고리즘을 수행하면 어떻게 될까요?

일단 패턴 매칭 알고리즘의 수행에는 덱(Deque, Double-ended queue)를 사용합니다.

스택, 큐, 덱의 구조를 간단히 나타낸 그림입니다.

스택은 프링글스 통 처럼 마지막에 들어간 걸 먼저 꺼내는 LIFO(Last in First out) 구조이고,

큐는 터널처럼 먼저 들어간 것이 먼저 나오는 FIFO(First in First out) 구조입니다.

덱은 이러한 스택과 큐의 특징을 섞은 것으로, 자유롭게 양방향 삽입/삭제가 가능한 자료구조입니다. 위아래가 뚫린 프링글스 통을 생각하시면 될 것 같아요.

그렇다면 이제부터 이 덱이라는 자료구조를 어떻게 활용하는지 알아보겠습니다.

 

간단하게 "AAABDABCD" 라는 스트링에서 "AAABD" 라는 패턴을 매칭해보도록 하겠습니다.

AAABD 를 매칭하는 과정을, 게임에서 차근차근 A, A, A, B, D라는 아이템을 순서대로 하나씩 모아 "A-A-A-B-D" 라는 졸업템을 갖추기 위해 던전을 탐험하는 것에 비유하겠습니다.

일단 위에서 만든 패턴 매칭 장치를 가져와서 함께 보겠습니다.

입구인 0에 서 있는 모습입니다. 옆의 덱을 보면 +, 5가 있습니다. 일단 앞으로 갈 목적지를 +의 아래에 넣는 겁니다.

5의 위치에 도달하면 일단 덱에서 5를 빼고, 갈림길에서 6 또는 2로 갈 수 있으니 6과 2를 덱 아래에 넣습니다.

게임에서 아이템 파밍을 위해 같은 던전에 캐릭터를 여러 개 돌리는 경우를 심심치 않게 볼 수 있는데,

우리도 캐릭터를 몇 개 더 만들어서 하나는 6, 하나는 2의 갈림길로 가보겠습니다.

2번에 도착한 캐릭터를 먼저 보겠습니다. 

2에 도착하면 3과 1의 갈림길이 있으니 또 덱에 넣어줍니다. 이번에도 방금처럼 캐릭터를 하나 더 만들어서 하나는 3, 하나는 1로 보내겠습니다.

이 상태에서 1로 간 경우 A 아이템을 발견합니다. 우리가 맞춰야 할 아이템의 "A-A-A-B-D" 순서의 첫 번째로 파밍해야 할 A 아이템이 필요했는데, 마침 잘 됐네요. 게임 데이터가 날라가지 않도록 서둘러 세이브파일을 저장해 줍니다.

세이브 파일을 저장하기 위해서 + 문자의 위에 "2" 를 저장하는데,

그 이유는, 1번에 도달하여 A라는 아이템을 얻었다는 세이브 파일을 만들고 나중에 그 다음부터 진행하기 위해 그 다음 단계인 2번 노드를 덱에 저장해 놓습니다.

또한 여기서 + 문자는 중간지점을 표시하기 위한 "scan" 기호로, 일종의 분리자 입니다.

+ 문자의 위에는 "현재까지 일치한 상태", 아래에는 "앞으로 방문할 상태" 를 삽입합니다. 따라서 2를 덱 위에 삽입해줍니다.

 

이제는 다른 계정으로 진입할 차례입니다. 2번에 서 있던 때로 돌아와 이번에는 3번으로 향합니다.

3번은 B 상태를 만나게 되는데, 우리는 "AAABD"를 매칭해야 하므로, 지금은 A를 만나는 경우만 필요합니다.

따라서 3번으로 가는 경우는 매칭이 되지 않으므로, 그냥 캐릭터를 삭제해버립니다. 망캐는 캐삭해야죠..

방금 전까지 5번에서 2번으로 가는 경우를 보였고, 이번에는 6번으로 간 캐릭터를 살펴보겠습니다.

 

6번에서도 아까 1번에 도착했을 때 처럼 A가 매칭되고, 매칭된 사실을 저장하기 위해 7을 덱에 삽입합니다.

이제 여러분은 두 개의 세이브 파일을 갖고 있는 겁니다.

이제 + 연산자 아래에 아무 것도 남아있지 않은 상태, 즉 앞으로 방문할 곳이 없는 상태가 된다면 덱에서 역전이 일어납니다. + 연산자가 맨 위로 이동하고 7, 2가 앞으로 방문할 상태로 전환되는 것입니다.

이런 역전이 일어나는 이유는, 방금 말씀드린 "A라는 아이템을 얻은 세이브 파일"을 불러와 그 다음 단계부터 던전 탐험을 계속 하기 위해서입니다.

2에 도착하고, 갈림길이 있으니 이를 복제하여 또 캐릭터 하나를 더 만듭니다.

현재 이 두 캐릭터는 A 아이템을 하나씩 갖고 있습니다.

하나는 3에, 하나는 1에 보내는데, 1에 도착하면 A 아이템을 얻어 A-A 아이템을 갖고 있는 상태가 됩니다.

아까와 같이 세이브파일을 + 위에 저장해 줍니다.

또 이번에 3에 간 캐릭터도 A-A를 파밍해야 하는데, A-B가 파밍된 망캐이므로 삭제 해버립니다.

다시 돌아와서, 6번에 서 있던 캐릭터를 불러옵니다. 7번으로 가게 되면, A-C 아이템을 파밍하므로 망캐는 삭제합니다.

이제 남은 것은 방금 A-A를 파밍하여 2번 위치를 저장한 캐릭터 하나 뿐입니다.

그런데 또 + 연산자 아래가 비워졌으니 역전시킵니다.

역전시킨 후, 2번에 도달하여 3, 1로 가는 갈림길이 나와서 또 캐릭터를 복제하여 하나 더 만듭니다.

지금부터는 위에서 설명한 과정과 동일하기 때문에 설명을 줄이도록 하겠습니다.

이 때, A-A-A-B 가 필요하므로, 1번 노드로 가서 A를 파밍한 캐릭터는 지웁니다.

3번 노드에서 B를 파밍하여 A-A-A-B 순서의 아이템을 맞춘 캐릭터만 남아있는 상태입니다.

이제 또 덱 아래가 비었으니 반전을 해줍니다.

남은 9번 노드가 마지막일 경우, 루프를 종료합니다.

이렇게 해서 끝판왕 졸업템인 AAABD를 모두 모았습니다.

 

지금까지 "AAABDABCD" 라는 스트링에서 "AAABD" 라는 패턴을 매칭하는 과정을 보았습니다.

그런데 첫 시작이 AAABD가 아니라면 어떤 과정이 일어날까요?

"CDAAB...." 에서 "AAABD"를 검색하는 과정을 보겠습니다.

이렇듯 CDAAB의 첫 글자인 C조차 AAABD와 맞지 않기 때문에, 한 글자만 비교하고 바로 종료합니다.

반복문을 이용하여 문장의 끝까지 패턴매칭 알고리즘을 돌리게 된다면, 위의 경우에는 계속 비교하다가 AAABD라는 패턴을 스트링에서 확인한다면 그 값을 리턴하여 "패턴 발생 위치: 15" 식으로 출력하도록 만들 수 있습니다.

 

<틀린 점이 있다면 지적 부탁드립니다. 감사합니다.>