hye0.log hye0.log

스트링 편집 거리

• [알고리즘] 스트링 편집 거리

  Computer Science/Algorithm 2021. 12. 14. 19:19

  스트링 편집 거리(string edit distance) 두 스트링의 유사도를 측정하기 위해 사용 Levenshtein distance(LD)라고도 함 원래 스트링을 S, 목표 스트링을 T S를 T로 변환하는 데 필요한 삽입, 삭제, 대치 연산의 최소 비용 편집 거리가 커질수록, 두 스트링의 유사도는 낮아지게 됨 논문이나 보고서의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용됨 동적 계획법의 적용 스트링 편집 거리 예시를 들어 설명하겠습니다. S = GUMBO T = GAMBOL U -> A 로 교체 L 을 추가 따라서, GUMBO를 GAMBOL로 변경하는 최소 편집 거리는 2임을 알 수 있습니다. 스트링 편집 거리를 구하기 위해선, 간단히 표로 작성하여 구할 수 있습니다. 1. 초기 테이블을 ..

  Read More