[algorithm] 가장 가까운 문자열 일치

약 1 년 전에 사용자가 기타 정보 데이터베이스에 석유 굴착 장치에 대한 정보를 입력했을 때이 문제가 발생했습니다. 목표는 가장 일반적인 요소로 데이터베이스 항목을 식별 할 수있는 일종의 퍼지 문자열 검색을 수행하는 것이 었습니다.

연구의 일환으로 레 벤슈 테인 거리 알고리즘을 구현하는 것이 포함 되었는데,이 알고리즘은 문자열이나 구를 다른 문자열이나 구로 바꾸는 횟수를 결정합니다.

내가 생각해 낸 구현은 비교적 간단했으며 두 구의 길이, 각 구 사이의 변경 횟수 및 각 단어를 대상 항목에서 찾을 수 있는지 여부를 가중 비교했습니다.

이 기사는 개인 사이트에 있으므로 여기에 관련 내용을 추가하기 위해 최선을 다하겠습니다.

퍼지 문자열 일치는 두 단어 나 구의 유사성을 인간과 같은 방식으로 평가하는 프로세스입니다. 많은 경우에, 그것은 서로 가장 유사한 단어 나 문구를 식별하는 것을 포함합니다. 이 기사에서는 퍼지 문자열 일치 문제에 대한 사내 솔루션과 이전에 지루한 사용자 참여가 필요했던 작업을 자동화 할 수있는 다양한 문제를 해결하는 데 유용한 점에 대해 설명합니다.

소개

퍼지 문자열 일치는 원래 멕시코만 검사기 도구를 개발하는 동안 시작되었습니다. 기존의 멕시코 석유 굴착 장치 및 플랫폼의 데이터베이스가 존재했으며 보험을 구매하는 사람들은 자산에 대한 정보를 잘못 입력했으며 알려진 플랫폼의 데이터베이스와 일치시켜야했습니다. 정보가 거의 없었을 때, 우리가 할 수있는 최선의 방법은 보험업자가 자신이 언급 한 정보를 “인식”하고 적절한 정보를 불러오는 것입니다. 이 자동화 된 솔루션이 유용합니다.

나는 퍼지 문자열 매칭 방법을 연구하면서 하루를 보냈고 결국 Wikipedia에서 매우 유용한 Levenshtein 거리 알고리즘을 발견했습니다.

이행

그 배후의 이론에 대해 읽은 후, 나는 그것을 최적화하는 방법을 구현하고 발견했습니다. VBA에서 내 코드는 다음과 같습니다.

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
    Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
    Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter
    Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
    L1 = Len(S1): L2 = Len(S2)
    ReDim D(0 To L1, 0 To L2)
    For i = 0 To L1: D(i, 0) = i: Next i
    For j = 0 To L2: D(0, j) = j: Next j

    For j = 1 To L2
        For i = 1 To L1
            cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare))
            cI = D(i - 1, j) + 1
            cD = D(i, j - 1) + 1
            cS = D(i - 1, j - 1) + cost
            If cI <= cD Then 'Insertion or Substitution
                If cI <= cS Then D(i, j) = cI Else D(i, j) = cS
            Else 'Deletion or Substitution
                If cD <= cS Then D(i, j) = cD Else D(i, j) = cS
            End If
        Next i
    Next j
    LevenshteinDistance = D(L1, L2)
End Function

간단하고 빠르며 매우 유용한 지표입니다. 이를 사용하여 두 문자열의 유사성을 평가하기위한 두 개의 개별 메트릭을 만들었습니다. 하나는 “valuePhrase”이고 다른 하나는 “valueWords”입니다. valuePhrase는 두 구 사이의 Levenshtein 거리이며 valueWords는 공백, 대시 및 기타 원하는 항목과 같은 구분 기호를 기반으로 문자열을 개별 단어로 나누고 각 단어를 서로 단어와 비교하여 가장 짧은 단어를 합칩니다. 두 단어를 연결하는 레 벤슈 테인 거리. 본질적으로 한 단어 문구의 정보가 단어 단위 순열과 같이 다른 문구에 실제로 포함되어 있는지 여부를 측정합니다. 구분 기호를 기반으로 문자열을 분할하는 가장 효율적인 방법을 제안하는 부수 프로젝트로 며칠을 보냈습니다.

valueWords, valuePhrase 및 Split 함수 :

Public Function valuePhrase#(ByRef S1$, ByRef S2$)
    valuePhrase = LevenshteinDistance(S1, S2)
End Function

Public Function valueWords#(ByRef S1$, ByRef S2$)
    Dim wordsS1$(), wordsS2$()
    wordsS1 = SplitMultiDelims(S1, " _-")
    wordsS2 = SplitMultiDelims(S2, " _-")
    Dim word1%, word2%, thisD#, wordbest#
    Dim wordsTotal#
    For word1 = LBound(wordsS1) To UBound(wordsS1)
        wordbest = Len(S2)
        For word2 = LBound(wordsS2) To UBound(wordsS2)
            thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2))
            If thisD < wordbest Then wordbest = thisD
            If thisD = 0 Then GoTo foundbest
        Next word2
