파이썬 Sørensen–Dice coefficient

Sørensen–Dice coefficient

Sørensen–Dice coefficient - Wikipedia

 

1. 쇠렌센-다이스 계수

이 계수는 두 샘플의 유사도를 측정하기 위한 통계량이다.

(통계량이기 때문에, "aaba", "abaa"와 같은 형식은 같다고 생각한다.)

 

@wikipedia

|X|, |Y|는 두 set의 집합의 크기이고, 

쇠렌센 index는 각 set의 요소 수들의 합으로 나눈, 두 set의 교집합 요소 수의 두배와 같다. 

 

이 계수를 이용해서, 두 문자열을 비교해볼 것이다. (같을수록 1, 다를수록 0)

 

2. 파이썬 구현

1. 각 문자의 띄어쓰기를 제거
2. 단순 비교로 같으면 1, 둘 중에 길이가 1이면 0을 return
3. dictionary 이용
4. 첫번째 문자열로, i, i + 1 둘 다 사전에 있으면 +1, 아니면 1로 설정 (i.e "ab" in dict)
5. 교차 크기는 두번째 문자열로, i, i + 1 둘 다 사전에 있고, 0보다 크면,
6. 사전["i" + "i + 1"] 값을 -1, 교차 크기는 +1
7. (교차 크기 x 2) / (두 문자열 길이 합 - 2)

def compare(first, second):
    first = first.replace(" ", "")
    second = second.replace(" ", "")

    if first == second:
        return 1
    if len(first) < 2 or len(second) < 2:
        return 0

    firstBigrams = {}
    for i in range(len(first) - 1):
        bigram = first[i : i + 2]
        if bigram in firstBigrams:
            firstBigrams[bigram] += 1
        else:
            firstBigrams[bigram] = 1

    intersectionSize = 0
    for i in range(len(second) - 1):
        bigram = second[i : i + 2]
        if bigram in firstBigrams and firstBigrams[bigram] > 0:
            firstBigrams[bigram] -= 1
            intersectionSize += 1

    return (2.0 * intersectionSize) / (len(first) + len(second) - 2)

 

결과

if __name__ == "__main__":
    a = "안녕하세요, 자바입니다."
    b = "파이썬입니다, 안녕하세요, 자바와 친구입니다."

    print(compare(a, b))
    print(compare("ababacac", "abacabac"))
    print(compare("abacccac", "abacabac"))
    print(compare("abadac", "aba  cfc"))
    
    
''' 결과
0.625
1.0
0.7142857142857143
0.6
'''

 

3. 가장 매치되는 문자열 찾기

위 compare 함수로,

main = "안녕하세요." 와 target = [ "안녕하슈.", "안녕.?", "하세용안녕." ]

target 중 main과 가장 일치되는 문자열을 찾을 수 있다.

def find_best(main, target):
    assert isinstance(target, list), "Target must be a list of strings"

    ratings = []  # 점수 평가
    bestMatchIndex = 0

    for i in range(len(target)):
        currentTargetString = target[i]
        currentRating = compare(main, currentTargetString)
        ratings.append({"target": currentTargetString, "rating": currentRating})
        if currentRating > ratings[bestMatchIndex]["rating"]:
            bestMatchIndex = i  # selection sort랑 비슷

    bestMatch = ratings[bestMatchIndex]

    return {
        "bestMatch": bestMatch,
        "bestMatchIndex": bestMatchIndex,
        "ratings": ratings,
    }

 

결과

if __name__ == "__main__":
    import pprint
    pp = pprint.PrettyPrinter(indent=4)  # 예쁘게 print

    pp.pprint(
        find_best(
            "돋고, 영락과 무엇이 위하여, 만물은 피어나기 있다.",  # main
            [
                "우리 작고 희망의 가는 칼이다.",
                "못하다 우리 동산에는 무엇을 얼마나 만물은 피고 위하여서 행복스럽고 것이다.",
                "피어나는 꽃, 무엇을 위하여 피는가.",
            ],
        )
    )

''' 결과

{   'bestMatch': {   'rating': 0.2702702702702703,
                     'target': '피어나는 꽃, 무엇을 위하여 피는가.'},
    'bestMatchIndex': 2,
    'ratings': [   {   'rating': 0.058823529411764705,
                       'target': '우리 작고 희망의 가는 칼이다.'},
                   {   'rating': 0.25925925925925924,
                       'target': '못하다 우리 동산에는 무엇을 얼마나 만물은 피고 위하여서 행복스럽고 것이다.'},
                   {   'rating': 0.2702702702702703,
                       'target': '피어나는 꽃, 무엇을 위하여 피는가.'}]}
                       
'''

 

참고

쇠렌센-다이스 계수 @위키백과

파이썬으로 구현된 다양한 문자열 비교 알고리즘 @Github