Отладка реализации расстояния Левенштейна - как рассчитывается минимальное расстояние? - PullRequest
Новая
       21

Отладка реализации расстояния Левенштейна - как рассчитывается минимальное расстояние?

1 голос
/ 05 июня 2019

Я некоторое время пытался понять этот код, но не могу понять, как рассчитываются расстояния.Я знаю, как должен работать алгоритм (он обеспечивает расстояние редактирования в символах между двумя строками, и я могу сделать это на бумаге), но я не понимаю, как эта строка (в качестве примера)

d (i, j) = d (i - 1, j - 1)

возвращается как целое число.То же самое для min1, min2.Мы уже определим

d (i, 0)

и

d (0, j)

, но как получить значение, когда

d (i, j)

не равно 0 в одном из двух аргументов?

Код: 

Option Explicit
Public Function Levenshtein(s1 As String, s2 As String)

Dim i As Integer
Dim j As Integer
Dim l1 As Integer
Dim l2 As Integer
Dim d() As Integer
Dim min1 As Integer
Dim min2 As Integer

l1 = Len(s1)
l2 = Len(s2)
ReDim d(l1, l2)
For i = 0 To l1
    d(i, 0) = i
Next
For j = 0 To l2
    d(0, j) = j
Next
For i = 1 To l1
    For j = 1 To l2
        If Mid(s1, i, 1) = Mid(s2, j, 1) Then
            d(i, j) = d(i - 1, j - 1)   
        Else
            min1 = d(i - 1, j) + 1
            min2 = d(i, j - 1) + 1
            If min2 < min1 Then
                min1 = min2
            End If
            min2 = d(i - 1, j - 1) + 1
            If min2 < min1 Then
                min1 = min2
            End If
            d(i, j) = min1
        End If
    Next
Next
Levenshtein = d(l1, l2)
End Function

?Levenshtein("saturday","sunday")

3

1 Ответ

1 голос
/ 05 июня 2019

Я не очень разбираюсь в Левенштейне, однако я могу объяснить, что происходит в этом массиве, пожалуйста, смотрите комментарии в коде: 

l1 = Len(s1) 'this sets a variable with the length of the first string
l2 = Len(s2) 'this sets a variable with the length of the second string

ReDim d(l1, l2) 'redimension the array to this size, though this can be seen as ReDim d(0 to l1, 0 to l2)

For i = 0 To l1 'for i = 0 to length of first string
    d(i, 0) = i 'allocate the value of i to each row in the array, at col 0
Next i

For j = 0 To l2 'for j = 0 to length of second string
    d(0, j) = j 'allocate the value of j to each column in the array, at row 0
Next j

РЕДАКТИРОВАТЬ: I 'мы добавили некоторую отладку (напечатает в ActiveSheet).Синий для совпадения букв, красный для остальных ... хотя цвет не имеет значения.

Насколько я могу судить, при каждой итерации цикла он строит матрицу различий, начиная ссравнивая 1: 1 первые буквы, до последних.Основываясь на позиции цикла и на каждой итерации, он будет использовать предыдущие значения позиции для вычисления разницы в текущей позиции.

Вероятно, это проще выполнить с более короткими строками.

  • Цикл каждой буквы второго слова, затем цикл каждой буквы первого слова

  • в первом внешнем цикле (для каждой строки), в первом внутреннем цикле (для каждого столбца),мы имеем S встретить S = 0. (d(i, j) = d(i - 1, j - 1) оценивается в d(i, j) = d(1 - 1, 1 - 1), то есть: 0)

  • в первом внешнем цикле, во втором внутреннем цикле, мыимеют S встречаются U = 1.

  • и т. д. и т. д.

enter image description here

Кроме того, пошагово пройдитесь по коду и посмотрите, как переменные меняются в зависимости от условий if ... не уверен, что я смогу объяснить это лучше. 

Public Function Levenshtein(s1 As String, s2 As String)

Dim i As Integer, j As Integer
Dim l1 As Integer, l2 As Integer
Dim min1 As Integer, min2 As Integer
Dim d() As Integer

'For debugging purposes only
Cells.Clear
Dim rngOutput As Range: Set rngOutput = ActiveSheet.Range("A1").Resize(Len(s1) + 2, Len(s2) + 2)

With rngOutput
    .ColumnWidth = 3
    .HorizontalAlignment = xlCenter
    .VerticalAlignment = xlCenter
End With

l1 = Len(s1): l2 = Len(s2): ReDim d(l1, l2)

For i = 0 To l1
    d(i, 0) = i
    With rngOutput
        .Cells(i + 3, 1) = Mid(s1, i + 1, 1)
        If Not i = 0 Then .Cells(i + 2, 2) = i
    End With
Next i

For j = 0 To l2
    d(0, j) = j
    With rngOutput
        .Cells(1, j + 3) = Mid(s2, j + 1, 1)
        If Not j = 0 Then .Cells(2, j + 2) = j
    End With
Next j

For i = 1 To l1
    For j = 1 To l2
        If Mid(s1, i, 1) = Mid(s2, j, 1) Then
            d(i, j) = d(i - 1, j - 1)

            With rngOutput.Cells(i + 2, j + 2)
                .Value = d(i, j)
                .Font.Color = vbBlue
            End With
        Else
            min1 = d(i - 1, j) + 1
            min2 = d(i, j - 1) + 1
            If min2 < min1 Then
                min1 = min2
            End If
            min2 = d(i - 1, j - 1) + 1
            If min2 < min1 Then
                min1 = min2
            End If
            d(i, j) = min1

            With Cells(i + 2, j + 2)
                .Value = d(i, j)
                .Font.Color = vbRed
            End With
        End If
    Next
Next

Levenshtein = d(l1, l2)
End Function
...