Levenshtein Distance ✨ - 온라인 시험에서 당신을 사로잡는 알고리즘

작업 중인 프로젝트에서 두 문자열 간의 유사성 검사를 수행해야 했을 때 이 알고리즘을 발견했습니다. 선임 개발자가 이 알고리즘을 매우 간단한 용어로 설명했습니다.

Levenshtein distance between two strings is nothing but the number of single-character edits the first string is away from becoming the second

소비에트 수학자Vladimir Levenshtein의 이름을 딴 Levenshtein 거리(일명 편집 거리)는 다음과 같은 현대 응용 프로그램에서 볼 수 있습니다.

맞춤법 검사

DNA 분석

음성인식

표절 탐지

네, 친구의 과제에서 무언가를 복사하다가 잡힌 이유는 이 사람 때문입니다. 1960년대 소비에트 시대에 개발된 알고리즘은 여전히 ​​Google 키보드, 스마트 장치 및 스마트 교실 프레임워크에서 사용되고 있습니다.


이제 세부 사항은 충분합니다. 여기 알고리즘의 수학적 표기법이 있습니다 👇



모든 코더가 더 잘 이해할 수 있도록 이것을 파이썬 함수로 정의해 봅시다.

import numpy as np

def levi_dist(a,b):
    '''
    takes two strings as arguments, need not be of same length - a,b
    returns the levenshtein distance between the two strings
    '''

    # Initializing a matrix of zeros 
    rows = len(a) + 1
    cols = len(b) + 1
    arr = np.zeros((rows,cols),dtype=int)

    # Initializing the first row and first column with string indices
    for i in range(rows):
        for j in range(cols):
            arr[i][0] = i
            arr[0][j] = j

    # Iterating over the elements of the matrix except index column and row
    for i in range(1,rows):
        for j in range(1,cols):
            if a[i-1] == b[j-1]:
                cost = 0
            else:
                cost = 1

            arr[i][j] = min(arr[i-1][j] + 1,     # deletion
                        arr[i][j-1] + 1,         # insertion
                        arr[i-1][j-1] + cost)    # replacement

    return f'Levenshtein Distance between string A and string B is {arr[len(a)][len(b)]}' 

엄청난! 이제 함수를 정의했으므로 이를 테스트하려면 두 개의 문자열이 필요합니다. 제 경우에는 monty를 문자열 A로, python을 문자열 B로 하겠습니다. 원하는 두 문자열을 선택할 수 있습니다.

문자열로 함수를 호출하면

 > levi_dist('monty','python')
 Levenshtein Distance between string A and string B is 6

즉, monty는 파이썬이 되기까지 6개의 단일 문자 편집입니다.

행렬은 다음과 같습니다.


자, 우리는 임무를 완수했습니다. 이제 저처럼 게으르고 알고리즘을 직접 작성하고 싶지 않다면 해파리, 인챈트 등과 같은 텍스트 변환 모듈의 일부 기능을 활용할 수 있습니다.

 > from jellyfish import levenshtein_distance
 > levenshtein_distance('monty','python')
 6

건배! 다음 포스팅에서 뵙겠습니다.