0
$\begingroup$

I have a single list containing strings like this:

list={"house", "cat", "dog" ,"horse", "horses", "tree"};

How can I compare these strings within a list and return those strings which are similar (e.g. by using threshold values defined by SmithWatermanSimilarity). Thus, the output should be

{"house", "horse", "horses"}
$\endgroup$
  • 4
    $\begingroup$ This may get you started GatherBy[list, SmithWatermanSimilarity[#, ##] &]. $\endgroup$ – High Performance Mark Mar 27 at 10:47
0
$\begingroup$
c = ClusterClassify[list, 4];

GatherBy[list, c]

{{"house", "horse", "horses"}, {"cat"}, {"dog"}, {"tree"}}

First[%]

{"house", "horse", "horses"}

$\endgroup$
  • $\begingroup$ That is nice, but here I need to define n in ClusterClassify(4). Is there an unsupervised way? $\endgroup$ – M.A. Mar 27 at 18:47
  • $\begingroup$ There is no "proper" assignment of $n$---it depends upon your task and application. In some cases you want every distinct element to be in its own category, and in other cases you want all elements to be the in same category. There is no way around this. Even if you use some off-the-shelf code for unsupervised clustering, that code is, in effect, choosing $n$ for you... just in an opaque way, or one that minimizes some global criterion function (such as sum of squared distances...). $\endgroup$ – David G. Stork Mar 27 at 18:52
  • $\begingroup$ my first idea was to use a combination of StringLengthand SmithWatermanSimilarityto automatically detect similar strings. However my problem is, I have no Idea how this can be applied WITHIN the elements of a list... $\endgroup$ – M.A. Mar 27 at 19:02
  • $\begingroup$ I have no Idea how this can be applied ... you follow the approach illustrated in my comment above, and write a two-argument function (combining your desired functions) which scores the similarity of pairs of elements from the list. $\endgroup$ – High Performance Mark Mar 27 at 21:33
0
$\begingroup$

This may be overkill, but it looks like a clique problem: look for cliques of strings that all have a mutual similarity of at least threshold:

list = {"house", "cat", "dog", "horse", "horses", "tree"};

With[{threshold = 3},
  cliques = FindClique[AdjacencyGraph[
    UnitStep[Round[Outer[SmithWatermanSimilarity, list, list]] - threshold]],
    ∞, All]]

{{1, 4, 5}, {6}, {3}, {2}}

list[[#]] & /@ cliques

{{"house", "horse", "horses"}, {"tree"}, {"dog"}, {"cat"}}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.