KR20200075295A - 2차 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭 알고리즘 - Google Patents

2차 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭 알고리즘 Download PDF

Info

Publication number
KR20200075295A
KR20200075295A KR1020180163814A KR20180163814A KR20200075295A KR 20200075295 A KR20200075295 A KR 20200075295A KR 1020180163814 A KR1020180163814 A KR 1020180163814A KR 20180163814 A KR20180163814 A KR 20180163814A KR 20200075295 A KR20200075295 A KR 20200075295A
Authority
KR
South Korea
Prior art keywords
gram
ranking
pattern
fingerprint
pattern matching
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
KR1020180163814A
Other languages
English (en)
Other versions
KR102158317B1 (ko
Inventor
심정섭
유광모
김영호
Original Assignee
인하대학교 산학협력단
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 인하대학교 산학협력단 filed Critical 인하대학교 산학협력단
Priority to KR1020180163814A priority Critical patent/KR102158317B1/ko
Publication of KR20200075295A publication Critical patent/KR20200075295A/ko
Application granted granted Critical
Publication of KR102158317B1 publication Critical patent/KR102158317B1/ko
Assigned to 심정섭 reassignment 심정섭 권리의 전부이전등록 Assignors: 인하대학교 산학협력단
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/02—Comparing digital values

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Software Systems (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

일 실시예에 따른 핑거프린트를 이용한 순위패턴매칭 방법은, 패턴(P)에 대한 위치테이블, 이동테이블 및 복수 개의 q-그램에 대한 핑거프린트를 계산하는 전처리 단계; 및 상기 패턴(P)에 대한 위치테이블, 상기 이동테이블 및 상기 복수 개의 q-그램에 대한 핑거프린트를 계산한 값을 이용하여 상기 패턴(P)과 순위동형인 텍스트(T)의 부분문자열을 탐색하는 계산 단계를 포함할 수 있다.

Description

2차 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭 알고리즘{AN ORDER-PRESERVING PATTERN MATCHING ALGORITHM USING FINGERPRINT OF SECONDARY Q-GRAMS}
아래의 설명은 복수 개의 q-그램에 대한 핑거프린트를 이용하여 수행시간을 개선한 순위패턴매칭 알고리즘에 관한 것이다.
두 문자열의 길이가 같고, 각 문자열에서 문자들의 상대적인 순위가 모든 위치에서 일치하면 순위동형이라 한다. 예를 들면, T=(15, 33, 26, 41, 7, 6, 51)와 P=(33, 21, 7)가 주어졌을 때,
Figure pat00001
과 P는 순위동형이다. 순위패턴매칭문제(order-preserving pattern matching problem)는 대소비교가 가능한 알파벳
Figure pat00002
로 구성된 텍스트 T와 패턴 P가 주어졌을 때, P와 순위동형인 T의 모든 부분문자열을 찾는 문제이다. 이때, 순위패턴매칭문제는 두 음악의 유사멜로디 검출이나 주가분석 등에 활용될 수 있다.
최근 순위패턴매칭문제를 해결하기 위한 연구들이 활발하게 진행되고 있다. 길이가 각각 n, m인 텍스트 T와 패턴 P가 주어졌을 때, 순위패턴매칭문제를 KMP알고리즘을 기반으로
Figure pat00003
시간에 해결하는 알고리즘이 제시되었다. 다른 연구에서는 P와 순위동형인 T의 부분문자열의 개수를 occ라 할 때, 순위접미사트리(order-preserving suffix trees)를
Figure pat00004
시간에 생성하는 알고리즘을 제시하고, 이를 이용하여 순위패턴매칭문제를
Figure pat00005
시간에 해결하는 알고리즘을 제시하였다. 또 다른 연구에서는 q개의 연속된 문자인 q-그램(q-gram)에 대한 핑거프린트(fingerprint)와 Horspool 알고리즘의 오문자규칙(bad-character heuristic)을 이용하여, 정수 알파벳일 때
Figure pat00006
시간, 일반 알파벳일 때
Figure pat00007
시간에 순위패턴매칭문제를 해결하는 알고리즘을 제시하였고, KMP 알고리즘을 함께 이용하여 정수 알파벳일 때
Figure pat00008
시간, 일반 알파벳일 때
Figure pat00009
시간에 순위패턴매칭문제를 해결하는 알고리즘이 제시되었다.
복수 개의 q-그램에 대한 핑거프린트들을 이용한 순위패턴매칭 알고리즘을 제공할 수 있다.
전처리부 및 계산부를 포함하는 순위패턴매칭 장치에서 수행되는 핑거프린트를 이용한 순위패턴매칭 방법은, 상기 전처리부에서, 패턴(P)에 대한 위치테이블, 이동테이블 및 복수 개의 q-그램에 대한 핑거프린트를 계산하는 전처리 단계; 및 상기 계산부에서, 상기 패턴(P)에 대한 위치테이블, 상기 이동테이블 및 상기 복수 개의 q-그램에 대한 핑거프린트를 계산한 값을 이용하여 상기 패턴(P)과 순위동형인 텍스트(T)의 부분문자열을 탐색하는 계산 단계를 포함할 수 있다.
상기 복수 개의 q-그램은, 상기 패턴(P)와 텍스트(T)가 주어졌을 때, 상기 패턴(P)의 가장 오른쪽 q-그램을 1차 q-그램, 상기 1차 q-그램을 기준으로 상기 1차 q-그램의 이전에 위치한 q- 그램을 2차 q-그램이라고 하고, 상기 1차 q-그램 및 상기 2차 q-그램을 포함할 수 있다.
상기 계산 단계는,
Figure pat00010
과 비교를 시작하는 텍스트(T)의 위치를 i라고 할 때, 각
Figure pat00011
에 대해 1차 q-그램의 핑거프린트인
Figure pat00012
와
Figure pat00013
가 일치하는지 판단하는 단계를 포함할 수 있다.
상기 계산 단계는, 상기 각
Figure pat00014
에 대해 1차 q-그램의 핑거프린트인
Figure pat00015
와
Figure pat00016
가 일치할 경우, 2차 q-그램의 핑거프린트인
Figure pat00017
와
Figure pat00018
가 일치하는지 확인하는 단계를 포함할 수 있다.
상기 계산 단계는, 상기 2차 q-그램의 핑거프린트인
Figure pat00019
와
Figure pat00020
가 일치할 경우, 패턴(P)와
Figure pat00021
의 순위동형 여부를 위치테이블을 이용하여 확인하고,
Figure pat00022
을 단계를 포함할 수 있다.
상기 계산 단계는, 순위동형 여부에 관계없이 텍스트의 위치(i)를
Figure pat00023
만큼 증가시기는 단계를 포함할 수 있다.
순위패턴매칭 장치는, 패턴(P)에 대한 위치테이블, 이동테이블 및 복수 개의 q-그램에 대한 핑거프린트를 계산하는 전처리부; 및 상기 패턴(P)에 대한 위치테이블, 상기 이동테이블 및 상기 복수 개의 q-그램에 대한 핑거프린트를 계산한 값을 이용하여 상기 패턴(P)과 순위동형인 텍스트(T)의 부분문자열을 탐색하는 계산부를 포함할 수 있다.
2개의 q-그램을 이용하여 순위동형을 검증하는 횟수를 감소시켜 수행속도를 개선할 수 있다.
도 1은 일 실시예에 따른 2개의 q-그램에 대한 핑거프린트들을 이용한 순위패턴매칭 알고리즘을 나타낸 예이다.
도 2는 일 실시예에 따른 순위패턴매칭 장치의 구성을 설명하기 위한 블록도이다.
도 3은 일 실시예에 따른 순위패턴매칭 장치에서 수행되는 순위패턴매칭 방법을 설명하기 위한 흐름도이다.
도 4는 일 실시예에 있어서, 텍스트 T와 q-그램 핑거프린트의 분포율을 나타낸 그래프이다.
이하, 실시예를 첨부한 도면을 참조하여 상세히 설명한다.
알파벳
Figure pat00024
는 상수시간에 비교 가능한 정수문자 집합이다.
Figure pat00025
로 구성된 길이가 m인 문자열들의 집합을
Figure pat00026
로 표기한다. 문자열
Figure pat00027
의 길이를
Figure pat00028
,
Figure pat00029
의 i번째
Figure pat00030
문자를
Figure pat00031
로 표시한다. 문자열
Figure pat00032
의 i번째부터 j번째까지의 부분문자열
Figure pat00033
를
Figure pat00034
로 표기한다.
Figure pat00035
에서 i=0이면, 이를
Figure pat00036
의 접두사(prefix)라고 하고,
Figure pat00037
이면
Figure pat00038
의 접미사(suffix)라 한다. 두 문자열
Figure pat00039
,
Figure pat00040
에 대해
Figure pat00041
이고
Figure pat00042
이면
Figure pat00043
,
Figure pat00044
는 순위동형이라 하고
Figure pat00045
로 표기한다.
문자열의 순위관계를 표현하는 방법으로 접두사표현(prefix representation)과 최근접이웃표현(nearest neighbor representation)이 있다. 문자열
Figure pat00046
의 접두사표현은 접두사테이블(prefix table)
Figure pat00047
를 이용하여 정의된다.
Figure pat00048
다시 말해서,
Figure pat00049
는 문자열
Figure pat00050
에서
Figure pat00051
보다 작은 문자들의 수이다. 문자열
Figure pat00052
,
Figure pat00053
Figure pat00054
에 대한
Figure pat00055
가 주어졌을 때,
Figure pat00056
이면,
Figure pat00057
이다.
문자열
Figure pat00058
에 대한 최근접이웃표현은 위치테이블(location table)
Figure pat00059
,
Figure pat00060
을 이용하여 정의된다.
Figure pat00061
Figure pat00062
다시 말해서,
Figure pat00063
는
Figure pat00064
에서
Figure pat00065
보다 작은 값 중 가장 큰 값의 위치
Figure pat00066
이고,
Figure pat00067
은
Figure pat00068
에서
Figure pat00069
보다 큰 값 중 가장 작은 값의 위치 j이다. 만약 그러한 j가 복수 개 존재한다면, 가장 큰 위치를 저장한다. 만약, 그러한 위치 j가 존재하지 않으면, -1을 저장한다. 문자열
Figure pat00070
,
Figure pat00071
Figure pat00072
와
Figure pat00073
,
Figure pat00074
가 주어졌을 때,
Figure pat00075
이면,
Figure pat00076
이다.
표 1은 문자열 P=(11, 83, 32, 40, 9, 56)일 때, P에 대한 접두사테이블
Figure pat00077
와 위치테이블
Figure pat00078
,
Figure pat00079
를 보여준다. 접두사테이블은 순위통계트리, 위치테이블은 정렬알고리즘을 이용하여 각각
Figure pat00080
시간에 계산할 수 있다.
표 1: P=(11, 83, 32, 40, 9, 56)에 대한 접두사테이블과 위치테이블
Figure pat00081
순위패턴매칭문제에서 입력은 텍스트
Figure pat00082
, 패턴
Figure pat00083
이고, 출력은
Figure pat00084
인 모든 위치 i 이다. 편의상 P와 T는 서로 다른 정수로 구성된다고 가정한다.
도 1은 일 실시예에 따른 2개의 q-그램에 대한 핑거프린트들을 이용한 순위패턴매칭 알고리즘을 나타낸 예이다.
실시예에서는 복수 개의 q-그램, 예를 들면, 2개의 q-그램을 이용하여 순위동형을 검증하는 횟수를 감소시켜 수행속도를 개선하는 방법을 설명하기로 한다. 예를 들면, q 개의 연속된 문자인 q-그램
Figure pat00085
에 대한 핑거프린트
Figure pat00086
가 다음과 같이 정의될 수 있다.
Figure pat00087
이때,
Figure pat00088
는 계승수체계(factorial number system)를 사용하므로 0~q!-1 중 하나의 정수로 변환될 수 있다. 예를 들면, q=3일 때, q-그램
Figure pat00089
=(11, 83, 32)라면,
Figure pat00090
=(0, 1, 1)이며,
Figure pat00091
에 대한 핑거프린트
Figure pat00092
=(0X0!)+(1X1!)+(1X2!)=3이다.
Figure pat00093
일 때,
Figure pat00094
의 일치여부를 확인한 뒤 일치하였을 경우에 위치테이블을 이용하여 순위동형 여부를 확인한다. 이때,
Figure pat00095
는 패턴 P의 가장 오른쪽 q-그램 핑거프린트를 의미할 수 있다.
도 2는 일 실시예에 따른 순위패턴매칭 장치의 구성을 설명하기 위한 블록도이고, 도 3은 일 실시예에 따른 순위패턴매칭 장치에서 수행되는 순위패턴매칭 방법을 설명하기 위한 흐름도이다.
실시예에서 제시하는 알고리즘은 전처리 단계(310)와 계산 단계(320)로 구성될 수 있다. 이러한 알고리즘은 전처리부(210)와 계산부(220)를 포함하는 순위패턴매칭 장치(200)에 의해 수행될 수 있다.
Figure pat00096
을 P의 1차 q-그램,
Figure pat00097
을 P의 2차 q-그램이라고 하자. 다시 말해서, 2차 q-그램은 1차 q-그램의 바로 앞에 위치한 q-그램이 된다.
전처리 단계(310)에서 전처리부(210)는 패턴 P에 대한 위치테이블과 이동테이블, 2개의 q-그램에 대한 핑거프린트를 계산할 수 있다. 이때, 예를 들면, 이동테이블 D는 모든 가능한 q-그램
Figure pat00098
에 대해 최대이동거리 m-q+1로 초기화한 뒤, 다음의 수식을 이용하여 계산될 수 있다. 이동테이블 D는 모든 가능한 q-그램에 대한 정보를 저장할 수 있다.
Figure pat00099
계산 단계(320)에서 계산부(220)는 패턴 P에 대한 위치테이블과 이동테이블, 2개의 q-그램에 대한 핑거프린트를 계산한 각각의 값을 이용하여 패턴 P와 순위동형인 텍스트 T의 모든 부분문자열을 탐색할 수 있다. 구체적으로,
Figure pat00100
과 비교를 시작하는 텍스트 T의 위치를 i라고 할 때, 각
Figure pat00101
에 대해 1차 q-그램의 핑거프린트인
Figure pat00102
와
Figure pat00103
가 일치하면 2차 q-그램의 핑거프린트인
Figure pat00104
와
Figure pat00105
가 일치하는지 확인한다. 만약, 2차q-그램의 핑거프린트도 일치하면, 패턴 P와
Figure pat00106
의 순위동형 여부를 위치테이블을 이용하여 확인하여
Figure pat00107
이면, 위치 i-m+1을 출력할 수 있다. 이후, 순위동형 여부에 관계없이 i를
Figure pat00108
만큼 증가시키고 위 과정을 반복할 수 있다.
도 1을 참고하면, 예를 들면, T=(15, 33, 26, 41, 18, 6, 51, 99, 36, 2)와 P=(33, 21, 7, 35, 70)이 주어졌을 때, 단계 7은 다음과 같이 수행될 수 있다. 텍스트 T와 패턴 P의 1차 q-그램의 핑거프린트가 5로 일치하므로 2차 q-그램의 핑거프린트를 계산하고 비교한다. 이 두 값도 4로 일치하므로 두 문자열이 순위동형인지 확인한다. 순위동형을 확인한 결과,
Figure pat00109
이므로 3을 출력하고 이동테이블 D[5]=3을 이용하여 비교위치i를 10으로 증가시킨다. 이때, i>n-1이므로 탐색을 종료한다.
실시예에서 제안된 알고리즘의 전처리 단계에서 패턴 P에 대한 위치테이블, 이동테이블은 각각
Figure pat00110
,
Figure pat00111
시간에 계산할 수 있다. 계산 단계에서 q-그램들의 핑거프린트 계산과, P와
Figure pat00112
의 순위동형 확인은 각각 총
Figure pat00113
시간,
Figure pat00114
시간에 수행할 수 있다. 이에 따라, 실시예에서 제안된 알고리즘의 총 수행시간은
Figure pat00115
시간이 된다.
도 4는 일 실시예에 있어서, 텍스트 T와 q-그램 핑거프린트의 분포율을 나타낸 그래프이다.
실시예에서 제안된 알고리즘에 대한 실험이 수행될 수 있다. 실험 환경으로 OS는 Windows 10(64 비트), CPU 및 RAM은 Intel Core i7-6700(3.4GHz), 32GB RAM, 개발 툴 및 언어는 Visual studio 2015, c++이 구성될 수 있다. 텍스트 T와 패턴 P는 C++ boost library를 이용하여
Figure pat00116
에 대해 무작위로 생성한 정수형 문자열(n=5,000,000)과 1985년 2월 16일부터 2010년 12월 31일까지의 다우존스산업평균지수의 일별 종가(n=34,685)로 생성한 다우존스지수 데이터를 이용하였다. m은 5, 10, 15에 대해, q는 3부터 7까지 변경하며 실험이 진행될 수 있다.
수행시간은 무작위로 생성된 정수형 문자열에 대해 1000번 실험한 수행시간의 합으로, 다우존스지수 데이터에 대해 10000번 실험한 수행시간의 합이 측정될 수 있다. 무작위로 생성한 문자열의 경우 패턴 또한 무작위로 생성될 수 있으며, 다우존스지수 데이터에서 패턴은 T의 위치에서 무작위로 추출될 수 있다. 편의상 종래의 연속된 문자인 q-그램(q-gram)에 대한 핑거프린트(fingerprint)와 Horspool 알고리즘의 오문자규칙(bad-character heuristic)을 이용하여 순위패턴매칭문제를 해결하는 알고리즘을 OPQ, 실시예에서 제안된 알고리즘을 OPSQ로 기재하여 설명하기로 한다.
제1 실험으로서, 입력 데이터에 대한 수행시간을 비교하는 실험이 수행될 수 있다. 표 2는 입력 데이터에 따른 OPQ와 OPSQ의 수행시간을 나타낸 것이다. 각 실험에서 수행시간이 가장 빠른 알고리즘을 진하게 표시하였다.
표 2: m=4, 10, 15, 3≤q≤7에 대한 OPQ와 OPSQ의 수행시간
Figure pat00117
ran은 무작위로 생성된 입력 데이터, dow는 다우존스지수 입력 데이터를 의미한다. ran의 경우, m=10, q=3일 때, OPSQ 가 OPQ보다 약 12% 빠르게 수행되었다. m, q의 크기와 상관없이 모든 경우에서 OPSQ 가 OPQ보다 평균 약 9% 빠른 수행시간을 보여준다.
Figure pat00118
= 4, 10인 경우에도 유사한 결과를 보인다.
dow의 경우, m=10, q=3일 때, OPSQ 가 OPQ보다 최대 약 10% 빠르게 수행되었다. 그런데, q≥4일 때에는 ran의 경우와 달리, OPSQ의 수행시간은 OPQ에 비해 크게 개선되지 않고 평균적으로 1% 정도 빠르게 수행되었다. 특히, m=15, q=6일 때, OPSQ는 OPQ보다 오히려 느린 수행시간을 보인다. 이러한 결과에 대해서 다음 실험을 통하여 분석할 수 있다.
제2 실험은 알고리즘의 성능에 영향을 미치는 요소는 분석한 것이다. 제1 실험의 결과, 실시예에서 제안된 알고리즘은 dow의 경우, q≥4일 때 기존의 알고리즘보다 수행시간이 크게 개선되지 않았다. 이는 다우존스지수의 특성상 q-그램 핑거프린트가 균일하게 나타나지 않기 때문이라 유추될 수 있다. 이러한 경우, 알고리즘의 성능을 향상시키기 위하여 제1 실험에서 사용된 텍스트 T의 모든 q-그램 핑거프린트의 분포를 확인하고 그 결과를 이용하여 패턴을 추출한 실험이 진행될 수 있다.
도 4는 제1 실험에서 사용한 ran과 dow에서 길이가 각각 3, 4이고, 시작 위치가
Figure pat00119
인 q-그램 핑거프린트
Figure pat00120
의 분포를 나타낸 것이다. 핑거프린트 함수에 의하면, q가 커질수록 가능한 핑거프린트의 범위는 증가한다. ran에 대해서는 모든 핑거프린트가 거의 동일하게 분포되지만, dow는 그렇지 않으며, 특히 핑거프린트가 q!-1인 경우 자주 발생되었다. 과거부터 지속적으로 주가가 상승해온 dow의 특성에 의한 것으로 판단된다. 이러한 이유로 제1 실험의 dow에서 패턴을 랜덤으로 추출하였지만 2차 q-그램 핑거프린트가 q!-1인 경우가 상대적으로 많았고, 이로 인하여 순위동형 검증 횟수를 줄인 효과가 감소하여 ran에 비해 수행시간이 크게 줄지 않았다.
표 3은 제1 실험에서 사용된 dow를 패턴 P에서 생성할 때, P의 1, 2차 q-그램 핑거프린트가 q!-1이 되지 않도록 추출하여 실험한 OPQ와 OPSQ의 수행시간이다. 실험결과, 모든 경우에서 제1 실험의 OPSQ보다 제2 실험의 OPSQ가 더 빠르게 수행되었다. q=3일 때, OPSQ가 OPQ보다 평균 18% 정도 빠르게 수행되었고, q≥4일 때도 평균적으로 11% 정도 빠르게 수행되었다. 특히, m=15, q=3일 때는 OPSQ가 OPQ보다 약 23% 빠르게 수행되었다.
표 3: T에서 드물게 나타나는 부분문자열을 P로 설정했을 때의 OPQ와 OPSQ의 수행시간
Figure pat00121
이상에서 설명된 장치는 하드웨어 구성요소, 소프트웨어 구성요소, 및/또는 하드웨어 구성요소 및 소프트웨어 구성요소의 조합으로 구현될 수 있다. 예를 들어, 실시예들에서 설명된 장치 및 구성요소는, 예를 들어, 프로세서, 콘트롤러, ALU(arithmetic logic unit), 디지털 신호 프로세서(digital signal processor), 마이크로컴퓨터, FPGA(field programmable gate array), PLU(programmable logic unit), 마이크로프로세서, 또는 명령(instruction)을 실행하고 응답할 수 있는 다른 어떠한 장치와 같이, 하나 이상의 범용 컴퓨터 또는 특수 목적 컴퓨터를 이용하여 구현될 수 있다. 처리 장치는 운영 체제(OS) 및 상기 운영 체제 상에서 수행되는 하나 이상의 소프트웨어 애플리케이션을 수행할 수 있다. 또한, 처리 장치는 소프트웨어의 실행에 응답하여, 데이터를 접근, 저장, 조작, 처리 및 생성할 수도 있다. 이해의 편의를 위하여, 처리 장치는 하나가 사용되는 것으로 설명된 경우도 있지만, 해당 기술분야에서 통상의 지식을 가진 자는, 처리 장치가 복수 개의 처리 요소(processing element) 및/또는 복수 유형의 처리 요소를 포함할 수 있음을 알 수 있다. 예를 들어, 처리 장치는 복수 개의 프로세서 또는 하나의 프로세서 및 하나의 콘트롤러를 포함할 수 있다. 또한, 병렬 프로세서(parallel processor)와 같은, 다른 처리 구성(processing configuration)도 가능하다.
소프트웨어는 컴퓨터 프로그램(computer program), 코드(code), 명령(instruction), 또는 이들 중 하나 이상의 조합을 포함할 수 있으며, 원하는 대로 동작하도록 처리 장치를 구성하거나 독립적으로 또는 결합적으로(collectively) 처리 장치를 명령할 수 있다. 소프트웨어 및/또는 데이터는, 처리 장치에 의하여 해석되거나 처리 장치에 명령 또는 데이터를 제공하기 위하여, 어떤 유형의 기계, 구성요소(component), 물리적 장치, 가상 장치(virtual equipment), 컴퓨터 저장 매체 또는 장치에 구체화(embody)될 수 있다. 소프트웨어는 네트워크로 연결된 컴퓨터 시스템 상에 분산되어서, 분산된 방법으로 저장되거나 실행될 수도 있다. 소프트웨어 및 데이터는 하나 이상의 컴퓨터 판독 가능 기록 매체에 저장될 수 있다.
실시예에 따른 방법은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체에 기록되는 프로그램 명령은 실시예를 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다.
이상과 같이 실시예들이 비록 한정된 실시예와 도면에 의해 설명되었으나, 해당 기술분야에서 통상의 지식을 가진 자라면 상기의 기재로부터 다양한 수정 및 변형이 가능하다. 예를 들어, 설명된 기술들이 설명된 방법과 다른 순서로 수행되거나, 및/또는 설명된 시스템, 구조, 장치, 회로 등의 구성요소들이 설명된 방법과 다른 형태로 결합 또는 조합되거나, 다른 구성요소 또는 균등물에 의하여 대치되거나 치환되더라도 적절한 결과가 달성될 수 있다.
그러므로, 다른 구현들, 다른 실시예들 및 특허청구범위와 균등한 것들도 후술하는 특허청구범위의 범위에 속한다.

Claims (7)

  1. 전처리부 및 계산부를 포함하는 순위패턴매칭 장치에서 수행되는 핑거프린트를 이용한 순위패턴매칭 방법에 있어서,
    상기 전처리부에서, 패턴(P)에 대한 위치테이블, 이동테이블 및 복수 개의 q-그램에 대한 핑거프린트를 계산하는 전처리 단계; 및
    상기 계산부에서, 상기 패턴(P)에 대한 위치테이블, 상기 이동테이블 및 상기 복수 개의 q-그램에 대한 핑거프린트를 계산한 값을 이용하여 상기 패턴(P)과 순위동형인 텍스트(T)의 부분문자열을 탐색하는 계산 단계
    를 포함하는 순위패턴매칭 방법.
  2. 제1항에 있어서,
    상기 복수 개의 q-그램은,
    상기 패턴(P)와 텍스트(T)가 주어졌을 때, 상기 패턴(P)의 가장 오른쪽 q-그램을 1차 q-그램, 상기 1차 q-그램을 기준으로 상기 1차 q-그램의 이전에 위치한 q- 그램을 2차 q-그램이라고 하고, 상기 1차 q-그램 및 상기 2차 q-그램을 포함하는 순위패턴매칭 방법.
  3. 제1항에 있어서,
    상기 계산 단계는,
    Figure pat00122
    과 비교를 시작하는 텍스트(T)의 위치를 i라고 할 때, 각
    Figure pat00123
    에 대해 1차 q-그램의 핑거프린트인
    Figure pat00124
    와
    Figure pat00125
    가 일치하는지 판단하는 단계
    를 포함하는 순위패턴매칭 방법.
  4. 제3항에 있어서,
    상기 계산 단계는,
    상기 각
    Figure pat00126
    에 대해 1차 q-그램의 핑거프린트인
    Figure pat00127
    와
    Figure pat00128
    가 일치할 경우, 2차 q-그램의 핑거프린트인
    Figure pat00129
    와
    Figure pat00130
    가 일치하는지 확인하는 단계
    를 포함하는 순위패턴매칭 방법.
  5. 제4항에 있어서,
    상기 계산 단계는,
    상기 2차 q-그램의 핑거프린트인
    Figure pat00131
    와
    Figure pat00132
    가 일치할 경우, 패턴(P)와
    Figure pat00133
    의 순위동형 여부를 위치테이블을 이용하여 확인하고,
    Figure pat00134
    을 단계
    를 포함하는 순위패턴매칭 방법.
  6. 제1항에 있어서,
    상기 계산 단계는,
    순위동형 여부에 관계없이 텍스트의 위치(i)를
    Figure pat00135
    만큼 증가시기는 단계
    를 포함하는 순위패턴매칭 방법.
  7. 순위패턴매칭 장치에 있어서,
    패턴(P)에 대한 위치테이블, 이동테이블 및 복수 개의 q-그램에 대한 핑거프린트를 계산하는 전처리부; 및
    상기 패턴(P)에 대한 위치테이블, 상기 이동테이블 및 상기 복수 개의 q-그램에 대한 핑거프린트를 계산한 값을 이용하여 상기 패턴(P)과 순위동형인 텍스트(T)의 부분문자열을 탐색하는 계산부
    를 포함하는 순위패턴매칭 장치.
KR1020180163814A 2018-12-18 2018-12-18 2차 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭 알고리즘 Active KR102158317B1 (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020180163814A KR102158317B1 (ko) 2018-12-18 2018-12-18 2차 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭 알고리즘

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020180163814A KR102158317B1 (ko) 2018-12-18 2018-12-18 2차 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭 알고리즘

Publications (2)

Publication Number Publication Date
KR20200075295A true KR20200075295A (ko) 2020-06-26
KR102158317B1 KR102158317B1 (ko) 2020-09-21

Family

ID=71136959

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020180163814A Active KR102158317B1 (ko) 2018-12-18 2018-12-18 2차 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭 알고리즘

Country Status (1)

Country Link
KR (1) KR102158317B1 (ko)

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0696124A (ja) * 1992-09-11 1994-04-08 Sumitomo Metal Ind Ltd 情報検索装置
KR20110110736A (ko) * 2010-04-01 2011-10-07 삼성전자주식회사 핵산 서열을 검색하는 방법, 장치 및 시스템
JP2014063306A (ja) * 2012-09-20 2014-04-10 Casio Comput Co Ltd 検索装置、検索方法及びプログラム
KR101662957B1 (ko) * 2015-07-30 2016-10-05 인하대학교 산학협력단 해싱기반의 순위다중패턴매칭 방법

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0696124A (ja) * 1992-09-11 1994-04-08 Sumitomo Metal Ind Ltd 情報検索装置
KR20110110736A (ko) * 2010-04-01 2011-10-07 삼성전자주식회사 핵산 서열을 검색하는 방법, 장치 및 시스템
JP2014063306A (ja) * 2012-09-20 2014-04-10 Casio Comput Co Ltd 検索装置、検索方法及びプログラム
KR101662957B1 (ko) * 2015-07-30 2016-10-05 인하대학교 산학협력단 해싱기반의 순위다중패턴매칭 방법

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
유광모 등, "2개의 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭알고리즘", 정보과학회논문지, 한국정보과학회, Vol.45, no.11, pp.1111-1116 1부.* *

Also Published As

Publication number Publication date
KR102158317B1 (ko) 2020-09-21

Similar Documents

Publication Publication Date Title
US11481494B2 (en) System and method for identifying and comparing code by semantic abstractions
KR102584035B1 (ko) 스플라이스 동작을 수행하는 장치 및 방법
WO2015101097A1 (zh) 特征提取的方法及装置
WO2022105497A1 (zh) 文本筛选方法、装置、设备及存储介质
US7818278B2 (en) Large scale item representation matching
US20200098161A1 (en) System and method for executing non-graphical algorithms on a gpu (graphics processing unit)
CN108664512B (zh) 文本对象分类方法及装置
Jain et al. Co-linear chaining with overlaps and gap costs
KR101662957B1 (ko) 해싱기반의 순위다중패턴매칭 방법
JP6237632B2 (ja) テキスト情報監視用辞書作成装置、テキスト情報監視用辞書作成方法、及び、テキスト情報監視用辞書作成プログラム
US9715374B2 (en) Multi-branch determination syntax optimization apparatus
CN116089951B (zh) 一种恶意代码检测方法、可读存储介质及电子设备
CN107341224A (zh) 一种字符串的匹配方法及装置
Oehlert et al. MacAnova user's guide
KR102158317B1 (ko) 2차 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭 알고리즘
JP6160232B2 (ja) コンパイルプログラムおよびコンパイル方法
CN116028936B (zh) 一种基于神经网络的恶意代码检测方法、介质及设备
KR102288282B1 (ko) 이진인코딩을 이용한 호스풀 알고리즘 기반 순위패턴매칭 방법 및 장치
KR20160067469A (ko) 개체 간 사회 관계 추출 장치 및 방법
KR102190285B1 (ko) 공간효율적인 순위다중패턴매칭 알고리즘
Mahmud et al. An improved hashing approach for biological sequence to solve exact pattern matching problems
KR102907818B1 (ko) 이진인코딩을 이용한 순위다중패턴매칭 방법 및 시스템
KR101626721B1 (ko) 사각망 순열패턴매칭을 위한 효율적인 알고리즘
KR101893661B1 (ko) 정수문자집합에 대한 문자열의 δ-근사주기와 γ-근사주기 계산 방법
KR102233217B1 (ko) 분할순위패턴매칭 알고리즘

Legal Events

Date Code Title Description
PA0109 Patent application

St.27 status event code: A-0-1-A10-A12-nap-PA0109

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

R18-X000 Changes to party contact information recorded

St.27 status event code: A-3-3-R10-R18-oth-X000

D13-X000 Search requested

St.27 status event code: A-1-2-D10-D13-srh-X000

D14-X000 Search report completed

St.27 status event code: A-1-2-D10-D14-srh-X000

PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

E13-X000 Pre-grant limitation requested

St.27 status event code: A-2-3-E10-E13-lim-X000

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U11-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 5

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R11-asn-PN2301

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R14-asn-PN2301

P14 Amendment of ip right document requested

Free format text: ST27 STATUS EVENT CODE: A-5-5-P10-P14-NAP-X000 (AS PROVIDED BY THE NATIONAL OFFICE)

P14-X000 Amendment of ip right document requested

St.27 status event code: A-5-5-P10-P14-nap-X000

P16 Ip right document amended

Free format text: ST27 STATUS EVENT CODE: A-5-5-P10-P16-NAP-X000 (AS PROVIDED BY THE NATIONAL OFFICE)

P16-X000 Ip right document amended

St.27 status event code: A-5-5-P10-P16-nap-X000

Q16 A copy of ip right certificate issued

Free format text: ST27 STATUS EVENT CODE: A-4-4-Q10-Q16-NAP-X000 (AS PROVIDED BY THE NATIONAL OFFICE)

Q16-X000 A copy of ip right certificate issued

St.27 status event code: A-4-4-Q10-Q16-nap-X000

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 6

U11 Full renewal or maintenance fee paid

Free format text: ST27 STATUS EVENT CODE: A-4-4-U10-U11-OTH-PR1001 (AS PROVIDED BY THE NATIONAL OFFICE)

Year of fee payment: 6