I have got my exam tomorrow and this video really helped me to understand the edit distance algorithm thoroughly. Probably one of the best explanation that one can find on TH-cam for edit distance. Thank you very much !
Crap, man, in a little over three months it will be 6 years since you shot this video, and it helped me today! Thanks a lot, Tushar, and I hope you're doing well these corona-days!
Hey, I feel you should also hover over optimal subproblems and what a state of the DP represents, For example, In this question, when not equal, you take the min of(top,left,diagonal) , where in you should explain that the top refers to inserting a[i], left refers to deleting a[i] and diagonal refers to editing a[i]. On a side note, you should have mentioned the case where the cost of edit, insert and delete are different.
@@parmoksha +1 I don't know why they complain! His videos are not meant for proof or theory or how he thought of the solution just how to solve a problem, which is what we are all trying to learn
Man, you helped me a lot. I have an exam soon. And I have to learn a lot of code which I don't understand. After watching your video, man, that code is so easy. Thanks a lot.
What kind of proof do you need? If they are the same, then do nothing, if not, add 1 more operation to whatever gets the least in previous ops. To me, the logic is pretty obvious.
azklinok Well. First of all, if two characters are same, you don't do anything, that's clear right? If not, then there's 3 possible moves: delete, replace and insert. Suppose your rows represents str1, cols represents str2. If you wanna delete, you go back to previous column, which is T[i][j-1], because you'd like to retrieve the last character in str2. Similarly, if you wanna insert, you go back to previous row, which is T[i-1][j]. For replacing current character, you need to retrieve last character in both str1 and str2, which is T[i-1][j-1]. At last, you get the minimum among the above 3 moves and plus 1 to it to get T[i][j]. I'm not sure if I articulate it in a proper way, at least that's how I understand this problem.
Tushar your explanations are extremely clear and have been immensely helpful Great job .Looking forward to more videos from you .Please keep them coming !
I salute this guy!!! Thanks so much for the video. I was cracking my head to solve this problem. your explanation helped me understand in less than 10 minutes
Awesome video. I already knew how to write out the DP table and but deriving the edit operations being done from the table was the crucial part I did not understand. This was a big help.
your clear explanation as to how each number came up for each cell is really helpful (also the shortcut). i've been having a hard time understanding the this but you removed the complexity with your explanation
I have few suggestions, 1. As many people have pointed out, I don't think I'm getting to know why this solution works before seeing the complete video. It would be helpful if Tushar goes over other approaches as well to prove that this solution works or mathematical proof shall be sufficient. 2. I think it would be better if the video explains what happens to the string(s) when we delete a character(s) and how the comparison shall be made rather than asking to the take the minimum of top, left and diagonal 3. Adding to the second point, if the characters are not same, I don't think it is just 1 + Min(cost(top), cost(dia), cost(left)). I think it shall be min(1 + cost(top), 1 + cost(left), 2 + cost(dia)). Because, when we are taking from the diagonal we are removing one element from str1 and one from str2. Assuming cost of removal is 1, it shall be 2 + cost(diag) rather than 1 + cost(dia) I welcome any suggestions for correction.
Nope, it's talking about changing one string into the other, so you're either operating on str1 or str2. If you want to go down that route, then by the way string is stored by computer memory, insertion or deletion should cost much more than changing. This is just the definition of edit distance. Of course, if you want to go to variants where there are different costs, your point is correct. As for the explaining part many people are asking about, he has a lot of videos on dynamic programming itself, it's basically all the same logic, and would be rather redundant for viewers otherwise. You can check out other videos explaining DP to get a better understanding, but here is a cut short version Dynamic Programming works because when looking for answers for a question with length of n, we can look at it as an answer for question of length n - 1 ( or some other lesser length, generally something that can be achieved from an atomic operation ), plus some trivial atomic operations. So in the case of edit distance, what is an atomic operation on string edits. We have insertion, removal, or changing. And if you create a table like the one in the video, the three separate n-1 length question corresponds to the three cells to the left, diagonal, and top. The minimum of the three is choosing the best way to starting point from the previous three states, and + 1 is the cost to go from that state to the current state.
Use f[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]): if c == d, then : f[i][j] = f[i-1][j-1] Otherwise we can use three operations to convert word1 to word2: (a) if we replaced c with d: f[i][j] = f[i-1][j-1] + 1; (b) if we added d after c: f[i][j] = f[i][j-1] + 1; (c) if we deleted c: f[i][j] = f[i-1][j] + 1; Note that f[i][j] only depends on f[i-1][j-1], f[i-1][j] and f[i][j-1], therefore we can reduce the space to O(n) by using only the (i-1)th array and previous updated element(f[i][j-1]).
one thing he did not mention how we detect addition. so when computing all kind operations, if you move up the cell (e.g from (2,1) to (1,1) that means we need to add that particular row character in the conversion.
Great series of videos to prepare of interviews... already subscribed to your channel... One suggestion though... instead of directly jumping to the matrix right from start... it would be awesome if you could explain the solution for a min or 30 seconds, in terms of what you will be doing before jumping to solving of the table. Although you kind of mention the formula in the end, but it would be better if it is verbally explained at the beginning and then mathematically written at the end. That would help people in understanding that how DP can solve this problem in the first place.
i have been looking for tree edit distance theory, and this is the best explanation ever. i just watch at once, i really understand. thanks for sharing education. I'm subscribing U right now..
please understand where the formula came from Use f[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]): if c == d, then : f[i][j] = f[i-1][j-1] Otherwise we can use three operations to convert word1 to word2: (a) if we replaced c with d: f[i][j] = f[i-1][j-1] + 1; (b) if we added d after c: f[i][j] = f[i][j-1] + 1; (c) if we deleted c: f[i][j] = f[i-1][j] + 1; Note that f[i][j] only depends on f[i-1][j-1], f[i-1][j] and f[i][j-1], therefore we can reduce the space to O(n) by using only the (i-1)th array and previous updated element(f[i][j-1]).
+Tushar Roy In source code, I believe assuming string2 is modified according to string 1... if T[i][j] == T[ i-1 ][ j ] + 1 "Delete in String 1" ... Should be changed to Insert in string 1. We are not supposed to delete in both string1 and string 2
So with your algorithm the edit distance of 'b' and 'ababab' is 3. But its 5. Please correct at 3:26 - 3:30. It's NOT minimum of the three+0/1 , it's "min{ left+1, up+1, leftUp+0/1(depending on the match)}". Rest is cool.
No body could explain me better than this, thank you and thank you, however although you explained why when we have two equals we should go diagonal you didn't explain why in inequality we get three minimums and plus it to 1,I played with giving an example for myself and I understood that part! When they are Not equal: First we suppose that last char is not there and we go for previous chars we need to see what permutations takes the least operations to have the conversion, after that we need 1 operation to add the one we supposed to get rid of it in the beginning so that is why we have minimum plus 1 here Thank you very much,you help has been greatly appreciated.
'Why' part is missing here. Statement: We have three operations 1. Insert, 2. Remove, 3. Replace to convert string1 to string2. If not specified, all three operations will have same cost. Naturally, there will be there operations to convert string1 to string2.(give a thought about it.).e.g s1(i)=pupy, s2(j)=pupxyz=> if we insert x in s1, then we need to take care of s1(i) and s2(j-1) which implies d[i][j-1]. Similar to this case, you can take up other two cases. Since, all these three operations take same cost, then why are we trying to find minimum of them? The reason is one of them may be faster(minimum no. of steps) than others to convert string1 to string 2 completely. Also optimal substructure and overlapping subproblem scenario missing.
This logic might fail when repetition of characters occurs as originally we would want to delete the repeated character(and hence increase number of operation by 1) but by this logic we will not count that operation . Eg: String 1: aaaa & String 2: a Ideally, output must be 3 (deleting 3 characters) but we will get 0 according to your logic.
Yes, you are right. Minimum should not be chosen in case of a match. The diagonal element must be chosen. If you have a match at i , j then i - 1, j - 1 should be chosen
Thank you for the explaination. My prof just went straight from the matrix with all the values filled in and didn't explain what they were, and only listed all the formulas without explicitly going through each of them, I found it very confusing :P
If we use this algorithm on 'b' and 'aab'. The table making path and backtracking path is different. Table making path is the path you get from the min([i-1, j-1], [i, j-1], [i-1, j]). That is magical.
Hi Tushar, Great Job Man, one small suggestion-> it would be great maybe if you tell about the practical application of the programs we can actually do some real time implementation of it and i think it add more value to it :). Kudos Happy coding!!!
Legend! I couldn't figure it out after an hour of looking at my lectures but within 3 minutes of you explaining it just clicked! Thank you!
I have got my exam tomorrow and this video really helped me to understand the edit distance algorithm thoroughly. Probably one of the best explanation that one can find on TH-cam for edit distance. Thank you very much !
mine is tmrw.. 8 years same vibe
@@vaibhavmourya65 2024 same vibe tomorrow exam
@@nihadbkirli347
I am graduate now 2024 batch
I spent hours and couldn't figure it out. You explained the concept so nicely in just 9 minutes.
Crap, man, in a little over three months it will be 6 years since you shot this video, and it helped me today! Thanks a lot, Tushar, and I hope you're doing well these corona-days!
Hey, I feel you should also hover over optimal subproblems and what a state of the DP represents, For example, In this question, when not equal, you take the min of(top,left,diagonal) , where in you should explain that the top refers to inserting a[i], left refers to deleting a[i] and diagonal refers to editing a[i].
On a side note, you should have mentioned the case where the cost of edit, insert and delete are different.
Thank you
@@sankethb.k642 worst lecture
7:00 - Diagonal ( EDIT)
7:25 - Left ( DELETE )
Top -> Insert (Implied)
yes but this is how indians study
can you guys recommend me a more detailed lectures?
@@parmoksha +1 I don't know why they complain! His videos are not meant for proof or theory or how he thought of the solution
just how to solve a problem, which is what we are all trying to learn
I got the idea of the algorithm quickly. It's a nice and clear implementation with good explanation. Thanks for the effort to pass on the knowledge.
I have been spamming your videos before the olympiad in informatics and they are quite literally my lifeline. Thanks so much for these videos!
Man, you helped me a lot. I have an exam soon. And I have to learn a lot of code which I don't understand. After watching your video, man, that code is so easy. Thanks a lot.
You learn code!!??? Wtf
You didn't say why this works. It is very important!
He actually did, even in detail- you´d better watch the clip again..
He did not. He told us the method, not its proof.
What kind of proof do you need? If they are the same, then do nothing, if not, add 1 more operation to whatever gets the least in previous ops. To me, the logic is pretty obvious.
The logic is obvious to all of us. I want to know WHY the logic works, and gets us the right answer.
azklinok Well. First of all, if two characters are same, you don't do anything, that's clear right? If not, then there's 3 possible moves: delete, replace and insert.
Suppose your rows represents str1, cols represents str2. If you wanna delete, you go back to previous column, which is T[i][j-1], because you'd like to retrieve the last character in str2. Similarly, if you wanna insert, you go back to previous row, which is T[i-1][j]. For replacing current character, you need to retrieve last character in both str1 and str2, which is T[i-1][j-1]. At last, you get the minimum among the above 3 moves and plus 1 to it to get T[i][j].
I'm not sure if I articulate it in a proper way, at least that's how I understand this problem.
Man! Respect! Awesome Job! ..i spent hours together breaking my head on this before seeing this video!
Lucid Explanation!
Tushar your explanations are extremely clear and have been immensely helpful Great job .Looking forward to more videos from you .Please keep them coming !
Thank you, I had been looking at some dp question for days. Your explanation and graph really became a breakthrough.
I didn't understand this until I watched your video. Thanks a lot!
Simple and straightforward. I looked at 3 different videos before this. This is a really good explanation.
I salute this guy!!! Thanks so much for the video. I was cracking my head to solve this problem. your explanation helped me understand in less than 10 minutes
Hey Amith, I understood the approach. Could you help me explain why this method works?
I've been slamming my head against this problem for days. Cheers! You made it very understandable and easy to grasp.
Awesome video. I already knew how to write out the DP table and but deriving the edit operations being done from the table was the crucial part I did not understand. This was a big help.
Bro really drew the 2d array even before starting the video.
Thank you so much. I have computer algorithm exam tomorrow and this video really helps me. You're the man.
Tushar, your explanation of how to populate the table, and then how to work it backwards to identify operations was awesome. Thank you.
Until this video I could not wrap my head around it. So thank you very much. Straight to the point.
Thank God, you did before I am learning DP. Intuition building is hard and there is a way. My instructors don't know it. You know it and you show it.
I think this is one of the best explanations out there for this problem. Thanks much. Your implementation is very simple too. love it.
+Abhi Tk Absolutely, very easy to understand. Keep going.
the best video i have found on this topic so far, you explain it better than in a paid coursera course
Thank you very much, this is my AHA MOMENT. This is what I'm looking for all this time.
Evergreen video even u can watch this video 10 year later and understand the dp.
You explain it a lot better than some of the newer videos.
Short and crisp explanation.. Thank u so much... Finally i got to understand this
I can say that, you have the best Dynamic Programming TH-cam tutorial in the market ❤️❤️❤️
Wow very nice man! I will definitely go through all your videos to brush up my algorithms!
DP was my nightmare , always used give up , after watching your videos, its like DP marathon at weekend. thanks a lot
How is it going on now
This is really cool! 9 years since posting and it helped. Nice work!
your clear explanation as to how each number came up for each cell is really helpful (also the shortcut). i've been having a hard time understanding the this but you removed the complexity with your explanation
Without you video, I will definitely fuck up on leetcode. Thx a lot! Please keep doing this!
I have few suggestions,
1. As many people have pointed out, I don't think I'm getting to know why this solution works before seeing the complete video. It would be helpful if Tushar goes over other approaches as well to prove that this solution works or mathematical proof shall be sufficient.
2. I think it would be better if the video explains what happens to the string(s) when we delete a character(s) and how the comparison shall be made rather than asking to the take the minimum of top, left and diagonal
3. Adding to the second point, if the characters are not same, I don't think it is just 1 + Min(cost(top), cost(dia), cost(left)). I think it shall be min(1 + cost(top), 1 + cost(left), 2 + cost(dia)). Because, when we are taking from the diagonal we are removing one element from str1 and one from str2. Assuming cost of removal is 1, it shall be 2 + cost(diag) rather than 1 + cost(dia)
I welcome any suggestions for correction.
Nope, it's talking about changing one string into the other, so you're either operating on str1 or str2. If you want to go down that route, then by the way string is stored by computer memory, insertion or deletion should cost much more than changing. This is just the definition of edit distance. Of course, if you want to go to variants where there are different costs, your point is correct.
As for the explaining part many people are asking about, he has a lot of videos on dynamic programming itself, it's basically all the same logic, and would be rather redundant for viewers otherwise. You can check out other videos explaining DP to get a better understanding, but here is a cut short version
Dynamic Programming works because when looking for answers for a question with length of n, we can look at it as an answer for question of length n - 1 ( or some other lesser length, generally something that can be achieved from an atomic operation ), plus some trivial atomic operations.
So in the case of edit distance, what is an atomic operation on string edits. We have insertion, removal, or changing. And if you create a table like the one in the video, the three separate n-1 length question corresponds to the three cells to the left, diagonal, and top. The minimum of the three is choosing the best way to starting point from the previous three states, and + 1 is the cost to go from that state to the current state.
Use f[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]):
if c == d, then : f[i][j] = f[i-1][j-1]
Otherwise we can use three operations to convert word1 to word2:
(a) if we replaced c with d: f[i][j] = f[i-1][j-1] + 1;
(b) if we added d after c: f[i][j] = f[i][j-1] + 1;
(c) if we deleted c: f[i][j] = f[i-1][j] + 1;
Note that f[i][j] only depends on f[i-1][j-1], f[i-1][j] and f[i][j-1], therefore we can reduce the space to O(n) by using only the (i-1)th array and previous updated element(f[i][j-1]).
How the hell people think so out of the box to solve problem, I can never imagine this problem can be solved this way... really burst up 🤯
Great explanation! So so much easier this way to understand this way
one thing he did not mention how we detect addition. so when computing all kind operations, if you move up the cell (e.g from (2,1) to (1,1) that means we need to add that particular row character in the conversion.
Got stuck on this problem in an NLP textbook and this really helped tysm :)
Bravo! one of the best teachers in this field! thank you
Great series of videos to prepare of interviews... already subscribed to your channel...
One suggestion though...
instead of directly jumping to the matrix right from start...
it would be awesome if you could explain the solution for a min or 30 seconds, in terms of what you will be doing before jumping to solving of the table.
Although you kind of mention the formula in the end, but it would be better if it is verbally explained at the beginning and then mathematically written at the end. That would help people in understanding that how DP can solve this problem in the first place.
THIS WAS A HUGE HELP. Thank you for posting this.
excellent thanks ! More useful than 3 hours of lectures at school
In MIT DP 3 video, Eric explains the logic behind the "min(the three cells)" beautifully.
In short its the representation of insert, delete, replace.
Your videos on dynamic programming are extremely helpful....!!! Great Job Tushar.....!!!!
i have been looking for tree edit distance theory, and this is the best explanation ever. i just watch at once, i really understand. thanks for sharing education. I'm subscribing U right now..
old video Tushar Roy but really helpful. I appreciate your help. Made this pretty straight forward.
Excellent explanation, great clarity. I've seen a video from CS50 on the subject that was a mess. This is great.
Thank you!! This is the second time already a video of you made a problem 'click' for me :D, it all makes so much sense now!
thing is that you teach better than my professor . thank you bro
This is the best explanation I have found sofar. Thanks so much Tushar! Keep up the good work.
please understand where the formula came from
Use f[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]):
if c == d, then : f[i][j] = f[i-1][j-1]
Otherwise we can use three operations to convert word1 to word2:
(a) if we replaced c with d: f[i][j] = f[i-1][j-1] + 1;
(b) if we added d after c: f[i][j] = f[i][j-1] + 1;
(c) if we deleted c: f[i][j] = f[i-1][j] + 1;
Note that f[i][j] only depends on f[i-1][j-1], f[i-1][j] and f[i][j-1], therefore we can reduce the space to O(n) by using only the (i-1)th array and previous updated element(f[i][j-1]).
you're better than my teacher greetings from Quebec
Just awesome video. Was searching short video which i can learn this algorithm.
thank you so much for this video!! i have a test on this in a few hours and this explanation was really helpful :)
+Tushar Roy In source code, I believe assuming string2 is modified according to string 1... if T[i][j] == T[ i-1 ][ j ] + 1 "Delete in String 1" ... Should be changed to Insert in string 1. We are not supposed to delete in both string1 and string 2
I completed this question on leetcode online judge, after watching this video I had a deeper understanding of Dynamic programming
Thanks for the upload! The intuition behind taking the Min of three cells would be helpful.
You are doing a really good job. Keep up man.
This guy really casuallly out here just helping peopel
Best explanation on the internet! Thanks for the video
Thanks sir, cleared all my doubts in a short time.
thanx thanx thanx bro....Dynamic programming is sick to understand but this logic helps me a lot....Thnaks bhaai
So with your algorithm the edit distance of 'b' and 'ababab' is 3. But its 5.
Please correct at 3:26 - 3:30. It's NOT minimum of the three+0/1 ,
it's "min{ left+1, up+1, leftUp+0/1(depending on the match)}".
Rest is cool.
I have NLP exams tomorrow. Thank you very much for this!
this is the best explanations. Thanks much. Your implementation is very simple too. I really helped for my exam.
respect !! i pass the exam because of you
I owe you so much
Perfectly presented. You had explained this within 10 minutes
Thank you very much...
best explanation i have seen so far..
Thank you, that was perfect. Explained better than my lecturer
No body could explain me better than this, thank you and thank you, however although you explained why when we have two equals we should go diagonal you didn't explain why in inequality we get three minimums and plus it to 1,I played with giving an example for myself and I understood that part!
When they are Not equal:
First we suppose that last char is not there and we go for previous chars
we need to see what permutations takes the least operations to have the conversion, after that we need 1 operation to add the one we supposed to get rid of it in the beginning so that is why we have minimum plus 1 here
Thank you very much,you help has been greatly appreciated.
'Why' part is missing here. Statement: We have three operations 1. Insert, 2. Remove, 3. Replace to convert string1 to string2. If not specified, all three operations will have same cost. Naturally, there will be there operations to convert string1 to string2.(give a thought about it.).e.g s1(i)=pupy, s2(j)=pupxyz=> if we insert x in s1, then we need to take care of s1(i) and s2(j-1) which implies d[i][j-1]. Similar to this case, you can take up other two cases. Since, all these three operations take same cost, then why are we trying to find minimum of them? The reason is one of them may be faster(minimum no. of steps) than others to convert string1 to string 2 completely. Also optimal substructure and overlapping subproblem scenario missing.
shout out to you man. really empowering content.
Bro, you've done a wonderful job here. Thanks!!!
This logic might fail when repetition of characters occurs as originally we would want to delete the repeated character(and hence increase number of operation by 1) but by this logic we will not count that operation .
Eg: String 1: aaaa & String 2: a
Ideally, output must be 3 (deleting 3 characters) but we will get 0 according to your logic.
Yes, you are right. Minimum should not be chosen in case of a match. The diagonal element must be chosen. If you have a match at i , j then i - 1, j - 1 should be chosen
Thank you my friend! Very clear explanation of the algorithm
Thanks a lot Tushar. One of the best explanations I came across. :)
Thank you for the explaination. My prof just went straight from the matrix with all the values filled in and didn't explain what they were, and only listed all the formulas without explicitly going through each of them, I found it very confusing :P
Tushar! Awesome! Great job!
If we use this algorithm on 'b' and 'aab'. The table making path and backtracking path is different.
Table making path is the path you get from the min([i-1, j-1], [i, j-1], [i-1, j]). That is magical.
i'm so powerful right now, no one gonna stop me
😂
Great explanation, easy to understand, really helped me to clearly understand DP
Your explanation is really clear.
Thank you very much
Thanks for a clear and concise explanation!
Thank YOU for explaining this in detail.
Hi Tushar, Great Job Man, one small suggestion-> it would be great maybe if you tell about the practical application of the programs we can actually do some real time implementation of it and i think it add more value to it :). Kudos Happy coding!!!
Thanks a lot, that's so easy when you explained it :)
Very good short video .
Good job.
Love from Pakistan. So simple. So concise. So comprehensive.
Good and clear explanation. Easy to understand!!!
Nice problem, Nice solution, and of course excellent explanation. +1 tushar
Thank you for uploading this video. It's extremely helpful!
Helpful video! Totally understand after watching your videos :)
absolutely better explanation than wikipedia!!!........thank you man!
Thanks, Tushar. Very clear explanation.
Awesome video! Thanks for posting, this has helped me a lot!
Holy Shit, Who is the guy who made this algorithm! Awesome explanation!
Wonderful explanation. Please also mention at the end the time complexity and maybe you should mention this is "Levenshtein distance"
This helped me out so much! Thank you!
6:20 If the letters are same you allways take the diagonal number ot the minimum of the 3 numbers (top diagonal left)?
Thank you for your videos, helped me understand it properly.