본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보과학회논문지. Journal of KIISE. 시스템 및 이론 v.32 no.9, 2005년, pp.475 - 482   피인용횟수: 1

와일드카드 문자를 포함하는 스트링 데이터 사이의 포함관계 확인을 위한 효율적인 알고리즘
An Effective Algorithm for Checking Subsumption Relation on String Data Containing Wildcard Characters

김도한   (서울시립대학교 기계정보공학과UU0000710  ); 박희진   (한양대학교 정보통신대학UU0001519  ); 백은옥   (서울시립대학교 기계정보공학과UU0000710  );
  • 초록

    와일드카드 문자를 포함하는 스트링 데이타는 텍스트에 나타나는 특정 패턴을 표현하는 데에 사용될 수 있다. 임의의 두 패턴 사이의 포함 관계는 각 패턴과 매칭이 가능한 모든 스트링의 집합 사이의 포함관계로 나타낼 수 있으며, 포함 관계를 결정하는 것은 패턴이 나타내는 스트링의 집합을 중복성없이 표현하기 위해 필요하다. 본 논문에서는 이와 같이 패턴의 중복성을 판단하기 위해 와일드카드 문자를 포함하는 스트링 데이타 사이의 포함 관계를 결정하기 위한 효율적인 알고리즘을 제안한다. 먼저 기존의 접미사 트리 알고리즘을 단순하게 확장하여 와일드카드 문자를 포함하는 스트링 데이타 사이의 포함 관계를 확인할 수 있도록 하는 방법과 이러한 접미사 트리를 스트링 데이타의 각 위치 별로 나누어 구성하여 포함 관계를 확인하는 방법을 제안한다.


    String data containing wildcard characters may represent certain patterns in texts. A subsumption relation between two patterns can be defined by a subset relation between sets of strings that match those patterns. Thus, the subsumption relation check is important to determine whether each pattern represents a set of strings without any overlap with another pattern. In this paper, we propose an effective algorithm that can determine subsumption relation between strings with wildcard characters. First, we consider a simple extension of the suffix tree algorithm so that it nay include wildcard characters and then we propose another method that checks the subsumption relation by dividing a suffix tree structure at each location of string data.


  • 주제어

    포함 관계 .   접미사 트리 .   트라이 .   와일드카드 문자.  

  • 참고문헌 (14)

    1. I. Horrocks and P. F. Patel-Schneider, Optimising description logic subsumption, Journal of Logic and Computation, 9(3), 267-293, 1999 
    2. G. M. Kuper and J. Simeon, Subsumption for XML types, Proc. Of International Conference on Database Theory, London, 2001 
    3. C. Chang and R. Lee, Symbolic logic and mechanical theorem proving, Academic Press, 1973 
    4. C. Sigrist, L. Cerutti, N. Hulo, A. Gattiker, L. Falquet, M. Pagni, A. Bairoch, and P. Bucher, PROSITE: A documented database using patterns and profiles as motif descriptors, Brief Bioinformatics, Vol. 3 no. 3, 265-274, 2002 
    5. Inge Jonassen, Efficient discovery of conserved patterns using a pattern graph, CABIOS, 13, 509-522, 1997 
    6. Andrea Califano, SPLASH: structural pattern localization analysis by sequential histograms, Bioinformatics, Vol. 16 no. 4, 341-357, 2000 
    7. E. M. McCreight, 'A space-economical suffix tree construction algorithms,' J. ACM 23, pp. 262-272, 1976 
    8. P. Weiner, Linear pattern matching algorithms, Proc. 14th IEEE Symp. Switching and Automata Theory, 1-11, 1973 
    9. M.T. Chen and J. Seiferas, Efficient and elegant subword tree construction, In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, NATO ASI Series F: Computer and System Sciences, 97-107, 1985 
    10. M. Farach, Optimal suffix tree construction with large alphabets, FOCS, 137-143, 1997 
    11. M. Farach-Colton, P. Ferragina and S. Muthukrishnan, On the sorting-complexity of suffix tree construction, JACM 47, 987-1011, 2000 
    12. S. Kurtz, Reducing the space requirement of suffix trees, Software Practice and Experience, 29, 1149-1171, 1999 
    13. E. Ukkonen, 'On-line construction of suffix trees,' Algorithmica 14, pp. 353-364, 1993 
    14. Dan Gusfield, Algorithms on Strings, Trees and Sequences, Cambridge University Press, 1997 
  • 이 논문을 인용한 문헌 (1)

    1. Kim, Young-Tae ; Kang, Dong-Min ; Park, Sang-Woo ; Ra, Dong-Yul 2011. "A Fast Search Method for Korean Chosung Wildcard Queries Using Chosung-First Lexicographic Order" 정보과학회논문지. Journal of KIISE. 컴퓨팅의 실제 및 레터, 17(10): 527~535     

 저자의 다른 논문

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기