0
$\begingroup$

I am working on a text processer which gives out similarities between a set of strings. After weighted LCS, Levenshtein distance and double metaphone matching, I get buckets of strings such as

  • Bucket for string $i \rightarrow [s, k, m]$
  • Bucket for string $j \rightarrow [i, s, k]$

This effectively implies that $i,j,s,k,m$ belong to the same cluster.

One of the ways I could do this is to build a connectivity graph and cluster all the connected components.

The other way is to iteratively check for the matches.

Could somebody help me do it better.

$\endgroup$
  • 2
    $\begingroup$ What is "better" ? if the only information you have is the connectivity structure, then you need graph based approaches, and spectral methods might be of use. $\endgroup$ – Suresh Venkat Mar 29 '11 at 21:20
  • $\begingroup$ So i used the connectivity analysis to deal with it. Its real fast. $\endgroup$ – Stattrav Apr 13 '11 at 6:08
  • $\begingroup$ @Suresh Venkat I am more interested in learning what spectral methods you were referring to. $\endgroup$ – Stattrav Apr 13 '11 at 6:08
  • $\begingroup$ Look for spectral graph partitioning on google. The idea is to use the connectivity (as encoded by the Laplacian) to split the graph into pieces. $\endgroup$ – Suresh Venkat Apr 13 '11 at 7:02

Your Answer

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

Browse other questions tagged or ask your own question.