레벤슈타인 거리

[Python-이론/python-인공지능] - 레벤슈타인 거리를 이용해서 두 문장 비교하기

레벤슈타인 거리를 이용해서 두 문장 비교하기

예전에 이런 글을 적은 적이 있는데 까먹고 잊고 살다가 최근 문제에서 만나면서 다시 풀어보게 되었다. 저 당시에는 dp도 몰랐는데 문제를보고 정리한거 같다.

 

레벤 슈타인 거리의 경우는 두개의 문자열을 어떻게 변형해주면(삭제, 교환, 덧셈) 등을 진행해줄 때 최소한 몇개의 변화를 통해서 만들 수 있는지 구하는 것이다. 

 

dp의 값은 해당 위치의 문자들끼리 비교했을 때 가장 적게 변화시킨 수 입니다. 

 

substitudeCost = [base-1][compare-1] + cost(대체되었을 경우)

addCost = [base-1][compare] + 1(값을 추가했을 경우)

deleteCost = [base][compare-1] + 1(값이 삭제되었을 경우)

dp[base][compare] = min(substitudeCost, addCost, deleteCost);

 

substitude의 cost의 경우에는 비교하는 문자랑 base가 되는 문자가 일치하는지 체크해서 다르다면 cost 값을 1을 같다면 연산을 해줄 필요가 없기 때문에 0을 넣어주면 된다.

 

using namespace std;

int levenshteinDistance(string str1, string str2) {
  vector<vector<int>> dp(str1.size()+1, vector<int>(str2.size()+1, 0));
	
	for(int i = 0; i <= str1.size(); i++)
		dp[i][0] = i;
	
	for(int i = 0; i <= str2.size(); i++)
		dp[0][i] = i;
	
	for(int base = 1; base <= str1.size(); base++){
		for(int compare = 1; compare <= str2.size(); compare++){
			int cost = 0;
			
			if(str1[base-1] != str2[compare-1])
				cost = 1;
			
			int substitudeCost = dp[base-1][compare-1] + cost;
			int addCost = dp[base-1][compare] + 1;
			int deleteCost = dp[base][compare-1] + 1;
			
			dp[base][compare] = min(substitudeCost, min(addCost, deleteCost));
			
		}
	}
	
  return dp[str1.size()][str2.size()];
}