지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학위논문
- 저자정보
- 지도교수
- 심정섭
- 발행연도
- 2019
- 저작권
- 인하대학교 논문은 저작권에 의해 보호받습니다.
이용수0
이 논문의 연구 히스토리 (3)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
길이가 같은 두 문자열 x, y가 주어졌을 때, x와 y의 같은 위치에 있는 문자들의 순위의 순서(order)가 모두 일치한다면, x와 y는 순위동형이라 한다. 길이가 m인 문자열 P와 길이가 n인 텍스트 T가 주어졌을 때, P와 순위동형인 T의 모든 부분문자열을 찾는 문제를 순위패턴매칭문제(ordre-preserving pattern matching problem)라 한다. 음악 표절분석, 주가 변동분석 등과 같이 순위의 순서가 중요한 응용분야에서 순위패턴매칭문제가 활발히 연구되고 있다. 패턴집합 ^P와 텍스트 T가 주어졌을 때, ^P에 속한 패턴과 순위동형을 이루는 T의 모든 부분문자열을 찾는 문제를 순위다중패턴매칭문제(order-preserving multiple pattern matching problem)라 한다. 본 논문에서는 순위다중패턴매칭문제를 해결하는 Wu-Manber 알고리즘 기반 알고리즘의 이동테이블(shift table)과 해시테이블(hash table) 대신 핑거프린트 테이블(fingerprint table)을 사용하여 공간복잡도를 O(q!+k+M)에서 O(k+M)으로 개선한 알고리즘을 제시한다.
목차
제1장 서론 1제2장 관련연구 52.1. 용어정리 52.2. 문제정의 52.3. 접두사표현법 62.4. 핑거프린트함수 72.5. 위치테이블과 이진벡터 72.6. 해싱기반 순위다중패턴매칭 알고리즘 10제3장 공간효율적인 해싱기반 알고리즘 143.1. 전처리단계 143.2. 검색단계 163.3. 복잡도 분석 17제4장 실험결과 19제5장 결론 26참고 문헌 27
최근 본 자료
댓글(0)
0