Home > General > Levenshtein distance

Levenshtein distance

Imagine a scenario where a single script is deployed to several hundred different locations. Due to various constraints, this script cannot be centralized, so making a change means I’ll need to deploy it to several hundred locations.

But it gets worse. Some of these scripts are customized and include special logic, so I cannot blindly copy the updated script to all locations. In addition to that, most of the existing scripts contain comments such as:

#
# This script was created on 1/1/1970 by John Doe.
#

If these scripts didn’t include their own unique comments, I could have compared the file sizes or generated SHA1 hashes for each script to see which were identical and which contained their own special logic. Since each script contains their own unique comments, generating hashes would mean a different hash for each script.

Instead of reviewing each script individually, I can use the Levenshtein distance to determine how similar the target script is compared to my updated script.

According to Wikipedia, the Levenshtein distance is:

… a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion, substitution) required to change one word into the other.

Sorting each script by the Levenshtein distance gives me a good indication of which scripts I can safely copy over and which I need to review manually. Overwriting scripts with a Levenshtein distance close to zero gives me reasonable assurance that I won’t break anything. While it’s not a bullet proof solution, it’s better then reviewing hundreds of scripts manually.

  1. July 24, 2014 at 1:42 am

    Good post! We will be linking to this great article on our website.
    Keep up the great writing.

  2. July 24, 2014 at 7:50 am

    This is my first time pay a quick visit at here and i am in fact happy
    to read all at alone place.

  3. July 27, 2014 at 7:06 pm

    Of course, if you want to build teamwork, you will definitely want
    to practice together. So, strap on all your paintball load and gear up those paintball guns!
    If” scenarios, and more, work on defensive and offensive strategies, code words, “what-.
    Study from the opposition along with your
    very own teammates. Directly notice other paintball players to build up new and successful
    methods for long term games. Does the opposite staff talk over your group
    does? Will they seem more structured? Watching the way your adversaries work
    together can help improve your team’s functionality.
    If your team is lacking in that area, take a look at your opponents paintball gear and see.
    This may greatly outcome your game play

  4. August 7, 2014 at 12:20 pm

    you are actually a excellent webmaster. The site loading speed is incredible.
    It seems that you’re doing any distinctive trick. Moreover, The
    contents are masterwork. you’ve performed a excellent job on this subject!

  5. August 11, 2014 at 11:33 am

    Putting your children in the middle of adult decisions and conflicts hurts them more than it hurts your ex-spouse.
    s young enough to have less competition but it also has enough traffic to get you the sales you need.
    ” Make sure it’s shouted in a French accent as well.

  6. August 14, 2014 at 11:52 pm

    I do consider all the ideas you have offered for your post.
    They are really convincing and will certainly work.
    Still, the posts are very brief for novices.
    May you please extend them a little from subsequent time?
    Thank you for the post.

  7. August 15, 2014 at 2:15 am

    First off I want to say excellent blog! I had a quick question which I’d like to ask if
    you do not mind. I was curious to find out how you center yourself and clear your thoughts before writing.
    I have had difficulty clearing my mind in getting my
    thoughts out. I truly do take pleasure in writing however
    it just seems like the first 10 to 15 minutes are usually lost just trying to figure
    out how to begin. Any ideas or hints? Appreciate it!

  8. August 18, 2014 at 10:56 am

    Hi there, You hzve done an excellent job. I’ll definitely digg it annd personally
    recommend to my friends. I am confident they’ll be benefited from this website.

  9. August 18, 2014 at 6:58 pm

    I enjoy, lead to I discovered exactly what I was looking for.
    You’ve ended my four day long hunt! God Bless you man. Have a great day.
    Bye

  10. August 19, 2014 at 8:45 am

    Wow that was strange. I just wrote an really long comment but
    after I clicked submit my comment didn’t show up.
    Grrrr… well I’m not writing all that over again. Regardless,
    just wanted to say superb blog!

  11. August 21, 2014 at 5:14 am

    Its like you learn my thoughts! You appear to grasp so much about this,like youu wrote the book
    in it or something. I think that you could do with some p.c.
    to force thee message home a bit, however instead of that, this is excellent blog.
    A great read. I wjll certainly be back.

  12. August 22, 2014 at 10:33 am

    Każdy spośród nas zetknął się z faktem,
    zalecam zaznajomienie się z problemem.

  13. October 1, 2014 at 5:05 pm

    My brother suggested I may like this website.
    He was totally right. This post actually made my day.
    You cann’t consider just how so much time I had spent for this
    info! Thanks!

  14. May 17, 2015 at 1:27 am

    My partner and I absolutely love your log and find neatly all oof your post’s to be just what I’m looking for.
    Would you offer guest writers tto write content for yourself?

    I wouldn’t mind composing a post or elaborating on a lot of the subjects
    you write wjth regards to here. Again, awesome weblog!

  15. May 17, 2015 at 4:00 am

    What’s up it’s me, I am alo visiting this sitee on a regular
    basis, this web page is in fact good and thee users are truly sharing nice thoughts.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: