Hi all,

I have a big number (~10e6) of strings (in fact, titles of articles), and I want to cluster together those that are very similar (i.e. those that are the same title, or misspellings of the same article). Typically, the frequency of titles (i.e. the size of the final clusters) varies between 1 and a few hundreds.

Maybe, the obvious solution for smaller sets of "titles" would be to make a matrix with the Levenshtein distance (with Text::Levenshtein) of all the title pairs and cluster together all the titles having a distance lower than a cut-off (for example, 3). But in this case, the number of comparisons needed makes this approach unfeasible.

Can you think of an "efficient" solution (algorithm/data structure or whatever) that can help here?

Any help would be appreciated,

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.