지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 1997.6
- 수록면
- 595 - 603 (9page)
이용수
초록· 키워드
오류제보하기
본 논문에서는 ‘각 노드 υ∈V에 텍스트 T_υ가 대응되고 각 간선 (υ,ω) ∈E 는 텍스트 T_υ의 끝위치와 텍스트 T_ω 의 시작위치를 연결하는 유향그래프 G=(V, E)와 패턴 P가 주어졌을 때, 그래프 G상에 나타난 패턴의 끝위치를 모두 찾으라’ 는 그래프에서의 스트링 매칭 문제에 대한 알고리즘을 제시한다. 여기서 패턴의 길이는 m이고, 그래프 G상에서 모든 텍스트 T_υ의 길이의 합은 N이다. 이 문제의 응용분야중 하나는 유향그래프로 모델링된 하이퍼텍스트에서의 스트링 매칭이다. 이 문제에서 어려운 점은 패턴이 간선들을 넘어가며 존재할 수도 있다는 것이다.
G 가 일반 그래프이고 모든 노도 υ에서 길이 n_υ=|T_υ|가 m보다 크거나 같은 경우에 선형 시간복잡도 O(N+|E|)의 알고리즘을 제시하며, G가 사이클이 없고 n_υ＜m를 만족하는 노드 υ가 존재할 경우에는 시간복잡도 O(N+|E|m)의 확장된 알고리즘을 제시한다. 이를 위하여 ‘witness 와 duel’의 개념과 suffix tree를 결합하므로써, 패턴의 부분스트링에 대해서도 duel을 수행할 수 있도록 하였다.
G 가 일반 그래프이고 모든 노도 υ에서 길이 n_υ=|T_υ|가 m보다 크거나 같은 경우에 선형 시간복잡도 O(N+|E|)의 알고리즘을 제시하며, G가 사이클이 없고 n_υ＜m를 만족하는 노드 υ가 존재할 경우에는 시간복잡도 O(N+|E|m)의 확장된 알고리즘을 제시한다. 이를 위하여 ‘witness 와 duel’의 개념과 suffix tree를 결합하므로써, 패턴의 부분스트링에 대해서도 duel을 수행할 수 있도록 하였다.
목차
요약
Abstract
1. Introduction
2. Basics
3. The Algorithms
4. Texts on Edges
5. Concluding Remarks
References
저자소개
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
Order υ Entropy and Cross Entropy of Uncertain Variables for Portfolio Selection
INTERNATIONAL JOURNAL of FUZZY LOGIC and INTELLIGENT SYSTEMS
2020 .03
-
k-ε-υ'² 모델을 이용한 경사진 충돌제트의 유동 및 열전달 특성에 대한 수치해석적 연구 ( A Numerical Study on Flow and Heat Transfer Characteristics for an Oblique Impingement Jet Using k-ε-υ'² Model )
대한기계학회 논문집 B권
2001 .09
-
k-ε-υ´2 난류 모델을 이용한 충돌 제트의 유동 및 열전달 특성에 관한 수치해석적 연구 ( Numerical Simulation of Flow and Heat Transfer Characteristics of Impinging Jet Using k-ε-υ´2 Model )
대한기계학회 논문집 B권
2000 .02
-
Υ-Fe2O3 후막형 탄화수소계 가스 감지소자 ( Υ-Fe2O3 Thick Film Hydrocarbon Gas Sensor )
대한전자공학회 학술대회
1988 .11
-
Υ-Fe2O3/Pd 후막형 가스 감지소자 ( Υ-Fe2O3/Pd Thick Film Gas Sensors )
전자공학회논문지
1990 .09
-
Temperature Effects of Side Chains on Poly (Υ-alkyl a, L-glutamate)
한국고분자학회 학술대회 연구논문 초록집
1998 .10
-
Conference Key Agreement Protocol Employing a Symmetric Balanced Incomplete Block Design
한국멀티미디어학회 학술발표논문집
2007 .05
-
토러스의 일대일 서로소인 경로 커버
정보과학회논문지 : 시스템 및 이론
2011 .02
-
하이퍼텍스트에서 스트링 매칭 알고리즘
한국정보과학회 학술발표논문집
1994 .10
-
Microcontact Printing of ϒ-APS Monolayer on Polyimide Film for gold Nanoparticle Patterning
한국고분자학회 학술대회 연구논문 초록집
2008 .04
-
평균적으로 빠른 스트링 매칭
(구)정보과학회논문지
1994 .07
-
재귀원형군의 위상 특성 : 서로소인 경로
정보과학회논문지(A)
1999 .08
-
대칭 3-정규 유향 그래프의 해밀톤 분할과 응용
정보과학회논문지(A)
1998 .07
-
동적 환경 소셜 네트워크 그래프에서 다중 제약 조건 그래프 패턴 매칭
한국정보과학회 학술발표논문집
2015 .12
-
Preparation and Characterization of Fish Oil-loaded Microcapsules with Υ-Cyclodextrin, Whey protein and Chitosan Wall Materials
한국생물공학회 학술대회
2010 .04
-
효율적인 개념그래프 매칭 알고리즘
한국정보기술학회지
2006 .12
-
그래프 패턴 매칭을 이용한 차량 네트워크에서의 결함 탐색 방법
한국정보과학회 학술발표논문집
2014 .12
-
물, 증기, 얼음의 압력과 온도에 대한 정밀계산 : CFD를 위한 공식
대한기계학회 춘추학술대회
2009 .11
이 논문의 저자 정보
이 논문과 함께 이용한 논문
IoT 기술과 보안
김호원
,
김동규
정보보호학회지
2012
.02
A String Reconstruction Algorithm and Its Application to Exponentiation Problems
심정섭
,
이문규
,
김동규
정보과학회논문지 : 시스템 및 이론
2008
.10
DNA 스트링에 대하여 써픽스 배열을 구축하는 빠른 알고리즘
조준하
,
김남희
,
권기룡
외 1명
정보과학회논문지 : 시스템 및 이론
2007
.08
소셜 서비스 네트워크 모델에 기반한 서비스의 평판 계산
김경률
,
정주익
,
이경호
한국정보과학회 학술발표논문집
2013
.06
스마트 기기를 위한 모바일 온톨로지 기반의 시맨틱 검색
고지훈
,
신상진
,
송민재
외 2명
한국정보과학회 학술발표논문집
2013
.06
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017726944