foundbest:
        wordsTotal = wordsTotal + wordbest
    Next word1
    valueWords = wordsTotal
End Function

''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' SplitMultiDelims
' This function splits Text into an array of substrings, each substring
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' contain any number of delimiter characters. It returns a single element
' array containing all of text if DelimChars is empty, or a 1 or greater
' element array if the Text is successfully split into substrings.
' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur.
' If Limit greater than 0, the function will only split Text into 'Limit'
' array elements or less. The last element will contain the rest of Text.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _
        Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
        Optional ByVal Limit As Long = -1) As String()
    Dim ElemStart As Long, N As Long, M As Long, Elements As Long
    Dim lDelims As Long, lText As Long
    Dim Arr() As String

    lText = Len(Text)
    lDelims = Len(DelimChars)
    If lDelims = 0 Or lText = 0 Or Limit = 1 Then
        ReDim Arr(0 To 0)
        Arr(0) = Text
        SplitMultiDelims = Arr
        Exit Function
    End If
    ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit))

    Elements = 0: ElemStart = 1
    For N = 1 To lText
        If InStr(DelimChars, Mid(Text, N, 1)) Then
            Arr(Elements) = Mid(Text, ElemStart, N - ElemStart)
            If IgnoreConsecutiveDelimiters Then
                If Len(Arr(Elements)) > 0 Then Elements = Elements + 1
            Else
                Elements = Elements + 1
            End If
            ElemStart = N + 1
            If Elements + 1 = Limit Then Exit For
        End If
    Next N
    'Get the last token terminated by the end of the string into the array
    If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart)
    'Since the end of string counts as the terminating delimiter, if the last character
    'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent
    If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1

    ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements
    SplitMultiDelims = Arr
End Function

유사성 측정

이 두 메트릭과 두 문자열 사이의 거리를 단순히 계산하는 세 번째 메트릭을 사용하여 가장 많은 수의 일치를 달성하기 위해 최적화 알고리즘을 실행할 수있는 일련의 변수가 있습니다. 퍼지 문자열 일치는 그 자체로 퍼지 과학이므로 문자열 유사성을 측정하기 위해 선형으로 독립적 인 메트릭을 만들고 서로 일치하는 알려진 문자열 집합을 가짐으로써 특정 스타일에 대한 매개 변수를 찾을 수 있습니다. 문자열은 퍼지 일치 결과가 가장 좋습니다.

처음에이 메트릭의 목표는 정확한 일치를 위해 낮은 검색 값을 사용하고 점점 더 순열되는 측정 값을위한 검색 값을 높이는 것이 었습니다. 실용적이지 않은 경우, 잘 정의 된 순열을 사용하여 정의하기가 매우 쉬웠으며 원하는대로 검색 값 결과가 증가하도록 최종 공식을 엔지니어링했습니다.

위의 스크린 샷에서 나는 휴리스틱을 조정하여 검색 용어와 결과 사이의 인식 된 차이로 멋지게 확장 된 느낌을 얻었습니다. Value Phrase위의 스프레드 시트에서 사용한 휴리스틱 은 =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2))입니다. 레 벤스 타인 거리의 페널티를 두 “문구”의 길이 차이의 80 %만큼 효과적으로 줄였습니다. 이렇게하면 길이가 같은 “구문”은 전체 페널티를 받지만 “추가 정보”(더 긴)를 포함하지만 여전히 대부분 동일한 문자를 공유하는 “구문”은 페널티가 줄어 듭니다. Value Words함수를있는 그대로 사용하고 최종 SearchVal휴리스틱을 다음과 같이 정의했습니다.=MIN(D2,E2)*0.8+MAX(D2,E2)*0.2-가중 평균. 두 점수 중 더 낮은 점수가 80 %, 더 높은 점수의 20 %를 가중했습니다. 이것은 좋은 사용률을 얻기 위해 사용 사례에 적합한 휴리스틱이었습니다. 이 가중치는 테스트 데이터와 가장 일치하는 비율을 얻기 위해 조정할 수있는 것입니다.

보시다시피, 퍼지 문자열 일치 메트릭 인 마지막 두 메트릭은 이미 일치하는 문자열 (대각선 아래)에 낮은 점수를주는 경향이 있습니다. 이것은 매우 좋습니다.

적용
퍼지 매칭을 최적화하기 위해 각 메트릭에 가중치를 부여합니다. 따라서 퍼지 문자열 일치의 모든 응용 프로그램은 매개 변수의 가중치를 다르게 지정할 수 있습니다. 최종 점수를 정의하는 공식은 단순히 메트릭과 가중치의 조합입니다.

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
      + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
      + lengthWeight*lengthValue

