순위다중패턴매칭문제에 대한 공간효율적인 해싱기반 알고리즘

박정훈; 김영호; 심정섭; Jeonghoon Park; Youngho Kim; Jeong Seop Sim

연구문헌

국내 논문지

홈 > 연구문헌 > 국내 논문지 > 한국정보과학회 논문지 > 정보과학회 컴퓨팅의 실제 논문지 (KIISE Transactions on Computing Practices)

정보과학회 컴퓨팅의 실제 논문지 (KIISE Transactions on Computing Practices)

Current Result Document : 6 / 74 이전건 다음건

한글제목(Korean Title)	순위다중패턴매칭문제에 대한 공간효율적인 해싱기반 알고리즘
영문제목(English Title)	A Space-Efficient Hashing-Based Algorithm for Order-Preserving Multiple Pattern Matching Problem
저자(Author)	박정훈 김영호 심정섭 Jeonghoon Park Youngho Kim Jeong Seop Sim
원문수록처(Citation)	VOL 24 NO. 08 PP. 0399 ~ 0404 (2018. 08)
한글내용 (Korean Abstract)	길이가 같은 두 문자열 x,y 가 주어졌을 때, x와 y 의 문자들의 순위가 모두 일치하면 x 와 y는 순위동형이라 한다. 순위다중패턴매칭문제는 텍스트 T와 k개의 패턴들로 구성된 패턴집합 P이 주어질 때, P에 속한 패턴과 순위동형을 이루는 T의 모든 부분문자열을 찾는 문제이다. 본 논문에서는 q-그램의 크기를 q라 하고 패턴들의 길이의 총합을 M 이라 할 때, 기존의 순위다중패턴매칭문제를 해결하는 해싱기반 알고리즘을 개선하여 공간복잡도를 O (q!+k+M)에서 O(k+M)으로 줄인 알고리즘을 제시한다.
영문내용 (English Abstract)	Given two strings x and y of the same length, when all ranks of characters in x and y are the same, x is order-isomorphic to y . Given a text T and a pattern set P consisting of k patterns, order-preserving multiple pattern matching problem is to find all substrings in T that are order-isomorphic to any pattern in P. In this paper, when the size of a q-gram is q and the sum of lengths of patterns is M, we propose a space-efficient hashing-based algorithm for order-preserving multiple pattern matching problem to reduce space complexity from O (q! k M)to O(k M) .
키워드(Keyword)	패턴매칭 순위동형 순위다중패턴매칭 핑거프린트 테이블 pattern matching order-isomorphism order-preserving multiple pattern matching fingerprint table
파일첨부	PDF 다운로드