| 1 |
1
사용자로부터 유사도 비교를 위한 문서를 입력받는 문서 입력부와,입력된 문서에서 초성을 추출하고, 추출된 초성을 1바이트로 맵핑하고 압축하여 초성만으로 이루어진 스킨파일을 생성하는 전처리 모듈과,상기 전처리 모듈에서 생성된 스킨파일을 이용하여 버로우즈-휠러 변환(burrows-wheeler transform) 및 FM-Index 자료구조를 사용하여 색인을 생성하고, 입력된 질의 문서를 분할한 후, 상기 생성한 색인을 이용하여 분할된 각 문서조각들이 본문에서 나타나는 위치를 탐색하는 본처리 모듈과,상기 본처리 모듈에서 탐색된 각 문서조각들의 위치정보를 이용하여 분포 밀도를 계산하여 밀집된 구간을 검출하여 유사구간을 판정하는 후처리 모듈을 포함하여 구성되고,이때, 상기 본처리 모듈은상기 전처리 모듈에서 생성된 스킨파일을 이용하여 버로우즈-휠러 변환(burrows-wheeler transform) 및 FM-index 자료구조를 사용하여 색인을 생성하는 색인 생성부와,입력된 질의 문서를 N-gram 또는 게놈 집합체(genome assembly) 기법을 이용하여 분할하는 문서 분할부와,상기 색인 생성부에서 생성된 색인을 이용하여 문서 분할부에서 분할된 각 문서조각들이 본문에서 나타나는 위치를 탐색하는 위치 탐색부를 포함하는 것을 특징으로 하는 초고속 유사구간 탐색 장치
|
| 2 |
2
제 1 항에 있어서, 상기 전처리 모듈은원문에서 공백문자를 제거하고 초성만을 추출하는 초성 추출부와,상기 초성 추출부에서 추출된 초성을 1바이트로 표현할 수 있는 0~255의 숫자로 맵핑하고 압축하여 초성만으로 이루어진 스킨파일을 생성하는 스킨파일 생성부를 포함하는 것을 특징으로 하는 초고속 유사구간 탐색 장치
|
| 3 |
3
삭제
|
| 4 |
4
제 1 항에 있어서,상기 게놈 집합체(genome assembly) 기법은 질의 문서의 사본을 여러 개 만들고, 각 사본을 임의의 길이로 자른 후 생성된 색인을 이용하여 본문에서 나타나는 위치를 탐색하는 것을 특징으로 하는 초고속 유사구간 탐색 장치
|
| 5 |
5
(A) 문서가 입력되면, 입력된 문서의 문서뭉치에서 초성을 추출하는 단계와,(B) 상기 추출된 초성을 1바이트로 맵핑하고 압축하여 스킨파일을 생성하는 단계와, (C) 상기 생성된 스킨파일을 이용하여 버로우즈-휠러 변환(burrows-wheeler transform) 및 FM-Index 자료구조를 사용하여 색인을 생성하는 단계와, (D) 입력된 질의 문서를 N-gram 또는 게놈 집합체(genome assembly) 기법을 이용하여 분할하는 단계와,(E) 상기 분할된 질의 문서를 앞서 생성한 색인을 이용하여 본문에서 검색하여 분할된 각 문서조각들이 본문에서 나타나는 위치를 탐색하는 단계와,(F) 상기 탐색된 각 문서조각들의 위치정보를 이용하여 분포 밀도를 계산하여 밀집된 구간을 검출하여 가장 많이 나타는 구간을 유사구간으로 판정하는 단계를 포함하여 이루어지고,이때, 상기 게놈 집합체 기법은찾고자 하는 질의 문서의 사본을 생성하는 단계와,상기 생성된 각 사본을 임의의 길이로 잘라 분할하는 단계를 포함하는 것을 특징으로 하는 초고속 유사구간 탐색 방법
|
| 6 |
6
제 5 항에 있어서,상기 1바이트로의 맵핑은 0~255의 숫자로 맵핑하는 것을 특징으로 하는 초고속 유사구간 탐색 방법
|
| 7 |
7
제 5 항에 있어서,상기 버로우즈-휠러 변환은 입력된 문자열에 대해 한 글자씩 쉬프트시켜 생성된 모든 문자열을 알파벳순으로 정렬하는 단계와,상기 정렬된 상태에서 가장 마지막 열을 추출하는 단계를 포함하는 것을 특징으로 하는 초고속 유사구간 탐색 방법
|
| 8 |
8
제 7 항에 있어서, 상기 추출되는 가장 마지막열의 길이는 원문의 길이와 동일한 것을 특징으로 하는 초고속 유사구간 탐색 방법
|
| 9 |
9
제 7 항에 있어서,상기 FM-Index 자료구조는 각 알파벳 별 해당 알파벳이 버로우즈-휠러 변환 문자열에서 처음 나타나는 위치 C[c]와, 특정 위치까지의 누적 출현 회수 Occ(c,k)로 이루어져 있으며, 상기 C[c]는 버로우즈-휠러 변환의 결과 문자열에서 알파벳 순서로 정렬했을 때 각 알파벳이 처음으로 나타나는 위치를 저장하고, Occ(c,k)는 버로우즈-휠러 변환의 결과 문자열에서 각 알파벳이 출현하는 횟수를 누적하는 것을 특징으로 하는 초고속 유사구간 탐색 방법
|
| 10 |
10
삭제
|
| 11 |
11
삭제
|