최적화 알고리즘을 사용하면 (신경망은 이산적이고 다차원적인 문제이기 때문에 여기에서 가장 좋습니다), 목표는 이제 일치 횟수를 최대화하는 것입니다. 이 마지막 스크린 샷에서 볼 수 있듯이 각 세트의 서로 일치하는 수를 감지하는 함수를 만들었습니다. 가장 낮은 점수에 일치시킬 문자열이 할당되면 열 또는 행에 점이 표시되고 가장 낮은 점수에 대한 동점이 있으면 부분 점수가 제공되며, 일치하는 문자열이 묶인 일치 문자열 사이에 있습니다. 그런 다음 최적화했습니다. 녹색 셀이 현재 행과 가장 일치하는 열이고 셀 주위의 파란색 사각형이 현재 열과 가장 일치하는 행임을 알 수 있습니다. 하단 모퉁이의 점수는 대략 성공한 경기 수이며 최적화 문제가 최대화하도록 알려줍니다.

알고리즘은 대단한 성공을 거두었으며 솔루션 매개 변수는 이러한 유형의 문제에 대해 많은 것을 말해줍니다. 최적화 된 점수는 44이고 가능한 최고 점수는 48입니다. 끝에있는 5 개의 열은 미끼이며 행 값과 전혀 일치하지 않습니다. 미끼가 많을수록 자연스럽게 가장 잘 어울리는 것이 더 어려워집니다.

이 특정 일치하는 경우, 더 긴 단어를 나타내는 약어를 기대하기 때문에 문자열의 길이는 관련이 없으므로 길이의 최적 가중치는 -0.3이므로 길이가 다른 문자열에 불이익을주지 않습니다. 우리는 이러한 약어를 예상하여 점수를 줄임으로써 문자열이 더 짧기 때문에 대체가 덜 필요한 비 단어 일치를 대체하기 위해 부분 단어 일치를위한 더 많은 공간을 제공합니다.

단어 가중치는 1.0이고 구문 가중치는 0.5에 불과합니다. 즉, 한 문자열에서 누락 된 전체 단어에 불이익을주고 전체 구문을 그대로 유지합니다. 이 문자열의 많은 부분이 하나의 공통된 단어 (위험)를 가지고 있기 때문에 실제로 중요한 것은 조합 (지역 및 위험)이 유지되는지 여부입니다.

마지막으로 최소 가중치는 10으로 최적화되고 최대 가중치는 1로 최적화됩니다. 이는 두 점수 중 최고 점수 (값 구 및 값 단어)가 좋지 않은 경우 일치가 크게 불이익을 받지만 두 점수 중 최악의 점수를 크게받지 않습니다. 본질적으로, 필요에이 풋 강조 하거나 valueWord 또는 valuePhrase 좋은 점수 있지만 모두 가지고 있습니다. 일종의 “우리가 얻을 수있는 것을 가져라”정신.

퍼지 스트링 매칭의 종류에 대해이 5 가지 가중치의 최적화 된 값이 말하는 것은 정말 매력적입니다. 퍼지 문자열 일치의 완전히 다른 실제 사례의 경우 이러한 매개 변수는 매우 다릅니다. 지금까지 3 가지 응용 프로그램에 사용했습니다.

최종 최적화에서 사용되지는 않았지만 벤치마킹 시트가 확립되어 대각선 아래로 모든 완벽한 결과를 얻기 위해 열을 자체와 일치시키고 사용자가 점수가 0에서 분기되는 속도를 제어하도록 매개 변수를 변경하고 검색 구 사이의 고유 유사성을 기록 할 수 있습니다 ( 이론적으로 결과에서 오 탐지를 상쇄하는 데 사용될 수 있음)

추가 응용

이 솔루션은 사용자가 컴퓨터 시스템이 완벽하게 일치하지 않는 일련의 문자열에서 문자열을 식별하도록 원하는 모든 위치에서 사용될 수 있습니다. (문자열에 대한 대략적인 일치 vlookup처럼).

따라서 이것에서 취해야 할 것은 레 벤슈 테인 거리 알고리즘의 구현과 함께 높은 수준의 휴리스틱 (하나의 문구에서 다른 문구의 단어 찾기, 두 문구의 길이 등) 조합을 사용하고 싶을 것입니다. “최상”일치 항목을 결정하는 것은 휴리스틱 (퍼지) 결정이므로 유사성을 결정하기 위해 어떤 메트릭에 대해서도 가중치를 설정해야합니다.

적절한 휴리스틱 및 가중치 세트를 사용하면 비교 프로그램에서 결정을 신속하게 내릴 수 있습니다.

답변

function levenshtein_distance(str1, str2)
    local len1, len2 = #str1, #str2
    local char1, char2, distance = {}, {}, {}
    str1:gsub('.', function (c) table.insert(char1, c) end)
    str2:gsub('.', function (c) table.insert(char2, c) end)
    for i = 0, len1 do distance[i] = {} end
    for i = 0, len1 do distance[i][0] = i end
    for i = 0, len2 do distance[0][i] = i end
    for i = 1, len1 do
        for j = 1, len2 do
            distance[i][j] = math.min(
                distance[i-1][j  ] + 1,
                distance[i  ][j-1] + 1,
                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
                )
        end
    end
    return distance[len1][len2]
end