맞춤기술찾기

홈으로 가기
맞춤기술찾기
이전대상기술
프린트하기

이전대상기술

해싱기반의 순위다중패턴매칭 방법(A METHOD FOR ORDER-PRESERVING MULTIPLE PATTERN MATCHING BASED ON HASHING)

  • 기술번호 : KST2018004362
  • 담당센터 : 인천기술혁신센터
  • 전화번호 : 032-420-3580
상담신청 PDF 받기
요약, Int. CL, CPC, 출원번호/일자, 출원인, 등록번호/일자, 공개번호/일자, 공고번호/일자, 국제출원번호/일자, 국제공개번호/일자, 우선권정보, 법적상태, 심사진행상태, 심판사항, 구분, 원출원번호/일자, 관련 출원번호, 기술이전 희망, 심사청구여부/일자, 심사청구항수의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 서지정보 표입니다.
요약 본 발명에서는 순위다중패턴매칭문제를 해결하는 해싱기반의 알고리즘을 제안한다. 순위패턴매칭은 두 문자열의 일치여부를 문자열 내의 각 문자들의 순위가 동일한 순서로 나타나는지를 기준으로 판단하는 문자열매칭방법이다. 순위패턴매칭은 주가지수분석과 음악의 유사성분석과 같이 값의 변화순서가 중요한 분야에 응용이 가능하다. 순위다중패턴매칭문제는 텍스트와 여러 개의 패턴들로 이루어진 패턴집합이 이루어졌을 때, 패턴집합내의 패턴과 각 문자들의 순위가 동일한 순서로 나타나는 텍스트의 모든 부분문자열을 찾는 문제이다.
Int. CL G06K 9/72 (2006.01.01) G06F 17/30 (2006.01.01)
CPC G06K 9/723(2013.01) G06K 9/723(2013.01)
출원번호/일자 1020150108101 (2015.07.30)
출원인 인하대학교 산학협력단
등록번호/일자 10-1662957-0000 (2016.09.28)
공개번호/일자
공고번호/일자 (20161005) 문서열기
국제출원번호/일자
국제공개번호/일자
우선권정보
법적상태 등록
심사진행상태 수리
심판사항
구분 신규
원출원번호/일자
관련 출원번호
심사청구여부/일자 Y (2015.07.30)
심사청구항수 7

출원인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 출원인 표입니다.
번호 이름 국적 주소
1 인하대학교 산학협력단 대한민국 인천광역시 미추홀구

발명자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 발명자 표입니다.
번호 이름 국적 주소
1 심정섭 대한민국 인천광역시 남동구
2 강문성 대한민국 서울특별시 관악구
3 조석현 대한민국 인천광역시 남구

대리인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 대리인 표입니다.
번호 이름 국적 주소
1 양성보 대한민국 서울특별시 강남구 선릉로***길 ** (논현동) 삼성빌딩 *층(피앤티특허법률사무소)

