레벤슈타인 거리에 대해 쉽게 설명 된 블로그가 있어 복붙 하여 참고함.
다만 JAVA로 짠 코드가 잘 못된 부분이 있어 Python 코드로 새로 짰음.
처음 비교 대상은 공집합과 공집합이다. 둘 다 같은 문자열이기 때문에 비용은 0이다. 그 다음은 공집합과 "나" 이다. 공집합이 "나"가 되려면 비용이 1이다. 그 다음은 공집합과 "나는"이다. 마찬가지로 비용이 2가든다. 계속 진행하면 위와 같이 표가 완성된다.
이제 "너" 와 공집합 - "나" - "나는" - "나는 "... - "나는 너를 좋아해!"를 비교해보자.
"너"와 공집합을 보자. '너'가 {}이 되려면 문자를 삭제해야 한다. 그러므로 비용 1
"너"와 "나"를 보자. '너'와 '나'는 서로 다르기 때문에 교체해야 한다. 그러므로 비용 1
"너"와 "나는"을 보자. 길이가 다르기 때문에 추가해야 하고, 교체해야 한다. 그러므로 비용 2
"너"와 "나는 "을 보자. 역시 길이가 다르기 때문에 2개 추가해야 하고, 교체해야 한다. 그러므로 비용 3
"너"와 "나는 너"를 보자. 길이가 다르기 때문에 문자 3개를 추가해야 하지만, '너'는 서로 같기 때문에 그대로 둔다. 그러므로 비용 3
이런식으로 "나는 너를 좋아해!"까지 표를 완성하면 위와 같이 된다.
한번만 더 해보자. "너는"과 공집합 - "나" - "나는" - "나는 " - ... - "나는 너를 좋아해!"를 비교해보자
"너는"과 공집합을 비교해보자. "너는"이 {}이 되려면 문자 두개를 삭제해야 한다. 그러므로 비용 2
"너는"과 "나"를 비교해보자. 문자 한개 삭제와 교체가 필요하다. 그러므로 비용 2
"너는"과 "나는"을 비교해보자. '는'은 서로 같고, '너'와 '나'는 다르기 때문에 교체가 필요하다. 그러므로 비용 1
"너는"과 "나는 "을 비교해보자. 추가, 교체가 필요하다. 그러므로 비용 2
이런식으로 표를 완성하면 다음과 같이 된다.
쉽게 정리하면
- 글자가 서로 동일하면 대각선 값을 가져온다
- 변경이 필요하면 대각선 값에서 + 1을 한다.
- 삽입이 필요하면 위의 값에서 +1을 한다.
- 삭제가 필요하면 왼쪽 값에서 +1을 한다.
- 이전까지의 값에서 대각선 위 왼쪽 에서 최소로 바뀔 수 있는 값을 참고한다.
- 그래야 가장 가까운 값이니깐.
결론 :
코드 :
def levenshtein_distance(t1, t2):
# Create a 2D array to store the minimum edit distances between all prefixes of t1 and t2.
rows, columns = len(t1) + 1, len(t2) + 1
arr = [[0 for j in range(columns)] for i in range(rows)]
# Initialize the first row and column of the array to be the edit distances required to transform an empty string to the corresponding prefixes of t1 and t2, respectively.
for i in range(rows):
arr[i][0] = i
for j in range(columns):
arr[0][j] = j
# Compute the edit distances for longer prefixes of t1 and t2 by considering the minimum edit distance among three possible operations: deletion, insertion, and substitution.
for i in range(1, rows):
for j in range(1, columns):
if t1[i-1] == t2[j-1]:
# If the characters at positions i-1 and j-1 are equal, there is no need to perform a substitution.
# The minimum edit distance is equal to the edit distance between the prefixes up to positions i-2 and j-2.
arr[i][j] = arr[i-1][j-1]
else:
# Otherwise, compute the minimum edit distance by adding 1 to the minimum edit distance among the three possible operations.
deletion = arr[i-1][j]
insertion = arr[i][j-1]
substitution = arr[i-1][j-1]
arr[i][j] = min(deletion, insertion, substitution) + 1
# Print the entire 2D array.
for row in arr:
print(row)
# Return the minimum edit distance between the entire strings t1 and t2.
return arr[rows-1][columns-1]
levenshtein_distance('abdc','asdf')
레벤슈타인 알고리즘을 사용해서 엑셀 파일들을 파일명에 따라 분리하는 코드 파이썬으로 짜줘
먼저, 파이썬에서 엑셀 파일을 다루기 위해서는 openpyxl이나 pandas와 같은 라이브러리를 사용해야 합니다. 또한, 레벤슈타인 알고리즘을 사용하기 위해서는 jellyfish 라이브러리를 설치해야 합니다.
아래는 엑셀 파일들을 파일명에 따라 분리하는 코드입니다. 이 코드는 파일명에 대해 레벤슈타인 거리를 계산하고, 일정 거리 이내에 있는 파일들을 같은 폴더에 저장합니다.
import os
import shutil
import jellyfish
# 폴더 경로와 레벤슈타인 거리의 기준값을 지정합니다.
folder_path = "/path/to/folder"
threshold = 2
# 폴더 내의 파일들을 모두 불러옵니다.
file_names = os.listdir(folder_path)
# 파일명에 대해 레벤슈타인 거리를 계산하여 같은 그룹에 속하는 파일들을 찾습니다.
groups = {}
for i, name in enumerate(file_names):
for j in range(i+1, len(file_names)):
if jellyfish.levenshtein_distance(name, file_names[j]) <= threshold:
# 동일한 그룹을 위해 새로운 파일 그룹을 추가합니다.
if name not in groups:
groups[name] = set([name])
groups[name].add(file_names[j])
# 같은 그룹에 속하는 파일들을 하나의 폴더에 저장합니다.
for group in groups.values():
# 공통 접두사를 폴더 이름으로 사용합니다.
folder_name = os.path.commonprefix(group)
new_folder_path = os.path.join(folder_path, folder_name)
# 폴더가 없는 경우 새로 생성합니다.
os.makedirs(new_folder_path, exist_ok=True)
for file_name in group:
file_path = os.path.join(folder_path, file_name)
new_file_path = os.path.join(new_folder_path, file_name)
# 파일을 새 폴더로 복사합니다.
shutil.copyfile(file_path, new_file_path)이 파이썬 스크립트는 파일의 레벤슈타인 거리(두 문자열 사이의 유사성 측정 지표)를 기반으로 폴더 내의 파일을 그룹화하고, 공통 접두사를 가진 새로운 폴더에 저장합니다. 다음은 코드가 작동하는 방식을 설명하는 주석입니다.
import os
import shutil
import jellyfish
# 폴더 경로와 레벤슈타인 거리의 기준값을 지정합니다.
folder_path = "/path/to/folder"
threshold = 2
# 폴더 내의 파일들을 모두 불러옵니다.
file_names = os.listdir(folder_path)- os 모듈은 운영 체제와 관련된 작업을 위해 가져오고, shutil 모듈은 파일 작업에 사용됩니다. 그리고 jellyfish 모듈은 레벤슈타인 거리를 계산하는 데 사용됩니다.
- folder_path 변수는 파일이 들어 있는 폴더의 경로로 설정됩니다.
- threshold 변수는 동일한 그룹으로 간주할 파일들의 최대 레벤슈타인 거리로 설정됩니다.
- os.listdir() 함수는 폴더 내 모든 파일의 목록을 가져오는 데 사용됩니다.
# 파일명에 대해 레벤슈타인 거리를 계산하여 같은 그룹에 속하는 파일들을 찾습니다.
groups = {}
for i, name in enumerate(file_names):
for j in range(i+1, len(file_names)):
if jellyfish.levenshtein_distance(name, file_names[j]) <= threshold:
if name not in groups:
groups[name] = set([name])
groups[name].add(file_names[j])- groups 딕셔너리는 공통 접두사를 가진 파일 그룹을 저장합니다.
- 중첩된 루프는 각 파일 이름 쌍의 레벤슈타인 거리를 비교하는 데 사용됩니다.
- 거리가 임계값 이하인 경우, 파일이 동일한 그룹에 속한다고 판단됩니다.
- 파일 이름은 groups 딕셔너리에 추가됩니다.
# 같은 그룹에 속하는 파일들을 하나의 폴더에 저장합니다.
for group in groups.values():
folder_name = os.path.commonprefix(group)
new_folder_path = os.path.join(folder_path, folder_name)
os.makedirs(new_folder_path, exist_ok=True)
for file_name in group:
file_path = os.path.join(folder_path, file_name)
new_file_path = os.path.join(new_folder_path, file_name)
shutil.copyfile(file_path, new_file_path)- 루프를 사용하여 각 파일 그룹을 반복합니다.
- 그룹의 공통 접두사는 새 폴더의 폴더 이름으로 사용됩니다.
- os.makedirs() 함수를 사용하여 새 폴더를 생성합니다. 이미 폴더가 존재하면 exist_ok=True 인자로 설정하여 에러 없이 진행합니다.
- 그룹 내 파일은 shutil.copyfile() 함수를 사용하여 새 폴더에 복사됩니다.
'알고리즘' 카테고리의 다른 글
| KMP/ ROBIN KMP (0) | 2023.03.22 |
|---|