Dynamic Programming : Edit Distance (and Lucene FuzzyQuery)
Lucene에서 Edit Distance를 이용해 쿼리를 날려서 검색 결과를 받는 기능이 있다. 그때 막연하게 시간이 많이 걸린다고 책에서 나와 있는 관계로 왜 많이 걸릴까 고민을 하지 않던 찰라 기회가 생겨서 Edit Distance를 구하는 알고리즘을 공부하고 구현해 봤다. 결과적으로 Dynamic Programming 문제이긴 한데, 이것과 배낭문제 그리고 어제 학교에서 공부했던 Routing Algorithm(최단 라우팅 거리 측정 알고리즘)을 비교해서 보니 […]
계속 읽기