levenstein의 편집 거리 알고리즘을 응용해야만 하는 문제가 있었다.
이 것은 알고나면 쉽지만 편집 거리 알고리즘을 사전에 알지 못한다면 푸는데 상당한 어려움이 있을 수 있는 문제다. 알고리즘을 숙지 하지 못했다면 즉석에서 응용할 수 있는 감각도 필요하다.
문제
우리는 두 id를 비교하며 유사한지를 판단하고자 한다. 이 때 두 id가 유사하다고 판단하기 위해서는 다음과 같은 거리를 계산한다.
- 두 단어에서 특정한 spelling을 각각 지워줌으로써 같아질 수 있는지 확인할 수 있다.
- 두 단어에서 모두 합하여 2개 이하의 spelling을 제거할 수 있다면 두 단어는 유사하다고 판단한다.
samsara와samskra라는 두 단어는 각각a와k을 삭제함으로써 2개 이하의 spelling을 제거하여 유사한 단어가 된다.
풀이
이 문제는 편집 거리 계산의 응용으로, 두 id 가 같다고 판단하기 위해서 편집 거리의 원칙을 따르는 것이 아니라, 한쪽에서 다른 쪽을 지워서 같아지는 경우로 한정한다고 보는 것이다.
samsara 와 samskra 라는 두 단어가 있다. levenstein 편집 거리는 1이다. 왜냐면 a를 k로 replace 해주면 되기 때문이다. 하지만 이 문제에서는 replace를 하는 방식으로 계산하지 않는다. 두 단어가 같아지려면 각 단어에서 각각 a와 k를 하나씩 지워주어야 하기 때문에 2의 거리가 된다.
편집 거리에서는 세 가지 경우를 고려하여 Dynamic Programming을 하고 결과를 return 한다.
여기서의 연산이란, 삽입(Insertion), 삽입(Deletion), 대체(Replacement)를 말한다. 알고리즘 코드를 보더라도 이 부분을 확인할 수 있다.
def are_similar(str1, str2):
len1 = len(str1)
len2 = len(str2)
if abs(len1 - len2) > 2:
return False
dp = np.zeros((len1 + 1, len2 + 1), dtype=int)
for i in range(len1 + 1):
for j in range(len2 + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
#dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1
return differences = dp[len1][len2]
여기서 보이는가? 가장 아래쪽에 주석처리를 해 놓은 라인에는 min 함수 안에 dp[i-1][j-1] 이라는 요소가 있다. 다른 두 요소가 각각 삽입(insertion)과 삭제(deletion)에 관한 요소라면 이 요소는 바로 replace 에 관한 요소이다. 따라서 주석 아래의 코드 처럼 replace 요소만 min 함수 내에서 지우고 계산하면 원하는 결과가 나온다.
결과
def are_similar(str1, str2):
len1 = len(str1)
len2 = len(str2)
if abs(len1 - len2) > 2:
return False
dp = np.zeros((len1 + 1, len2 + 1), dtype=int)
for i in range(len1 + 1):
for j in range(len2 + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
#dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1
differences = dp[len1][len2]
print(differences)
return differences <= 2
# Example usage
string_pair = ["samsara", "samskra"]
if are_similar(string_pair[0], string_pair[1]):
print("The strings are similar.")
else:
print("The strings are not similar.")