Levenshtein distance facts for kids

Levenshtein distance is a clever way to figure out how different two words or groups of words are from each other. Think of it like a game where you try to change one word into another using the fewest possible steps!

The idea is simple: you count how many changes you need to make to turn one word into another. Each change costs one "point."

There are three main types of changes allowed:

• Inserting a character: Adding a letter, number, or symbol. For example, changing "sit" to "sits" (you inserted an 's').
• Deleting a character: Taking away a letter, number, or symbol. For example, changing "sits" to "sit" (you deleted an 's').
• Substituting a character: Swapping one character for another. For example, changing "cat" to "bat" (you substituted 'c' for 'b').

Other changes, like moving a character around or swapping two characters, don't count as a single step in Levenshtein distance.

For example, let's find the Levenshtein distance between "kitten" and "sitting". It's 3, because you can do it in three steps:

• kitten → sitten (we changed 'k' to 's')
• sitten → sittin (we changed 'e' to 'i')
• sittin → sitting (we added 'g' at the end)

You can't do it in fewer than three steps!

How Levenshtein Distance Is Used

This special distance measurement is used in many cool ways, especially with computers!

Checking Passwords

Some websites use Levenshtein distance when you change your password. They want to make sure your new password isn't too similar to your old one. If it's too similar, it might be easier for someone to guess, which makes your account less safe.

For example, a website might say the Levenshtein distance between your old and new password must be at least 5. This means you need to make at least 5 changes (insertions, deletions, or substitutions) to your old password to create a new one that the website will accept. This helps keep your online accounts more secure!

Detecting Plagiarism

Levenshtein distance can also help figure out if one piece of writing has been copied from another. If two texts have a very small Levenshtein distance, it means they are very similar, which could suggest plagiarism (copying someone else's work without giving them credit).

Images for kids

• 

  Edit distance matrix for two words using cost of substitution as 1 and cost of deletion or insertion as 0.5

See also

In Spanish: Distancia de Levenshtein para niños