[논문]다중바이트 문자집합 텍스트에서의 문자열 검색 알고리즘

김은상; 김진욱; 박근수

초록
AI-Helper

문자열 완전일치 검색 알고리즘용 지금까지 많은 연구가 되어왔지만, EUC-KR 용 다중바이트 문자집합에 대해서는 연구원 것이 부족한 상황이다. 이 논문에서는 기존의 KMP 알고리즘을 사용할 때 EUC-KR과 같은 다중바이트 문자집합 텍스트에서 오검색이 발생할 수 있음을 보이며, 문자 단위의 접두사 함수를 적용하여 오검색이 발생하지 않도록 개선한 KMP 알고리즘을 제안한다. 또한, 널리 사용되고 있는 편집기인 Vim과 Emacs의 검색 알고리즘 및 기존의 오토마타 방식의 연구 결과에 비해 논문에서 제안한 알고리즘이 더 빠른 속도를 보이는 실험 결과를 제시한다.

Abstract ▼ AI-Helper

An extensive research on exact string matching has been done, but there have been few researches on the matching in multi-byte character set texts such as EUC~KR. This paper shows that false matches may occur in multi-byte character set texts such as EUC-KR when using KMP algorithm, and presents a r...

An extensive research on exact string matching has been done, but there have been few researches on the matching in multi-byte character set texts such as EUC~KR. This paper shows that false matches may occur in multi-byte character set texts such as EUC-KR when using KMP algorithm, and presents a refined KMP algorithm without false matches applying a character-based prefix function. And also, Experimental results show that our algorithm is faster than string matching algorithms of widely used editors, Vim and Emacs, and the existing automata-based algorithm.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

이 논문에서는 처음으로 문자 단위의 접두사 함수를 정의하고, 이를 적용하여 EUC-KR 문자집합 텍스트 상에서 오검색을 피하고 문자열 완전일치 검색을 할 수 있도록 개선한 KMP 알고리즘을 제안한다. 논문의 구조는 다음과 같다.
이 논문에서는, 처음으로 문자 단위의 접두사 함수를 정의하고, 이를 적용하여 EUC-KR 문자집합 텍스트 상에서 오검색을 피하고 문자열 완천일치 검색을 할 수 있도록 개선한 KMP 얄고리즘을 제안하였다. 논문에서 제안한 New KMP 알고리즘은 널리 사용되고 있는 편집기인 Vim과 Egics에서 적용한 검색 알고리즘들과 오토마타 방식의 기존 연구 결과보다 훨씬 빠른 실험 결과를 보였다.
그런데 동기화 여부를 확인하기 위해서는 텍스트를 처음부터 차례대로 읽어가면서 텍스트의 현재 바이트가 어떤 문자의 첫 번째 바이트인지 확인해야 하기 때문에 일반적으로 접두사 접근방식의 문자열 검색 알고리즘이 선호된다. 이 논문에서는 기존의 KMP 알고리즘을 문자 단위로 동작하도록 개선하여 동기화와 문자열 검색을 동시에 수행하는 알고리즘을 제안하도록 할 것이다.

제안 방법

