Excel VBA NGram 유사도 알고리즘 계산

Excel VBA NGram 유사도 알고리즘 계산

excel vba NGram 유사도 알고리즘 계산을 vba 코드로 옮겨봄.
N-Gram 유사도에서 1에 가까운 값은 두 텍스트 또는 시퀀스가 매우 유사하다는 것을 의미.
N-Gram 유사도는 주로 교집합의 크기를 합집합의 크기로 나누어 계산하기 때문에, 이 비율이 1에 가까워질수록 두 시퀀스 사이의 공통된 N-Gram의 비율이 높아지는 것을 나타냄.
따라서, 유사도가 1에 가깝다면 두 시퀀스는 거의 동일하거나 매우 비슷한 패턴을 가지고 있다고 볼 수 있음.
반대로, 유사도가 0에 가까운 경우는 두 시퀀스 간에 공통된 N-Gram이 거의 없거나 전혀 없다는 것을 의미하며, 이는 두 시퀀스가 매우 다르다는 것을 나타냄.

 

텍스트 예시로, "과과과과과과과"와 "과과과과과궈"를 예로 들겠습니다.

여기서는 2-Gram을 기준으로 계산하는 과정을 살펴보겠습니다.

1. 2-Gram 생성: 먼저 각 텍스트를 2글자씩 나누어 2-Gram을 생성합니다.
   • "과과과과과과과"에서 생성되는 2-Gram: 과과, 과과, 과과, 과과, 과과, 과과
   • "과과과과과궈"에서 생성되는 2-Gram: 과과, 과과, 과과, 과과, 과궈
2. 중복 제거: 2-Gram 집합에서 중복을 제거합니다.
   • "과과과과과과과"의 2-Gram 집합: {과과}
   • "과과과과과궈"의 2-Gram 집합: {과과, 과궈}
3. 교집합과 합집합 계산:
   • 교집합: 두 집합에 공통으로 있는 2-Gram은 {과과}입니다.
   • 합집합: 두 집합의 모든 유니크한 2-Gram을 합친 것은 {과과, 과궈} 임.
4. 유사도 계산: 유사도는 교집합의 크기를 합집합의 크기로 나누어 계산.
   • 교집합의 크기: 1 (과과)
   • 합집합의 크기: 2 (과과, 과궈)
   • 유사도: 1 / 2 = 0.5

결론적으로, "과과과과과과과"와 "과과과과과궈"의 2-Gram 유사도는 0.5. 이는 두 텍스트가 일부 유사하지만 완전히 같지는 않음을 나타냄. 현재 텍스트 비교시 자카드 유사도와 함께 2-Gram 유사도를 혼합하여 쓰고 있음. "레벤슈타인 거리"와 비교시 조금 더 정밀한 텍스트 비교가 필요하여 넣었으나, 엑셀 로직 돌아갈시 부하가 크게 나타남.

 

' NGram 유사도를 계산하는 함수입니다.
Function NGramSimilarity(text1 As String, text2 As String, n As Integer) As Double
    Dim gramSet1 As Object, gramSet2 As Object, gram As Variant
    Dim intersectCount As Integer, unionCount As Integer

    ' 문자열을 N-Gram 집합으로 변환합니다.
    Set gramSet1 = CreateNGramSet(text1, n)
    Set gramSet2 = CreateNGramSet(text2, n)

    ' 교집합과 합집합의 개수를 계산합니다.
    intersectCount = 0
    unionCount = gramSet1.Count + gramSet2.Count

    For Each gram In gramSet1
        If gramSet2.Exists(gram) Then
            intersectCount = intersectCount + 1
            gramSet2.Remove gram ' 중복 계산을 방지합니다.
        End If
    Next gram

    ' 합집합 개수에서 교집합 개수를 빼서 업데이트합니다.
    unionCount = unionCount - intersectCount

    ' 유사도를 계산합니다 (교집합 개수 / 합집합 개수).
    NGramSimilarity = intersectCount / unionCount
End Function

' 주어진 텍스트에서 N-Gram 집합을 생성하는 함수입니다.
Function CreateNGramSet(text As String, n As Integer) As Object
    Dim i As Integer
    Dim nGram As String
    Set CreateNGramSet = CreateObject("Scripting.Dictionary")

    ' N-Gram을 생성하고 집합에 추가합니다.
    For i = 1 To Len(text) - n + 1
        nGram = Mid(text, i, n)
        If Not CreateNGramSet.Exists(nGram) Then
            CreateNGramSet.Add nGram, nGram
        End If
    Next i
End Function

' NGram 유사도를 테스트하는 Sub 프로시저입니다.
Sub TestNGramSimilarity()
    Dim testString1 As String
    Dim testString2 As String
    Dim result As Double

    ' 오류 처리를 위한 레이블입니다.
    On Error GoTo ErrorHandler

    ' 비교할 문자열을 지정합니다.
    testString1 = activeSheet.Range("A1").value   '과과과과과과과
    testString2 = activeSheet.Range("B1").value   '과과과과과궈

    ' N-Gram 유사도를 계산합니다 (예: 2-Gram).
    result = NGramSimilarity(testString1, testString2, 2)

    ' 결과를 출력합니다.
    Debug.Print "Similarity: " & result '0.5

    ' Sub 프로시저 종료 전에 실행됩니다.
    Exit Sub

ErrorHandler:
    ' 오류가 발생한 경우 오류 메시지를 출력합니다.
    Debug.Print "Error in TestNGramSimilarity: " & Err.Description
End Sub