Tính toán khoảng cách chỉnh sửa văn bản tối thiểu Python

Hiểu thuật toán Levenshtein

Báo cáo vấn đề

Xét hai xâu đầu vào A và B có độ dài lần lượt là n và m, chỉ chứa các chữ cái tiếng Anh viết thường. Vấn đề là tìm khoảng cách Levenshtein giữa A và B bằng cách sử dụng các chỉnh sửa sau

• Chèn một ký tự vào A
• Xóa một ký tự khỏi A
• Thay thế một ký tự trong A bằng bất kỳ ký tự nào khác

Chi phí của mỗi hoạt động là 1

Thuật toán [Sử dụng các bài toán con]

Khoảng cách Levenshtein giữa hai chuỗi có thể được tìm thấy bằng lập trình động. Thuật toán thể hiện tính chất của các bài toán con trùng nhau

Xét hai dây A và B

• Trường hợp 1. A[1]=B[1]A[1] = B[1]A[1]=B[1]. Trong trường hợp này, chúng ta có thể bỏ qua vị trí đầu tiên và khoảng cách chỉnh sửa của toàn bộ bài toán bằng khoảng cách chỉnh sửa của A[2. n]A[2. n]A[2. n] và B[2. m]B[2. m]B[2. tôi]. Đây S[i. j]S[i. j]S[i. j] có nghĩa là chuỗi con của SSS từ vị trí iii đến vị trí jjj
• Trường hợp 2. A[1]≠B[1]A[1] \neq B[1]A[1]≠B[1]. Trong trường hợp này, chúng tôi sẽ sử dụng ba thao tác được đề cập ở trên để tìm khoảng cách chỉnh sửa
  • Chèn B[1]B[1]B[1] vào AAA. Khoảng cách chỉnh sửa bằng 1 + khoảng cách chỉnh sửa của A[1. n]A[1. n]A[1. n] và B[2. m]B[2. m]B[2. tôi]. Điều này là do ký tự đầu tiên trong BBB khớp với ký tự đầu tiên mới được thêm vào trong AAA
  • Xóa A[1]A[1]A[1]. Khoảng cách chỉnh sửa bằng 1 + khoảng cách chỉnh sửa của A[2. n]A[2. n]A[2. n] và B[1. m]B[1. m]B[1. tôi]. Điều này là do chúng tôi đã xóa ký tự đầu tiên trong AAA. Các ký tự còn lại trong cả hai chuỗi sẽ góp phần chỉnh sửa khoảng cách của toàn bộ vấn đề
  • Thay A[1]A[1]A[1] bằng B[1]B[1]B[1]. Khoảng cách chỉnh sửa sẽ bằng 1 + khoảng cách chỉnh sửa của A[2. n]A[2. n]A[2. n] và B[2. m]B[2. m]B[2. tôi]. Khoảng cách chỉnh sửa sẽ là chi phí tối thiểu để chèn, xóa hoặc thay thế các ký tự trong AAA để có được chuỗi BBB

Ý tưởng chung của thuật toán là biến đổi tiền tố của xâu A[1. tôi]A[1. tôi]A[1. i] bằng tiền tố của chuỗi B[1. j]B[1. j]B[1. j] sử dụng số lượng thao tác chèn, xóa và thay thế tối thiểu. Tại mỗi điểm không phù hợp, chúng ta cần áp dụng ba loại chỉnh sửa và chọn thao tác giảm thiểu khoảng cách chỉnh sửa tổng thể của vấn đề

Thí dụ

Chúng ta hãy xem xét một ví dụ trong đó AAA = "cổng" và BBB = "dê". Để tính khoảng cách Levenshtein, chúng tôi sẽ sử dụng phương pháp trên

• AAA = "cổng" và BBB = "con dê". Vì A[1]=B[1]A[1] = B[1]A[1]=B[1] nên chúng ta chỉ cần di chuyển đến ký tự tiếp theo
• Vì A[2]≠B[2]A[2] \neq B[2]A[2]≠B[2] nên ta có ba cách chọn. Nếu chúng ta thực hiện
  • Chèn. Chúng tôi nhận được AAA = "con dê" và BBB = "con dê"
  • Xóa bỏ. Chúng tôi nhận được AAA = "gte" và BBB = "dê"
  • Thay thế. Chúng tôi nhận được AAA = "gote" và BBB = "con dê"

Bây giờ nếu chúng ta nhìn vào lựa chọn nơi chúng ta chèn một phần tử, chúng ta sẽ thấy rằng việc xóa ký tự cuối cùng khỏi AAA = "goate" sẽ biến nó thành chuỗi B. Do đó trong trường hợp này, khoảng cách chỉnh sửa sẽ là 222. Các trường hợp còn lại ta thấy số phép toán sẽ nhiều hơn nên lấy nhỏ nhất trong 3 trường hợp. Chỉnh sửa Khoảng cách của AAA = "cổng" và BBB = "dê" là 222

Hiểu mảng

Bây giờ để tính toán hiệu quả kết quả, chúng ta cần thêm ghi nhớ trong thuật toán trên. Để làm điều này, chúng ta cần một số trạng thái để xác định duy nhất một bài toán con. Để xác định một bài toán con, ta chỉ cần biết độ dài tiền tố của xâu AAA và xâu BBB. Do đó, chúng tôi cần hai biến iii và jjj, để xác định trạng thái lập trình động của chúng tôi. Hãy để chúng tôi xác định DP[i][j]DP[i][j]DP[i][j] = Khoảng cách Levenshtein của chuỗi A[1. tôi]A[1. tôi]A[1. i] và chuỗi B[1. j]B[1. j]B[1. j]

