Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Edit distance

  • Given two strings S1 and S2, the minimum number of operations to convert one to the other

  • Operations are typically character-level

    • Insert, Delete, Replace, (Transposition)

  • E.g., the edit distance from dof to dog is 1

    • From cat to act is 2 (Just 1 with transpose.)

    • from cat to dog is 3.

  • Generally found by dynamic programming.


Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.