정규 언어와 문맥 자유 언어 사이의 편집 거리 계산 = Computing the Edit Distance between a Regular Language and a Context-free Language

국문 초록 (Abstract)

우리는 주어진 정규 언어와 문맥 자유 언어 사이의 편집 거리(edit distance)를 계산하는 알고리즘을 제안한다. 편집 거리는 일반적으로 하나의 문자열을 다른 문자열로 변환할 때 필요한 최소한의 연산의 개수를 의미한다. 문자열 단위가 아닌 언어 단위에서의 편집 거리를 계산함으로써, 패턴 매칭(pattern matching)이나 파싱(parsing)을 위해 주어지는 정규 언어와 문맥 자유 언어 간의 유사도를 효율적으로 파악할 수 있다.

다국어 초록 (Multilingual Abstract)

We propose an algorithm for computing the edit distance between a regular language and a context-free language. The edit distance is generally defined as the smallest number of operations required to transform a string into the other. By computing the edit distance between two languages instead of strings, we estimate the similarity between a regular language and a context-free language, which are often used for pattern matching or parsing.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 예비 지식
• 3. 정렬 그래프(alignment graph) 만들기
• 4. 정렬 그래프를 이용하여 편집 비용 구하기
• 5. 편집 거리 계산하기
• 6. 결론
• 참고문헌

참고문헌 (Reference)

1 Karen Kukich, "Techniques for automatically correcting words in text" 24 : 377-439, 1992

2 John E. Hopcroft, "Introduction to Automata Theory, Languages, and Computation (3rd Edition)" Addison- Wesley Longman Publishing 2006

3 M. Mohri, "Edit-distance of weighted automata: General definitions and algorithms" 14 (14): 957-982, 2003

4 Mehryar Mohri, "Edit-distance of weighted automata: General definitions and algorithms" 14 (14): 957-982, 2003

5 Horst Bunke, "Edit distance of regular languages" 113-124, 1996

6 Stavros Konstantinidis, "Computing the edit distance of a regular language" 205 : 1307-1316, 2007

7 Sagnur N. Srihari, "Computer Text Recognition and Error Correction" IEEE Computer Society Press 1985

8 Alfred V. Aho, "Compilers: principles, techniques, and tools" Addison-Wesley Longman Publishing 1986

9 R. Durbin, "Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids" Cambridge University Press 1998

10 Vladimir I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals" (1s0(8)) : 707-710, 1966

11 Fei-yue Ye, "Application of Information Extraction in Oil Search Engine" 98-102, 2009

12 Alfred V. Aho, "Algorithms for Finding Patterns in Strings. Handbook of Theoretical Computer Science, In Volume A: Algorithms and Complexity" 255-300, 1990