이번 장에서는 오검색이 발생하지 않도록 문자 단위로 접두사 함수를 구성하고 검색 과정을 진행하는 KMP 알고리즘을 제안한다. 문자 단위의 접두사 함수는 이 논문에서 처음으로 제안되는 것이다.
논문에서 제안하고 있는 알고리즘, EUC-KR DFA와 오토마타를 결합한 PMM(Pattem Matching Machine) [4] 및 Vim 편집기, Emacs 편집기의 검색 알고리즘 속도를 비교하는 실험을 진행하였다. 4가지 알고리즘 모두 직접 구현하였으며, 실험한 환경은 다음과 같다.
먼저 Vim 편집기의 알고리즘은 텍스트와 패턴의 첫 번째 문자를 비교하고 서로 일치한 경우에 C library의 stmcmpO 함수를 사용하여 검색을 진행한다. EUC-KR 텍스트 상에서 이와 동일한 동작을 하기 위해 Naive 알고리즘을 수정하였다.
먼저 Vim 편집기의 알고리즘은 텍스트와 패턴의 첫 번째 문자를 비교하고 서로 일치한 경우에 C library의 stmcmpO 함수를 사용하여 검색을 진행한다. EUC-KR 텍스트 상에서 이와 동일한 동작을 하기 위해 Naive 알고리즘을 수정하였다. 수정한 사항은, 현재 텍스트의 문자가 2바이트 문자인 경우에 다음 비교할 위치를 2바이트만큼 이동하여 다음 문자부터 비교 작업을 반복하도록 한 것이다.
EUC-KR 텍스트 상에서 이와 동일한 동작을 하기 위해 Naive 알고리즘을 수정하였다. 수정한 사항은, 현재 텍스트의 문자가 2바이트 문자인 경우에 다음 비교할 위치를 2바이트만큼 이동하여 다음 문자부터 비교 작업을 반복하도록 한 것이다. 다음으로 Emacs 편집기의 검색 알고리즘은 텍스트와 패턴을 UTF-8 인코딩으로 변환한 후 Horspool 알고리즘을 적용하는 것이다.
이를 구현하기 위해서 Emacs 편집기 코드에 포함되어 있는 EUC-KR to UTF-8 매핑 파일을 사용하여 EUC-KR 텍스트를 UTF-8 인코딩으로 변환하였고, Horspool 알고리즘보다 개선된 SundaytlO] 알고리즘을 적용하였다. 그리고 PMM 알고리즘은 기본적으로 AC 오토마타를 사용한 다중패턴 (multi-pattern) 검색 알고리즘이지만, 다른 알고리즘과의 비교를 위해서 매번 1개의 패턴만으로 AC 오토마타를 구성하여 실험을 진행하였다.

대상 데이터

실험 데이터는, 한글 웹사이트에서 모은 약 2000 페이지 중에서 script와 HTML tag둥을 제외한 평문(약 28MB)을 텍스트로 하고, 바이트 길이가 2, 4, 6, 8, 10, 12, 18, 24, 30, 36, 42, 铿 54, 60인 문자열을 텍스트에서 랜덤하게 100개씩 추출하여 패턴으로 사용하였다. 14 가지 길이의 패턴에 대하여 4가지 알고리즘이 각각 사용한 시간의 평균값올 그림 4에 나타내었다’ 논문에서 제안하고 있는 알고리즘을 New KMP라고 표기하였으며, Vim 편집기에서 사용하고 있는 Naive 알고리즘을 Vim[4]의 알고리즘을 PMM, Emacs 편집기의 방법을 Emacs라고 표기하였다.

이론/모형

다음으로 Emacs 편집기의 검색 알고리즘은 텍스트와 패턴을 UTF-8 인코딩으로 변환한 후 Horspool 알고리즘을 적용하는 것이다. 이를 구현하기 위해서 Emacs 편집기 코드에 포함되어 있는 EUC-KR to UTF-8 매핑 파일을 사용하여 EUC-KR 텍스트를 UTF-8 인코딩으로 변환하였고, Horspool 알고리즘보다 개선된 SundaytlO] 알고리즘을 적용하였다. 그리고 PMM 알고리즘은 기본적으로 AC 오토마타를 사용한 다중패턴 (multi-pattern) 검색 알고리즘이지만, 다른 알고리즘과의 비교를 위해서 매번 1개의 패턴만으로 AC 오토마타를 구성하여 실험을 진행하였다.

성능/효과

4가지 알고리즘 중에서 New KMP 알고리즘이 속도가 가장 빠른 것을 확인할 수 있으며, Vim의 Naive 알고리즘에 비해서 약 20% 빠른 속도를 보였다. 한편, PMM 알고리즘의 속도가 느린 것은 오토마타를 계속해서 확인하고 그 stat©를 유지 및 변화시켜가는 추가비용으로 인한 것이며, Emacs의 알고리즘의 경우, EUC KR 텍스트를 UTFT 인코딩으로 변환하는 시간과 검색 시간을 합한 결과가 New KMP 알고리즘보다 느린 것을 확인할 수 있었다.
비해서 약 20% 빠른 속도를 보였다. 한편, PMM 알고리즘의 속도가 느린 것은 오토마타를 계속해서 확인하고 그 stat©를 유지 및 변화시켜가는 추가비용으로 인한 것이며, Emacs의 알고리즘의 경우, EUC KR 텍스트를 UTFT 인코딩으로 변환하는 시간과 검색 시간을 합한 결과가 New KMP 알고리즘보다 느린 것을 확인할 수 있었다.
논문에서 제안한 New KMP 알고리즘은 널리 사용되고 있는 편집기인 Vim과 Egics에서 적용한 검색 알고리즘들과 오토마타 방식의 기존 연구 결과보다 훨씬 빠른 실험 결과를 보였다. 일반적으로 ASCII 문자집합 기반의 텍스트 상에서 바이트 단위의 Naive 알고리즘과 KMP 알고리즘의 실제 속도는 거의 차이가 없다[11].
일반적으로 ASCII 문자집합 기반의 텍스트 상에서 바이트 단위의 Naive 알고리즘과 KMP 알고리즘의 실제 속도는 거의 차이가 없다[11]. 그러나 다중바이트 문자집합 기반의 텍스트 상에서 오검색이 발생하지 않도록 개선한 New KMP 알고리즘은 Vim 편집기에서 사용되는 Naive 알고리즘보다 약 20% 빠른 속도를 보였다. 논문에서는 EUC-KR 인코딩 텍스트를 주 대상으로 하였지만, 오검색이 발생할 수 있는 다른 언어의 EUC(Extended-Unix-Code) 인코딩 텍스트에서도 논문에서 제안한 문자 단위의 접두사 함수를 해당인 코딩의 특성에 따라 수정하여 적용할 수 있을 것이다.

