| 1 |
1
N개(N은 2 이상의 자연수)의 정규 표현식 패턴을 결정적 유한 오토마타로 변환하는 방법으로서,(a) 상기 N개의 정규 표현식 패턴 각각의 문자열 길이를 L(i)에 저장하는 단계;(b) 상기 저장된 패턴의 길이 L(i)에 따라 패턴을 역방향 정렬하는 단계;(c) 상기 역방향 정렬된 정규 표현식 패턴을 기계가 받아들이는 유한 오토마타 가운데, 상태 천이 시 변환된 상태의 유일성을 갖는 결정적 유한 오토마타로 변환하는 단계;(d) 상기 (c)에서 변환된 결정적 유한 오토마타 가운데, i(1≤i≤N-1)번째 패턴으로부터 생성된 결정적 유한 오토마톤과 j(i+1≤j≤N)번째 패턴으로부터 생성된 결정적 유한 오토마톤 내 상태 간 비교 과정을 통해 동일한 입력 문자를 갖는 상태를 찾는 단계;(e) 상기 (d) 단계에서 찾은 결합 가능한 상태를 병합하여 새로운 상태를 생성하는 단계;(f) 상기 (e) 단계에서 생성된 결정적 유한 오토마타에 기존 알고리듬을 적용하는 단계를 포함하는, 정규 표현식 패턴의 메모리 효율적인 결정적 유한 오토마타를 생성하는 방법
|
| 2 |
2
제1항에 있어서, 상기 (a) 단계는,(a-1) 상기 N개의 패턴의 길이를 계산하는 단계;(a-2) 상기 N개의 패턴의 길이를 L(i)에 저장하는 단계를 포함하는 정규 표현식 패턴의 길이 저장 단계인, 정규 표현식 패턴의 메모리 효율적인 결정적 유한 오토마타를 생성하는 방법
|
| 3 |
3
제2항에 있어서, 상기 (b) 단계는,(b-1) 상기 (a-2) 단계에서 저장된 L(i)에 따라 N개의 패턴을 역방향 정렬하는 단계;(b-2) 역방향 정렬된 패턴의 순서에 따라 N개의 패턴의 순서를 업데이트하는 단계를 포함하는 N개의 정규 표현식 패턴의 역방향 정렬 단계인, 정규 표현식 패턴의 메모리 효율적인 결정적 유한 오토마타를 생성하는 방법
|
| 4 |
4
제1항에 있어서, 상기 (d) 단계는,(d-1) 상기 역방향 정렬된 패턴 중 i(1≤i≤N-1)번째 패턴으로부터 생성된 결정적 유한 오토마톤을 선택하는 단계;(d-2) 상기 역방향 정렬된 패턴 중 j(i+1≤j≤N)번째 패턴의 결정적 유한 오토마톤을 선택하는 단계;(d-3) 상기 (d-1) 단계의 결정적 유한 오토마톤에서 L(i)번째 상태를 선택하는 단계;(d-4) 상기 (d-2) 단계의 결정적 유한 오토마톤에서 L(j)번째 상태를 선택하는 단계;(d-5) 상기 (d-3) 단계와 상기 (d-4) 단계에서 선택된 상태의 입력 값을 비교하는 단계;(d-6) 상기 (d-5) 단계에서 동일한 입력 값 'a'를 갖는 상태가 존재하는 경우, 해당 상태 (Sx,a,b,i)와 (Sy,a,c,j)를 SS에 저장하는 단계;(d-7) 상기 (d-5) 단계에서 동일한 입력 값 'a'를 갖는 상태가 존재하는 경우, 상기 L(i)값을 1만큼 감소시켜 L(i)값이 0이 될 때까지 상기 (d-3)단계부터 반복 수행하는 단계;(d-8) 상기 (d-5) 단계에서 동일한 입력 값을 갖는 상태가 없는 경우, L(j)값을 1만큼 감소시켜 L(j)값이 0이 될 때까지 상기 (d-4) 단계부터 반복 수행하는 단계; (d-9) 상기 (d-5) 단계에서 동일한 입력 값을 갖는 상태가 없는 경우, 상기 L(i)값을 1만큼 감소시켜 L(i)값이 0이 될 때까지 상기 (d-3) 단계부터 반복 수행하는 단계를 포함하는 병합 가능한 상태 찾기 단계인, 정규 표현식 패턴의 메모리 효율적인 결정적 유한 오토마타를 생성하는 방법
|
| 5 |
5
제4항에 있어서, 상기 (e) 단계는,(e-1) 상기 SS로부터 병합 가능한 상태 (Sx, a, b, i)와 (Sy, a, c, j)를 확인하는 단계;(e-2) 각 상태의 입력 값과 출력 값을 새로운 병합 상태에 각각 비트맵으로 저장하는 단계;(e-3) 상기 (e-1) 단계에서 선택된 상태 (Sx, a, b, i)와 (Sy, a, c, j)를 병합하여 새로운 상태 (Sx_y, a/i, a/j, b
|
| 6 |
6
제1항에 있어서, 상기 (f) 단계는,(f-1) 상기 (e) 단계에서 생성된 결정적 유한 오토마타를 참조하는 단계;(f-2) 상기 (f-1) 단계에서 생성된 결정적 유한 오토마타에서 기존 알고리듬을 적용하여 상태를 감소시키는 단계를 포함하는 기존 알고리듬과의 결합 단계인, 정규 표현식 패턴의 메모리 효율적인 결정적 유한 오토마타를 생성하는 방법
|
