# comparing lists of strings

I have two lists of strings like this:

list1={"a dog is in the house","have a nice day","hello my friend"};
list2={"a dog is in house","watching tv is nice","hello my friends"};


Now i want to use SmithWatermanSimilarity to check for similarity like this: For each element in list1 check if there are similar elements in list2 (by defining a threshold value for SmithWatermanSimilarity e.g. the value should be higher than 0.9 of StringLenght or so)

The desired output should be a list like this:

list3={{"a dog is in the house","a dog is in house"},{"have a nice day"},{"hello my friend","hello my friends"}};


I already found a rough solution which uses a combination of If and two nested Table but this seems to me a little bit clumsy one...

Table[Table[
If[SmithWatermanSimilarity[list1[[x]],
list2[[y]]] > (StringLength[list1[[x]]]*0.8), {list1[[x]],
list2[[y]]}, list1[[x]]], {x, 1, Length[list1]}], {y, 1,
Length[list2]}]

• @High Performance Mark: See update above. It is not even a rough solution since the desired output is not obtained. How can I efficiently manage to put out EITHER the pair of similar strings OR the string in list1??
– M.A.
Mar 5, 2019 at 11:08

t = .9;
{#, Select[list2, Function[x, t StringLength[#] <= SmithWatermanSimilarity[x, #]]]}&/@list1


{{"a dog is in the house", {}},
{"have a nice day", {}},
{"hello my friend", {"hello my friends"}}}

t = .6;
{#, Select[list2, Function[x, t StringLength[#] <= SmithWatermanSimilarity[x, #]]]}&/@list1


{{"a dog is in the house", {"a dog is in house"}},
{"have a nice day", {}},
{"hello my friend", {"hello my friends"}}}

We can use RelationGraph to visualize:

t = .6;
RelationGraph[t StringLength[#] <= SmithWatermanSimilarity[##] &, list1, list2,
VertexLabels -> "Name",
VertexCoordinates -> Join[MapIndexed[# -> {0, -#2[[1]]/3} &, list1],
MapIndexed[# -> {1, -#2[[1]]/3} &, list2]]]


• That is a very nice code but i have another question: what if list1 and list2 are themselves lists of lists? For example {"hello my friend", "DATA Y", "DATA YY"} and {"hello my friends", "DATA Z", "DATA ZZ"}. How do i modify your code to select and match the whole lists based on the first element "hello my friend" / "hello my friends". Or would you suggest, in this case, a different approach? thx.
– M.A.
Mar 12, 2019 at 13:43
• @M.A. is the desired output {{"hello my friend", "DATA Y", "DATA YY"},{"hello my friends", "DATA Z", "DATA ZZ"}} for the example?
– kglr
Mar 12, 2019 at 13:55
• yes. but the matching criterion (SmithWaterman) is only relevant for the first element.
– M.A.
Mar 12, 2019 at 14:03
• @M.A. something like: t = .9; lista = {"hello my friend", "DATA Y", "DATA YY"} ; listb = { {"hello my friends", "DATA Z", "DATA ZZ"}, {"hello my friendsss", "DATA W", "DATA YY"}}; {lista, Select[listb, t StringLength[#[[1]]] <= SmithWatermanSimilarity[lista[[1]], #[[1]]] &]}?
– kglr
Mar 12, 2019 at 14:30
• Thats it! I was close to it - i just used a wrong part specification! thx!
– M.A.
Mar 12, 2019 at 14:49