최종권리자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 최종권리자 표입니다.
번호 이름 국적 주소
1 인하대학교 산학협력단 대한민국 인천광역시 미추홀구
번호, 서류명, 접수/발송일자, 처리상태, 접수/발송일자의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 행정처리 표입니다.
번호 서류명 접수/발송일자 처리상태 접수/발송번호
1 [특허출원]특허출원서
[Patent Application] Patent Application		 2015.07.30 수리 (Accepted) 1-1-2015-0742917-66
2 [우선심사신청]심사청구(우선심사신청)서
[Request for Preferential Examination] Request for Examination (Request for Preferential Examination)		 2015.11.19 수리 (Accepted) 1-1-2015-1129140-64
3 [우선심사신청]선행기술조사의뢰서
[Request for Preferential Examination] Request for Prior Art Search		 2015.11.21 수리 (Accepted) 9-1-9999-9999999-89
4 [우선심사신청]선행기술조사보고서
[Request for Preferential Examination] Report of Prior Art Search		 2015.11.30 수리 (Accepted) 9-1-2015-0074391-68
5 의견제출통지서
Notification of reason for refusal		 2016.01.27 발송처리완료 (Completion of Transmission) 9-5-2016-0072147-15
6 [명세서등 보정]보정서
[Amendment to Description, etc.] Amendment		 2016.03.25 보정승인간주 (Regarded as an acceptance of amendment) 1-1-2016-0286549-27
7 [거절이유 등 통지에 따른 의견]의견(답변, 소명)서
[Opinion according to the Notification of Reasons for Refusal] Written Opinion(Written Reply, Written Substantiation)		 2016.03.25 수리 (Accepted) 1-1-2016-0286553-11
8 최후의견제출통지서
Notification of reason for final refusal		 2016.06.23 발송처리완료 (Completion of Transmission) 9-5-2016-0455541-29
9 [명세서등 보정]보정서
[Amendment to Description, etc.] Amendment		 2016.07.01 보정승인 (Acceptance of amendment) 1-1-2016-0637947-29
10 [거절이유 등 통지에 따른 의견]의견(답변, 소명)서
[Opinion according to the Notification of Reasons for Refusal] Written Opinion(Written Reply, Written Substantiation)		 2016.07.01 수리 (Accepted) 1-1-2016-0637948-75
11 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2016.09.05 수리 (Accepted) 4-1-2016-5127132-49
12 등록결정서
Decision to grant		 2016.09.23 발송처리완료 (Completion of Transmission) 9-5-2016-0683369-19
13 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2018.03.02 수리 (Accepted) 4-1-2018-5036549-31
14 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2018.12.27 수리 (Accepted) 4-1-2018-5266647-91
번호, 청구항의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 청구항 표입니다.
번호 청구항
1 1
해싱기반의 순위다중패턴매칭을 수행하는 방법에 있어서, 텍스트(T)와 k(k는 자연수) 개의 패턴()들로 구성된 패턴집합()이 주어짐에 따라 상기 패턴집합 내의 패턴과 각 문자들의 순위가 동일한 순서로 나타나는 텍스트의 모든 부분문자열을 탐색하기 위하여 이동테이블 및 해시테이블을 생성하고, 모든 에 대해 와 를 계산하는 전처리단계; 및상기 패턴 와 순위동형인 T의 모든 부분문자열의 위치를 탐색하는 검색단계를 포함하고,상기 는, 상기 가 상기 패턴집합 에 속한 문자열이고, 길이가 라고 할 때, 를 만족하는 정수 j, k에 대해 를 만족하는 배열을 의미하고,상기 는, 문자열 에서 문자 의 순위가 k라는 것을 의미하고, 는 상기 문자열 에서 k번째 순위의 문자가 라는 것을 의미하고, 상기 는, 상기 가 상기 패턴집합 에 속하고, 상기 길이가 이라 할 때, 를 만족하는 정수 j에 대해 는 상기 에서 상기 보다 크기가 작은 문자의 개수와 에서 상기 와 크기가 같은 문자의 개수를 합한 값이며, 상기 를 상기 범위에서 계산하여 저장한 배열을 의미하고, 상기 는, 상기 가 상기 패턴집합 에 속하고, 상기 길이가 이라 할 때, 상기 를 만족하는 정수 j에 대해 는 일 때 0이고, 일 때 1이고, 상기 는 상기 를 범위에서 계산하여 저장한 배열을 의미하는 것을 특징으로 하는 해싱기반의 순위다중패턴매칭 수행 방법
2 2
제1항에 있어서,상기 전처리단계는,상기 이동테이블에 존재하는 값들을 로 초기화하는 단계;상기 에 대하여 위치 에서 q-그램 에 대한 핑거프린트함수를 계산하는 단계;상기 에 대한 핑거프린트함수의 값이 인 경우, 상기 이동테이블의 번째 위치의 값을 참조하는 단계; 및상기 이동테이블의 번째 위치의 값이 보다 크다면, 로 갱신하고, 상기 이동테이블의 번째 위치의 값이 보다 작다면, 기존의 값을 유지하는 단계를 포함하고, 상기 m은, 상기 패턴집합에서 가장 짧은 패턴의 길이, 상기 q-그램은, 길이가 q인 문자열을 하나의 단위로 취급하는 개념을 의미하고, 상기 q는, 상기 q-그램에 속한 문자의 수를 의미하고,상기 는, 상기 가 상기 패턴집합 에 속하고, 상기 길이가 라 할 때, 정수 l, q는 를 만족하는 경우, 상기 의 l-q+1번째 문자에서 시작하고 l번째 문자에서 끝나는 길이가 q인 부분문자열을 의미하는것을 특징으로 하는 해싱기반의 순위다중패턴매칭 수행 방법
3 3
제2항에 있어서,상기 전처리단계는,상기 패턴집합내의 가장 오른쪽에서 가 발생한 위치를 기준으로 계산된 이동거리를 이동테이블의 번째 위치에 저장하는 단계를 포함하는 해싱기반의 순위다중패턴매칭 수행 방법
4 4
제1항에 있어서,상기 전처리단계는,상기 해시테이블을 생성하기 위하여 상기 의 길이가 q인 접미사 에 대한 핑거프린트함수를 계산하는 단계; 및상기 에 대한 핑거프린트함수의 값이 인 경우, 상기 해시테이블의 번째 위치에 저장된 패턴들의 리스트에 를 추가하는 단계를 포함하고,상기 m은, 상기 패턴집합에서 가장 짧은 패턴의 길이, 상기 는, 상기 가 상기 패턴집합 에 속하고, 상기 에 속한 패턴 중 가장 짧은 패턴의 길이가 m이고, 정수 q는 을 만족하는 경우, 상기 의 m-q+1번째 문자에서 시작하고 m번째 문자에서 끝나는 길이가 q인 의 부분문자열을 의미하는것을 특징으로 하는 해싱기반의 순위다중패턴매칭 수행 방법
5 5
제1항에 있어서,상기 검색단계는,상기 텍스트 T의 검색위치를 j라 할 때, 상기 j가 m부터 시작하여 n에 도달할 때까지 진행되며,상기 검색위치 j에서 q-그램 에 대하여 핑거프린트함수를 계산하는 단계;상기 핑거프린트함수의 값이 라면, 상기 이동테이블의 번째 값을 참조하여 이동거리 s를 도출하는 단계; 상기 s가 0임에 따라 순위동형이 발생 가능한 경우에 상기 해시테이블의 번째 값에 포함된 모든 에 대해 상기 와 상기 를 사용하여 와 의 순위동형 여부를 조사하고, 상기 검색위치 j를 오른쪽으로 1만큼 이동시키는 단계; 및상기 s가 0이 아닌 경우에 상기 j를 오른쪽으로 s만큼 이동시키는 단계를 포함하고,상기 q는, 상기 q-그램에 속한 문자의 수,상기 m은, 상기 패턴집합에서 가장 짧은 패턴의 길이, 상기 n은 상기 텍스트의 길이,상기 는, 상기 의 길이, 상기 는, 상기 의 길이, 상기 는, 상기 텍스트 T에 대하여 정수 j, q가 을 만족할 때, 상기 텍스트 T의 j-q+1번째 문자부터 시작하고 j번째 문자에서 끝나는 길이가 q인 상기 텍스트 T의 부분문자열,상기 는, 상기 텍스트 T에 대하여 정수 j, q가 을 만족할 때, j-m+1번째 문자에서 시작하여 번째 문자에서 끝나는 상기 텍스트 T의 부분문자열을 의미하는 것을 특징으로 하는 해싱기반의 순위다중패턴매칭 수행 방법
6 6
제1항에 있어서,가장 긴 패턴의 길이를 이라고 하고, 상기 이동테이블을 생성할 때, 상기 의 위치 에서 에 대한 핑거프린트함수를 계산하므로 시간이 소요되고, 상기 해시테이블을 생성할 때, 상기 의 에 대해 핑거프린트함수를 계산하므로 시간이 소요되고,패턴집합에 속한 모든 패턴 에 대해 와 를 계산할 때 시간이 소요되고,상기 전처리단계를 계산하기 위한 시간은,시간에 계산되는 단계를 포함하고,상기 q는, 상기 q-그램에 속한 문자의 수, 상기 m은, 상기 패턴집합에서 가장 짧은 패턴의 길이,상기 M은, 상기 패턴집합 에 속한 패턴들의 길이의 합을 의미하는것을 특징으로 하는 해싱기반의 순위다중패턴매칭 수행 방법
7 7
해싱기반의 순위다중패턴매칭을 수행하는 장치에 있어서, 텍스트(T)와 k(k는 자연수) 개의 패턴()들로 구성된 패턴집합()이 주어짐에 따라 상기 패턴집합 내의 패턴과 각 문자들의 순위가 동일한 순서로 나타나는 텍스트의 모든 부분문자열을 탐색하기 위하여 이동테이블 및 해시테이블을 생성하고, 모든 에 대해 와 를 계산하는 전처리부; 및상기 패턴 와 순위동형인 T의 모든 부분문자열의 위치를 탐색하는 검색부를 포함하고,상기 는, 상기 가 상기 패턴집합 에 속한 문자열이고, 길이가 라고 할 때, 를 만족하는 정수 j, k에 대해 를 만족하는 배열을 의미하고,상기 는, 문자열 에서 문자 의 순위가 k라는 것을 의미하고, 는 상기 문자열 에서 k번째 순위의 문자가 라는 것을 의미하고, 상기 는, 상기 가 상기 패턴집합 에 속하고, 상기 길이가 이라 할 때, 를 만족하는 정수 j에 대해 는 상기 에서 상기 보다 크기가 작은 문자의 개수와 에서 상기 와 크기가 같은 문자의 개수를 합한 값이며, 상기 를 상기 범위에서 계산하여 저장한 배열을 의미하고, 상기 는, 상기 가 상기 패턴집합 에 속하고, 상기 길이가 이라 할 때, 상기 를 만족하는 정수 j에 대해 는 일 때 0이고, 일 때 1이고, 상기 는 상기 를 범위에서 계산하여 저장한 배열을 의미하는 것을 특징으로 하는 해싱기반의 순위다중패턴매칭 수행 장치
지정국 정보가 없습니다
패밀리정보가 없습니다
순번, 연구부처, 주관기관, 연구사업, 연구과제의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 국가R&D 연구정보 정보 표입니다.
순번 연구부처 주관기관 연구사업 연구과제
1 미래창조과학부 인하대학교 산학협력단 도약연구지원사업(전략)(상향식) 시계열데이터 패턴분석을 위한 순위패턴매칭 알고리즘 개발