Posted on by Yucxxxxxx

Edit Distance

The edit distance algorithm is very popular among the data scientists. It's one of the basic algorithms used for evaluation of machine translation and speech recognition.

The naive approach would be to check for all possible edit sequences and choose the shortest one in-between. That would result in an exponential complexity and it's an overkill since we actually don't need to have all possible edit sequences but just the shortest one.

Here is an example for this approach in LeetCode.

Use D[i][j] refer to the edit distance for word 1 and word 2. D[i][j] = edit distance between word 1[1...i] word 2[1...j].

It turns out that one could compute D[i][j], knowing D[i - 1][j], D[i][j - 1] and D[i - 1][j - 1].

If the last character is the same, i.e. word1[i] = word2[j] then

D[i][j] = 1 + min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1] - 1)

and if not, i.e. word1[i] != word2[j] we have to take into account the replacement of the last character during the conversion.

D[i][j] = 1 + min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1])

The above assumption means:

1.When the last character is the same:
  • [i-1][j] -> [i][j]: edit distance of change i-1 of word 1 to j of word 2, plus one more distance of deleteing the i of word 1.
  • [i][j-1] -> [i][j]: edit distance of change i of word 1 to j-1 of word 2, plus one more distace of adding the j of word 2.
  • [i-1][j-1] - 1 -> [i][j]: edit distance of change i-1 of word 1 to j-1 of word 2, no need more distance of minus one first and plus one then
2.When the last character is not the same:
  • [i-1][j] -> [i][j]: edit distance of change i-1 of word 1 to j of word 2, plus one more distance of deleteing the i of word 1.
  • [i][j-1] -> [i][j]: edit distance of change i of word 1 to j-1 of word 2, plus one more distace of adding the j of word 2.
  • [i-1][j-1] -> [i][j]: edit distance of change i-1 of word 1 to j-1 of word 2, plus one more distance of replacing the i of word 1 with j of the word 2

The code is below:

class Solution {
    public int minDistance(String word1, String word2) {

        // got length of word 1 and word 2
        int len1 = word1.length();
        int len2 = word2.length();

        // if one of word is empty, need to change all of another
        if( len1 * len2 == 0 )
            return len1 + len2;

        // build the dp array 
        int [][]edit = new int[len1+1][len2+1];

        // build the basic case for change word 1 to empty
        for( int i = 0; i <= len1; i++ )
            edit[i][0] = i;

        // build the basic case for change empty to word 2
        for( int j = 0; j <= len2; j++ )
            edit[0][j] = j;

        // calculate 
        for( int i = 1; i <= len1; i++ ){ // from 1 bc it means the actually length
            for( int j = 1; j <= len2; j++ ){

                if( word1.charAt(i-1) == word2.charAt(j-1) ){
                    edit[i][j] = edit[i-1][j-1]; // no need to change 
                }
                else{
                    edit[i][j] = 1 + Math.min( edit[i-1][j-1], Math.min( edit[i-1][j], edit[i][j-1] ));
                }

            }
        }

        return edit[len1][len2];
    }
}

46 Replies to “Edit Distance”

  9. I really love your website.. Pleasant colors & theme. Did you build this website yourself? Please reply back as I’m trying to create my own personal blog and would love to know where you got this from or just what the theme is called. Many thanks!

    Reply

  10. These bags are manufactured with a product that stops the heat from getting inside. An identical condition applies in cold weather. Because the bag is so small, you can make it around anywhere you want.

    Reply

  13. A person necessarily help to make severely articles I might state. That is the first time I frequented your web page and thus far? I surprised with the research you made to make this particular publish extraordinary. Great activity!

    Reply

  15. whoah this blog is fantastic i love reading your posts. Keep up the good work! You know, many people are hunting around for this info, you can aid them greatly.

    Reply

  18. Very good blog! Do you have any tips for aspiring writers? I’m planning to start my own blog soon but I’m a little lost on everything. Would you suggest starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m completely confused .. Any suggestions? Thanks!

    Reply

  21. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point. You clearly know what youre talking about, why throw away your intelligence on just posting videos to your blog when you could be giving us something enlightening to read?

    Reply

  24. Hey just wanted to give you a quick heads up. The text in your content seem to be running off the screen in Opera. I’m not sure if this is a format issue or something to do with browser compatibility but I figured I’d post to let you know. The design look great though! Hope you get the issue resolved soon. Kudos

    Reply

  30. Youre so cool! I dont suppose Ive read anything like this before. So nice to find somebody with some original thoughts on this subject. realy i appreciate you for beginning this up. this amazing site is something that is required on-line, somebody with a bit of originality. valuable problem for bringing something new to the net!

    Reply

  34. I’m impressed, I must say. Seldom do I come across a blog that’s both educative and entertaining, and without a doubt, you have hit the nail on the head. The problem is something not enough folks are speaking intelligently about. Now i’m very happy I came across this during my search for something concerning this.

    Reply

  36. Nice post. I learn something more challenging on diverse blogs everyday. It will always be stimulating to study content off their writers and rehearse a little something from their store. I’d want to apply certain using the content on my own weblog regardless of whether you do not mind. Natually I’ll provide you with a link on the web weblog. Thanks for sharing.

    Reply

  39. A large range of information on Technology is to be discovered by surfing on the web, as well as making use of the internet search engine. Taking your first actions – this is what the understanding we have offered is fixated. What you need to do now is take your first steps, understand that you won’t accomplish every little thing overnight, yet that you are using the actions needed to obtain where you intend to go. It’s all about documenting your objectives, advising on your own daily of what you wish to achieve, as well as getting there by means of persistency as well as willpower. Lots of guidelines as well as methods can be acquired at Our Technology Site, specifically in regard to aiding you to achieve your goals. Any person that mosts likely to this internet site can easily discover something from it, as well as despite the big quantity of info, it will certainly assist you in the long run.

    Reply

  43. I am extremely impressed with your writing skills and also with the layout on your blog. Is this a paid theme or did you customize it yourself? Anyway keep up the excellent quality writing, it’s rare to see a great blog like this one nowadays..

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *