Python'da Düzenleme Mesafesi

Question

Python'da bir yazım denetimi programı programlıyorum. Geçerli kelimelerin bir listesi (sözlük) var ve bu sözlükten belirli bir geçersiz kelimeden 2'lik bir düzenleme mesafesine sahip bir sözcük listesi çıkarmam gerekiyor.

Geçersiz kelimeden bir düzenleme mesafesi olan bir liste oluşturarak başlamanız gerektiğini biliyorum (ve sonra oluşturulan tüm sözcüklerde bunu tekrar çalıştırın). Üç yöntemim var, ekler (...), silme (...) ve (...) sözcükleri bir liste çıktısı olan bir liste çıktısı olan ekler, burada ekler tüm geçerli sözcükleri bir harfden daha fazla harfle gönderir. Verilen sözcük, silme işlemi geçerli kelimelerin tümünü bir harfle çıkarır ve tüm geçerli kelimeleri tek bir harfle değiştirir.

Bir sürü yeri işaretledim ancak bu işlemi açıklayan bir algoritma bulamıyorum. Geldiğim tüm fikirler çok fazla zaman harcayacak olan sözlükler listesinden bir çok kez girmeyi içeriyor. Eğer birileri bir fikir verebilirse, son derece minnettar olurum.

Answer 1

Tanımladığınız belirli algoritmaya Levenshtein mesafesi denir. Hızlı bir Google, hesaplamak için birkaç Python kitaplığı ve tarifleri atar.

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

İşte Levenshtein mesafeye

 
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

Burada bir düzenleme mesafesi denir bakarak ve olduğu şey bir nice explanation on wiki olduğu için benim sürümüdür. İki kelime ile istediğiniz sözcük arasındaki mesafeyi nasıl tanımlayacağınız konusunda birçok yol vardır ve Levenshtein mesafesi denir ve burada python'da bir DP uygulamasıdır.

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] 

Ve couple of more implementations are here. Bunun yerine bu algoritmalar olarak, Levenshtein mesafe algo kullanımı BK ağaç veya TRIE ile gitmeyi

Answer 5

daha az karmaşıklık düzenleme mesafe var. Bu konu üzerinde iyi bir göz atmak ayrıntılı bir açıklama verecektir.

Bu link yazım denetimi hakkında daha fazla yardımcı olacaktır.