برنامه محاسبه فاصله ویرایش — به زبان ساده
دو رشته str1 و str2 داده شده و عملیات بیان شده در زیر، روی رشته str1 قابل انجام است. هدف، پیدا کردن حداقل ویرایشهای لازم برای تبدیل یک رشته (str1) به رشته دیگر (str2) است. در واقع، در ادامه روش نوشتن برنامه محاسبه فاصله ویرایش (Edit Distance) - برای مثال جهت تبدیل رشته «str1» به «str2» - آموزش داده خواهد شد. همچنین، پیادهسازی روش آموزش داده شده در زبانهای برنامهنویسی گوناگون شامل «سیپلاسپلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پیاچپی» (PHP) انجام شده است.
- درج (Insert)
- حذف (Remove)
- جایگزینی (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 به روش بازگشتی
1// A Naive recursive C++ program to find minimum number
2// operations to convert str1 to str2
3#include<bits/stdc++.h>
4using namespace std;
5
6// Utility function to find minimum of three numbers
7int min(int x, int y, int z)
8{
9 return min(min(x, y), z);
10}
11
12int editDist(string str1 , string str2 , int m ,int n)
13{
14 // If first string is empty, the only option is to
15 // insert all characters of second string into first
16 if (m == 0) return n;
17
18 // If second string is empty, the only option is to
19 // remove all characters of first string
20 if (n == 0) return m;
21
22 // If last characters of two strings are same, nothing
23 // much to do. Ignore last characters and get count for
24 // remaining strings.
25 if (str1[m-1] == str2[n-1])
26 return editDist(str1, str2, m-1, n-1);
27
28 // If last characters are not same, consider all three
29 // operations on last character of first string, recursively
30 // compute minimum cost for all three operations and take
31 // minimum of three values.
32 return 1 + min ( editDist(str1, str2, m, n-1), // Insert
33 editDist(str1, str2, m-1, n), // Remove
34 editDist(str1, str2, m-1, n-1) // Replace
35 );
36}
37
38// Driver program
39int main()
40{
41 // your code goes here
42 string str1 = "sunday";
43 string str2 = "saturday";
44
45 cout << editDist( str1 , str2 , str1.length(), str2.length());
46
47 return 0;
48}
برنامه محاسبه فاصله ویرایش در جاوا به روش بازگشتی
1// A Naive recursive Java program to find minimum number
2// operations to convert str1 to str2
3class EDIST
4{
5 static int min(int x,int y,int z)
6 {
7 if (x<=y && x<=z) return x;
8 if (y<=x && y<=z) return y;
9 else return z;
10 }
11
12 static int editDist(String str1 , String str2 , int m ,int n)
13 {
14 // If first string is empty, the only option is to
15 // insert all characters of second string into first
16 if (m == 0) return n;
17
18 // If second string is empty, the only option is to
19 // remove all characters of first string
20 if (n == 0) return m;
21
22 // If last characters of two strings are same, nothing
23 // much to do. Ignore last characters and get count for
24 // remaining strings.
25 if (str1.charAt(m-1) == str2.charAt(n-1))
26 return editDist(str1, str2, m-1, n-1);
27
28 // If last characters are not same, consider all three
29 // operations on last character of first string, recursively
30 // compute minimum cost for all three operations and take
31 // minimum of three values.
32 return 1 + min ( editDist(str1, str2, m, n-1), // Insert
33 editDist(str1, str2, m-1, n), // Remove
34 editDist(str1, str2, m-1, n-1) // Replace
35 );
36 }
37
38 public static void main(String args[])
39 {
40 String str1 = "sunday";
41 String str2 = "saturday";
42
43 System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) );
44 }
45}
46/*This code is contributed by Rajat Mishra*/
برنامه محاسبه فاصله ویرایش در پایتون به روش بازگشتی
1# A Naive recursive Python program to fin minimum number
2# operations to convert str1 to str2
3def editDistance(str1, str2, m , n):
4
5 # If first string is empty, the only option is to
6 # insert all characters of second string into first
7 if m==0:
8 return n
9
10 # If second string is empty, the only option is to
11 # remove all characters of first string
12 if n==0:
13 return m
14
15 # If last characters of two strings are same, nothing
16 # much to do. Ignore last characters and get count for
17 # remaining strings.
18 if str1[m-1]==str2[n-1]:
19 return editDistance(str1,str2,m-1,n-1)
20
21 # If last characters are not same, consider all three
22 # operations on last character of first string, recursively
23 # compute minimum cost for all three operations and take
24 # minimum of three values.
25 return 1 + min(editDistance(str1, str2, m, n-1), # Insert
26 editDistance(str1, str2, m-1, n), # Remove
27 editDistance(str1, str2, m-1, n-1) # Replace
28 )
29
30# Driver program to test the above function
31str1 = "sunday"
32str2 = "saturday"
33print editDistance(str1, str2, len(str1), len(str2))
34
35# This code is contributed by Bhavya Jain
برنامه محاسبه فاصله ویرایش در #C به روش بازگشتی
1// A Naive recursive C# program to
2// find minimum numberoperations
3// to convert str1 to str2
4using System;
5
6class GFG
7{
8 static int min(int x, int y, int z)
9 {
10 if (x <= y && x <= z) return x;
11 if (y <= x && y <= z) return y;
12 else return z;
13 }
14
15 static int editDist(String str1 , String str2 , int m ,int n)
16 {
17 // If first string is empty, the only option is to
18 // insert all characters of second string into first
19 if (m == 0) return n;
20
21 // If second string is empty, the only option is to
22 // remove all characters of first string
23 if (n == 0) return m;
24
25 // If last characters of two strings are same, nothing
26 // much to do. Ignore last characters and get count for
27 // remaining strings.
28 if (str1[m - 1] == str2[n - 1])
29 return editDist(str1, str2, m - 1, n - 1);
30
31 // If last characters are not same, consider all three
32 // operations on last character of first string, recursively
33 // compute minimum cost for all three operations and take
34 // minimum of three values.
35 return 1 + min ( editDist(str1, str2, m, n - 1), // Insert
36 editDist(str1, str2, m - 1, n), // Remove
37 editDist(str1, str2, m - 1, n - 1) // Replace
38 );
39 }
40
41 // Driver code
42 public static void Main()
43 {
44 String str1 = "sunday";
45 String str2 = "saturday";
46 Console.WriteLine( editDist( str1 , str2 , str1.Length,
47 str2.Length ));
48 }
49}
50
51// This Code is Contributed by Sam007
برنامه محاسبه فاصله ویرایش در PHP به روش بازگشتی
1<?php
2// A Naive recursive Python program
3// to find minimum number operations
4// to convert str1 to str2
5function editDistance($str1, $str2,
6 $m, $n)
7{
8 // If first string is empty,
9 // the only option is to insert.
10 // all characters of second
11 // string into first
12 if ($m == 0)
13 return $n;
14
15 // If second string is empty,
16 // the only option is to
17 // remove all characters of
18 // first string
19 if ($n == 0)
20 return $m;
21
22 // If last characters of two
23 // strings are same, nothing
24 // much to do. Ignore last
25 // characters and get count
26 // for remaining strings.
27 if ($str1[$m - 1] == $str2[$n - 1])
28 {
29 return editDistance($str1, $str2,
30 $m - 1, $n - 1);
31 }
32
33 // If last characters are not same,
34 // consider all three operations on
35 // last character of first string,
36 // recursively compute minimum cost
37 // for all three operations and take
38 // minimum of three values.
39
40 return 1 + min(editDistance($str1, $str2,
41 $m, $n - 1), // Insert
42 editDistance($str1, $str2,
43 $m - 1, $n), // Remove
44 editDistance($str1, $str2,
45 $m - 1, $n - 1)); // Replace
46}
47
48// Driver Code
49$str1 = "sunday";
50$str2 = "saturday";
51echo editDistance($str1, $str2, strlen($str1),
52 strlen($str2));
53
54// This code is contributed
55// by Shivi_Aggarwal
56?>
خروجی قطعه کدهای بالا به صورت زیر است.
3
پیچیدگی زمانی راهکار بالا به صورت نمایی است. در بدترین حالت، این کار دارای درجه پیچیدگی O(3m) است. بدترین حالت هنگامی اتفاق میافتد که هیچ یک از کاراکترهای بالا از دو رشته تطبیق پیدا نکنند. در زیر، نمودار فراخوانی بازگشتی برای بدترین حالت ارائه شده است.
محاسبه فاصله ویرایش به روش برنامهنویسی پویا
میتوان مشاهده کرد که زیر مسائل دوباره و دوباره حل میشوند. برای مثال، eD(2,2) سه آیتم را فراخوانی میکند. با توجه به اینکه زیرمسائل مشابهی چندین و چند بار تکرار میشوند، این مسائل، دارای زیرمسائل همپوشان هستند.
بنابراین، مساله ویرایش فاصله، دارای دو مشخصه از مسائل «برنامهنویسی پویا» (Dynamic Programming) است. محاسبه مجدد زیر مسائل مشابه با ساخت یک آرایه موقت که نتایج زیر مسائل را ذخیره میکند، قابل اجتناب است.
برنامه محاسبه فاصله ویرایش در ++C به روش برنامهنویسی پویا
1// A Dynamic Programming based C++ program to find minimum
2// number operations to convert str1 to str2
3#include<bits/stdc++.h>
4using namespace std;
5
6// Utility function to find the minimum of three numbers
7int min(int x, int y, int z)
8{
9 return min(min(x, y), z);
10}
11
12int editDistDP(string str1, string str2, int m, int n)
13{
14 // Create a table to store results of subproblems
15 int dp[m+1][n+1];
16
17 // Fill d[][] in bottom up manner
18 for (int i=0; i<=m; i++)
19 {
20 for (int j=0; j<=n; j++)
21 {
22 // If first string is empty, only option is to
23 // insert all characters of second string
24 if (i==0)
25 dp[i][j] = j; // Min. operations = j
26
27 // If second string is empty, only option is to
28 // remove all characters of second string
29 else if (j==0)
30 dp[i][j] = i; // Min. operations = i
31
32 // If last characters are same, ignore last char
33 // and recur for remaining string
34 else if (str1[i-1] == str2[j-1])
35 dp[i][j] = dp[i-1][j-1];
36
37 // If the last character is different, consider all
38 // possibilities and find the minimum
39 else
40 dp[i][j] = 1 + min(dp[i][j-1], // Insert
41 dp[i-1][j], // Remove
42 dp[i-1][j-1]); // Replace
43 }
44 }
45
46 return dp[m][n];
47}
48
49// Driver program
50int main()
51{
52 // your code goes here
53 string str1 = "sunday";
54 string str2 = "saturday";
55
56 cout << editDistDP(str1, str2, str1.length(), str2.length());
57
58 return 0;
59}
برنامه محاسبه فاصله ویرایش در جاوا به روش برنامهنویسی پویا
1// A Dynamic Programming based Java program to find minimum
2// number operations to convert str1 to str2
3class EDIST
4{
5 static int min(int x,int y,int z)
6 {
7 if (x <= y && x <= z) return x;
8 if (y <= x && y <= z) return y;
9 else return z;
10 }
11
12 static int editDistDP(String str1, String str2, int m, int n)
13 {
14 // Create a table to store results of subproblems
15 int dp[][] = new int[m+1][n+1];
16
17 // Fill d[][] in bottom up manner
18 for (int i=0; i<=m; i++)
19 {
20 for (int j=0; j<=n; j++)
21 {
22 // If first string is empty, only option is to
23 // insert all characters of second string
24 if (i==0)
25 dp[i][j] = j; // Min. operations = j
26
27 // If second string is empty, only option is to
28 // remove all characters of second string
29 else if (j==0)
30 dp[i][j] = i; // Min. operations = i
31
32 // If last characters are same, ignore last char
33 // and recur for remaining string
34 else if (str1.charAt(i-1) == str2.charAt(j-1))
35 dp[i][j] = dp[i-1][j-1];
36
37 // If the last character is different, consider all
38 // possibilities and find the minimum
39 else
40 dp[i][j] = 1 + min(dp[i][j-1], // Insert
41 dp[i-1][j], // Remove
42 dp[i-1][j-1]); // Replace
43 }
44 }
45
46 return dp[m][n];
47 }
48
49
50
51 public static void main(String args[])
52 {
53 String str1 = "sunday";
54 String str2 = "saturday";
55 System.out.println( editDistDP( str1 , str2 , str1.length(), str2.length()) );
56 }
57}/*This code is contributed by Rajat Mishra*/
برنامه محاسبه فاصله ویرایش در پایتون به روش برنامهنویسی پویا
1# A Dynamic Programming based Python program for edit
2# distance problem
3def editDistDP(str1, str2, m, n):
4 # Create a table to store results of subproblems
5 dp = [[0 for x in range(n+1)] for x in range(m+1)]
6
7 # Fill d[][] in bottom up manner
8 for i in range(m+1):
9 for j in range(n+1):
10
11 # If first string is empty, only option is to
12 # insert all characters of second string
13 if i == 0:
14 dp[i][j] = j # Min. operations = j
15
16 # If second string is empty, only option is to
17 # remove all characters of second string
18 elif j == 0:
19 dp[i][j] = i # Min. operations = i
20
21 # If last characters are same, ignore last char
22 # and recur for remaining string
23 elif str1[i-1] == str2[j-1]:
24 dp[i][j] = dp[i-1][j-1]
25
26 # If last character are different, consider all
27 # possibilities and find minimum
28 else:
29 dp[i][j] = 1 + min(dp[i][j-1], # Insert
30 dp[i-1][j], # Remove
31 dp[i-1][j-1]) # Replace
32
33 return dp[m][n]
34
35# Driver program
36str1 = "sunday"
37str2 = "saturday"
38
39print(editDistDP(str1, str2, len(str1), len(str2)))
40# This code is contributed by Bhavya Jain
برنامه محاسبه فاصله ویرایش در #C به روش برنامهنویسی پویا
1// A Dynamic Programming based
2// C# program to find minimum
3// number operations to
4// convert str1 to str2
5using System;
6
7class GFG
8{
9 static int min(int x, int y, int z)
10 {
11 if (x <= y && x <= z) return x;
12 if (y <= x && y <= z) return y;
13 else return z;
14 }
15
16 static int editDistDP(String str1, String str2, int m, int n)
17 {
18 // Create a table to store
19 // results of subproblems
20 int [,]dp = new int[m + 1,n + 1];
21
22 // Fill d[][] in bottom up manner
23 for (int i = 0; i <= m; i++)
24 {
25 for (int j = 0; j <= n; j++)
26 {
27 // If first string is empty, only option is to
28 // insert all characters of second string
29 if (i == 0)
30
31 // Min. operations = j
32 dp[i, j] = j;
33
34 // If second string is empty, only option is to
35 // remove all characters of second string
36 else if (j == 0)
37
38 // Min. operations = i
39 dp[i,j] = i;
40
41 // If last characters are same, ignore last char
42 // and recur for remaining string
43 else if (str1[i - 1] == str2[j - 1])
44 dp[i, j] = dp[i - 1, j - 1];
45
46 // If the last character is different, consider all
47 // possibilities and find the minimum
48 else
49 dp[i, j] = 1 + min(dp[i, j - 1], // Insert
50 dp[i - 1, j], // Remove
51 dp[i - 1, j - 1]); // Replace
52 }
53 }
54
55 return dp[m, n];
56 }
57
58
59 // Driver code
60 public static void Main()
61 {
62 String str1 = "sunday";
63 String str2 = "saturday";
64 Console.Write( editDistDP( str1 , str2 , str1.Length,
65 str2.Length ));
66 }
67}
68// This Code is Contributed by Sam007
برنامه محاسبه فاصله ویرایش در PHP به روش برنامهنویسی پویا
1<?php
2// A Dynamic Programming based
3// Python program for edit
4// distance problem
5function editDistDP($str1, $str2,
6 $m, $n)
7{
8// Fill d[][] in bottom up manner
9for ($i = 0; $i <= $m; $i++)
10{
11 for ($j = 0; $j <= $n; $j++)
12 {
13
14 // If first string is empty,
15 // only option is to insert
16 // all characters of second string
17 if ($i == 0)
18 $dp[$i][$j] = $j ; // Min. operations = j
19
20 // If second string is empty,
21 // only option is to remove
22 // all characters of second string
23 else if($j == 0)
24 $dp[$i][$j] = $i; // Min. operations = i
25
26 // If last characters are same,
27 // ignore last char and recur
28 // for remaining string
29 else if($str1[$i - 1] == $str2[$j - 1])
30 $dp[$i][$j] = $dp[$i - 1][$j - 1];
31
32 // If last character are different,
33 // consider all possibilities and
34 // find minimum
35 else
36 {
37 $dp[$i][$j] = 1 + min($dp[$i][$j - 1], // Insert
38 $dp[$i - 1][$j], // Remove
39 $dp[$i - 1][$j - 1]); // Replace
40 }
41 }
42}
43return $dp[$m][$n] ;
44}
45
46// Driver Code
47$str1 = "sunday";
48$str2 = "saturday";
49
50echo editDistDP($str1, $str2, strlen($str1),
51 strlen($str2));
52
53// This code is contributed
54// by Shivi_Aggarwal
55?>
خروجی قطعه کدهای بالا به صورت زیر است.
3
پیچیدگی زمانی این روش از درجه O(m x n) و فضای کمکی آن از درجه O(m x n) است. کاربردهای عملی زیادی برای الگوریتم بیان شده وجود دارد.
به عنوان مثالی در این رابطه، میتوان به نمایش همه کلمات در لغتنامهای اشاره کرد که تقریب نزدیکی به کلمه نوشته شده به صورت اشتباه دارند.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامهنویسی پایتون
- آموزش تکمیلی برنامهنویسی پایتون
- مجموعه آموزشهای دادهکاوی و یادگیری ماشین
- زبان برنامهنویسی پایتون (Python) — از صفر تا صد
- یادگیری علم داده (Data Science) با پایتون — از صفر تا صد
- آموزش پایتون (Python) — مجموعه مقالات جامع وبلاگ فرادرس
^^
سلام وقت بخیر
امکانش هست کد پایتون این بخش رو به صورت خط به خط برای من بنویسید که هر خط چیکار میکنه؟یا برای من ارسال کنید ممنونم