Edit Distance Algorithm

Programming language

Edit Distance

-:Definition    
    The minimum of operations required to convert one string into other such as:-
Deletion
Insertion
replace
Operations:-
    
                        •Deletion          Insertion            substitute

                     •Gold                 Gold                   Gold

                     • Old                 Goaled               •sold

Edit distance =    1                        2                         1

Edit Distance:- 
 •Edit distance  depends  on  the  available operations.
 The edit distance that allows……
   (Insertion,deletion,replace)
    •Operations is the levenshtien distance

    Levenshtien distance:-
Devised  in 1965by Vladimir levenshtien a Russian scientist .
Some terminology:-
 A string S   S1 , S2 ,  S3 ,………….,Sn              caterpillar  n = 11
 A substring S1…k   S1 …….. Sk,………….,Sn   caterpillar  k = 3

To find the edit distance between string S and T It’s  handy to examine their sub strings……

     Sn                                and                      Tm 
     S1….j                                                       T1….k
for all jfrom n-1 to 1                               for all kfrom n-1 to 1

Edit distance:-

E[ j , k ] = D(S1….j ,T1….k)

E[ j , 0 ] = D(S1….j , “   ”  )     =  j                            deletion

E[ 0 , k ] = D( “   ” ,T1….k)      = k                           insertion



   Computation of the edit distance:-

E[ j , 0 ] = j
Distance of any string of length jto empty string


E[ 0 , k ] = k
Distance from empty string to string of length k


 deletion                                   E[ j-1 , k ] + 1                        
 insertion                                  E[ j , k-1 ] + 1                        
 do no thing                             E[ j-1 , k-1 ]               Sj=Tk 
 substitute                                E[ j-1 , k-1 ] +1         Sj=Tk         

The table of edit distance:-
table
An algorithm for edit distance:-


this

  time complexity:-
The time complexity of above solution is exponential. 

   Time Complexity: O(m x n)

Auxiliary Space: O(m x n)
Applications:-
    Edit distance finds applications in computational biology and natural language processing, e.g. the correction of spelling mistakes or OCR errors, and approximate string matching, where the objective is to find matches for short strings in many longer texts, in situations where a small number of differences is to be expected

Matlab Code:-


Ashampoo Snap 2016.12.25 01h08m55s 003 Editor%2B %2BC  Users Gom3a Documents MATLAB EditDistance m  
Result of Run:-



Ashampoo Snap 2016.12.25 01h08m31s 002 MATLAB%2B%2B7 8 0%2B R2009a



        Thank you




مقالات ذات صلة

خوارزمية الترتيب بالإختيار selection sorting

خوارزمية الترتيب بالإختيار من الخوارزميات الأساسية التي يجب معرفتها لجميع دارسي علم الخوارزميات، و ربما ستندهش من حقيقة أنك قد...

Linear Search Algorithm خوارزمية البحث الخطي

خوارزمية البحث الخطي هي إحدى خوارزميات البحث التقليدية و الأساسية، إذ تُعتبر طريقة للبحث عن موقع قيمة معينة داخل مصفوفة، و...

مسألة برمجية : نظام جداول البيانات

فى نظام من نظم جداول البيانات مثل اكسل على سبيل المثال يتم استخدام الترقيم التالي فى الأعمدة       ...

Binary Search Algorithm خوارزمية البحث الثنائي

  كيف تعمل خوارزمية البحث الثنائي كغيرها من الخوارزميات لا بد من توافر المدخلات المطلوبة و التي تتمثل في...

كتب بواسطة عمرو العربى

مؤسس مطور

التعليقات

اترك تعليقك

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

*