ansaurus

Question

grouping strings by substring in mysql/python or mysql/.net

Answer 1

+2 A:

Re (2), what you want are called "stopwords" -- e.g., in NLTK (which is Python, but I imagine there will be C# equivalents), per chapter 2 in its excellent online book,

>>> from nltk.corpus import stopwords
>>> stopwords.words('english')
['a', "a's", 'able', 'about', 'above', 'according', 'accordingly', 'across',
'actually', 'after', 'afterwards', 'again', 'against', "ain't", 'all', 'allow',
'allows', 'almost', 'alone', 'along', 'already', 'also', 'although', 'always',
 ...]

The book I quoted can also help with your point 1, but point 3 is really a different field -- clustering. You want a very peculiar kind of clustering (specified and identical cluster size), so existing algorithms may not be suitable for you, but it's not too hard to devise some based on what you mention.

Basically you want each word to be worth a "score" that's higher for words that are rarer in English (and NLTK, or any equivalently powerful natural language processing toolkit in C#, can of course help you with that) -- minus the logarithm of the word's frequency for example could be a start.

You only need to score non-stop words that occur in at least five documents, according to the specs you mentioned, so the number of meaningful words should be pretty low, and exhaustive search might even be feasible.

In fact the biggest issue might be another -- what if there's a group of fewer than 5 docs that, collectively, don't have any non-stop words in common with any of the others? The possibility of such occurrences shows you'll have to relax your specs in some respect (since I don't know anything about your app I can't give specific suggestions, of course, but it might be anything from allowing groups with a number of docs different from 5, to relaxing the criteria for grouping, etc).

Or, would you rather just diagnose that some situation exists where actually meeting your tight constraints is impossible, and provide an error message instead of any results if it occurs?

Alex Martelli 2010-08-19 03:15:40

alex, this a beautiful answer thanks so much, i will wait for others to respond too

I__ 2010-08-19 17:00:40

@l__, you're welcome, if other answers are coming I'll be interested too. BTW, removing stopwords will reduce computational load, but may not be a major issue for your task: stopwords by definition are very likely, so, using e.g. `-log(freq(word))` as a word's "score", stopwords will score low and shouldn't infuence things much. So maybe you should remove only the very "worst" stopwords ("a", "the", "of", ...), not all that NLTK gives (more than 2000, and a few of them, such as e.g. "afterwards" or "ain't", may not at all be very common in _your_ specific text of interest, classical CDs!-)

Alex Martelli 2010-08-19 17:56:13

@alex martelli: thank you. u know i did a stopwords.words('english') and i am getting FEWER words than you are, only like a few hundred. do know why that is?

I__ 2010-08-19 18:11:32

@l__, no idea -- I'm pretty sure I didn't alter that corpus after downloading NLTK. I didn't count though, the "over 2000" number comes from NLTK's _docs_ (which I trusted -- maybe wrongly?-).

Alex Martelli 2010-08-20 01:54:27

ansaurus

tags:

views:

answers:

grouping strings by substring in mysql/python or mysql/.net

related questions