- 정규 언어와 문맥 자유 언어 사이의 편집 거리 계산
- ㆍ 저자명
- 고상기,한요섭,Ko. Sang-Ki,Han. Yo-Sub
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 컴퓨팅의 실제 및 레터
- ㆍ 권/호정보
- 2012년|18권 6호|pp.464-468 (5 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
우리는 주어진 정규 언어와 문맥 자유 언어 사이의 편집 거리(edit distance)를 계산하는 알고리즘을 제안한다. 편집 거리는 일반적으로 하나의 문자열을 다른 문자열로 변환할 때 필요한 최소한의 연산의 개수를 의미한다. 문자열 단위가 아닌 언어 단위에서의 편집 거리를 계산함으로써, 패턴 매칭(pattern matching)이나 파싱(parsing)을 위해 주어지는 정규 언어와 문맥 자유 언어 간의 유사도를 효율적으로 파악할 수 있다.
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.