C++でレーベンシュタインアルゴリズムを書きました
入力した場合:
文字列 s: 民主主義者
文字列 t: 共和党
行列 D を埋めて、操作の数 (レーベンシュタイン距離) を D[10][8] = 8 で読み取ることができます
。埋められた行列を超えて、最適解を構築したいと考えています。このソリューションはどのように見える必要がありますか? アイデアがありません。
この例では、どのように見える必要があるかだけを書いてください。
9509 次
8 に答える
40
問題は
、レーベンシュタイン アルゴリズムによって生成された行列が与えられた場合、どのようにして「最適解」を見つけることができるかということです。
つまり、's string' を 't string' に変換するために必要な、挿入、削除、[1 文字の] 置換などの文字列操作の正確なシーケンスをどのように見つけることができるでしょうか?
まず、多くの場合、いくつかの最適解があることに注意してください。
レーベンシュタイン アルゴリズムは最小数の操作(民主党/共和党の例では 8) を提供しますが、この変換を生成できる (8 つの操作の) 多数のシーケンスがあります。
レーベンシュタイン行列を「解読」することにより、そのような最適な配列をすべて列挙することができます。
一般的な考え方は、最適解はすべて、左上隅から右下隅(または他の方向) への「パス」をたどるということです。これにより、このパス上のマトリックス セルの値は同じままか、1 ずつ増加 (または減少) します。逆方向に 1 つずつ)、0 から始まり、問題の文字列の最適な操作数 (0 から 8 の民主党/共和党の場合) で終了します。操作が必要な場合は数値が増加し、文字列内の対応する位置の文字が同じ場合は同じままです。
そのようなパスを生成するアルゴリズムを作成するのは簡単です (考えられるすべてのパスを作成するには少し複雑です)。また、そのようなパスから一連の操作を推測します。
この経路検索アルゴリズムは、右下隅から始まり、逆方向に進む必要があります。このアプローチの理由は、最適なソリューションであるためには、このコーナーで終了する必要があり、このコーナーで終了するには、3 つのセルのいずれかからすぐ左またはすぐ上にある必要があることがわかっているためです。それまたはすぐに斜めに。これらの 3 つのセルから、「同じ値または 1 だけ減少する」要件を満たすセルを選択することにより、最適なパスの 1 つにあるセルを効果的に選択します。左上隅に到達するまで (または実際には値が 0 のセルに到達するまで) 操作を繰り返すことで、最適なパスを効果的にバックトラックします。
民主党のイラスト - 共和党の例
また、マトリックスを 2 つの方法のいずれかで構築できることにも注意してください。水平方向または垂直方向の「デモクラット」を使用します。これは、レーベンシュタイン距離の計算を変更したり、必要な操作のリストを変更したりしません。マトリックスを解釈する方法を変更するだけです。たとえば、「パス」上を水平に移動すると、「文字列 s」が「水平」であるかどうかに応じて、[t 文字列から] 文字を挿入するか、[s 文字列から] 文字を削除することを意味します。またはマトリックスの「垂直」。
次のマトリックスを使用します。したがって、規則は次のとおりです（左から右および/または上から下の方向のみ）
- 水平方向の移動は、「t ストリング」からの文字の挿入です。
- 垂直方向の移動は、「文字列」からの文字の削除です
- 斜めの動きは次のいずれかです。
- 無操作（それぞれの位置の両方の文字が同じ）; 数は変わらない
- a SUBSTITUTION (それぞれの位置の文字は区別されます); 数が一つ増えます。
- 無操作（それぞれの位置の両方の文字が同じ）; 数は変わらない
レーベンシュタイン行列 s = "democrat", t="republican"
r e p u b l i c a n
0 1 2 3 4 5 6 7 8 9 10
d 1 1 2 3 4 5 6 7 8 9 10
e 2 2 1 2 3 4 5 6 7 8 9
m 3 3 2 2 3 4 5 6 7 8 9
o 4 4 3 3 3 4 5 6 7 8 9
c 5 5 4 4 4 4 5 6 6 7 8
r 6 5 5 5 5 5 5 6 7 7 8
a 7 6 6 6 6 6 6 6 7 7 8
t 8 7 7 7 7 7 7 7 7 8 8
考えられるいくつかの最適なパスから 1 つのパスを選択するために使用する任意のアプローチを以下に大まかに説明します。
Starting at the bottom-rightmost cell, and working our way backward toward
the top left.
For each "backward" step, consider the 3 cells directly adjacent to the current
cell (in the left, top or left+top directions)
if the value in the diagonal cell (going up+left) is smaller or equal to the
values found in the other two cells
AND
if this is same or 1 minus the value of the current cell
then "take the diagonal cell"
if the value of the diagonal cell is one less than the current cell:
Add a SUBSTITUTION operation (from the letters corresponding to
the _current_ cell)
otherwise: do not add an operation this was a no-operation.
elseif the value in the cell to the left is smaller of equal to the value of
the of the cell above current cell
AND
if this value is same or 1 minus the value of the current cell
then "take the cell to left", and
add an INSERTION of the letter corresponding to the cell
else
take the cell above, add
Add a DELETION operation of the letter in 's string'
この非公式の擬似コードに従うと、次のようになります。
右下の「n」、「t」セルから始めます。
[対角線] "a", "a" セルは他の 2 つよりも小さいため (同じまたは -1 の条件を満たしているため)、次の目的地として選択します。
新しいセルは現在のセルよりも 1 つ少ない
ため、手順 8 では "t" を "n" に置き換えます: democra N
「a」、「a」セルに進み
、[対角]「c」、「r」セルを次の宛先として選択します...
新しいセルは現在のセルと同じ値であることに注意してください==>操作は不要です。
「c」、「r」セルを続行し、
次の目的地として [斜め] 「i」、「c」セルを選択します...
新しいセルは現在のセルよりも 1 つ少ない
ため、手順 7 は「r」に置き換えられます。 "c" の場合: democ C an
「i」、「c」セルを続行し
、[対角線]「l」、「o」セルを次の宛先として選択します...
新しいセルは現在のセルよりも 1 つ少ない
ため、手順 6 は「c」に置き換えられます。 with " i ":できるデモ
「l」、「o」セルを続行し、
次の目的地として [斜め] 「b」、「m」セルを選択します...
新しいセルは現在のセルよりも 1 つ少ない
ため、手順 5 は「o」に置き換えられます。 "l" の場合: dem L ican
「b」、「m」セルに進み、
次の目的地として [斜め]「u」、「e」セルを選択します...
新しいセルは現在のセルよりも 1 つ少ない
ため、手順 4 は「m」に置き換えられます。 "b" の場合: de B lican
「u」、「e」のセルに進み
ます。「左」のセルはそれよりも小さいため、「対角線」のセルは修飾されないことに注意してください。[左]「p」、「e」セルを次の宛先として選択します...
したがって、ステップ3は「e」の後に「u」を挿入します: de U blican
「p」、「e」セルに進みます。
再び「対角」セルは適格ではありません [左]「e」、「e」セルを次の目的地として選択します...
したがって、ステップ 2 は後に「p」を挿入します"e": de Publican
「e」、「e」セルに進み
、[対角]「r」、「d」セルを次の宛先として選択します...
新しいセルは現在のセルと同じ値であることに注意してください ==>操作は必要ありません.
「r」、「d」セルを続行し、
次の目的地として[対角線]「開始」セルを選択します...
新しいセルは現在のセルより1つ少ない
ため、ステップ1は「d」を「r」に置き換えます。 : 共和党_
値が 0 のセルに到達しました。作業は完了です。
于 2011-05-02T18:57:54.183 に答える
1
私がそれで遊んでから数回経ちましたが、マトリックスは次のように見えるはずです：
. . r e p u b l i c a n
. 0 1 2 3 4 5 6 7 8 9 10
d 1 1 2 3 4 5 6 7 8 9 10
e 2 2 1 2 3 4 5 6 7 8 9
m 3 3 2 2 3 4 5 6 7 8 9
o 4 4 3 3 3 4 5 6 7 8 9
c 5 5 4 4 4 4 5 6 7 8 9
r 6 5 5 5 5 5 5 6 7 8 9
a 7 6 6 6 6 6 6 6 7 7 8
t 8 7 7 7 7 7 7 7 7 7 8
ただし、当然のこととは思わないでください。
于 2011-05-01T15:28:51.643 に答える
1
これは、mjv の回答に基づく VBA アルゴリズムです。（非常によく説明されていますが、一部のケースが欠落しています）。
Sub TU_Levenshtein()
Call Levenshtein("democrat", "republican")
Call Levenshtein("ooo", "u")
Call Levenshtein("ceci est un test", "ceci n'est pas un test")
End Sub
Sub Levenshtein(ByVal string1 As String, ByVal string2 As String)
' Fill Matrix Levenshtein (-> array 'Distance')
Dim i As Long, j As Long
Dim string1_length As Long
Dim string2_length As Long
Dim distance() As Long
string1_length = Len(string1)
string2_length = Len(string2)
ReDim distance(string1_length, string2_length)
For i = 0 To string1_length
distance(i, 0) = i
Next
For j = 0 To string2_length
distance(0, j) = j
Next
For i = 1 To string1_length
For j = 1 To string2_length
If Asc(Mid$(string1, i, 1)) = Asc(Mid$(string2, j, 1)) Then
distance(i, j) = distance(i - 1, j - 1)
Else
distance(i, j) = Application.WorksheetFunction.min _
(distance(i - 1, j) + 1, _
distance(i, j - 1) + 1, _
distance(i - 1, j - 1) + 1)
End If
Next
Next
LevenshteinDistance = distance(string1_length, string2_length) ' for information only
' Write Matrix on VBA sheets (only for visuation, not used in calculus)
Cells.Clear
For i = 1 To UBound(distance, 1)
Cells(i + 2, 1).Value = Mid(string1, i, 1)
Next i
For i = 1 To UBound(distance, 2)
Cells(1, i + 2).Value = Mid(string2, i, 1)
Next i
For i = 0 To UBound(distance, 1)
For j = 0 To UBound(distance, 2)
Cells(i + 2, j + 2) = distance(i, j)
Next j
Next i
' One solution
current_posx = UBound(distance, 1)
current_posy = UBound(distance, 2)
Do
cc = distance(current_posx, current_posy)
Cells(current_posx + 1, current_posy + 1).Interior.Color = vbYellow ' visualisation again
' Manage border case
If current_posy - 1 < 0 Then
MsgBox ("deletion. " & Mid(string1, current_posx, 1))
current_posx = current_posx - 1
current_posy = current_posy
GoTo suivant
End If
If current_posx - 1 < 0 Then
MsgBox ("insertion. " & Mid(string2, current_posy, 1))
current_posx = current_posx
current_posy = current_posy - 1
GoTo suivant
End If
' Middle cases
cc_L = distance(current_posx, current_posy - 1)
cc_U = distance(current_posx - 1, current_posy)
cc_D = distance(current_posx - 1, current_posy - 1)
If (cc_D <= cc_L And cc_D <= cc_U) And (cc_D = cc - 1 Or cc_D = cc) Then
If (cc_D = cc - 1) Then
MsgBox "substitution. " & Mid(string1, current_posx, 1) & " by " & Mid(string2, current_posy, 1)
current_posx = current_posx - 1
current_posy = current_posy - 1
GoTo suivant
Else
MsgBox "no operation"
current_posx = current_posx - 1
current_posy = current_posy - 1
GoTo suivant
End If
ElseIf cc_L <= cc_D And cc_L = cc - 1 Then
MsgBox ("insertion. " & Mid(string2, current_posy, 1))
current_posx = current_posx
current_posy = current_posy - 1
GoTo suivant
Else
MsgBox ("deletion." & Mid(string1, current_posy, 1))
current_posx = current_posx
current_posy = current_posy - 1
GoTo suivant
End If
suivant:
Loop While Not (current_posx = 0 And current_posy = 0)
End Sub
于 2016-05-18T12:09:53.857 に答える
0
最近、レーベンシュタイン距離アルゴリズムの行列を使っていくつかの作業を行いました。あるリストを別のリストに変換する操作を作成する必要がありました。(これは文字列でも機能します。)
次の (誓約) テストは、探している機能の種類を示していますか?
, "lev - complex 2"
: { topic
: lev.diff([13, 6, 5, 1, 8, 9, 2, 15, 12, 7, 11], [9, 13, 6, 5, 1, 8, 2, 15, 12, 11])
, "check actions"
: function(topic) { assert.deepEqual(topic, [{ op: 'delete', pos: 9, val: 7 },
{ op: 'delete', pos: 5, val: 9 },
{ op: 'insert', pos: 0, val: 9 },
]); }
}
, "lev - complex 3"
: { topic
: lev.diff([9, 13, 6, 5, 1, 8, 2, 15, 12, 11], [13, 6, 5, 1, 8, 9, 2, 15, 12, 7, 11])
, "check actions"
: function(topic) { assert.deepEqual(topic, [{ op: 'delete', pos: 0, val: 9 },
{ op: 'insert', pos: 5, val: 9 },
{ op: 'insert', pos: 9, val: 7 }
]); }
}
, "lev - complex 4"
: { topic
: lev.diff([9, 13, 6, 5, 1, 8, 2, 15, 12, 11, 16], [13, 6, 5, 1, 8, 9, 2, 15, 12, 7, 11, 17])
, "check actions"
: function(topic) { assert.deepEqual(topic, [{ op: 'delete', pos: 0, val: 9 },
{ op: 'insert', pos: 5, val: 9 },
{ op: 'insert', pos: 9, val: 7 },
{ op: 'replace', pos: 11, val: 17 }
]); }
}
于 2011-06-21T18:52:36.733 に答える
0
編集マトリックス、ソース、ターゲットに従ってすべての編集パスを取得するコード。バグがあればコメントしてください。どうもありがとう！
import copy
from typing import List, Union
def edit_distance(source: Union[List[str], str],
target: Union[List[str], str],
return_distance: bool = False):
"""get the edit matrix
"""
edit_matrix = [[i + j for j in range(len(target) + 1)] for i in range(len(source) + 1)]
for i in range(1, len(source) + 1):
for j in range(1, len(target) + 1):
if source[i - 1] == target[j - 1]:
d = 0
else:
d = 1
edit_matrix[i][j] = min(edit_matrix[i - 1][j] + 1,
edit_matrix[i][j - 1] + 1,
edit_matrix[i - 1][j - 1] + d)
if return_distance:
return edit_matrix[len(source)][len(target)]
return edit_matrix
def get_edit_paths(matrix: List[List[int]],
source: Union[List[str], str],
target: Union[List[str], str]):
"""get all the valid edit paths
"""
all_paths = []
def _edit_path(i, j, optimal_path):
if i > 0 and j > 0:
diagonal = matrix[i - 1][j - 1] # the diagonal value
vertical = matrix[i - 1][j] # the above value
horizontal = matrix[i][j - 1] # the left value
current = matrix[i][j] # current value
# whether the source and target token are the same
flag = False
# compute the minimal value of the diagonal, vertical and horizontal
minimal = min(diagonal, min(vertical, horizontal))
# if the diagonal is the minimal
if diagonal == minimal:
new_i = i - 1
new_j = j - 1
path_ = copy.deepcopy(optimal_path)
# if the diagnoal value equals to current - 1
# it means `replace`` operation
if diagonal == current - 1:
path_.append(f"Replace | {new_j} | {target[new_j]}")
_edit_path(new_i, new_j, path_)
# if the diagonal value equals to current value
# and corresponding positional value of source and target equal
# it means this is current best path
elif source[new_i] == target[new_j]:
flag = True
# path_.append(f"Keep | {new_i}")
_edit_path(new_i, new_j, path_)
# if the position doesn't have best path
# we need to consider other situations
if not flag:
# if vertical value equals to minimal
# it means delete source corresponding value
if vertical == minimal:
new_i = i - 1
new_j = j
path_ = copy.deepcopy(optimal_path)
path_.append(f"Delete | {new_i}")
_edit_path(new_i, new_j, path_)
# if horizontal value equals to minimal
# if mean insert target corresponding value to source
if horizontal == minimal:
new_i = i
new_j = j - 1
path_ = copy.deepcopy(optimal_path)
path_.append(f"Insert | {new_j} | {target[new_j]}")
_edit_path(new_i, new_j, path_)
else:
all_paths.append(list(reversed(optimal_path)))
# get the rows and columns of the edit matrix
row_len = len(matrix) - 1
col_len = len(matrix[0]) - 1
_edit_path(row_len, col_len, optimal_path=[])
return all_paths
if __name__ == "__main__":
source = "BBDEF"
target = "ABCDF"
matrix = edit_distance(source, target)
print("print paths")
paths = get_edit_paths(matrix, source=list(source), target=list(target))
for path in paths:
print(path)
于 2021-11-26T04:44:33.600 に答える