[python] Edit Distance, Normalized edit distance

edit distance 는 단순하게 두 문장 or 단어가 얼마나 다르냐를 평가하는 값으로 아래와 같이 nltk에서 제공하는 함수를 import하면 바로 사용할 수 있다.

# 단순한 ED score
>>> from nltk.metrics.distance import edit_distance
>>> edit_distance("바나나", "가나나") # 가-바 -> 한 글자 차이
1
>>> edit_distance("바나나", "가나다") # 가-바, 나-다 -> 두 글자 차이
2

 

이 edit distance를 정규화(ICDAR2019 평가 방식 참고)해서 표현해주면 아래와 같다.

norm_ED += 1 - edit_distance("바나나", "가나나") / max(len("바나나"), len("가나나")) # 0.6666666666666667
norm_ED += 1- edit_distance("바나나", "가나나") / max(len("바나나"), len("가나다라"))# 0.75

 

수치값에 길이가 긴 length를 기준으로 구한 값을 나누고, 1에서 빼주면 정규화된 값을 얻을 수 있다

 

max로 처리하는 방법 외에 아래와 같이 if문으로 좀 더 직관적으로 정의할 수도 있다.

curr_ed = 0
if len(gt) == 0 or len(pred) == 0:
    norm_ED += 0
elif len(gt) > len(pred):
    curr_ed = 1 - edit_distance(pred, gt) / len(gt)
    norm_ED += curr_ed
else:
    curr_ed = 1 - edit_distance(pred, gt) / len(pred)
    norm_ED += curr_ed
    
    
norm_ED = norm_ED / float(length_of_data)

도움 준 사이트

https://github.com/clovaai/deep-text-recognition-benchmark/issues/100