trường hợp cơ sở

Trong trường hợp cơ bản, chúng ta có thể coi độ dài của một trong các chuỗi là 000. Trong trường hợp này, chúng tôi sẽ chỉ sử dụng các thao tác chèn nếu độ dài của AAA là 000 hoặc chúng tôi sẽ chỉ sử dụng các thao tác xóa nếu độ dài của chuỗi BBB là 000. DP[0][j]=jDP[0][j] = jDP[0][j]=j cho tất cả jjj từ 111 đến mmm. DP[i][0]=iDP[i][0] = iDP[i][0]=i cho tất cả iii từ 111 đến nnn

chuyển tiếp

Giả sử chúng ta muốn tính khoảng cách chỉnh sửa của A[0. tôi]A[0. tôi]A[0. tôi] và B[0. j]B[0. j]B[0. j], sau đó

• Trường hợp 1. A[i]==B[j]⇒DP[i][j]=DP[i−1][j−1]A[i] == B[j] \Rightarrow DP[i][j] =
• Trường hợp 2. A[i]≠B[j]A[i] \neq B[j]A[i]≠B[j]. Trong trường hợp này, chúng ta cần thực hiện thao tác chỉnh sửa
  • Nếu chúng ta thực hiện thao tác chèn thì chúng ta sẽ lấy i−1i-1i−1 ký tự từ AAA và ký tự jjj từ BBB, vì vậy DP[i][j]=1+DP[i−1][j]DP[i][
  • Nếu chúng tôi thực hiện thao tác xóa thì chúng tôi chưa khớp với ký tự thứ jthj^{th}j trong B, vì vậy chúng tôi chỉ cần chuyển tiếp khoảng cách chỉnh sửa được tính cho đến ký tự thứ ithi^{th}i của AAA và [j−1]th[
  • Nếu chúng ta thay thế, thì DP[i][j]=1+DP[i−1][j−1]DP[i][j] = 1 + DP[i-1][j-1]DP

Cuối cùng, chúng ta viết DP[i][j]=1+min{DP[i−1][j],DP[i][j−1],DP[i−1][j−1]}DP[

Kết quả cuối cùng

Sau khi chúng tôi tính toán tất cả các chuyển đổi, Khoảng cách Levenshtein sẽ bằng DP[N][M]DP[N][M]DP[N][M]

Thí dụ

Chúng ta hãy nhìn vào ma trận DPDPDP cho AAA = "gate" và BBB = "con dê". Ở đây n=m=4n = m = 4n=m=4. Coi i=0i = 0i=0 và j=0j = 0j=0 là các trình vòng lặp. Khi i=1i = 1i=1 và j=1. mj = 1. mj=1. m chúng tôi tính toán khoảng cách chỉnh sửa cho A[1]A[1]A[1] với tất cả các tiền tố của BBB. Vì A[1]==B[1]A[1] == B[1]A[1]==B[1] nên DP[1][1]=DP[i−1][j−1 . Vì B[2]B[2]B[2] là một ký tự phụ nên cần phải thực hiện thao tác xóa, DP[1][2]=DP[1][1]+1=2DP[1][2] = . Bằng cách này, chúng tôi xây dựng phần còn lại của ma trận

Khi i=2i = 2i=2 và j=1. mj = 1. mj=1. m, chúng tôi tính toán khoảng cách chỉnh sửa cho A[1. 2]A[1. 2]A[1. 2] với tất cả các tiền tố của BBB

Lặp lại quy trình tương tự, chúng ta sẽ có toàn bộ ma trận DPDPDP

Thực hiện

def levenshteinDistance[A, B]:
    N, M = len[A], len[B]
    # Create an array of size NxM
    dp = [[0 for i in range[M + 1]] for j in range[N + 1]]

    # Base Case: When N = 0
    for j in range[M + 1]:
        dp[0][j] = j
    # Base Case: When M = 0
    for i in range[N + 1]:
        dp[i][0] = i
    # Transitions
    for i in range[1, N + 1]:
        for j in range[1, M + 1]:
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min[
                    dp[i-1][j], # Insertion
                    dp[i][j-1], # Deletion
                    dp[i-1][j-1] # Replacement
                ]

    return dp[N][M]

if __name__ == '__main__':
    A = ["helo", "algorithm", "kitten", "gate"]
    B = ["hello", "rhythm", "sitting", "goat"]
    for i in range[len[A]]:
        print["Levenshtein Distance between {} and {} = {}".format[A[i], B[i], levenshteinDistance[A[i], B[i]]]]

đầu ra

  

Levenshtein Distance between helo and hello = 1
Levenshtein Distance between algorithm and rhythm = 6
Levenshtein Distance between kitten and sitting = 3
Levenshtein Distance between the gate and goat = 2
Phân tích độ phức tạp của thuật toán Levenshtein
Thời gian phức tạp
Trong quá trình triển khai, chúng tôi có trạng thái n∗mn*mn∗m và đối với mỗi lần chuyển đổi, chúng tôi mất O[1]O[1]O[1] thời gian, do đó độ phức tạp thời gian là O[n∗m]O[n . Thời gian phức tạp. O[n∗m]O[n*m]O[n∗m]
Độ phức tạp không gian
Trong quá trình triển khai, chúng tôi sử dụng một bảng để lưu trữ n∗mn*mn∗m trạng thái của vấn đề, do đó độ phức tạp của không gian là O[n∗m]O[n*m]O[n∗m] trong đó nnn và mmm là . Độ phức tạp không gian. O[n∗m]O[n*m]O[n∗m]