Comparing a string to the next in a list lazarus / 21-General ---------------------------------------------------------------------- maurobio · 2021-09-16 13:06 Dear ALL, I want to compare each string in a list with the next string in the same list, printing it if they are identical. I tried two versions, as shown below: version 1 Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program comp1; {$APPTYPE CONSOLE} uses Classes; var  s: TStringList;  i: integer; begin  s := TStringList.Create;  s.Add('this');  s.Add('this');  s.Add('and');  s.Add('that');  for i := 1 to s.Count do  begin    if s[i] = s[i - 1] then          WriteLn(s[i]);  end;  s.Free;end.  version 2: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program comp2; {$APPTYPE CONSOLE} uses Classes; var  s: TStringList;  i: integer; begin  s := TStringList.Create;  s.Add('this');  s.Add('this');  s.Add('and');  s.Add('that');  for i := 0 to s.Count - 1 do  begin    if s[i] = s[i + 1] then          WriteLn(s[i]);  end;  s.Free;end. Both versions give me out-of-bounds errors!  Could someone point out what is wrong? I feel rather dumb today. Thanks in advance! ---------------------------------------------------------------------- Zvoni · 2021-09-16 13:45 Version 1: You run i from 1 to s.count which is 4 in your sample. You compare s[ i] with s[i-1] --> There is no Member with Index 4 The same in Version 2: you run i from 0 to s.count-1 which equals 3. You compare s[ i] with s[i+1] --> There is no Member with Index 4 ---------------------------------------------------------------------- marcov · 2021-09-16 13:46 first can do a s[ i] with i=s.count, which is out of bounds. second can do s[i+1] with i=s.count-1 which is effectively also  s[ i] with i=s.count, which is out of bounds. ---------------------------------------------------------------------- Zvoni · 2021-09-16 13:48 No Out-Of-Bounds-Error: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program Project1; Uses  Classes; Var  s:TStringList;  i:Integer; begin  s:=TStringList.Create;  s.Add('this');  s.add('this');  s.add('and');  s.add('that');  For i:=s.count-1 DownTo 1 Do      If s[i]=s[i-1] Then WriteLn(s[i]);//The other direction  For i:=0 To s.count-2 Do      If s[i]=s[i+1] Then WriteLn(s[i]);  s.Free;end.  EDIT: What's the purpose of this comparison? ---------------------------------------------------------------------- maurobio · 2021-09-16 19:37 @Zvoni, Thanks a lot for your suggestions, they were quite helpful. That sample code had no other purpose than illustrate my problem. But what I really want is to perform a statistical comparison of each string in a list with all others in the same list, using one of the indexes provided in the FuzzyWuzzy library (https://github.com/DavidMoraisFerreira/FuzzyWuzzy.pas). Here is another sample, in which the list contains botanical names: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program comp; {$APPTYPE CONSOLE} uses Classes, FuzzyWuzzy; var  s: TStringList;  i: integer; begin  s := TStringList.Create;  s.Add('Anacardium occidentale');  s.Add('Unknown 1');  s.Add('Unknown 2');  s.Add('Eriotheca sp.');  s.Add('Dead dead');  s.Add('Myrcia lengua');  s.Add('Myrcia lingua');  s.Add('Myrcia sp1');  s.Add('Myrcia sp2');  s.Add('Myrcia sp3');  s.Add('Pseudobombax sp.');  s.Add('Trema micranthum');    for i := 0 to s.Count - 2 do  begin    if PartialRatio(s[i], s[i + 1]) > 90 then          WriteLn(s[i]);  end;  s.Free;end.  It works, incorporating one of your suggestions. With best wishes, ---------------------------------------------------------------------- Zvoni · 2021-09-17 09:57 Quote from: maurobio on September 16, 2021, 09:37:37 pmThat sample code had no other purpose than illustrate my problem. But what I really want is to perform a statistical comparison of each string in a list with all others in the same list, using one of the indexes provided in the FuzzyWuzzy library (https://github.com/DavidMoraisFerreira/FuzzyWuzzy.pas). Uh, you do realize, that's not what you're doing with your simple loop? ---------------------------------------------------------------------- maurobio · 2021-09-17 11:29 @Zvoni, Of course, as I wrote in my previous message, it is working fine. Thank you! With best wishes, ---------------------------------------------------------------------- Zvoni · 2021-09-17 11:31 You sure? In your sample above, you never compare "Myrcia lengua" with "Myrcia sp3" ---------------------------------------------------------------------- maurobio · 2021-09-17 11:34 @Zvoni, Why not? As far as I can see, the algorithm seems to be working fine - "Myrcia lengua" is correctly identified as an ortographic error. Regards, ---------------------------------------------------------------------- Zvoni · 2021-09-17 11:50 You misunderstood: You compare "Myrcia lengua" with "Dead dead" and "Myrcia lingua" but never with "Myrcia sp1" It's contrary to what you wrote: to compare EACH string with EVERY other string of the List. Nevermind sorted vs. unsorted List ---------------------------------------------------------------------- maurobio · 2021-09-17 11:55 @Zvoni, Perhaps you could provide an example of how the algorithm should better work? The lists which I use are always sorted by species name. Regards, ---------------------------------------------------------------------- Zvoni · 2021-09-17 12:16 After thinking about it: The question is not sorted vs. unsorted List, but "Do you really need to compare EACH string with EVERY other String of the List"? Basically it boils down to running through your List and compare each entry with every other entry. Of the top of my head, i'd probably go along these lines: 2 Loops. 2 StringLists (initially identical) Outer Loop: Take (current) entry of List1 and remove this entry from List2 (to avoid comparing it with itself) Inner Loop: Run through List2 and do your comparisons. --> If you need to save the result you have to provide a place to store it (The associated Object of the StringList-Entry?) or you process the Result directly. The result of the above is, that List2 shrinks consecutively, since you're removing the current entry from List2, and there is no difference in result for, e.g. PartialRatio('Myrcia lengua','Myrcia sp3') and PartialRatio('Myrcia sp3,'Myrcia lengua') (commutative). As i said: From the top of my head. Pretty sure someone else might chip in with something better. btw: In my above example both Lists have to be in the same order (that's where sorted gives an advantage) and I'd run through both Lists Top-Down, since you'd always remove the last entry (no overhead moving memory around) in List2 EDIT: Maybe remove the "[SOLVED]" from the Subject? ---------------------------------------------------------------------- maurobio · 2021-09-17 12:36 @Zvoni, Not sure if I understood correctly, anyway I removed the [SOLVED] tag from the message subject per your suggestion. I will have to try the algorithm with a larger sample of names. Regards, ---------------------------------------------------------------------- Gustavo 'Gus' Carreno · 2021-09-17 12:42 Boas Maurobio, Attached is a sample project that will compare all the strings to each other, skipping the ones with the same index. I made it visually appealing with two List Boxes that animate where the comparison is made. Points of interest on the code: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure TfrmMain.FormCreate(Sender: TObject);begin  FWordList:= TStringList.Create;  FWordList.Add('Anacardium occidentale');  FWordList.Add('Unknown 1');  FWordList.Add('Unknown 2');  FWordList.Add('Eriotheca sp.');  FWordList.Add('Dead dead');  FWordList.Add('Myrcia lengua');  FWordList.Add('Myrcia lingua');  FWordList.Add('Myrcia sp1');  FWordList.Add('Myrcia sp2');  FWordList.Add('Myrcia sp3');  FWordList.Add('Pseudobombax sp.');  FWordList.Add('Trema micranthum');   lbLeft.Items.Text:= FWordList.Text;  lbRight.Items.Text:= FWordList.Text;end; procedure TfrmMain.actCompareGoExecute(Sender: TObject);var  indexLeft, indexRight: Integer;begin  actCompareGo.Enabled:= False;  Application.ProcessMessages;  try    for indexLeft:= 0 to Pred(FWordList.Count) do    begin      for indexRight:= 0 to Pred(FwordList.Count) do      begin        if indexLeft = indexRight then continue;        lbLeft.ItemIndex:= indexLeft;        lbRight.ItemIndex:= indexRight;        {          This is where you should perform your FuzzyWuzzy compare.          I'm just doing an equals.        }        if FWordList[indexLeft] = FWordList[indexRight] then        begin          memLog.Append(Format(            'String index %d is identical to String index %d ("%s" = "%s")',            [              indexLeft,            indexRight,              FWordList[indexLeft],            FWordList[indexRight]            ]          ));        end;        Application.ProcessMessages;        Sleep(80);      end;    end;  finally    lbLeft.ItemIndex:= -1;    lbRight.ItemIndex:= -1;    Application.ProcessMessages;    actCompareGo.Enabled:= True;  end;end;  Hope this helps clarify the compare every string in a list with all the strings in the list challenge you were trying. Grande abraço, Gus ---------------------------------------------------------------------- Zvoni · 2021-09-17 12:52 Gus, you do realize (i admit, haven't looked too closely) that you compare strings twice? e.g. in your left List (outer loop) you reach Member 4 and compare it with each Member of the right List (inner Loop) except Member 4, for example member 7 Now, you reach in your left List Member 7 and compare it with each Member of the right list except Member 7, but you compare it (again) with Member 4! It's why i assumed, FuzzyWuzzy returns the same result for (Member4,Member7) and (Member7,Member4) --> commutative ---------------------------------------------------------------------- Gustavo 'Gus' Carreno · 2021-09-17 13:17 Hey Zvoni, Quote from: Zvoni on September 17, 2021, 02:52:57 pmyou do realize (i admit, haven't looked too closely) that you compare strings twice? Yeap, you are completely right! I opted for the lazy, brute force approach of just doing it with a simple 2 nested loops and skipping comparing the same indexes. There is of course a more complex way of doing it that will not make reverse comparisons. I guess it's the permutations versus (Crap, I always forget the other name, the one with repeats, or is permutations the one with repeats? ARGHHH brain is not working ATM, sorry!!!) dilemma. I'll let the more complex routine with no repeats as an exercise to the person that has the brain more switched on than I do Cheers, Gus ---------------------------------------------------------------------- maurobio · 2021-09-17 13:39 @Gus, @Zvoni, Thanks for your time... I didn't think the thing would turn out to be so complex! The original FuzzyWuzzy library, written in Python (https://github.com/seatgeek/fuzzywuzzy) provides a handy 'extract' function which select the best match in a list or dictionary of choices; however, the author of the Free Pascal translation of that library (https://github.com/DavidMoraisFerreira/FuzzyWuzzy.pas) did not provide a corresponding translation of said function, therefore what we are trying to achieve in practice is implementing it from scratch in Pascal! With best wishes, ---------------------------------------------------------------------- avk · 2021-09-17 14:08 @maurobio, just in case, I would like to draw your attention to the fact that the mentioned Pascal implementation of FuzzyWuzzy seems to be one continuous memory leak. ---------------------------------------------------------------------- maurobio · 2021-09-17 14:19 @avk, Continuous memory leak?  In this case, is there an alternative? I really just need to detect 'suspected' names (ie, names which may be ortographically incorrect). Regards, ---------------------------------------------------------------------- Gustavo 'Gus' Carreno · 2021-09-17 14:31 Boas Maurobio, If you don't need the ratio and all the other stuff implemented and are just looking for the Levenshtein Distance, the Free Pascal wiki has an article with code to implement it: https://wiki.freepascal.org/Levenshtein_distance I'm not sure that this version is memory leak free, since I haven't tested it, but it could be another avenue of pursuit? Sorry if this doesn't help and just adds to the noise, but at least you have one more implementation to look at Grande abraço, Gus ---------------------------------------------------------------------- avk · 2021-09-17 14:57 Quote from: maurobio on: Today at 04:19:49 pmContinuous memory leak?  IIRC, the Ratio() and PartialRatio() functions do without leaks, but do they seem the most interesting? Quote from:  Gustavo 'Gus' Carreno on: Today at 04:31:14 pmIf you don't need the ratio and all the other stuff implemented and are just looking for the Levenshtein Distance, the Free Pascal wiki has an article with code to implement it: https://wiki.freepascal.org/Levenshtein_distance To be honest, I think this is the worst example of the Levenshtein distance function. ---------------------------------------------------------------------- Gustavo 'Gus' Carreno · 2021-09-17 15:03 Hey AVK, Quote from: avk on September 17, 2021, 04:57:17 pmQuote from:  Gustavo 'Gus' Carreno on: Today at 04:31:14 pmIf you don't need the ratio and all the other stuff implemented and are just looking for the Levenshtein Distance, the Free Pascal wiki has an article with code to implement it: https://wiki.freepascal.org/Levenshtein_distance To be honest, I think this is the worst example of the Levenshtein distance function. OOOOPPPSSS!!! Please disregard my post then, LOL!!! @avk: On this subject, do you have a better example? Is the implementation on the FuzzyWuzzy.pas/Levenshtein.pas repo better? Sorry for the noise @Maurobio!! Cheers, Gus ---------------------------------------------------------------------- avk · 2021-09-17 15:44 Quote from: Gustavo 'Gus' Carreno on: Today at 05:03:11 pm Is the implementation on the FuzzyWuzzy.pas/Levenshtein.pas repo better? The implementation you mentioned calls as the Levenshtein distance a slightly different distance function. Quote from: maurobio on: Today at 04:19:49 pmIn this case, is there an alternative? I tried to implement some string algorithms, for example, here, but not all are implemented for unicode strings . ---------------------------------------------------------------------- Zvoni · 2021-09-17 15:52 Quote from: Gustavo 'Gus' Carreno on September 17, 2021, 03:17:56 pmHey Zvoni, Quote from: Zvoni on September 17, 2021, 02:52:57 pmyou do realize (i admit, haven't looked too closely) that you compare strings twice? Yeap, you are completely right! I opted for the lazy, brute force approach of just doing it with a simple 2 nested loops and skipping comparing the same indexes. There is of course a more complex way of doing it that will not make reverse comparisons. I guess it's the permutations versus (Crap, I always forget the other name, the one with repeats, or is permutations the one with repeats? ARGHHH brain is not working ATM, sorry!!!) dilemma. I'll let the more complex routine with no repeats as an exercise to the person that has the brain more switched on than I do Cheers, Gus Permutation = Respect the order of draw with/without repeat Combination = No respect for order of draw with/without repeat Gus, it‘s the reason why i wrote to remove current member of list1 from list2 Basically, it boils down to combination without repeat, which btw is a Lottery („6 out of 49“ etc.) ---------------------------------------------------------------------- Gustavo 'Gus' Carreno · 2021-09-17 16:08 Hey AVK, Quote from: avk on September 17, 2021, 05:44:09 pmQuote from: Gustavo 'Gus' Carreno on: Today at 05:03:11 pm Is the implementation on the FuzzyWuzzy.pas/Levenshtein.pas repo better? The implementation you mentioned calls as the Levenshtein distance a slightly different distance function. Hummm, was unaware of that. Thanks for the clarification, that's really helpfull!! Quote from: avk on September 17, 2021, 05:44:09 pmQuote from: maurobio on: Today at 04:19:49 pmIn this case, is there an alternative? I tried to implement some string algorithms, for example, here, but not all are implemented for unicode strings . Would it be too much of an effort to make them UTF8 compatible, cuz you have an impressive array of functions there. (Completely forgot that I already starred you repo, LOL!!) Cheers, Gus ---------------------------------------------------------------------- Gustavo 'Gus' Carreno · 2021-09-17 16:16 Hey Zvoni, Quote from: Zvoni on September 17, 2021, 05:52:10 pmPermutation = Respect the order of draw with/without repeat Combination = No respect for order of draw with/without repeat Combination, that's the one!! Crap, such a well used word and I always forget about it and just remember Permutations, LOL!! Thanks for the memory refresh!! Quote from: Zvoni on September 17, 2021, 05:52:10 pmGus, it‘s the reason why i wrote to remove current member of list1 from list2 Basically, it boils down to combination without repeat, which btw is a Lottery („6 out of 49“ etc.) Right, eliminating the pair already compared on a second list makes it quite easy to implement. I'll have a think about it and maybe update the example. Thanks very much for the tip. I've thought about it in the past for something else, but my memory is getting really bad and these, most simple, solutions are now fleeing my mind Cheers, Gus ---------------------------------------------------------------------- avk · 2021-09-17 16:24 Quote from: Gustavo 'Gus' Carreno on: Today at 06:08:56 pmWould it be too much of an effort to make them UTF8 compatible... Of course not, I just don't have a dozen hands and heads. ---------------------------------------------------------------------- Gustavo 'Gus' Carreno · 2021-09-17 16:27 Hey AVK, Quote from: avk on September 17, 2021, 06:24:47 pmOf course not, I just don't have a dozen hands and heads. The old problem of too many things to do and not that many hours in the day, gotcha Nonetheless, many thanks for the code you already presented us!!! Cheers, Gus ---------------------------------------------------------------------- avk · 2021-09-17 16:38 You're welcome! ---------------------------------------------------------------------- maurobio · 2021-09-17 18:02 @Gus, @Zvoni, @avk, Interesting discussion! Quote from: avk on September 17, 2021, 04:57:17 pm IIRC, the Ratio() and PartialRatio() functions do without leaks, but do they seem the most interesting? Yes, either the Ratio() or the PartialRatio() functions seem to be working fine. I still have to test them with a larger sample of names, but (at lteast for the time being) they should do. With best wishes,