AncomWiki

레벤슈타인 거리 (Levenshtein Distance) 알고리즘

Properties1
description두 문자열을 일치시키기 위한 최소 편집 횟수(삽입, 삭제, 대치)를 계산하는 레벤슈타인 거리 알고리즘의 동적 계획법(DP) 접근법을 정리한 내용입니다. 2 차원 DP 테이블을 구성하고, 각 셀에서 이전 상태의 최소 비용에 현재 연산의 비용을 더하여 최솟값을 선택하는 재귀적 관계를 설명합니다.

38 min read

레벤슈타인 거리 (Levenshtein Distance) 알고리즘

Source

  • Basic Journals/Daily Journals/2022 임인년/임인년 362일, 12월 28일 수요일.md

Summary

두 문자열을 일치시키기 위한 최소 편집 횟수(삽입, 삭제, 대치)를 계산하는 레벤슈타인 거리 알고리즘의 동적 계획법(DP) 접근법을 정리한 내용입니다. 2 차원 DP 테이블을 구성하고, 각 셀에서 이전 상태의 최소 비용에 현재 연산의 비용을 더하여 최솟값을 선택하는 재귀적 관계를 설명합니다.

Key Points

  • 레벤슈타인 거리는 두 문자열을 같게 만들기 위한 최소 편집 연산(삭제, 대치, 추가) 횟수를 의미합니다.
  • 이 문제는 동적 계획법(DP)을 사용하여 해결할 수 있으며, 2 차원 배열을 통해 부분 문제의 최적해를 저장합니다.
  • DP 상태 전이 식은 dp[ref][hyp] = min(대치 비용, 추가 비용, 삭제 비용) 으로 정의됩니다.
  • 각 연산의 비용은 이전 DP 상태 값에 현재 연산의 비용 (대치는 조건부, 추가/삭제는 1) 을 더하여 계산합니다.

그래프 뷰