Geek Answers Handbook

Unable to track intuition for minimum editing distance

So, I just started reading on MED, but I am completely unable to follow it. Suppose I need to convert "WATER" to "ATERW" Now I can replace:

W->A, A->T, T->E, E->R, R->W

Thus, the total cost = 2 + 2 + 2 + 2 + 2 = 10 (all permutations)

However, this is not true, I know it should be like

WATER-
-ATERW

Thus, the total cost here = 1 + 1 = 2 (delete and insert) But then my question is, how does the program know that it should not match 'W'->'A', but rather deletes 'W'and matches 'ATER'on both lines? How is this intuition / logic embedded in the program?

0
source share
1 answer

: https://en.wikipedia.org/wiki/Levenshtein_distance

, .

, ( ). , .

:

  • , 0 ;
  • A, 1 ();
  • AT, 2 ();
  • ATE, 3 ();
  • ..
  • W , 1 ();
  • WA , 2 ();
  • WAT , 3 ();
  • ..

.

  _ A T E R W
_ 0 1 2 3 4 5
W 1 ? ? ? ? ?
A 2 ? ? ? ? ?
T 3 ? ? ? ? ?
E 4 ? ? ? ? ?
R 5 ? ? ? ? ?

, . (2,2). W (.. WATER) A (ATERW).

. . ( ) ( ) 1. ( ) 1, , 0 .

:

  • INSERTION ( 2,1): 1 ( ) + 1 ( );
  • ( 1,1): 0 ( ) + 1 ( );
  • DELETION ( 1,2): 1 ( ) + 1 ( ).

: 1 (). Cell 2,2 1.

  _ A T E R W
_ 0 1 2 3 4 5
W 1 1 ? ? ? ?
A 2 ? ? ? ? ?
T 3 ? ? ? ? ?
E 4 ? ? ? ? ?
R 5 ? ? ? ? ?

2,3. W (.. WATER) T (ATERW).

:

  • INSERTION ( 2,2): 1 ( ) + 1 ( );
  • ( 1,2): 1 ( ) + 1 ( );
  • DELETION ( 1,3): 2 ( ) + 1 ( ).

: 2 ( ). 2,3 2.

, W AT 2.

  _ A T E R W
_ 0 1 2 3 4 5
W 1 1 2 ? ? ?
A 2 ? ? ? ? ?
T 3 ? ? ? ? ?
E 4 ? ? ? ? ?
R 5 ? ? ? ? ?

, ( 2,2) (2,3). .

. :

  _ A T E R W
_ 0 1 2 3 4 5
W 1 1 2 3 4 4
A 2 1 2 3 4 5
T 3 2 1 2 3 4
E 4 3 2 1 2 3
R 5 4 3 2 1 2

(6,6): 2. "" "ATERW".

, . , .

2,2 1,1
2,3 2,2
2,4 2,3
2,5 2,4
2,6 1,5
3,2 2,1
...
6,5 5,4
6,6 6,5

, .. (6,6) → (6,5) → (5,4)...

+3

More articles:


All Articles