DFA 기반 KMP

먼저 전처리를 위해, 찾을 패턴 안의 모든 문자열과 패턴을 행과 열로 가져야 한다. 예를 들어 패턴이 ABABAC일 경우, 행으로 A, B, C 열로 A, B, A, B, A, C 를 가져야 한다. 고로 문자 집합이 크다면 메모리를 많이 잡아먹게 된다. 대신 속도는 빠름 !!

사용 되는 예시 환경

네트워크 패킷 필터링
- 패킷이 수백만개씩 쏟아지기 때문에 그 중 바이러스 / 해킹 시그니처 같은 문자열들을 실시간으로 탐지해야 하기 때문에 속도가 중요함
하드웨어 기반 문자열 검색 (FPGA / ASIC)
- 문자열 검색을 직접 하드웨어 로직으로 처리하는 네트워크 장비, 보안 장비, SSD 컨트롤러 등에 사용됨
- 하드웨어에서는 조건 분기가 불가능함 !!
  - 조건 분기가 불가능하다는 것은 코드의 if -elif 문에서 조건을 만족하는 부분으로 이동할수가 없다는 것을 의미
  - 이를 DFA 테이블로 만들어서 원하는 방향으로 바로 이동할수 있도록 해줌
고속 로그 분석 시스템
- 많은 양의 서버 로그에서 실시간으로 에러 메세지나 특정 사용자 활동을 찾아야 할 때 사용
- 조건문 없이 테이블을 통해 바로 접근이 가능하므로 일정한 성능을 보장함

DFA 테이블 전처리

Deterministic Finite-State Automata

내가 텍스트에서 찾아야 할 패턴이 ABABAC 라고 가정하자.

여기서 표의 제목 열은 상태 번호를 의미하고, 변수 X는 패턴 미스매치 시에 돌아가야 할 상태 번호를 의미한다.

0번 상태

	0	1	2	3	4	5
	A	B	A	B	A	C
A	1
B	0
C	0
x	0

초기에 A로 시작해야 다음 상태로 전이될 수 있으므로 A외의 다른 문자들은 시작될수가 없으므로 0이다. X의 초깃값 또한 0이다.

1번 상태

	0	1	2	3	4	5
	A	B	A	B	A	C
A	1	1
B	0	2
C	0	0
x	0	0

이전 상태의 x 변수의 상태값으로 이동해서 해당 상태들을 복사해온다. 그 후, 상태 1 에서 B가 매치되면 다음 상태로 전이될 수 있으므로 DFA[B][1] 을 2로 바꾸어 준다. 그 다음, X값을 정해줘야 하는데 이전 상태(그러니까 x값)에서 현재 찾아야 할 문자 (B)의 값 ( DFA[B][previous x] ) 을 이번 상태의 x값으로 정해준다. 0번째 상태의 B 값의 0이므로 1번째 상태의 x값은 0이다.

2번 상태

	0	1	2	3	4	5
	A	B	A	B	A	C
A	1	1	3
B	0	2	0
C	0	0	0
x	0	0	1

이전 상태의 x 변수값은 0이다. 그러므로 2번 상태값은 0번 상태값을 모두 복사해온다. 그 후 A가 매칭되면 3번으로 이동할 수 있으므로 DFA[A][2] 의 값을 3으로 바꾸어준다. x값을 정하기 위해 이전 상태 x 변수값 이전 상태값으로 사용하여 이동한 다음 현재 매치된 문자 A가 상태값이 얼마인지 채워준다. 여기서 DFA[A][previous x]의 값은 1 이므로 이번 상태의 x 변수값은 1이다

3번 상태