| 1 |
1
사각망 순열패턴매칭(boxed-mesh permutation pattern matching)을 위한 방법에 있어서,상수 시간에 비교 가능한 문자 집합을 나타내는 상의 텍스트 와 패턴가 주어짐에 따라,길이가 인 배열 을 정렬하고 정렬된 배열 을 이용하여 와 을 계산하는 전처리단계; 및상기 텍스트 에 대하여 단계 의 각 스텝 에서 를 증가시키면서 상기 패턴 와 순위동형인 사각망 부분서열 을 찾는 탐색단계를 포함하고,상기 탐색단계는,서로 독립적인 각 단계 마다 스레드 를 이용하여 스텝 를 계산하는 것으로,상기 사각망 부분서열 을 관리하기 위해 짝 을 저장하는 배열 와 짝 를 저장하는 배열 를 사용하는 단계;스텝 에서 상기 배열 , 에 각각 , 를 삽입하는 단계;상기 사각망 부분서열 의 의 순위를 의 순위와 같도록 상기 사각망 부분서열 를 보정하는 단계; 및상기 배열 와 상기 에 대해 상기 사각망 부분서열 이 상기 패턴 와 순위동형인지 확인하는 단계를 포함하는 사각망 순열패턴매칭을 위한 방법
|
| 2 |
2
제1항에 있어서,상기 전처리단계는,개의 스레드를 이용하여 의사코드 전처리(Preprocessing)을 수행하는 것으로,상기 배열 에 짝 형태로 저장하고 상기 배열 을 상기 짝의 첫 번째 원소를 기준으로 병렬 바이토닉 정렬(bitonic sort)을 이용하여 정렬한 후 정렬된 배열을 이용하여 상기 와 상기 을 계산하는 것을 특징으로 하는 사각망 순열패턴매칭을 위한 방법
|
| 3 |
3
삭제
|
| 4 |
4
삭제
|
| 5 |
5
제1항에 있어서,상기 보정하는 단계는,상기 사각망 부분서열 에서 의 순위가 의 순위보다 높으면 상기 배열 에서 순위가 가장 낮은 원소 를 포함하는 짝 와 를 상기 배열 와 에서 각각 삭제하고, 의 순위가 의 순위보다 높지 않으면 상기 배열 에서 순위가 가장 높은 원소 를 포함하는 짝 와 를 상기 배열 와 에서 각각 삭제하는 단계를 포함하는 사각망 순열패턴매칭을 위한 방법
|
| 6 |
6
삭제
|
| 7 |
7
사각망 순열패턴매칭(boxed-mesh permutation pattern matching)을 위한 방법에 있어서,상수 시간에 비교 가능한 문자 집합을 나타내는 상의 텍스트 와 패턴가 주어짐에 따라,길이가 인 배열 을 정렬하고 정렬된 배열 을 이용하여 와 을 계산하는 전처리단계; 및상기 텍스트 에 대하여 단계 의 각 스텝 에서 를 증가시키면서 상기 패턴 와 순위동형인 사각망 부분서열 을 찾는 탐색단계를 포함하고,상기 탐색단계는,개의 스레드 그룹 를 이용하여 단계 를 계산하는 것으로,상기 사각망 부분서열 을 관리하기 위해 짝 을 저장하는 배열 와 짝 를 저장하는 배열 를 사용하는 단계;상기 스레드 그룹 를 이용하여 상기 배열 와 에 에 대한 각각의 짝 , 을 삽입하는 단계;상기 배열 와 상기 에 대해 상기 사각망 부분서열 이 상기 패턴 와 순위동형인지 확인하는 단계; 및스텝 에서 를 증가시키면서 크기를 으로 유지하고 를 포함하는 상기 사각망 부분서열 을 탐색하는 단계를 포함하는 사각망 순열패턴매칭을 위한 방법
|
| 8 |
8
제7항에 있어서,상기 각각의 짝 , 을 삽입하는 단계는,상기 배열 의 첫 번째 원소에 대해 인 스레드 는 임시 배열 에 을 저장하고, 인 스레드 중에서 인 스레드 가 존재하면 에 를 저장하고, 인 스레드 중에서 인 스레드 가 존재하지 않으면 에 를 저장하는 단계를 포함하는 사각망 순열패턴매칭을 위한 방법
|
| 9 |
9
제7항에 있어서,상기 탐색단계는,상기 사각망 부분서열 의 의 순위를 의 순위와 같도록 상기 사각망 부분서열 를 보정하는 단계를 더 포함하는 사각망 순열패턴매칭을 위한 방법
|
| 10 |
10
제9항에 있어서,상기 보정하는 단계는,상기 사각망 부분서열 에서 의 순위가 의 순위보다 높으면 상기 배열 에서 순위가 가장 낮은 원소 를 포함하는 짝 와 를 상기 배열 와 에서 각각 삭제하고, 의 순위가 의 순위보다 높지 않으면 상기 배열 에서 순위가 가장 높은 원소 를 포함하는 짝 와 를 상기 배열 와 에서 각각 삭제하는 단계를 포함하는 사각망 순열패턴매칭을 위한 방법
|
