Chỉnh sửa khoảng cách bằng Python

Question

Tôi đang lập trình một chương trình kiểm tra chính tả bằng Python. Tôi có một danh sách các từ hợp lệ (từ điển) và tôi cần xuất một danh sách các từ trong từ điển này có khoảng cách chỉnh sửa là 2 từ một từ không hợp lệ đã cho.

Tôi biết tôi cần bắt đầu bằng cách tạo danh sách có khoảng cách chỉnh sửa từ một từ không hợp lệ (và sau đó chạy lại từ đó trên tất cả các từ được tạo). Tôi có ba phương thức, chèn (...), xóa (...) và thay đổi (...) sẽ xuất danh sách các từ có khoảng cách chỉnh sửa là 1, trong đó chèn sẽ xuất tất cả các từ hợp lệ bằng một chữ cái nhiều hơn từ đã cho, việc xóa sẽ xuất tất cả các từ hợp lệ bằng một chữ cái ít hơn và các thay đổi sẽ xuất ra tất cả các từ hợp lệ bằng một chữ cái khác.

Tôi đã kiểm tra một loạt địa điểm nhưng dường như tôi không thể tìm thấy thuật toán mô tả quy trình này. Tất cả những ý tưởng tôi đã đưa ra liên quan đến việc lặp qua danh sách từ điển nhiều lần, điều này sẽ tốn rất nhiều thời gian. Nếu bất cứ ai có thể cung cấp một số cái nhìn sâu sắc, tôi sẽ rất biết ơn.

Answer 1

Thuật toán cụ thể mà bạn mô tả được gọi là khoảng cách Levenshtein. Google nhanh chóng đưa ra một số thư viện và công thức nấu ăn Python để tính toán nó.

Answer 2

#this calculates edit distance not levenstein edit distance 
word1="rice" 

word2="ice" 

len_1=len(word1) 

len_2=len(word2) 

x =[[0]*(len_2+1) for _ in range(len_1+1)]#the matrix whose last element ->edit distance 

for i in range(0,len_1+1): #initialization of base case values 

    x[i][0]=i 
for j in range(0,len_2+1): 

    x[0][j]=j 
for i in range (1,len_1+1): 

    for j in range(1,len_2+1): 

     if word1[i-1]==word2[j-1]: 
      x[i][j] = x[i-1][j-1] 

     else : 
      x[i][j]= min(x[i][j-1],x[i-1][j],x[i-1][j-1])+1 

print x[i][j] 

Answer 3

Đây là phiên bản của tôi cho Levenshtein khoảng cách

 
def edit_distance(s1, s2): 
    m=len(s1)+1 
    n=len(s2)+1 

    tbl = {} 
    for i in range(m): tbl[i,0]=i 
    for j in range(n): tbl[0,j]=j 
    for i in range(1, m): 
     for j in range(1, n): 
      cost = 0 if s1[i-1] == s2[j-1] else 1 
      tbl[i,j] = min(tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+cost) 

    return tbl[i,j] 

print(edit_distance("Helloworld", "HalloWorld")) 

Answer 4

Điều bạn đang nhìn được gọi là một chỉnh sửa khoảng cách và đây là một nice explanation on wiki. Có rất nhiều cách để xác định khoảng cách giữa hai từ và cái mà bạn muốn được gọi là khoảng cách Levenshtein và đây là một triển khai DP trong python.

def levenshteinDistance(s1, s2): 
    if len(s1) > len(s2): 
     s1, s2 = s2, s1 

    distances = range(len(s1) + 1) 
    for i2, c2 in enumerate(s2): 
     distances_ = [i2+1] 
     for i1, c1 in enumerate(s1): 
      if c1 == c2: 
       distances_.append(distances[i1]) 
      else: 
       distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1]))) 
     distances = distances_ 
    return distances[-1] 

Và couple of more implementations are here.

Answer 5

Thay vì sử dụng khoảng cách Levenshtein, hãy sử dụng BK cây hoặc TRIE vì các thuật toán này ít phức tạp hơn nên chỉnh sửa khoảng cách. Một trình duyệt tốt hơn các chủ đề này sẽ cung cấp cho một mô tả chi tiết.

Điều này link sẽ giúp bạn hiểu thêm về kiểm tra chính tả.