help in algorithm

[Tom Anderson]

On Wed, 10 Aug 2005, Paolino wrote:

> I have a self organizing net which aim is clustering words. Let's think 
> the clustering is about their 2-grams set. Words then are instances of 
> this class.
>
> class clusterable(str):
>  def __abs__(self):# the set of q-grams (to be calculated only once)
>    return set([(self+self[0])[n:n+2] for n in range(len(self))])
>  def __sub__(self,other): # the q-grams distance between 2 words
>    set1=abs(self)
>    set2=abs(other)
>    return len(set1|set2)-len(set1&set2)

Firstly:

- What do you mean by "to be calculated only once"? The code in __abs__ 
will run every time anyone calls abs() on the object. Do you mean that 
clients should avoid calling abs more than once? If so, how about 
memoising the function, or computing the 2-gram set up front, so clients 
don't need to worry about it?

- Could i suggest frozenset instead of set, since the 2-gram set of a 
string can't change?

- How about making the last line "return len(set1 ^ set2)"?

> I'm looking for the medium of a set of words, as the word which 
> minimizes the sum of the distances from those words.

I think i understand. Does the word have to be drawn from the set of words 
you're looking at? You can do that straightforwardly like this:

def distance(w, ws):
 	return sum([w - x for x in ws])

def medium(ws):
 	return min([(distance(w, ws), w) for w in ws])[1]

However, this is not terribly efficient - it's O(N**2) if you're counting 
calls to __sub__.

If you want a more efficient algorithm, well, that's tricky. Luckily, i am 
one of the most brilliant hackers alive, so here is an O(N) solution:



def distance_(w, counts, h, n):
 	"Returns the total distance from the word to the words in the set; the set is specified by its digram counts, horizon and size."
 	return h + sum([(n - (2 * counts[digram])) for digram in abs(w)])

def horizon(counts):
 	return sum(counts.itervalues())

def countdigrams(ws):
 	"Returns a map from digram to the number of words in which that digram appears."
 	counts = {}
 	for w in ws:
 		for digram in abs(w):
 			counts[digram] = counts.get(digram, 0) + 1
 	return counts

def distance(w, ws):
 	"Returns the total distance from the word to the words in the set."
 	counts = countdigrams(ws)
 	return distance_(w, counts, horizon(counts), len(ws))

def medium(ws):
 	"Returns the word in the set with the least total distance to the other words."
 	counts = countdigrams(ws)
 	h = horizon(counts)
 	n = len(ws)
 	return min([(distance_(w, counts, h, n), w) for w in ws])[1]



Note that this code calls abs a lot, so you'll want to memoise it. Also, 
all of those list comprehensions could be replaced by generator 
expressions, which would probably be faster - they certainly wouldn't 
allocate as much memory; i'm on 2.3 at the moment, so i don't have 
genexps.

I am ashamed to admit that i don't really understand how this code works. 
I had a flash of insight into how the problem could be solved, wrote the 
skeleton, then set to the details; by the time i'd finished with the 
details, i'd forgotten the fundamental idea! I think it's something like 
using the counts to represent the ensemble properties of the population of 
words, which means measuring the total distance for each word is O(1).

> Aka:sum([medium-word for word in words])

I have no idea what you're trying to do here!

tom

-- 
I sometimes think that the IETF is one of the crown jewels in all of 
western civilization. -- Tim O'Reilly