Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re: Group Similar Items

by traveler (Parson)
on May 27, 2003 at 17:56 UTC ( [id://261072]=note: print w/replies, xml ) Need Help??


in reply to Group Similar Items

On first thought, here is where I might start. Maybe someone who has taken an algorithms class recently might have a better idea. The overall concept is to create a hash of lists. The first item in each list is the "key". Each item in the input is compared with each key. If it is "close enough" to a key, it is added to that key's list, if not, it is installed as a new key.

It can be made much slower and more accurate if the input item is compared with all keys and the item is placed in the list with closest key if it is close enough to any of them.

The algorithm is not perfect and somewhat depandant on the input order. It might be "good enough" and it might be a starting point. In any case, perhaps it will get you or some other monk thinking on the right track to a better solution.

HTH, --traveler

Replies are listed 'Best First'.
Re: Re: Group Similar Items
by Dr. Mu (Hermit) on May 28, 2003 at 03:09 UTC
    I like this approach! To extend the idea even further, if the phrases are short and there is a small number of mismatch types, each item could be reduced to several canonical forms, and those could be used as keys to the hash. For example, cat could be reduced to ca?, c?t, and ?at, to cover single-letter substitutions. So cat is found in that hash as a value in three different buckets. Faced with the word hat, one of its canonical forms, ?at also keys into a bucket containing cat and gets added there.

    Other canonical forms might be obtained from Text::Soundex or Text::Metaphone where "similar" means "sound alike".

    How to then transform this hash of word affinities into a single list with no repeats is left as an exercize for the reader. :-)

    Update:

    To flesh out the soundex idea a little, here's a short example:

    use strict; use Text::Soundex; my @inwords = qw(holly perl monks yahoo monk holey google eperl holy g +oxgle kugel april); my (%hash, @outwords); push @{$hash{soundex($_)}}, $_ foreach @inwords; push @outwords, @{$hash{$_}} foreach keys %hash; print join(' ', @outwords);
    It prints:
    google goxgle kugel perl holly holey holy yahoo april monks monk eperl
    Since each word in this example has but one canonical form, it appears in the hash exactly once. So there are no repeats to untangle as with the cat/hat illustration.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://261072]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others imbibing at the Monastery: (7)
As of 2024-03-28 19:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found