1 |
1
전처리부 및 계산부를 포함하는 순위패턴매칭 장치에서 수행되는 핑거프린트를 이용한 순위패턴매칭 방법에 있어서,상기 전처리부에서, 패턴(P)에 대한 위치테이블, 이동테이블 및 복수 개의 q-그램에 대한 핑거프린트를 계산하는 전처리 단계; 및 상기 계산부에서, 상기 패턴(P)에 대한 위치테이블, 상기 이동테이블 및 상기 복수 개의 q-그램에 대한 핑거프린트를 계산한 값을 이용하여 상기 패턴(P)과 순위동형인 텍스트(T)의 부분문자열을 탐색하는 계산 단계를 포함하고,상기 복수 개의 q-그램은,길이가 m인 문자열로 구성된 패턴(P)와 길이가 n인 문자열로 구성된 텍스트(T)가 주어졌을 때, 상기 패턴(P)의 가장 오른쪽 q-그램을 1차 q-그램, 상기 1차 q-그램을 기준으로 상기 1차 q-그램의 이전에 위치한 q- 그램을 2차 q-그램이라고 하고, 상기 1차 q-그램 및 상기 2차 q-그램을 포함하고,상기 계산 단계는,과 비교를 시작하는 텍스트(T)의 위치를 i라고 할 때, 각 에 대해 패턴의 1차 q-그램 핑거프린트와 텍스트의 1차 q-그램 핑거프린트가 일치하는지 판단하고, 상기 패턴의 1차 q-그램 핑거프린트와 텍스트의 1차 q-그램 핑거프린트가 일치할 경우, 상기 패턴의 2차 q-그램 핑거프린트와 상기 텍스트의 2차 q-그램 핑거프린트가 일치하는지 확인하고, 상기 패턴의 2차 q-그램 핑거프린트와 상기 텍스트의 2차 q-그램 핑거프린트가 일치할 경우, 패턴(P)와 상기 텍스트의 순위동형 여부를 위치테이블을 이용하여 확인하여 위치 i-m+1을 출력하는 단계를 포함하는 순위패턴매칭 방법
|
2 |
2
삭제
|
3 |
3
삭제
|
4 |
4
삭제
|
5 |
5
삭제
|
6 |
6
제1항에 있어서, 상기 계산 단계는,순위동형 여부에 관계없이 텍스트의 위치(i)를 이동테이블에서 텍스트의 1차 q-그램 핑거프린트의 거리 만큼 증가시기는 단계를 포함하는 순위패턴매칭 방법
|
7 |
7
순위패턴매칭 장치에 있어서,패턴(P)에 대한 위치테이블, 이동테이블 및 복수 개의 q-그램에 대한 핑거프린트를 계산하는 전처리부; 및 상기 패턴(P)에 대한 위치테이블, 상기 이동테이블 및 상기 복수 개의 q-그램에 대한 핑거프린트를 계산한 값을 이용하여 상기 패턴(P)과 순위동형인 텍스트(T)의 부분문자열을 탐색하는 계산부를 포함하고,상기 복수 개의 q-그램은,길이가 m인 문자열로 구성된 패턴(P)와 길이가 n인 문자열로 구성된 텍스트(T)가 주어졌을 때, 상기 패턴(P)의 가장 오른쪽 q-그램을 1차 q-그램, 상기 1차 q-그램을 기준으로 상기 1차 q-그램의 이전에 위치한 q- 그램을 2차 q-그램이라고 하고, 상기 1차 q-그램 및 상기 2차 q-그램을 포함하고,상기 계산부는,과 비교를 시작하는 텍스트(T)의 위치를 i라고 할 때, 각 에 대해 패턴의 1차 q-그램 핑거프린트와 텍스트의 1차 q-그램 핑거프린트가 일치하는지 판단하고, 상기 패턴의 1차 q-그램 핑거프린트와 텍스트의 1차 q-그램 핑거프린트가 일치할 경우, 상기 패턴의 2차 q-그램 핑거프린트와 상기 텍스트의 2차 q-그램 핑거프린트가 일치하는지 확인하고, 상기 패턴의 2차 q-그램 핑거프린트와 상기 텍스트의 2차 q-그램 핑거프린트가 일치할 경우, 패턴(P)와 상기 텍스트의 순위동형 여부를 위치테이블을 이용하여 확인하여 위치 i-m+1을 출력하는순위패턴매칭 장치
|