| 1 |
1
소정의 텍스트에 N 개(N은 2 이상의 자연수)의 패턴 중 하나 이상의 패턴이 존재하는지 여부를 탐지하기 위한 방법으로서,
(a) 상기 N 개의 패턴 각각의 문자열 길이를 계산하고, 그 중 가장 짧은 패턴의 길이를 LSP(Length of Shortest Pattern)로 저장하는 단계;
(b) 상기 텍스트에 포함될 수 있는 모든 1바이트 문자들을 인덱스(index)로 하는 B 개(B는 2 이상의 자연수)의 시프트(SHIFT) 테이블을 생성하고, 상기 B개의 시프트 테이블 각각에 대하여 각 인덱스에 대응하는 값(value)들을 LSP로 초기화하는 단계;
(c) 상기 텍스트에 포함될 수 있는 길이 B의 모든 문자열에 대한 각각의 해시값들을 인덱스로 하는 해시(HASH) 테이블 및, 상기 텍스트에 포함될 수 있는 길이 Bp(Bp는 2 이상의 자연수)의 모든 문자열에 대한 각각의 해시값들을 인덱스로 하는 프리픽스(PREFIX) 테이블을 생성하는 단계;
(d) 상기 N 개의 패턴 중 어느 하나의 패턴을 선택하고, 상기 선택된 패턴의 가장 왼쪽 문자의 위치를 0 이라 할 때 왼쪽부터 0 에서 LSP - 1 위치까지의 문자열에 대하여, 상기 문자열의 가장 왼쪽부터 오른쪽으로 한 칸씩 이동하면서 해당 위치에 존재하는 문자의 시프트 값을 계산하여 상기 B 개의 시프트 테이블의 값을 업데이트하는 단계;
(e) 상기 (d) 단계에서 선택된 패턴에 대하여, 상기 선택된 패턴의 왼쪽부터 LSP - B 에서 LSP - 1 위치까지의 문자열에 대한 해시값들을 인덱스 값으로 하는 상기 해시(HASH) 테이블의 값(value)을 상기 선택된 패턴에 대한 포인터(pointer)로 저장하는 단계;
(f) 상기 (d) 단계에서 선택된 패턴에 대하여, 상기 선택된 패턴의 왼쪽부터 0 에서 Bp - 1 위치까지의 문자열에 대한 해시값들을 인덱스 값으로 하는 상기 프리픽스(PREFIX) 테이블의 값(value)을 상기 선택된 패턴에 대한 포인터(pointer)로 저장하는 단계;
(g) 상기 N 개의 패턴 모두에 대하여 상기 (c) 단계 내지 (f) 단계를 반복 수행하는 단계;
(h) 상기 (g) 단계의 수행 이후, 상기 B 개의 시프트 테이블, 해시 테이블 및 프리픽스 테이블을 이용하여 상기 텍스트 내에 상기 N 개의 패턴 중 하나 이상의 패턴이 존재하는지 여부를 탐색하는 단계;
를 포함하여 구성되는 문자열 패턴 탐지 방법
|
| 2 |
2
제1항에 있어서,
상기 B 개의 시프트 테이블 각각을 SHIFTLj 테이블(j는 0에서 B - 1 사이의 자연수)로 정의할 때,
상기 (d) 단계는,
(d-1) 상기 선택된 패턴상의 위치(k1)를 0으로 설정하는 단계;
(d-2) 상기 선택된 패턴에 대하여 상기 k1번째 위치에 해당하는 문자를 추출하는 단계;
(d-3) 상기 추출된 문자를 인덱스로 하는 SHIFTLj 테이블의 값 LSP - 1 - k1 을 계산하는 단계;
(d-4) 상기 (d-3) 단계에서 계산된 LSP - 1 - k1 값과 SHIFTLj 테이블의 현재값을 서로 비교하고, 이 중 작은 값을 상기 SHIFTLj 테이블의 해당 인덱스의 값으로 업데이트하는 단계;
(d-5) 만약 상기 k1 값이 LSP - 1 - j 값과 동일한 경우, 상기 k1 위치에 해당하는 문자를 인덱스로 하는 상기 SHIFTLj 테이블의 값을 0 으로 설정하는 단계;
(d-6) 상기 B 개의 시프트 테이블 모두에 대하여, 상기 (d-3) 단계 내지 (d-5) 단계를 반복 수행하는 단계;
(d-7) 상기 k1 값을 LSP - 1 에 도달할 때까지 1씩 증가시키면서, 상기 (d-2) 내지 (d-6) 단계를 반복 수행하는 단계;
를 포함하여 구성되는 문자열 패턴 탐지 방법
|
| 3 |
3
제1항 또는 제2항에 있어서,
상기 (e) 단계에서 상기 포인터를 저장하고자 하는 상기 해시 테이블의 값에 기 저장된 포인터가 있을 경우, 기 저장된 포인터를 삭제하지 않고 상기 선택된 패턴에 대한 포인터를 리스트 형태로 추가 저장하는 것을 특징으로 하는 문자열 패턴 탐지 방법
|
| 4 |
4
제1항 또는 제2항에 있어서,
상기 (f) 단계에서 상기 포인터를 저장하고자 하는 상기 프리픽스 테이블의 값에 기 저장된 포인터가 있을 경우, 기 저장된 포인터를 삭제하지 않고 상기 선택된 패턴에 대한 포인터를 리스트 형태로 추가 저장하는 것을 특징으로 하는 문자열 패턴 탐지 방법
|
| 5 |
5
제1항에 있어서,
상기 B 개의 시프트 테이블 각각을 SHIFTLj 테이블(j는 0에서 B - 1 사이의 자연수)로 정의할 때,
상기 (h) 단계는,
(h-1) 상기 텍스트의 왼쪽에서 가장 첫 번째 위치를 0 이라 할 때, 펀치 포인터(Sc)를 상기 텍스트의 LSP - 1 위치로 설정하는 단계;
(h-2) 상기 텍스트의 Sc 위치에 해당하는 문자에 대한 시프트 값을 SHIFTL0 테이블로부터 추출하는 단계;
(h-3) 상기 (h-2) 단계에서 추출된 시프트 값이 0인 경우, 상기 j 값을 1 부터 B - 1 까지 1씩 증가시키면서 상기 텍스트의 Sc - j 위치에 해당하는 문자에 대한 시프트 값을 SHIFTLj 테이블로부터 추출하는 단계;
(h-4) 상기 (h-3) 단계에서 추출된 시프트 값들이 모두 0인 경우, 상기 텍스트의 Sc - B + 1부터 Sc 위치까지의 문자열에 대한 해시값을 인덱스 값으로 하는 패턴들을 상기 해시 테이블로부터 검출하는 단계;
(h-5) 상기 (h-4) 단계에서 상기 해시 테이블로부터 패턴들이 검출된 경우, 상기 텍스트의 Sc - LSP + 1 부터 Sc - LSP + Bp 위치까지의 문자열에 대한 해시값을 인덱스 값으로 하는 패턴들을 상기 프리픽스 테이블로부터 검출하는 단계;
(h-6) 상기 (h-5) 단계에서 상기 프리픽스 테이블로부터 패턴들이 검출된 경우, 상기 프리픽스 테이블로부터 검출된 패턴과 상기 해시 테이블로부터 검출된 패턴 중 일치하는 패턴들이 존재하는지 여부를 판단하는 단계;
(h-7) 상기 (h-6) 단계에서의 판단 결과 일치하는 패턴들이 있는 경우, 상기 일치하는 패턴들과 상기 텍스트를 직접 비교하여 상기 패턴들이 실제로 상기 텍스트에 존재하는지 여부를 탐색하는 단계;
(h-8) 상기 (h-7) 단계에서의 판단 결과 상기 텍스트와 직접 비교한 패턴들 중 하나라도 상기 텍스트와 일치하는 패턴이 존재하는 경우, 해당 패턴을 상기 텍스트에 존재하는 패턴으로 판단하는 단계;
를 포함하여 구성되는 문자열 패턴 탐지 방법
|
| 6 |
6
제5항에 있어서,
상기 (h-2) 단계에서 추출된 시프트 값이 0이 아닌 경우, 추출된 상기 시프트 값 만큼 상기 Sc를 상기 텍스트의 오른쪽으로 이동하고, 이동된 상기 Sc를 기준으로 상기 (h-2) 단계 이하의 단계들을 수행하는 것을 특징으로 하는 문자열 패턴 탐지 방법
|
| 7 |
7
제5항에 있어서,
상기 (h-3) 단계의 수행 도중 최초로 0이 아닌 시프트 값이 추출된 경우, 다음 수식을 이용하여 상기 Sc를 상기 텍스트의 오른쪽으로 이동하고, 이동된 상기 Sc를 기준으로 상기 (h-2) 단계 이하의 단계들을 수행하는 것을 특징으로 하는 문자열 패턴 탐지 방법
|
| 8 |
8
제5항에 있어서,
상기 (h-4) 단계에서 상기 해시 테이블로부터 패턴들이 검출되지 않은 경우, 또는 상기 (h-5) 단계에서 상기 프리픽스 테이블로부터 패턴들이 검출되지 않은 경우, 또는 상기 (h-6) 단계에서 일치하는 패턴들이 없는 경우, 또는 상기 (h-7) 단계에서 직접 비교 결과 최종적으로 패턴들이 상기 텍스트와 불일치하는 것으로 판단되는 경우 중 어느 하나의 경우에 해당하는 경우,
상기 Sc를 상기 텍스트의 오른쪽으로 1 만큼 이동하고, 이동된 상기 Sc를 기준으로 상기 (h-2) 단계 이하의 단계들을 수행하는 것을 특징으로 하는 문자열 패턴 탐지 방법
|