후속연구

그러나 다중바이트 문자집합 기반의 텍스트 상에서 오검색이 발생하지 않도록 개선한 New KMP 알고리즘은 Vim 편집기에서 사용되는 Naive 알고리즘보다 약 20% 빠른 속도를 보였다. 논문에서는 EUC-KR 인코딩 텍스트를 주 대상으로 하였지만, 오검색이 발생할 수 있는 다른 언어의 EUC(Extended-Unix-Code) 인코딩 텍스트에서도 논문에서 제안한 문자 단위의 접두사 함수를 해당인 코딩의 특성에 따라 수정하여 적용할 수 있을 것이다.

참고문헌 (11)

D. E. Knuth, J. H. Morris Jr, and V. R. Pratt. Fast Pattern Matching in Strings. SIAM Journal on Computing, vol.6, pp.323-350, 1977.

상세보기
Robert S. Boyer and J. Strother Moore. A Fast String Searching Algorithm. Communications of the ACM, vol.20, no.10, pp.762-772, 1977.

상세보기
Cyril Allauzen, Maxime Crochemore, and Mathieu Raffinot. Efficient experimental string matching by weak factor recognition. 12th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol.2089, pp.51-72, 2001.
Masayuki Takeda, Satoru Miyamoto, Takuya Kida, Ayumi Shinohara, Shuichi Fukamachi, Takeshi Shinohara, and Setsuo Arikawa. Processing Text Files as Is: Pattern matching over Compressed Texts, Multibyte Character Texts, and Semi- structured Texts. String Processing and Information Retrieval (SPIRE) 2002, LNCS 2476, pp.170-186, 2002.
Heikki Hyyro, Jun Takaba, Ayumi Shinohara, and Masayuki Takeda. On Bit-parallel Processing of Multi-byte Text. Proceedings of the 1st Asia Information Retrieval Symposium (AIRS) 2004, LNCS 3411, pp.289-300, 2005.
Vim Editor, http://www.vim.org
GNU Emacs Editor, http://www.gnu.org/software/emacs
R. Nigel Horspool. Practical Fast Searching in Strings. Software Practice and Experience, vol.10, no.6, pp.501-506, 1980.

상세보기
Korean Industrial Standards, http://www.standard.go.kr
Daniel M. Sunday. A Very Fast Substring Search Algorithm. Communications of the ACM, vol.33, no.8, pp.132-142, 1990

상세보기
G. De V. Smit. A comparison of three string matching algorithms. Software: Practice and Experience, vol.12, no.1, pp.57-66, 1982.

상세보기

이 논문을 인용한 문헌

저자의 다른 논문 :

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] 다중바이트 문자집합 텍스트에서의 문자열 검색 알고리즘
String Matching Algorithm on Multi-byte Character Set Texts 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

Keyword

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

연구과제 타임라인

활용도 분석정보

활용도 Top5 논문

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 다중바이트 문자집합 텍스트에서의 문자열 검색 알고리즘 String Matching Algorithm on Multi-byte Character Set Texts 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

Keyword

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

김은상 (2) 김진욱 (1) 박근수 (40)

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

활용도 분석정보

활용도 Top5 논문 더보기

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 다중바이트 문자집합 텍스트에서의 문자열 검색 알고리즘
String Matching Algorithm on Multi-byte Character Set Texts 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

활용도 Top5 논문