Editierdistanz (Levenshtein)

Das Problem der Edit-Distanz

# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)

# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose  (delete r at index 1)
# 3. rose  → ros   (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')

DP-Zustand und Rekurrenz

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    # Base cases
    for i in range(m+1): dp[i][0] = i  # delete all of word1
    for j in range(n+1): dp[0][j] = j  # insert all of word2
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # no cost
            else:
                dp[i][j] = 1 + min(
                    dp[i][j-1],    # insert
                    dp[i-1][j],    # delete
                    dp[i-1][j-1]   # replace
                )
    return dp[m][n]

print(edit_distance('horse', 'ros'))          # 3
print(edit_distance('intention', 'execution')) # 5

Die drei Operationen verstehen

# Visualise the DP table for 'cat' → 'cut'
# dp[i][j] = min edits for word1[:i] vs word2[:j]

word1, word2 = 'cat', 'cut'
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
    for j in range(1, n+1):
        if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
        else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
print('  ', ' '.join(' '+word2))
for i, row in enumerate(dp):
    print((' ' if i==0 else word1[i-1]), row)

Optimierung des Speicherbedarfs auf O(n)

def edit_distance_1d(word1, word2):
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))  # initial row: 0,1,2,...,n
    for i in range(1, m + 1):
        diag = dp[0]       # dp[i-1][0]
        dp[0] = i          # dp[i][0] = i
        for j in range(1, n + 1):
            temp = dp[j]   # dp[i-1][j] before overwrite
            if word1[i-1] == word2[j-1]:
                dp[j] = diag
            else:
                dp[j] = 1 + min(dp[j],     # delete
                                dp[j-1],   # insert
                                diag)      # replace
            diag = temp
    return dp[n]

print(edit_distance_1d('horse', 'ros'))          # 3
print(edit_distance_1d('intention', 'execution')) # 5

Rekonstruktion der Edit-Operationen

def edit_ops(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0]=i
    for j in range(n+1): dp[0][j]=j
    for i in range(1,m+1):
        for j in range(1,n+1):
            if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
            else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
    ops, i, j = [], m, n
    while i>0 or j>0:
        if i>0 and j>0 and word1[i-1]==word2[j-1]:
            i-=1; j-=1
        elif j>0 and (i==0 or dp[i][j-1]<=dp[i-1][j] and dp[i][j-1]<=dp[i-1][j-1]):
            ops.append(f'Insert {word2[j-1]} at pos {i}'); j-=1
        elif i>0 and (j==0 or dp[i-1][j]<=dp[i][j-1] and dp[i-1][j]<=dp[i-1][j-1]):
            ops.append(f'Delete {word1[i-1]} at pos {i-1}'); i-=1
        else:
            ops.append(f'Replace {word1[i-1]} with {word2[j-1]}'); i-=1; j-=1
    return list(reversed(ops))

for op in edit_ops('horse', 'ros'): print(op)

Prüfung auf eine Edit-Distanz von eins

def is_one_edit_distance(s, t):
    m, n = len(s), len(t)
    if abs(m - n) > 1: return False
    if m > n: return is_one_edit_distance(t, s)  # ensure m <= n
    for i in range(m):
        if s[i] != t[i]:
            if m == n:
                return s[i+1:] == t[i+1:]   # replace
            else:
                return s[i:] == t[i+1:]     # insert into s (delete from t)
    return m + 1 == n  # all matched, lengths differ by 1

print(is_one_edit_distance('ab', 'acb'))   # True (insert c)
print(is_one_edit_distance('ab', 'ab'))    # False (zero edits)
print(is_one_edit_distance('ab', 'abc'))   # True (append c)
print(is_one_edit_distance('ab', 'xyz'))   # False

Vergleich von Edit-Distanz und LCS

def lcs_len(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
            else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    return dp[m][n]

def edit_insert_delete_only(s1, s2):
    return len(s1) + len(s2) - 2 * lcs_len(s1, s2)

print(edit_insert_delete_only('sea', 'eat'))  # 2
print(edit_distance('sea', 'eat'))            # 2 (same here: replace not needed)

Unscharfer Zeichenkettenabgleich

def spell_suggest(typed, dictionary, max_dist=2):
    '''Return words in dictionary within max_dist edits of typed.'''
    suggestions = []
    for word in dictionary:
        if abs(len(typed) - len(word)) <= max_dist:
            if edit_distance(typed, word) <= max_dist:
                suggestions.append(word)
    return suggestions

def edit_distance(w1, w2):
    dp = list(range(len(w2)+1))
    for i,c1 in enumerate(w1,1):
        prev = i
        for j,c2 in enumerate(w2,1):
            temp = dp[j]
            dp[j] = prev if c1==c2 else 1+min(dp[j],prev,dp[j-1])
            prev = temp
    return dp[len(w2)]

dictionary = ['horse', 'worse', 'house', 'morse', 'nurse']
print(spell_suggest('harse', dictionary))  # horse, worse, house, morse

Gewichtete Edit-Distanz

def damerau_levenshtein(s, t):
    m, n = len(s), len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0]=i
    for j in range(n+1): dp[0][j]=j
    for i in range(1,m+1):
        for j in range(1,n+1):
            cost = 0 if s[i-1]==t[j-1] else 1
            dp[i][j] = min(
                dp[i-1][j]+1,     # delete
                dp[i][j-1]+1,     # insert
                dp[i-1][j-1]+cost # replace
            )
            # Transposition
            if i>1 and j>1 and s[i-1]==t[j-2] and s[i-2]==t[j-1]:
                dp[i][j] = min(dp[i][j], dp[i-2][j-2]+1)
    return dp[m][n]

print(damerau_levenshtein('CA', 'ABC'))   # 2
print(damerau_levenshtein('ab', 'ba'))    # 1 (transposition)

DNA-Sequenzalignment

def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-1):
    m, n = len(seq1), len(seq2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i * gap
    for j in range(n+1): dp[0][j] = j * gap
    for i in range(1,m+1):
        for j in range(1,n+1):
            score = match if seq1[i-1]==seq2[j-1] else mismatch
            dp[i][j] = max(
                dp[i-1][j-1] + score,  # align
                dp[i-1][j] + gap,      # gap in seq2
                dp[i][j-1] + gap       # gap in seq1
            )
    return dp[m][n]

print(needleman_wunsch('GATTACA', 'GCATGCU'))  # alignment score

Vorgehensweise bei der Edit-Distanz im Vorstellungsgespräch

# Clean interview solution
def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    # O(n) space with rolling row
    dp = list(range(n + 1))
    for i in range(1, m + 1):
        diag = dp[0]   # dp[i-1][0]
        dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i-1] == word2[j-1]:
                dp[j] = diag
            else:
                dp[j] = 1 + min(dp[j], dp[j-1], diag)
            diag = temp
    return dp[n]

# Time: O(mn), Space: O(n)
print(min_distance('horse', 'ros'))          # 3
print(min_distance('intention', 'execution')) # 5
print(min_distance('', 'abc'))               # 3
print(min_distance('abc', ''))               # 3

Schnelltest

Zusammenfassung der Lektion