편집 거리

1 개요

edit distance

編輯 距離

편집 거리

• 전산 언어학 및 컴퓨터 과학 용어
• 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 작업 수를 계산하여 서로 다른 두 문자열(예 : 단어)이 얼마나 다른지를 정량화하는 방법
• 생물정보학에서는 A, C, G, T 문자의 문자열로 볼 수있는 DNA 서열의 유사성을 정량화하는 데 사용할 수 있다.
• 레벤슈타인 거리는 문자열에서 문자의 제거, 삽입, 대체 연산 횟수이다.

가장 일반적인 측정항목인 레벤슈타인 거리는 흔히 편집 거리와 같은 의미로 자주 사용된다.

2 유형

• 레벤슈타인 거리(Levenshtein distance)
• 최장 공통 부분수열(longest common subsequence)
• 해밍 거리(Hamming distance)
• 다메라우-레벤슈타인 거리(Damerau–Levenshtein distance)
• 자로-윙클러 거리(Jaro–Winkler distance)

3 같이 보기

• 편집
• 거리
• 문자열 메트릭
• 그래프 편집거리
• 타임워프 편집거리(TWED)
• 문자열-문자열 교정 문제

4 참고

• 영어 위키백과 "Edit distance"
• 위키백과 "편집 거리"
• 다음백과 "편집 거리"
• 네이버백과 "편집 거리"