OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



   RE: [xml-dev] [OT] Looking for a text algorithm

[ Lists Home | Date Index | Thread Index ]

This is an interesting problem.  One obvious yet pretty much useless
algorithm is the length() function and its variations: word count, unique
word count, etc.  It works similar to the genome size: measure of
information entropy potential.  All the song lyrics will be pretty close to
each other and so will novels.  While useless, it can handle all the
languages. <g>

Don Park

> -----Original Message-----
> From: David Megginson [mailto:david@megginson.com]
> Sent: Sunday, March 09, 2003 6:18 AM
> To: xml-dev@lists.xml.org
> Subject: Re: [xml-dev] [OT] Looking for a text algorithm
> Miles Sabin writes:
>  > Judging from your examples it looks like you're after a closeness
>  > criterion derived from longest common subsequences. But I don't see how
>  > you could use that to usefully construct a single characteristic number
>  > for _any_ string of _any_ length: with only 32 or 64 bits to play with,
>  > many many completely unrelated (on any criterion) strings will collide
>  > on the same code.
> Quite right.  However, if the alternative is a linear search (say,
> using an edit-distance algorithm), then reducing the number of
> candidates by a few orders of magnitude would not necessarily be a bad
> thing.
> The problem I was considering (in the shower) was detecting spam
> messages with minor variations, such as the insertion of the
> recipient's e-mail address in the body or the substitution of Zimbabwe
> for Nigeria.  Assume that I have a database containing many millions
> of known spam messages, and that I want to check an incoming e-mail
> message against it.  If I can narrow the field down to, say, 50
> candidates after a very inexpensive operation, then my system will be
> much more efficient; I can then use edit-distance against the closest
> matches to see if the message really is likely spam.
> That said, based on private e-mail from another list member, I suspect
> that there may be nothing original about the algorithm I came up with;
> nevertheless, here it is for anyone who would care to take a peek:
>   http://www.megginson.com/private/megginson-index-00.zip
> All the best,
> David
> --
> David Megginson, david@megginson.com, http://www.megginson.com/
> -----------------------------------------------------------------
> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> initiative of OASIS <http://www.oasis-open.org>
> The list archives are at http://lists.xml.org/archives/xml-dev/
> To subscribe or unsubscribe from this list use the subscription
> manager: <http://lists.xml.org/ob/adm.pl>


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS