برنامه محاسبه فاصله ویرایش — به زبان ساده

دو رشته str1 و str2 داده شده و عملیات بیان شده در زیر، روی رشته str1 قابل انجام است. هدف، پیدا کردن حداقل ویرایش‌های لازم برای تبدیل یک رشته (str1) به رشته دیگر (str2) است. در واقع، در ادامه روش نوشتن برنامه محاسبه فاصله ویرایش (Edit Distance) – برای مثال جهت تبدیل رشته «str1» به «str2» – آموزش داده خواهد شد. همچنین، پیاده‌سازی روش آموزش داده شده در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پی‌اچ‌پی» (PHP) انجام شده است.

1. درج (Insert)
2. حذف (Remove)
3. جایگزینی (Replace)

همه اعمال بیان شده در بالا دارای هزینه یکسانی هستند. مثال زیر در این رابطه جالب توجه است.

Input:   str1 = "geek", str2 = "gesek"
Output:  1
We can convert str1 into str2 by inserting a 's'.

Input:   str1 = "cat", str2 = "cut"
Output:  1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input:   str1 = "sunday", str2 = "saturday"
Output:  3
Last three and first characters are same.  We basically
need to convert "un" to "atur".  This can be done using
below three operations. 
Replace 'n' with 'r', insert t, insert a

محاسبه فاصله ویرایش به روش بازگشتی

ایده کلی برای حل این مسأله، پردازش همه کاراکترها یکی یکی با شروع از سمت راست یا چپ هر دو رشته است. در اینجا، پیمایش از سمت راست رشته آغاز می‌شود. دو احتمال برای هر جفت از کاراکترهای پیمایش شده وجود دارد.

m: Length of str1 (first string)
n: Length of str2 (second string)

اگر آخرین کاراکتر از دو رشته مشابه باشند، کار دیگری برای انجام دادن وجود ندارد. باید از آخرین کاراکتر صرف‌نظر کرد و محاسبه را برای ادامه رشته (رشته باقی‌مانده) انجام داد. بنابراین، بازگشت برای طول‌های m-1 و n-1 انجام می‌شود. در غیر این صورت (اگر آخرین کاراکتر دو رشته با یکدیگر مشابه نباشند)، همه عملیات روی str1 انجام می‌شود. در واقع، هر سه عملیات روی آخرین کاراکتر از رشته اول در نظر گرفته می‌شود و حداقل هزینه برای هر سه عملیات به صورت بازگشتی محاسبه و کمینه (Minimum) سه مقدار حاصل شده محاسبه می‌شود.

• درج: بازگشت برای m تا n-1
• حذف: بازگشت برای m-1 و n
• جایگزینی: بازگشت از m-1 و n-1

در ادامه، پیاده‌سازی راهکار بازگشتی ساده بالا در زبان برنامه‌نویسی ++C انجام می‌شود.

برنامه محاسبه فاصله ویرایش در ++C به روش بازگشتی

// A Naive recursive C++ program to find minimum number 
// operations to convert str1 to str2 
#include<bits/stdc++.h> 
using namespace std; 
  
// Utility function to find minimum of three numbers 
int min(int x, int y, int z) 
{ 
   return min(min(x, y), z); 
} 
  
int editDist(string str1 , string str2 , int m ,int n) 
{ 
    // If first string is empty, the only option is to 
    // insert all characters of second string into first 
    if (m == 0) return n; 
  
    // If second string is empty, the only option is to 
    // remove all characters of first string 
    if (n == 0) return m; 
  
    // If last characters of two strings are same, nothing 
    // much to do. Ignore last characters and get count for 
    // remaining strings. 
    if (str1[m-1] == str2[n-1]) 
        return editDist(str1, str2, m-1, n-1); 
  
    // If last characters are not same, consider all three 
    // operations on last character of first string, recursively 
    // compute minimum cost for all three operations and take 
    // minimum of three values. 
    return 1 + min ( editDist(str1,  str2, m, n-1),    // Insert 
                     editDist(str1,  str2, m-1, n),   // Remove 
                     editDist(str1,  str2, m-1, n-1) // Replace 
                   ); 
} 
  
// Driver program 
int main() 
{ 
    // your code goes here 
    string str1 = "sunday"; 
    string str2 = "saturday"; 
  
    cout << editDist( str1 , str2 , str1.length(), str2.length()); 
  
    return 0; 
} 

برنامه محاسبه فاصله ویرایش در جاوا به روش بازگشتی

// A Naive recursive Java program to find minimum number 
// operations to convert str1 to str2 
class EDIST 
{ 
    static int min(int x,int y,int z) 
    { 
        if (x<=y && x<=z) return x; 
        if (y<=x && y<=z) return y; 
        else return z; 
    } 
  
    static int editDist(String str1 , String str2 , int m ,int n) 
    { 
        // If first string is empty, the only option is to 
    // insert all characters of second string into first 
    if (m == 0) return n; 
       
    // If second string is empty, the only option is to 
    // remove all characters of first string 
    if (n == 0) return m; 
       
    // If last characters of two strings are same, nothing 
    // much to do. Ignore last characters and get count for 
    // remaining strings. 
    if (str1.charAt(m-1) == str2.charAt(n-1)) 
        return editDist(str1, str2, m-1, n-1); 
       
    // If last characters are not same, consider all three 
    // operations on last character of first string, recursively 
    // compute minimum cost for all three operations and take 
    // minimum of three values. 
    return 1 + min ( editDist(str1,  str2, m, n-1),    // Insert 
                     editDist(str1,  str2, m-1, n),   // Remove 
                     editDist(str1,  str2, m-1, n-1) // Replace                      
                   ); 
    } 
  
    public static void main(String args[]) 
    { 
        String str1 = "sunday"; 
        String str2 = "saturday"; 
   
        System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) ); 
    } 
} 
/*This code is contributed by Rajat Mishra*/

برنامه محاسبه فاصله ویرایش در پایتون به روش بازگشتی

# A Naive recursive Python program to fin minimum number 
# operations to convert str1 to str2 
def editDistance(str1, str2, m , n): 
  
    # If first string is empty, the only option is to 
    # insert all characters of second string into first 
    if m==0: 
         return n 
  
    # If second string is empty, the only option is to 
    # remove all characters of first string 
    if n==0: 
        return m 
  
    # If last characters of two strings are same, nothing 
    # much to do. Ignore last characters and get count for 
    # remaining strings. 
    if str1[m-1]==str2[n-1]: 
        return editDistance(str1,str2,m-1,n-1) 
  
    # If last characters are not same, consider all three 
    # operations on last character of first string, recursively 
    # compute minimum cost for all three operations and take 
    # minimum of three values. 
    return 1 + min(editDistance(str1, str2, m, n-1),    # Insert 
                   editDistance(str1, str2, m-1, n),    # Remove 
                   editDistance(str1, str2, m-1, n-1)    # Replace 
                   ) 
  
# Driver program to test the above function 
str1 = "sunday"
str2 = "saturday"
print editDistance(str1, str2, len(str1), len(str2)) 
  
# This code is contributed by Bhavya Jain 

برنامه محاسبه فاصله ویرایش در #C به روش بازگشتی

// A Naive recursive C# program to 
// find minimum numberoperations  
// to convert str1 to str2 
using System; 
  
class GFG 
{ 
    static int min(int x, int y, int z) 
    { 
        if (x <= y && x <= z) return x; 
        if (y <= x && y <= z) return y; 
        else return z; 
    } 
  
    static int editDist(String str1 , String str2 , int m ,int n) 
    { 
        // If first string is empty, the only option is to 
        // insert all characters of second string into first 
        if (m == 0) return n; 
          
        // If second string is empty, the only option is to 
        // remove all characters of first string 
        if (n == 0) return m; 
          
        // If last characters of two strings are same, nothing 
        // much to do. Ignore last characters and get count for 
        // remaining strings. 
        if (str1[m - 1] == str2[n - 1]) 
            return editDist(str1, str2, m - 1, n - 1); 
          
        // If last characters are not same, consider all three 
        // operations on last character of first string, recursively 
        // compute minimum cost for all three operations and take 
        // minimum of three values. 
        return 1 + min ( editDist(str1, str2, m, n - 1), // Insert 
                        editDist(str1, str2, m - 1, n), // Remove 
                        editDist(str1, str2, m - 1, n - 1) // Replace                      
                    ); 
    } 
      
    // Driver code 
    public static void Main() 
    { 
        String str1 = "sunday"; 
        String str2 = "saturday"; 
        Console.WriteLine( editDist( str1 , str2 , str1.Length,  
                                                 str2.Length )); 
    } 
} 
  
// This Code is Contributed by Sam007 

برنامه محاسبه فاصله ویرایش در PHP به روش بازگشتی

<?php  
// A Naive recursive Python program   
// to find minimum number operations  
// to convert str1 to str2  
function editDistance($str1, $str2,  
                      $m, $n) 
{  
    // If first string is empty,  
    // the only option is to insert. 
    // all characters of second 
    // string into first  
    if ($m == 0) 
        return $n;  
  
    // If second string is empty, 
    // the only option is to  
    // remove all characters of  
    // first string  
    if ($n == 0)  
        return $m;  
  
    // If last characters of two  
    // strings are same, nothing  
    // much to do. Ignore last  
    // characters and get count  
    // for remaining strings.  
    if ($str1[$m - 1] == $str2[$n - 1]) 
    {  
        return editDistance($str1, $str2,  
                            $m - 1, $n - 1);  
    } 
      
    // If last characters are not same,  
    // consider all three operations on  
    // last character of first string,  
    // recursively compute minimum cost  
    // for all three operations and take  
    // minimum of three values.  
  
    return 1 + min(editDistance($str1, $str2,  
                                $m, $n - 1), // Insert  
                   editDistance($str1, $str2,  
                                $m - 1, $n), // Remove  
                   editDistance($str1, $str2,  
                                $m - 1, $n - 1)); // Replace  
}  
  
// Driver Code 
$str1 = "sunday"; 
$str2 = "saturday"; 
echo editDistance($str1, $str2, strlen($str1),  
                                strlen($str2));  
  
// This code is contributed  
// by Shivi_Aggarwal 
?> 

خروجی قطعه کدهای بالا به صورت زیر است.

3

پیچیدگی زمانی راهکار بالا به صورت نمایی است. در بدترین حالت، این کار دارای درجه پیچیدگی O(3^m)‎ است. بدترین حالت هنگامی اتفاق می‌افتد که هیچ یک از کاراکترهای بالا از دو رشته تطبیق پیدا نکنند. در زیر، نمودار فراخوانی بازگشتی برای بدترین حالت ارائه شده است.

محاسبه فاصله ویرایش به روش برنامه‌نویسی پویا

می‌توان مشاهده کرد که زیر مسائل دوباره و دوباره حل می‌شوند. برای مثال، eD(2,2)‎ سه آیتم را فراخوانی می‌کند. با توجه به اینکه زیرمسائل مشابهی چندین و چند بار تکرار می‌شوند، این مسائل، دارای زیرمسائل هم‌پوشان هستند. بنابراین، مساله ویرایش فاصله، دارای دو مشخصه از مسائل «برنامه‌نویسی پویا» (Dynamic Programming) است. محاسبه مجدد زیر مسائل مشابه با ساخت یک آرایه موقت که نتایج زیر مسائل را ذخیره می‌کند، قابل اجتناب است.

برنامه محاسبه فاصله ویرایش در ++C به روش برنامه‌نویسی پویا

// A Dynamic Programming based C++ program to find minimum 
// number operations to convert str1 to str2 
#include<bits/stdc++.h> 
using namespace std; 
  
// Utility function to find the minimum of three numbers 
int min(int x, int y, int z) 
{ 
    return min(min(x, y), z); 
} 
  
int editDistDP(string str1, string str2, int m, int n) 
{ 
    // Create a table to store results of subproblems 
    int dp[m+1][n+1]; 
  
    // Fill d[][] in bottom up manner 
    for (int i=0; i<=m; i++) 
    { 
        for (int j=0; j<=n; j++) 
        { 
            // If first string is empty, only option is to 
            // insert all characters of second string 
            if (i==0) 
                dp[i][j] = j;  // Min. operations = j 
  
            // If second string is empty, only option is to 
            // remove all characters of second string 
            else if (j==0) 
                dp[i][j] = i; // Min. operations = i 
  
            // If last characters are same, ignore last char 
            // and recur for remaining string 
            else if (str1[i-1] == str2[j-1]) 
                dp[i][j] = dp[i-1][j-1]; 
  
            // If the last character is different, consider all 
            // possibilities and find the minimum 
            else
                dp[i][j] = 1 + min(dp[i][j-1],  // Insert 
                                   dp[i-1][j],  // Remove 
                                   dp[i-1][j-1]); // Replace 
        } 
    } 
  
    return dp[m][n]; 
} 
  
