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.

Improve this question
$\endgroup$
4
  • 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, 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$
    – Suresh Venkat
    Apr 13, 2011 at 7:02

0

Reset to default

Your Answer

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