Levenshtein distance - 가장 비슷한 텍스트 찾기

미리 정해진 텍스트 집합 안에서 주어진 텍스트와 일치하는 (또는 가장 유사한) 텍스트를 찾아야 하는 경우가 있습니다. 진료비영수증을 예로 들자면, 영수증의 항목명들을 OCR 기술로 추출한 경우 오인식/미인식이 존재하더라도 가장 유사한 항목명을 찾아야 해당 금액을 그 항목의 지출로 인식할 수 있을 겁니다.

두 텍스트의 유사도를 측정하기 위하여 Levenshtein distance를 사용할 수 있습니다. Levenshtein distance를 계산하는 원리는 이 포스팅에서 쉽게 설명하고 있으니 참고하시기 바랍니다. 한글의 경우 자소 단위로 비교하면 좀 더 세밀하게 유사도를 측정할 수 있고, 대량의 텍스트를 비교하는 경우 수행 시간을 단축하기 위하여 short-circuiting(기존의 최소 거리보다 커지면 계산을 중단함)을 도입한 python 코드를 아래에 공개해 두었습니다.

Python 코드 안에 주석으로도 명시하였지만, 기본 구현은 이 포스팅을 참고하였고 short-circuit 코드를 추가하고 다듬었습니다.

위의 github 코드는 아래와 같이 테스트해볼 수 있습니다.

import string
import levenshtein_distance

def normalize(str):

    s = str.translate({ord(c): None for c in string.whitespace})  # remove whitespaces

    if 0 == len(s):
        return ''

    names = ['식대', '1인실', 'DRG', 'CT검사료', 'PET검사료', '관리료', '마취료', '수탁료', '수혈료', '약품비', '입원료', '조제료', '주사료', '진찰료', '제증명', '후송료', '행위료', '의료보호', '진단서료', '제증명료', '캐스트료', '마취및통증치료', '응급의료관리료', '응급의학관리료', '전혈혈액제제료', '진단서제증명료', '질병군포괄수가', '치과병원진료비', '포괄수가진료비', '국민건강보험법제41조의4에따른요양급여']

    min_dist = 10000.0  # initialize with big number
    index = -1
    for i, name in enumerate(names):
        dist = levenshtein_distance.jamo_levenshtein(s, name, min_dist)
        if min_dist > dist:
            min_dist = dist
            index = i

    if index > -1:
        return names[index]

    return s

print(normalize('치과병원진료미'))
print(normalize('모골수가진료비'))

short-circuit 코드를 제거하고 수행한 시간과 비교하면 어느 정도의 이득이 있는지 확인할 수 있습니다.

2 Likes