| 1 |
1
사각망 순열패턴매칭을 수행하는 방법에 있어서,상수시간에 비교가능한 문자집합을 나타내는 상의 패턴 와 텍스트 가 주어짐에 따라,와 를 획득하고, 빈 순위통계트리 과 를 생성하는 전처리 단계; 및상기 T의 접두사 에 대하여 각각의 P와 순서동형인 부분서열이 있는지 여부를 검사하는 탐색 단계를 포함하고,상기 m은 상기 패턴 P의 길이, 상기 n은 상기 텍스트 T의 길이이며 m003c#n인 자연수인것을 특징으로 하는 사각망 순열패턴매칭을 수행하는 방법
|
| 2 |
2
제1항에 있어서, 상기 와 를 획득하고, 빈 순위통계트리 과 를 생성하는 전처리 단계는,상기와 를 획득함에 따라 상기 와 상기 를 순위통계트리를 이용하여 시간에 도출하는 단계를 포함하고,상기 는, 상기 상에서 P가 주어졌을 때, 각 문자의 순위(rank)를 저장한 서열을 의미하고, 상기 는,상기 각 문자의 순위를 저장한 서열로부터 순위별 위치를 저장한 서열을 의미하는 것을 포함하는 사각망 순열패턴매칭을 수행하는 방법
|
| 3 |
3
제1항에 있어서, 상기 T의 접두사 에 대하여 각각의 P와 순서동형인 부분서열이 있는지 여부를 검사하는 탐색 단계는,부터 까지 역순으로 각각의 문자 를과 에 순서대로 삽입하는 단계;를 삽입한 후, 상기 로부터 를 첫번째 문자, 를 마지막 문자로 하는 를 획득하고, 상기 와 상기 P가 순서동형일 경우 를 출력하는 단계; 및에 포함된 부분서열을 찾는 과정이 끝난 후 상기 과 상기 에 저장된 원소들을 삭제하는 단계를 포함하는 사각망 순열패턴매칭을 수행하는 방법
|
| 4 |
4
제3항에 있어서, 상기 T의 접두사 에 대하여 각각의 P와 순서동형인 부분서열이 있는지 여부를 검사하는 탐색 단계는,상기 를 삽입할 경우, 짝(pair) 을 에 삽입하고, 짝 을 에 삽입하는 단계; 및의 값을 이라고 정의하고, 상기 를 삽입한 후 상기 에서 의 순위 과 순위가 1인 원소 를 도출하되, 일 경우, 상기 에서 를 삭제하고 상기 에서 를 삭제하는 단계를 포함하고, 상기 k는, n보다 작은 임의의 자연수를 의미하는것을 특징으로 하는 사각망 순열패턴매칭을 수행하는 방법
|
| 5 |
5
제4항에 있어서, 상기 T의 접두사 에 대하여 각각의 P와 순서동형인 부분서열이 있는지 여부를 검사하는 탐색 단계는,상기 의 원소의 개수가 m보다 클 경우, 에서 순위가 m+1인 가장 큰 원소 를 구하고, 상기 과 상기 에서 각각 와 를 삭제하는 단계를 포함하고,상기 k는, 상기 n보다 작은 임의의 자연수를 의미하는 것을 특징으로 하는 사각망 순열패턴매칭을 수행하는 방법
|
| 6 |
6
제4항에 있어서, 상기 T의 접두사 에 대하여 각각의 P와 순서동형인 부분서열이 있는지 여부를 검사하는 탐색 단계는,상기 의 원소의 개수가 m이고, 를 포함하고 있는 경우, 트리를 중위순회(inorder traversal)하여 위치순으로 정렬된 를 출력하는 단계를 포함하는 사각망 순열패턴매칭을 수행하는 방법
|
| 7 |
7
제1항에 있어서,상기 사각망 순열패턴매칭을 수행하는 방법에서 시간복잡도는,상기 전처리 단계에서 시간이 소요되고, 상기 탐색단계에서 시간이 소요되는것을 특징으로 하는 사각망 순열패턴매칭을 수행하는 방법
|
| 8 |
8
사각망 순열패턴매칭을 위한 수행하는 장치에 있어서,상수시간에 비교가능한 문자집합을 나타내는 상의 패턴 와 텍스트 가 주어짐에 따라,와 를 획득하고, 빈 순위통계트리 과 를 생성하는 전처리부; 및 T의 접두사 에 대하여 각각의 P와 순서동형인 부분서열이 있는지 여부를 검사하는 탐색부를 포함하고,상기 m은 상기 패턴 P의 길이, 상기 n은 상기 텍스트 T의 길이이며 m003c#n인 자연수인것을 특징으로 하는 사각망 순열패턴매칭을 수행하는 장치
|
