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.

  • 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$ Mar 29, 2011 at 21:20
  • $\begingroup$ So i used the connectivity analysis to deal with it. Its real fast. $\endgroup$
    – Stattrav
    Apr 13, 2011 at 6:08
  • $\begingroup$ @Suresh Venkat I am more interested in learning what spectral methods you were referring to. $\endgroup$
    – Stattrav
    Apr 13, 2011 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$ Apr 13, 2011 at 7:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.