Indeterminate String Matching | DataHour by Munmun Das

Key Takeaways

okay so today's topic is indeterminate string matching algorithms and as Priyanka already suggested some of the you know like applications like where we can apply this it is a very like you know like useful tool in our NLP so national language processing and also we can do several other things like document matching detection of plagiarism uh then bioinformatics pattern matching pattern recognition Etc so our agenda today is I will be covering uh some of these algorithms which we widely use in in determinate string matching so first one is Robin curb algorithm 11 strain distance algorithm buyer more algorithm and KMP algorithm so these are some of the algorithms uh with the interest of time I would like to cover all of them but uh don't know like if in one hour I couldn't cover maybe I will continue in the next session so let me give brief introduction about myself so already Priyanka has told some of the points about me I have around 16 years of experience and I have also started my career as a developer and then I have worked in plethora of Technologies uh starting from.net and then uh Ruby on Rails python Java uh for the last Almost a decade I have worked in AIML and data science and RPA projects and mostly leading the delivery of those projects so I was leading actually the digital transformation as a part of Industry 4.0 along with that I was also mentoring as an industry speaker and a guest lecturer currently I am doing a research work in blockchain sustainable smart cities uh even I have you know like released my own book in Amazon recently so it is regarding Innovation and automation with VBA so some of the tips and tricks I have included in my book all so uh I like to I I am married I have two children I like to Trek and do off-road biking and one of my biggest accomplishment is that I have gone Solo in bike to ladakh so that was the biggest accomplishment I have so let's dive into this topic I will continue with an Excel file I won't go further with this PPT okay so let's understand this algorithms then we will see like how the coding and the syntax are not so coding and syntaxes like in any programming language you will if you search in the Google you will get about like like any coding or any you know like these functions and class and functions you will get like uh which is you know like built on these algorithms but understanding this algorithm is important because uh then you can build your own code uh around this algorithm if you understand the basic concept so let's understand the first one that is Robin called algorithm so um here we match the string so let's say like we have taken a string already like this is my string so this is my uh uh this is my best string with which I will be matching this pattern uh BCE so this is my pattern so this is a BC so if you see uh like either in the string you can see the mesh it is existing here BCE right uh but if we do like if we put the algorithm in place and if we try to do the matching then how we can do okay so if we just see the length of this string the first string is 13 and with they take the length as m equal to 13 and the length of the second string that is a pattern which we are trying to match that is n equal to three so let's take a like a basic example so here what we will do we will put some weightage into each character okay so till each character we will put some weightage it can be the ASCII code like ASCII code of a is 97 likewise you can get the ASCII code from Google and you can put the SD code you can multiply those ASCII codes for all the characters otherwise you can just for the simple uh understanding you can just put your way of coding so I have just taken like one two three four and I have assigned to a as 1B as 2C S3 DS4 likewise I have taken till z d as 26 so we have 26 characters in alphabets so we have taken till 26. uh so let's see uh like if I now assign some values to this BCE string so this is my pattern string now I want to assign the value so what will be my value to this Frame so my B is 2 C is 3 and E is 5 so it gives me the total of 10. right now if I try to you know like match this of entire value with the best ring uh and I will see that whether I am getting this um value as 10 right so let's start so now I am at the index 0 so this is my zero index so my first three uh length is AAA right so a is one one one so one plus one plus one three now you can put your algorithm as anywhere like you can put your value as multiplication also like you can use a multiplication operator like I have used a plus operator like I have used as b as I have taken as 2 and then I have taken uh c as 3 and then I have taken uh say ES file you can multiply it also so it is depending on how you take the value right it is not there is no hard and fast rule on it you can use your own hashing system on this to put the values okay so I have used a addition operator so here I am I am getting value of 10. now in my first three strings first three characters if you see the value is coming as three so it is not a match so again I will go to the next index so now I will move my base e to this uh index as one so here I will move I will again try to match with this so he now might uh match is like my value is probably of the best ring is that one plus one plus three so which comes as 5 5 is not again equal to 10 so I will move this to the next location next position so this is by position Now new position uh now my new value is if you see a is 1 C is 3 and a is again 1 so again it is 5 and but still it is not coming to ten so I will again move it to the my new to the new position to the next position basically so I will move it now like this I will compare the value and I will keep on moving it to the next position right so at the at the time when it will happen that I will be in the correct position so here I will be here and that time my value will be matching 10 and 10 so then I will smash the strings also it is not like that the value is matching the characters will also match so when the value is matching it is an indication that now I can match my characters so now I will match the characters okay so B is equal to B okay that is fine then the next character C is equal to C that is also fine e is equal to e okay that is a match so we got the match and what is the position so the position is if we put it as 0 and we start from the zero index so the position is the tenth position so we get the match at the tenth position so this is how these algorithm Works uh now let's say take a very bad example so this is a very good case so it is a happy example like where we are getting the like the exact match kind of now let's see uh take a bad example okay so this is my string now so this is my string and the uh total length of the string is 11 this is a pattern DBA and the total length of the pattern is three so this is fine okay now let's put some value into it so if I put some put the value in the same way as I have put in my previous case so right now I can I have four and for B I have two and for a I have one so four plus two plus one so that is seven so this is my uh pattern value right now if I see match with the first index putting it in the first position okay so now my C's value is 3 so 3 plus 3 6 plus 1 7 so it is 7 right but the string is not matching so though I am getting a value of 7 but if I go and match the strings like my D is not matching with C my B is not matching with C so it is an entire mismatch so it is not a match so again I will put this in this next position so I will just cut it and I will put it in the next position fine now what is my C's value then again 3 3 plus 3 6 6 plus 1 again 7 so again uh it should be a match but it is not magic right so again I am putting it in the next position so likewise I am keeping on just you know like putting and matching with my values though the value is matching but the strings are not matching so these kind of scenarios where you know like uh the values are matching but actually your pattern is not matching this is called the spurious Heats so your best hits basically so your heat serviced like you were you were guessing with the values but actually the string is not matching so this can actually waste your time it can have the time complexity as well as a space complexity So to avoid this kind of problem so this is the best hits so up to avoid this kind of problem we can put some algorithm in place and we can hash this value instead of you know like putting the plane this uh additional multiplication the operator we can actually wait these characters okay so how to wear these characters so the rule is thumbnail is this is a formula so if you understand this uh that is the first character okay so the first character is D now you take any value this 10 can be any value so I am taking till 10 like till J so I am taking 10 it can be 26 also it can be any other value you want to put that also you can put okay so this stain I am putting so I am assuming that I am taking till 10 characters so I am taking 10 so this is my value here now this aim is nothing but the length of your first string okay and a minus 1. so if you see this pattern only okay so if you see this pattern so in this pattern your length is three right so your first Formula will be your first Formula is these value is 4 okay then you are taking this base value that is 10 so I am assuming it is 10 you can take any value for your algorithm and it will be then n minus 1 that is a 10 to the power square right 10 to the power 2 so these value into 10 to the power score 2 then the second value is B these value is 2 then B is value into 10 to the power 1 that is M minus 2 okay so n is the length of the string so this time it is the minus the second value the second character okay so that's why we are putting 10 to the power 1 and then the last one that is a so A's value is 1 1 into 10 to the power 0 that is n minus 3 so it is the third character so in a minus 3 so m is the length of the string so n minus 3. so this is how the formula is have like taking place like you can put the formula like this now now when we will matching this pattern with this string now getting this exact match is uh you know like the chances are less that you get this curious hits or the vested Heats uh the chances will be less because you won't get this exact value because we you have already hashed this you know like the pattern so this is the way of hashing the pattern you can use another any other you know like valuation like you can use this any other base value or you can use some other formulas also but like formulas means you can take the modulus and you can divide it by two so any other thing you can use but the same thing you have to use with the base string also so now let's start this process so if I take this process in my initial positions that is the zeroth position so I will be taking this string so now my value is for 21 for this ring and the like with the valuation I have taken for this string uh so if I am going with this so if you take C's value so C is 3 so 3 into 10 to the power 2 so let me just calculate it then again C then 3 will 3 into 10 to the power 1 this time and plus 1 so a is value is 1 into 10 to the power 0 so that is 1 so we will be coming 331 so 331 is matching with 421 no it is not matching so if it is not matching then we I won't go and you know like match the string so I will just put my string to the next position so this is the algorithm which stays like this so I will be just copying this uh cutting this and I will be testing it here so I am putting it in my second position okay so now again I will calculate this hash the same hash which I have applied to the pattern the same hash I will apply to the best ring also and I will just continuously check the values like this okay so once this value is matched we will get the index of this pattern so this is how this algorithm works so am I going very fast your Priyanka you can suggest me if I need to slow down on this I think other places okay uh like moderate it as good okay so this is how like we can calculate you know like for the second position and if the second position is also not matching so if you see the same characters we have now now CAC so if you see uh if you see like now we have to do some you know like some uh mathematical calculations so first what we have taken we have taken 10 to the power 2 so this actually this part is going fully subtracting from this this part is fully subtracting and with this part we are multiplying again 10 and plus the unit part right so that we are calculating so if you again calculate this value so it will be coming as three into 10 to the power uh 10 to the power 2 Plus again it is a so a is value is 1 1 into 10 Plus 3 so this time 3 into 10 to the power 0 means one so I am putting it as only 3. so this is my three one three so three one three is again not matching with 421 so there is no you know like spurious heat so I am just rolling these hash functions which is also called rolling hash so I am just going and checking with this all these positions the value and when I will get the exact match I will just put uh like check my characters whether my character is matching also with the same position so this is how I need to do this like this is a you know like thumb rule for this algorithm okay now moving on next algorithm is slavingston distance so I have some code also python code but uh you know like python code or any other code like any LED this function you will get in many you know like many programming languages in C sharp also so you will get it easily in Google so I have also Googled it and get the code so it will be good that if you understand this algorithm and write the code so that is actually more you know like fruitful for understanding this algorithm for you okay so I will move on to the next algorithm okay so this one is actually very interesting and this is this gives you actually a confidence match so if you have two strings you can understand that how much uh like how much percentage match it is so running this function or algorithm you can understand that whether it's a 80 match or 85 percent match and you understand that by calculating just the number of edits so you have to calculate the minimum edit distance so what does it mean so if you see this formula I think you won't be understanding anything but if I just you know like and explain this uh entirely like this example you will be understanding so let's see the first thing the first we have taken a best ring so this is my best ring that is a b c d g and this is a pattern so a by CG this is my pattern right now if I want to match my base string to the pattern what I need to do so a is matching with a I don't have to do anything B I have to convert to Y so one edit so B to Y one edit right C is again matching with C I don't have to do anything D I have to delete if I delete D that is one delete then G is again matching so only two edits are there if I can convert B to Y that is one edit and if I can delete D that is one edit so then my this string best string will be exactly equal to my pattern okay now uh we will be calculating what is our minimum edits to understand that how much uh this percentage this pattern is matching with this tree okay so that will give us a confidence match or a good match kind of okay so seeing the percentage we can understand now how this is calculated now there is a matrix we can draw with this like how we need to do this so basically uh this is done like this so uh just follow this very you know like uh just put some you know like if some uh concentration on this so you can understand so let me take the best string so I have taken it in a matrix so a b c d g this is my base string the same string I have taken and this is my pattern as you can see I have taken in the vertically like a y c g so this is my pattern okay so I have given some indexing also so my null index is starting at zero so this is my initial index and then this is my first character so one two three four five I have put some indexing like this and again this is my first character of the pattern so one two three four I have put the indexing like this okay now let's understand this okay now see the first character so a and this a so this is the best string first character and this is a pattern first character so if this a is matching with this a is this a is matching with this a if it is a match then we will just pull whatever is diagonally there so here diagonally is zero so we are pulling this zero that means we don't have to do any edit are we editing anything no we are not editing anything so we are just putting a as in so no edit is there that's why we are putting 0. now if we take as a b now the second character okay now A B with a now how many edits we need to do for a b and b a so only one entry that is we need to delete B so I have put as one so because only one edit is there right so if I want to you know like convert a b to a I need to just delete B so that is my one edit right now ABC so how many edits I need to do to convert a b c to a that is two edges that is I have to build it till it B and C so that that is why I have put two likewise I have failed in all the other values okay now if you see the second position okay so this is a and this is y a y right now how many edits I have to make to uh to bring a to a y to match a to a y a is a and a is matching only Y is not there so I I have to add y right so I have to make one edit so this is how it is like one I have put now if you see the formula is here if the match is there like a to a matching then I am just pulling the diagonal element if it is not a match then I will to take these three uh these three the minimum of these three plus one okay so if I am considering a and a y so this position how I will draw the value here I will put the value here I will determine like with these three values so what is the minimum of these two so that is what is written over here minimum of these three so minimum of these three plus one so here the minimum of these three is zero the minimum is zero zero plus one one so if you see for all the values you can just draw The Matrix like this so if you see a b and a y so what is my B and Y is matching low B and Y is not matching so what is my minimum of these three so minimum work of these three will be 0 plus 1 again so on okay now again if you take the c a b c and a y is my C and Y matching no my C and Y is not not matching so what is my minimum of this three minimum of these three is one one plus one so two okay now if you see d a b c d and y a y so D and Y is matching now d y y is also not matching so what is my minimum of these three so minimum of these three is two plus one that is three so I have put three similarly for G I have put 4 because again the minimum of these three three plus one four right so this is how I am holding uh putting the all the values in The Matrix now if you see the next part so a and a a y c right so a y c what is the minimum A and C is not matching again so what is my minimum of these three minimum of these three is three two one so one one plus one two so I have put two again if you see B and C Okay so what is my again uh it is B and C is not matching so what is my minimum minimum is one so one plus one two right so this is how I am pulling the Matrix now if you see C C and C is matching okay so this is a match so what I'm doing I am just pulling the diagonal element here I am not taking the minimum of the three elements I am just pulling the diagonal element that is one so I am pulling it here so it is one so likewise I have pulled like I have done for all the values if you see the last one also G and G so G and G is matching so I am just pulling the diagonal element to here so it is 2 right now this last value of this Matrix it will be your number of edits actually and it is matching also if you see here so we have two edits one is we you have converted B to Y another is you have deleted D so we have to edits and in The Matrix also we are getting two edits right so this is uh the value of the algorithm like the minimum getting the minimum uh edit distance now uh the important part is now how we will understand where you are editing where you are deleting and where you are adding right so either you can edit either you can delete or you can add so now how you are doing it understanding this now if you see here these two two is coming here in the last value if you see these two from where it is Flowing it is Flowing from this diagonal element two okay so when it is moving diagonally when it is moving diagonally that means we are editing okay so we are actually converting right now if you see here okay so if you see here this D is not changing anything okay uh this is the G is not changing it is only just you know changing the position so basically we are deleting the D if you see the second last value that is two these two is Flowing from this one okay so if you see one plus one has become two so this is a minimum distance like minimum work was one one plus one was two so we put two so if we are going left so 2 is getting pulled from one actually so we are going left so D is deleted so if you see left means delete so here we have deleted D okay so we we are going to left that means we have deleted this okay now again for the c c again it is the diagonal element so there is no change okay so diagonal element whenever we are going it is no change right like g g there is no change so one delete is there that is a Delta delete deletion of T so I have written it here so left means delete okay again I am going to diagonal so again it is there is no change now if you see here this one has been coming from there this coming one has been coming from zero because this is a minimum element minimum value and 0 plus 1 is 1 so this one has been coming from zero so that means it is a conversion like we have converted B to Y okay so this is the edit right because if it is moving diagonally it is added right if there is no change then because if the values are matching like C and C then if there is no change G and G there is no change so there is one edit so this is one edit so if you see this is one edit so I will just highlight this cell with some other color so this is one edit and again this and this is another edits where B is getting converted to Y so this is another edit so this here we are going to left so left means delete and here we are going to diagonal and the string is also not matching the character here is not matching so it is our edit so here we are getting two edits so this is how it is happening so guys we are getting the edit distance okay now let's take another example so here we have the string as ABC and here we have a pattern as ABCD now in order to convert a b c to a b c d so this is how we have pulled a matrix so a and a there is no uh change actually so it is zero so if you see also like how many edits will be there we have to just add one character that is D then ABC will be you know like equal to ABC okay so there will be only one edit so only one value we are getting also in the last so this is our values the result that is one okay so if you see here now this one is coming from where this one is coming from this zero because this is the minimum value here out of these three cells so 0 plus 1 is getting one so when we are moving up this is an ad so we have to add one character here so as I told that if I am moving to left then it is a delete if I am moving diagonal it's a edit if I am moving up then it's like we are adding a character so this is the what is the Livingston distance matching uh I will show in the code also like how we can get the percentage like what is a like uh actually it gives in the percentage you can get like either it's 80 or 85 percent or even less than 50 percent so likewise you can give okay so moving to next uh shall I slow down or uh any questions on this uh there are a few questions in the Q a section but uh if you want we can take it okay will it be okay if I take at the end hello hi guys uh like it will be completely okay I feel yeah I've got a reply saying that the speed is good yeah we can take it at the end okay so this is how the Livingston distance is working so let's move to another algorithm called Bayern Moodle algorithm so uh this is also a very interesting one so uh let's understand this so there these are actually you know like different kinds of algorithms and they have their own pros and cons so we can use it to them accordingly so Livingston distance we can use when we had to get the you know like the percentage matching like how much a string is matching and this is very useful when we do some kind of sentiment analysis or we know like we like to get some percentage like how much percentage the match is there okay so if we are good with 80 or 85 percent then I think this algorithm is also good like we will go with this algorithm if we are trying to get the index like the index value then we will get this Robin called algorithm or boy algorithm or kmb algorithm which will give us the exact index like where the string is or the pattern is happening okay uh now let's understand this so this this is my base string in this algorithm this is indeterminate string so I have put it as together so this is my best string now my pattern is determine so this is my pattern so I want to see that where actually this pattern is opening now with our human eye if you see that this pattern is occurring here at the second Index right but when we will write this algorithm how we will do this and what is the rules for this algorithm to follow that we will see now see if I am writing this pattern again here okay now try to follow this so my pattern length is 8 okay so one two three four five six seven eight so the count is eight and I have to put some values to each of this character so that is the role for this algorithm now I have put some indexing also so the string index starting from 0 so 0 1 2 3 4 5 6 7 so till 7 it is okay and now I am putting some values to this to each of this character okay so what is the rule to put this value the rule is the formula is length minus index minus one so this is the formula and for the last character we are putting the length so last character we are not actually calculating this formula we are just putting the length the total length okay here so that's why I have put here eight the value for N I have put eight now let's see for D so if you see this formula so this is like the length is h 8 minus 0 minus one so this is giving us seven so for d e uh all the values I have calculated now there is a catch so if you see here e should be actually like going by the same formula if I drag this formula then my e should be actually 6 the first six but why I have put four because if a character is repeating then I have to put the last value so here the last value which I am getting is 4 so if you see here this is the formula I have used and E is repeating second time and the latest value which I am getting is 4 so I have just replace the 6 with this one okay so this is the rule so I am just replacing this ease value with 4 okay so any character which is repeating uh multiple times so we have to take the latest value okay so this is how we need to Value this value all these characters we put some values to all these characters okay now let us understand that how will this work like when we will do this matching right so if I take this let me just cut this and put in the initial position okay so now I am in the initial position now the rule for this algorithm is I have to always start from the last so from right to left I need to match okay now if you see here is my aim matching with my n okay so aim is not matching with them correct so it is not a match then what I will do I will try to search whether am is occurring in any of this match like in any of this you know like table it wherever in this table yes it is operating m is occurring and its value is two okay so if its value is 2 I will move this to the uh like plus two position so right now I am here so I will not consider this so 1 2 here I will move this string okay now I will again try to do like is my n and n is matching yes it is matching so now I will just try with the other characters also if everything is matching then this is giving my index as 2. okay now let's see if it is not matching like if my aim is not occurring in this uh like when I was in the first position my aim is not occurring here okay my aim is not occurring here let's say the aim is not occurring here then I will take the length of the string that is eight so my last length is eight so last character value is eight then I will move this string to the uh two plus eight position so like just excluding this Zero part I will count like this one two three four five six seven eight and I will put this ring again here and I will try to again match the last character so this is how this algorithm works uh so uh so I have right written a program also on this so anyhow this algorithm understanding this concept is important as I said so again this is returning the index value okay so you can also try with you know like uh Different Strings like matching the different patterns and all and you try to get the index so this is how it is working I can try with another thing another example so let's say I will take this uh let me just take this rmin so if this is my pattern to match okay so I will just take some valuation of on this so again this is my zeroth value so zero then one I am just indexing it three and total length of my character is 4 so as I can see one two three four okay and what is a valuation so for the last character I am putting the value same as the length of the string that is four okay now no character is matching here so it is fine then what will be the value of the r the value of the r will be 4 minus index that is 0 minus 1 so 4 minus 0 minus 1 so it will be 3 but will be the value of the m so M will be again 4 minus index that is 1 minus 1 so 4 minus 1 3 is 3 minus 1 2 so that will be the value of the N now what is the value of the I the value of the I will be 4 minus index that is 2 minus 1 that is 4 minus 2 is 2 and 2 minus 1 is 1. so I will put one and the last character is 4 so this is my value okay uh now let's try to find this in this string okay so instead of this I will just copy this I will put it here okay I will just delete this now my pattern one is this okay okay so this is my pattern one and I'm again matching starting the match okay so I will be starting the match from n the zeroth value so from the right side sorry so is my e is matching within no it is not matching but if e is here anywhere here no it is also not here uh then where I should move then I should take four like I should move to Plus 4. position so considering these excluding this I will count from here so one two three three four so I will move to this position so I will move my string here okay again I am just matching my uh from the right okay so if aim is matching within no aim is not matching with them okay is aim occurring anywhere here yes m is occurring two at the second position now where I will move I will move to the second post like plus two position so I am here right now so one two I will move here so I will move this string here okay now if you see if n is matching yes n is matching okay so n is matching I is matching I is matching also matching m is also matching R is also matching so this is a match and in which position I am getting it I am getting it at the sixth position so my index will be six so zero one two three four five six so my index will be six so this is how you you know like calculate this algorithm uh like you do this algorithm so you can use your own logic and do the programming also so this is the logic you need to put okay so going to the next one that is KMP this is the last one we have okay actually this is you know like this uh algorithms um like I am actually explaining the way I understood it uh it is little bit you know like if you go to understand by reading the books or articles it will be little bit difficult for you guys so uh but I am just you know like the way I understand so I am just explaining in the same way okay so uh this is an important algorithm okay so if you see here my best ring is a b c d e f j k l m sum string I have taken arbitrary string okay the pattern I have taken is i j k so if you see with the human eye I can see that this is a pattern where I J key is occurring okay so this is a match where I'm getting the match this is a position right now um if you do like now to understand this algorithm we need to uh see like there is a basic algorithm actually from where this one is derived like two you know like there were some cons in that algorithm to overcome that we this is algorithm has come into place so uh let's understand the basic one so basic one is that this is my pattern I am matching with so this is my ith position and let's say this is my J position so the initial position of the pattern is J and the initial position of the bare string is I so I is matching with J no I is not matching with J okay so what I will do I will move this i j k to the next position okay so I will be putting it okay now if I is matching with B this first position these first two strings are matching no it is also not matching okay so I will go to the next one I is matching with C this is also not a match okay so I will again put it to the next one I was mashing with D no it is also not a match so the first letter is also not matching so I will put to the next one I is matching with e no it is not a match so I am putting it to the next one okay I is matching with there no it is also not a match so I'm putting it to the next one G also it is not matching putting it to the next one H is it is also not matching with h so I am putting with next one okay so here it is matching so then I am receiving the second letter okay I and I is matching okay mobile move the index so if this is at the ith position and if this is the Z J so what we will do is when the match is there move j and move I so I is going to the next position and J is also going to the next position so now my new J will be in this position and new I will be in this position so this I am deleting okay now whether this second character is matching J and J is matching okay J and J is also matching it is a match okay move j again so J is new position is this okay and I also is moving to here so both the I both I and J is moving okay now my last character knk is matching yes it is matching so it is a good match it is a full match only and we got the index at eight so this is how there is no problem with this part right we understood this now let's see another problem and another example okay so let's understand the basic algorithm like why these are these uh KMP algorithm has arrived or you know like um like it is invented so let's understand the basic like what is what is the basic difficulty here now let's take another example so this is my best ring and this is my pattern okay now I have put some indexing also now if you see the ith and JS is starting this is the starting position so a and a is matching could match so I am moving the J moving the I right so what we have seen in the previous example okay now BNB is matching again it's a match so I am moving the J moving the I so I am deleting from the previous position okay CNC is also matching so what I'm doing I am moving the J again because it's a match and I am moving the IE again okay now d and e is matching no DNA is not matching so what we have what are the basic algorithm States is if it is not a match then we will go back again like J will go back to the first position and I will go back to the second position so initially I have started I from here so when I match here this is not a match so I will move I to the second position now now if you see the problem what is happening here is you are moving the eye backward also J is moving backward the both the variables are moving backward so since this string is already a match like if you see ABC is already a match but still it couldn't identify this match it is again going and matching the same pattern again and it will again do the same search again so this is these words are the dates one was a basic flaw so if you see the time complexity for this one was O into o the function of M and N so basically if m is the length of the best base string and N is the length of the pattern string then it will be M multiplied by n that many times it will you know like do the string matching searching like back and forth right so to overcome this problem only we have this knp algorithm so where the first thing we need to do is we need to you know like divide the string or any pattern into the prefix and suffix okay so if you see this pattern itself okay the second example which we have taken if you see this pattern itself there can be many prefixes and many suffixes right right so what can be the prefixes the prefixes can be a a b ABC a b c e so all these are prefixes and a b c e a right so this can be a prefix what can be the suffix suffix can be B then this is a suffix a b so I have written all all the suffixes so these are the suffixes okay now we would like to see whether there is any longest prefix occurring which is equivalent to a Sophie service which is matching to the suffix so the maximum uh prefix uh which is occurring as a suffix also like maximum length prefix which is occurring as a suffix also okay so here if you see we can see a b as a match right which is occurring as a prefix also which is occurring as a suffix also so if we in this string if you see a b is occurring here A B is again occurring here at the surface right so a b and a b is opening other than the a B I am not finding any other match so a b is the longest match which is you know like occurring as a prefix as well as suffix okay now when we understand this we will draw a matrix or we can say we can we will draw some value like we will draw our table okay so it is also called a pi table or the longest prefix suffix table whatever so I will call it a table only so I am just putting some values so if you see here how we are putting these values so this is my pattern so this is my original pattern so a b c a e a b so I am writing this pattern again a b c e a b okay now if you see a so I am just starting with so a is occurring now once so zero so B is also zero C is also zero e is zero now a again occurring so it is like same as the index one so if I put some index here like 1 2 3 4 like this is my first character second character likewise if I put some index okay so if you see so my fifth character is my actually the match of my first character so I will put the value here as one okay and again my sixth character is a match actual match of my second character so I will put the value as 2. okay so likewise I will put some values here okay now now what is the rule like how will you do this matching okay now how we will move this eye and you overcome these problems of you know like uh like getting you know like um like just iterating back and forth with the inj right so if you see here um now let's start with this matching okay now this is my eye this is my J so I am starting it here okay so let's see this pattern now okay now I have drawn this table and I have put some values here okay so forget this I am just deleting this index for the sake of understanding so I have already put these values okay now let's understand so what is a thumb rule is where diet will be in the eye and I will be indicating to J plus one so let's fix let's take the initial string as zero now my ith value is a right so my I is here I am I am saying in this position so this string is character is a now I am indicating to the J J is now standing here so I am writing it here so J plus 1 so J plus 1 is this character okay so a and a is a match yes it's a match so what I will do I will move j to this position so J is now in this position and I will be moving to the next position okay so when it is whenever it's a match I am moving the I to the next position okay now let's see whether my second position so B so B and now J plus 1 so J plus 1 is again B okay so B and B is matching yes B and B is matching so if it's a match what do I need to do I need to move Y and move j so now my next position for I is this and my next position of J is this the next position right now if I am saying I ATC so I is value is now C right now what will be the J plus 1 J plus 1 is again C now again it's a match so if it's a match then again I am moving the I so I am moving this I here and I am moving the J also okay so I am moving this J okay now let's see now now follow this now this is critical because it's not not it's not a match so my is value is D okay now my J is value J plus 1 value is z right now if you see it's not a match right now if it is not a match what I will do I will do is what I will go to the value of e now I have put some valuation for E right so this is the valuation of all the characters now I will look into my table what is my value at of e now my value of a is zero so I will move j again to the initial position at 0 right so now it is indicating J plus 1 a so is the D is matching with a no it is still not matching but this time I cannot put J more back because this is the initial position this is the initial uh position that we have started so this time we will move I so now my eye position will be here okay so if you follow this the I is not going backward again like like like we see in the basic algorithm I was also going you know like backward and again it is you know like iterating on the entire Loop so now actually the algorithm matches this string so this what is whatever the highest pattern it could match and it is just going forward okay so now I put I forward because uh I cannot move j more backward right because it is in the initial position okay now see if my eyes position is matching with my J plus 1 so J is at the zero so zero plus one is one so a so a is matching with a yes A is matching with a very good so I am moving J here to the next position and I also to the next position right now my next letter is b b and I am indicating like pointing to J plus 1 so my J plus 1 is again b b is matching B is matching that is also fine then I am moving the J again to the second position Okay so next position and I am moving also I because it's a match okay now I is this position now follow here okay now I is here so I is value is a J plus 1 is C right so A and C is matching A and C is not matching so if it is not matching what will I need to do I said on the earlier example I need to see the value of C okay so the value of C is again here 0 so what I have to do I have to move j again to the initial position so I am moving the J back okay now I is still here now I am pointing J plus 1 so a so a is matching with a yes A is matching with a then I am moving I to the next position so I is if you follow I is not going to the backward Direction okay so I am just moving I to the second next position and I am moving J also to the next position so if you see here I now I's value is B so it is pointing to J plus 1 so b b again B and B B is matching yes so again I am moving J here and I also to the next position now if you see I again rise value is C and it is pointing to J plus 1 that is C so C and C is matching so that is a match so again I have to move I to the next position and Jay also I am moving to the next position right so like likewise I can I I think I can match all of these strings because as you can say it is a match now so now likewise it will match the entire string and it will give me the index of this first like the first character that is occurring that is that is six so it will give me six so likewise uh this is actually you know like uh this is actually overcoming the uh basic you know like the flaw which have we which we have in the uh basic algorithm that is an a algorithm so if you see there we are moving I backward again we are moving J backward again so both the variables are moving backward and again we are reiterating on the characters but here if you see only I is moving forward okay so this is I think it reduces the time as well as the complexity so uh this is a great algorithm and uh this is also you know like gives us the good string match uh so here I will stop I will show some of the code but again I am telling that it will be good like if you write all this code yourself because now you understand the algorithm because these codes are easily available in Google even I have with due respect to the original programmers uh I have also you know like copied from Google only so uh but it is like that that I know this algorithm if I want I can write my own logic also around the same algorithm okay so for the you know like the interest of time I have put some algorithms here like amp search and this I will put in my GitHub Channel link so this is see if you if I uh sorry okay so then uh Robin karp is there so some of the algorithms are there so if I just go here if you see I have run these algorithms also so if you see this pattern is found at index 10 okay and uh this is again Robin curve algorithm so this is actually giving you know like all sorts of testers also with this um like with this function it is giving all sort of tests so you can test different you know like different patterns so and all the tester success so this is again like I have taken from Google itself so some of the sites are there where you can just search for the algorithms you will find this phone okay so and again here there is a uh boiled more algorithm so here also you can see the all the algorithms that are running fine so if you see ABA and this text so ABA is operating twice or one at zeroth position so that is why it is showing that shift at zero and then again it is occurring at here okay again at five it is operating so likewise it is giving the results and this is the last one Livingston ratio so I have given some two uh strings so if you see these strings are not matching completely it is giving me 43 percent match 43.47 percent if I little bit give it you know likes a little bit more match let's see what happens so it is they see like I have given little bit you know like more you know like more matching I have given so it is giving me seven to six percent match so likewise uh you can get a match also and based on this confidence level you can go like if you get 85 percent or 90 and if you think it's a good confidence too you know like take that string ahead then it is a like you can like based on your requirement you can do that so I will stop here I will take the question answers uh sure so the questions are available in the Q a section if you want I can see them out uh yes I can see that oh yeah okay is Robin curve used in GPT 3 DNS search sequence notation search yes you see these are actually various algorithms So based on the you know like different requirements you can use that okay so there are some advanced level also like where these algorithms are used and in the very Advanced way you can use those things okay so these are the sum of the you know like applications I have told where you can use all this algorithm physically but you need to see your requirement like where exactly you know like what is you know like based on your situation you can use those algorithms what is the difference between brawling hash and spuriously so I sweared already seriously it says the wasted Heats as I told you like told in my example like when your value is actually matching so if you see here uh I will go back again here Okay so yes so when your value is matching like I have given the value initial value I have taken as 10 or sorry the seven so this example I had taken so my value of the pattern was matching but when I was trying to search in the best ring there also my value is matching but the characters were not matching so every time I am trying to match my value with the you know like to do this like changing my position the value was coming say same but the characters were still not matching right so those are the like spurious hits or we can say it as a vested means like you are trying to match it but the value is also not matching but it is just taking your time but the strings are not matching right so that is like this period that is called spurious seeds now what is rolling here I told you like um when you you know like put your algorithm so I have put my algorithm here so like like this kind of you know like functional function you can put you can use your base value differently as I already said you can do some modulus operations also uh So based on your requirement you can you know like frame this formula and the same formula you can use your best string also so the pattern and the waste Rings formula should be matching and where you know like when you were changing the position and you were just doing some Opera like operations like you are subtracting this first position like suppose I was in the initial position right my value was 331. now second position I moved when I move to the second position my value was 313. so I did some subtraction I did some multiplication and again I have taken the value of the next character right so weighted value of the next character so likewise when I am just rolling the hash that is called that mechanism is called rolling hash so there is a difference between spurious hits and rolling Ash so spurious 8 is just wasted heat it is just wasting your time when the value is matching but the string is actually not matching okay can you tell me the minimum value once again uh which one uh minimum value are you talking about 11 stone distance foreign like two questions I'm getting the same okay for the Western distance only okay so yes so minimum value is minimum plus one so that is how you need to calculate so if you just see the formula also if you see that the positional Value Plus 1 they have taken and out of that the minimum so what I am doing is I am taking so let's take any position so if you just take D and C so this position so what I am taking is what is the minimum value here one two three so one is a minimum one plus one so two I am getting okay so if you take G and Y this position G and Y so G and Y is not matching so what is the minimum value minimum value here is like like I have highlighted this cells if you see three three four minimum value will be three three plus one four so that will be my yeah like how I will be uh like getting this Matrix value okay so this is how it is not the minimum value it is minimum plus one you need to do okay so that is how we will be putting this Matrix okay so uh now you understand busy sorry I can't see your response so if you just uh Priyanka if you just can't yeah uh they have mentioned there got it thank you okay can you show some real like examples implementations of these algorithms there are many actually uh maybe in the next some sessions I can cover some so we have some industry you know like applications where we you know like use these algorithms so uh yes for the you know like NLP it is used like it is like these algorithms are used in NLP and also for you know like pattern matching and not uh there are many examples so I can share those with uh I think in my next session I can share okay what we have done here for the textual data but if we do it for image analyzation then there will be so many colors to be considered for each pixel okay so I haven't gone yet into image or image pattern recognition I am just you know like understanding the string pattern here uh maybe in the next session we can you know like have some deep learning you know like sessions so that we can understand the image recognitions uh please go to share the Gate of matching code pattern matching code yes I will share that link uh when this video will be uploaded that Priyanka can either comment on that uh so the video will be uploaded like within two days we have mentioned the link as well in the chat section so you can get our earlier sessions as well on it and this one after a few of these okay so time complexity is basically you know like when you are iterating and trying to match the strings the whatever time you are taking in the matching actually so if we are considering the length of the best string is in and the length of the pattern string is in uh then mostly like we should you know like have our time complicity function as you know like little bit less than the most difficult scenarios like if it is the most difficult then we will have M into multiplied by n so that is maximum time complexity so multiplication operator we don't want so it will be nice like if we have M plus n so only you know like we have the like we have to go only one string like we are iterating only on one string like I show you in KMP like we are iterating only on the J like we are going backward and forward with I we are not iterating like we're the best string we are not iterating backwards we are just going forward okay so they are there actually we can calculate some tiny complexities complexity function okay okay how about left delete okay uh yes I will uh tell this again so if you see here uh if you see here so if we go like see if you like again I'm explaining this little bit so if you see the last one G and G G and G is matching yes and these two is Flowing from this diagonal value two okay so if I I say that if the if there is matching value only we are pulling a diagonal value so there is no change actually so it is not changing anything T and C is matching node DNC is not matching and where these two is coming this 2 is coming from one so this was a minimum value which got added to one and we got this two right so one plus one we got two now it is moving to left so if you see I have highlighted these also so it is moving to left so left means we are deleting so we are again we can see here we have deleted d right so this is the deletion okay again if I see C and C C and C is matching and the diagonal value is pulled so there is no change again if you say v and y b and Y again if you see the what is one is coming from this 0 so 0 plus 1 it is coming as one so it is moving uh like it is coming from zero and it is moving diagonally diagonally upward right so this one is actually coming from zero so if it is diagonal then it is I added so we have also can see here that B has been converted to 1. so this is the minimum edit you can do to convert this string completely to this string okay and he similarly here if you see to completely to change this string to completely this string we just have to add d right so that is why this one is coming from this 0 because this zero is a minimum out of this three cell zero one and two so zero plus one has become one so this one is coming from 0 so 1 is actually moving upward right so it is upward then it is ADD so you have to add a character okay I hope uh this is clear thanks everyone have a great day