When I started programming Mergifier, my "RSS feeds dispenser", I knew I was going to need some kind of terms filtering. It's useless to take into account the most common words, for they don't bring any information.
My initial solution was to split the text into an array of substrings and use array_diff to remove those in my blacklist array. I don't know the asymptotic cost of array_diff algorythm, but using it with plenty of items (featuring long titles, summaries and descriptions) soon appeared a bit too expensive.
Recently I studied a lot of pattern matching algorythms, including the well known "Aho-Corasick" which checks occourrences of multiple patterns "at once" inside a text of length n in O(M+n), being M the total number of characters composing the patterns. Useful for virus signature detection and bioinformatics, I did not find its implementation anywhere, so I did my own!
Download the code
As you could see inside the code, this algorythm is cool because one can precalculate delta/phi transition tables and cache them, brutally speeding up computations on many different texts made of many terms.
If you find this code useful, or if you have any kind of suggestion to improve it, please let me know. :)
Monday, 28 June 2010
Friday, 11 June 2010
Mergifier: prima alfa
Mergifier è entrato in funzione! Attualmente si occupa di classificare le notizie di interesse per studenti, docenti e dipendenti. Questi sono i link per sottoscrivere i feed ATOM:
Il progetto è in una fase embrionale e potrebbe manifestare qualche malfunzionamento; aiutaci segnalando bug o eventuali suggerimenti via email o sul canale facebook! :)
Monday, 7 June 2010
Mergifier: a bayesian RSS filter
The RSS feed is a popular format used to publish information. XML based, therefore machine-readable, it was thought as a "container" of news from frequently updated web pages. Personally, I love using iGoogle as aggregator to keep, in a single screen, lot of feeds that keep me constantly updated about intersting facts happening around the world.
We introduced early this technology on Bicocca's website, to spread interesting facts in an aggregate way; we placed RSS feeds in pages featuring news, events and so forth.
We recently talked about this system and we did not find it optimal. We think that it could be more effective to route all this informations into single feeds intended to particular audience, instead of fragmenting everything into many rarely-changed small feeds. Stefano has partially mitigated the problem by creating a feed's map, but we agreed that is sub-optimal: we still prefer something able to gather everything in a single channel and "skim" the news according to the reader's interest.
A similar project is Yahoo! Pipes, that I discovered during the course of knowledge representation. YP allows, among other, to "sum up" contribution of different feeds into a single one but cannot classify the outgoing items (or, at least, I can't find anything like that :) ). Reading some post from the project's board, it seems I'm not the only one lamenting this lack. Not a problem, because in the meanwhile I rediscovered the wheel.
"Mergifier", that's the name I gave to the software, draws from an arbitrary number of RSS feeds (and ATOM as well) and integrates them in a big cauldron. The administrator - that is us, at the moment - is allowed to create as many categories as he wants and every item can be classified in one or more of those. Naturally, I'm not talking about a trivial table, because we don't want to classify every entry by hand. That's why I used a bayesian filter.
More ham for everyone
The idea comes from the bayesian spam filtering used in software like Mozilla Thunderbird: whenever you receive an unwanted letter, you classify it as "junk". The client stores words' frequencies and use those informations to determine the probability of future e-mail's to be spam.
The probability estimation is quite simple:

where p1...Pn is the individual probability of a word to be present in a "junk e-mail". How can we determine that? By using the following formula:
where
This method works stunningly fine; we're testing the results in order to release an alpha during the next weeks :) .
We introduced early this technology on Bicocca's website, to spread interesting facts in an aggregate way; we placed RSS feeds in pages featuring news, events and so forth.
We recently talked about this system and we did not find it optimal. We think that it could be more effective to route all this informations into single feeds intended to particular audience, instead of fragmenting everything into many rarely-changed small feeds. Stefano has partially mitigated the problem by creating a feed's map, but we agreed that is sub-optimal: we still prefer something able to gather everything in a single channel and "skim" the news according to the reader's interest.
A similar project is Yahoo! Pipes, that I discovered during the course of knowledge representation. YP allows, among other, to "sum up" contribution of different feeds into a single one but cannot classify the outgoing items (or, at least, I can't find anything like that :) ). Reading some post from the project's board, it seems I'm not the only one lamenting this lack. Not a problem, because in the meanwhile I rediscovered the wheel.
"Mergifier", that's the name I gave to the software, draws from an arbitrary number of RSS feeds (and ATOM as well) and integrates them in a big cauldron. The administrator - that is us, at the moment - is allowed to create as many categories as he wants and every item can be classified in one or more of those. Naturally, I'm not talking about a trivial table, because we don't want to classify every entry by hand. That's why I used a bayesian filter.
More ham for everyone
The idea comes from the bayesian spam filtering used in software like Mozilla Thunderbird: whenever you receive an unwanted letter, you classify it as "junk". The client stores words' frequencies and use those informations to determine the probability of future e-mail's to be spam.
The probability estimation is quite simple:

where p1...Pn is the individual probability of a word to be present in a "junk e-mail". How can we determine that? By using the following formula:

- Pr(S|W) is the probability of e-mail to be spam
- Pr(W|S) is the chance of finding the word in a junk e-mail
- Pr(S) is the "a priori" probability of a mail to be spam
- Pr(W|H) is the chance of finding the word in a good email
- Pr(H) is the "a priori" probability of a mail to be ham (that is the way "not spam" e-mail are called!)
This method works stunningly fine; we're testing the results in order to release an alpha during the next weeks :) .
Tuesday, 27 April 2010
Just for fun: obfuscated hello world, in C
main(int argc,char*argv[]){memset(&argc,0,1);char*s[11]={0,-3,4,4,7,-40,15,7,10,4,-4};while(argc<11)printf("%c",s[argc++]+0x48);}
What could this code do? =)
The reason behind this code is here.
Thursday, 22 April 2010
IE - object does not support property or method
Have you ever experienced the error message I wrote in the title? Are you hitting the walls with your head wondering what the frak it means? This post might be useful to you!
I wrote a page that worked seemlessly inside every know browser but Internet Explorers. Well, nothing new under the sun, web developers' work consists mainly in making things run inside that shit.
Anyway, I was surprised by the nature of the error message: "object does not support property or method", raised during a getElementById call:
I wrote a page that worked seemlessly inside every know browser but Internet Explorers. Well, nothing new under the sun, web developers' work consists mainly in making things run inside that shit.
Anyway, I was surprised by the nature of the error message: "object does not support property or method", raised during a getElementById call:
foo = document.getElementById("foo");
Element "foo" was a DIV placed in the middle of the page.
So I asked to myself: "what is IE trying to say?". If it really meant that a method wasn't supported, therefore it had to be the getElementById() function, because no other method was involved. But I'm pretty sure that document object HAS a getElementById method.
The other possibility is the lack of support for the property... but which one? The foo variable?? Yay man! The correct answer is this: you cannot give a variable the name of an element's id. By renaming the variable everything works correctly.
baz = document.getElementById("foo");
Here we go. Do you think this is nonsense? Well, so do I.
- First, there's no reason why an HTML element should interfere with javascript variables.
- Second, the error raised is totally incomprehensible and misleading.
- Third, it's incredible that in 8 versions of IE Microsoft did not think of fixing this.
Subscribe to:
Posts (Atom)




