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