// Driver program 
int main() 
{ 
    // your code goes here 
    string str1 = "sunday"; 
    string str2 = "saturday"; 
  
    cout << editDistDP(str1, str2, str1.length(), str2.length()); 
  
    return 0; 
} 

برنامه محاسبه فاصله ویرایش در جاوا به روش برنامه‌نویسی پویا

// A Dynamic Programming based Java program to find minimum 
// number operations to convert str1 to str2 
class EDIST 
{ 
    static int min(int x,int y,int z) 
    { 
        if (x <= y && x <= z) return x; 
        if (y <= x && y <= z) return y; 
        else return z; 
    } 
  
    static int editDistDP(String str1, String str2, int m, int n) 
    { 
        // Create a table to store results of subproblems 
        int dp[][] = new int[m+1][n+1]; 
       
        // Fill d[][] in bottom up manner 
        for (int i=0; i<=m; i++) 
        { 
            for (int j=0; j<=n; j++) 
            { 
                // If first string is empty, only option is to 
                // insert all characters of second string 
                if (i==0) 
                    dp[i][j] = j;  // Min. operations = j 
       
                // If second string is empty, only option is to 
                // remove all characters of second string 
                else if (j==0) 
                    dp[i][j] = i; // Min. operations = i 
       
                // If last characters are same, ignore last char 
                // and recur for remaining string 
                else if (str1.charAt(i-1) == str2.charAt(j-1)) 
                    dp[i][j] = dp[i-1][j-1]; 
       
                // If the last character is different, consider all 
                // possibilities and find the minimum 
                else
                    dp[i][j] = 1 + min(dp[i][j-1],  // Insert 
                                       dp[i-1][j],  // Remove 
                                       dp[i-1][j-1]); // Replace 
            } 
        } 
   
        return dp[m][n]; 
    } 
  
      
  
    public static void main(String args[]) 
    { 
        String str1 = "sunday"; 
        String str2 = "saturday"; 
        System.out.println( editDistDP( str1 , str2 , str1.length(), str2.length()) ); 
    } 
}/*This code is contributed by Rajat Mishra*/

برنامه محاسبه فاصله ویرایش در پایتون به روش برنامه‌نویسی پویا

# A Dynamic Programming based Python program for edit 
# distance problem 
def editDistDP(str1, str2, m, n): 
    # Create a table to store results of subproblems 
    dp = [[0 for x in range(n+1)] for x in range(m+1)] 
  
    # Fill d[][] in bottom up manner 
    for i in range(m+1): 
        for j in range(n+1): 
  
            # If first string is empty, only option is to 
            # insert all characters of second string 
            if i == 0: 
                dp[i][j] = j    # Min. operations = j 
  
            # If second string is empty, only option is to 
            # remove all characters of second string 
            elif j == 0: 
                dp[i][j] = i    # Min. operations = i 
  
            # If last characters are same, ignore last char 
            # and recur for remaining string 
            elif str1[i-1] == str2[j-1]: 
                dp[i][j] = dp[i-1][j-1] 
  
            # If last character are different, consider all 
            # possibilities and find minimum 
            else: 
                dp[i][j] = 1 + min(dp[i][j-1],        # Insert 
                                   dp[i-1][j],        # Remove 
                                   dp[i-1][j-1])    # Replace 
  
    return dp[m][n] 
  
# Driver program 
str1 = "sunday"
str2 = "saturday"
  
print(editDistDP(str1, str2, len(str1), len(str2))) 
# This code is contributed by Bhavya Jain 

برنامه محاسبه فاصله ویرایش در #C به روش برنامه‌نویسی پویا

// A Dynamic Programming based  
// C# program to find minimum 
// number operations to  
// convert str1 to str2 
using System; 
  
