Levenshtein Distance

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Levenshtein Distance is a way to calculate how different two words are from one another.

The simple way this works is by counting how many times you need to change one word to turn it into another word.

For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:

  1. kitten → sitten (substitution of 's' for 'k')
  2. sitten → sittin (substitution of 'i' for 'e')
  3. sittin → sitting (insertion of 'g' at the end).

This can be used by various websites when you change your password to make sure you're not using a similar password that can decrease the security of the website. The given minimum distance between two passwords is recommended to be 5, so that means that 5 changes need to take place between your old password and your new password for certain websites to accept your new password.