Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

Edit Distance Problem for the Korean Alphabet

한글에 대한 편집 거리 문제

  • 노강호 (서울대학교 전기컴퓨터공학부) ;
  • 김진욱 (인하대학교 컴퓨터정보공학부) ;
  • 김은상 (서울대학교 전기컴퓨터공학부) ;
  • 박근수 (서울대학교 전기컴퓨터공학부) ;
  • 조환규 (부산대학교 정보.컴퓨터공학부)
  • Received : 2009.10.28
  • Accepted : 2009.11.20
  • Published : 2010.04.15
Download PDF
⟨ Previous Next ⟩

Abstract

The edit distance problem is finding the minimum number of edit operations to transform a string into another one. It is one of the important problems in algorithm research and there are some algorithms that compute an optimal edit distance for the one-dimensional languages such as the English alphabet. However, there are a few researches to find the edit distance for the more complicated language such as the Korean or Chinese alphabet. In this paper, we define the measure of the edit distance for the Korean alphabet and present an algorithm for the edit distance problem for the Korean alphabet.

문자열에 대한 편집 거리 문제는 하나의 문자열을 다른 문자열로 변환할 때 필요한 최소한의 연산의 개수를 구하는 문제이다. 편집 거리 문제는 오랫동안 연구가 진행되어 왔으며, 영어와 같이 1차원 문자열에 대해서는 최적해를 찾는 여러 가지 알고리즘이 개발되어 왔다. 그러나 한글 또는 한자와 같이 좀 더 복잡한 언어에 대한 편집 거리에 대해서는 많은 연구가 진행되지 못했다. 본 논문에서는 한글이 갖는 특징을 반영한 편집 거리를 정의하고, 한글 문자열에 대한 편집 거리를 구하는 알고리즘을 제안한다.

Keywords

References

  1. Gusfield, D.: Algorithms on strings, trees, and sequences : computer science and computational biology, Cambridge Univ. Press, January 2007.
  2. Wagner, R. A., Fischer, M. J.: The String-to- String Correction Problem, J. ACM, 21(1), pp.168-173, 1974. https://doi.org/10.1145/321796.321811
  3. Navarro, G.: A guided tour to approximate string matching, ACM Computing Surveys, 33(1), pp.31-88, 2001. https://doi.org/10.1145/375360.375365
  4. Gong, R., Chan, T. K.: Syllable Alignment: A Novel Model for Phonetic String Search, IEICE -Trans. Inf. Syst., E89-D(1), pp.332-339, 2006. https://doi.org/10.1093/ietisy/e89-d.1.332
  5. Hirschberg, D. S.: A linear space algorithm for computing maximal common subsequences, Commun. ACM, 18(6), pp.341-343, 1975. https://doi.org/10.1145/360825.360861
  6. Sowon Chang, Seong-kyu Kim, Seung-chul Jung, This slip of the tongue that slip of the pen: official documents, Ministry of Culture and Tourism, 2000 (in korean).