(23.03.29)
algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기
http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf
정리한 내용
6.3 Edit distance
Edit distance
- edit distance: 어떤 두 단어(문자열)가 같아지도록 하기 위해 수행해야하는 연산의 수 (minimum number of edits)
- 예를 들어 edit distance를 해결한 예시를 살펴보면 아래와 같다.
- edit distance by dynamic programming
- edit distance algorithm by dynamic programming
----> 예시를 통해 어떻게 진행되는지 살펴보았다.
- edit distance를 비롯한 dp 문제들은 underlying dag structure 를 갖고 있다.
---> node는 sub-problem, edge는 sub-problem을 해결하고자하는 precedence constraint 이다.
---> 아래와 같이 진행되는데, down: deletion, right: insertion, diagonal: match / substitution 에 해당한다.
728x90