class GFG 
{ 
    static int min(int x, int y, int z) 
    { 
        if (x <= y && x <= z) return x; 
        if (y <= x && y <= z) return y; 
        else return z; 
    } 
  
    static int editDistDP(String str1, String str2, int m, int n) 
    { 
        // Create a table to store 
        // results of subproblems 
        int [,]dp = new int[m + 1,n + 1]; 
      
        // Fill d[][] in bottom up manner 
        for (int i = 0; i <= m; i++) 
        { 
            for (int j = 0; j <= n; j++) 
            { 
                // If first string is empty, only option is to 
                // insert all characters of second string 
                if (i == 0) 
                  
                    // Min. operations = j 
                    dp[i, j] = j;  
      
                // If second string is empty, only option is to 
                // remove all characters of second string 
                else if (j == 0) 
                       
                     // Min. operations = i 
                    dp[i,j] = i;  
      
                // If last characters are same, ignore last char 
                // and recur for remaining string 
                else if (str1[i - 1] == str2[j - 1]) 
                    dp[i, j] = dp[i - 1, j - 1]; 
      
                // If the last character is different, consider all 
                // possibilities and find the minimum 
                else
                    dp[i, j] = 1 + min(dp[i, j - 1], // Insert 
                                    dp[i - 1, j], // Remove 
                                    dp[i - 1, j - 1]); // Replace 
            } 
        } 
  
        return dp[m, n]; 
    } 
  
      
    // Driver code 
    public static void Main() 
    { 
        String str1 = "sunday"; 
        String str2 = "saturday"; 
        Console.Write( editDistDP( str1 , str2 , str1.Length,  
                                               str2.Length )); 
    } 
} 
// This Code is Contributed by Sam007 

برنامه محاسبه فاصله ویرایش در PHP به روش برنامه‌نویسی پویا

<?php 
// A Dynamic Programming based  
// Python program for edit  
// distance problem  
function editDistDP($str1, $str2,  
                    $m, $n) 
{  
// Fill d[][] in bottom up manner  
for ($i = 0; $i <= $m; $i++)  
{   
    for ($j = 0; $j <= $n; $j++)  
    {  
  
        // If first string is empty,  
        // only option is to insert  
        // all characters of second string  
        if ($i == 0)  
            $dp[$i][$j] = $j ; // Min. operations = j  
  
        // If second string is empty,  
        // only option is to remove  
        // all characters of second string  
        else if($j == 0)  
            $dp[$i][$j] = $i; // Min. operations = i  
  
        // If last characters are same,  
        // ignore last char and recur  
        // for remaining string  
        else if($str1[$i - 1] == $str2[$j - 1])  
            $dp[$i][$j] = $dp[$i - 1][$j - 1]; 
  
        // If last character are different,  
        // consider all possibilities and  
        // find minimum  
        else
        {  
            $dp[$i][$j] = 1 + min($dp[$i][$j - 1],     // Insert  
                                  $dp[$i - 1][$j],     // Remove  
                                  $dp[$i - 1][$j - 1]); // Replace  
        } 
    } 
} 
return $dp[$m][$n] ; 
} 
  
// Driver Code  
$str1 = "sunday"; 
$str2 = "saturday"; 
  
echo editDistDP($str1, $str2, strlen($str1),  
                              strlen($str2)); 
  
// This code is contributed  
// by Shivi_Aggarwal 
?> 

خروجی قطعه کدهای بالا به صورت زیر است.

3

پیچیدگی زمانی این روش از درجه O(m x n)‎ و فضای کمکی آن از درجه O(m x n)‎ است. کاربردهای عملی زیادی برای الگوریتم بیان شده وجود دارد. به عنوان مثالی در این رابطه، می‌توان به نمایش همه کلمات در لغت‌نامه‌ای اشاره کرد که تقریب نزدیکی به کلمه نوشته شده به صورت اشتباه دارند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های برنامه‌نویسی پایتون
• آموزش تکمیلی برنامه‌نویسی پایتون
• مجموعه آموزش‌های داده‌کاوی و یادگیری ماشین
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• یادگیری علم داده (Data Science) با پایتون — از صفر تا صد
• آموزش پایتون (Python) — مجموعه مقالات جامع وبلاگ فرادرس

^^