Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Is there an algorithm which I can use in order to generate synonyms for some term (word) in respect of a spam. I am writing a simple spam filter.

For example, I set that the app must omit a word "viagra" and press a button which saves this term into a filter database. A script automatically creates synonyms of this word, such as: v.i.a.g.r.a, via_gra, via-gra, and similar. Or I filter a curse, and it generates all the tricks people use to have their curses appear in their comments.

share|improve this question
    
So do you want to detect those "synonyms" or do you want to generate them? –  Joachim Sauer May 10 '12 at 7:16
    
@JoachimSauer To generate them. To create a list of them –  deviDave May 10 '12 at 7:23
    
for what purpose? –  Joachim Sauer May 10 '12 at 7:24
    
@JoachimSauer I wrote it. To make it easy for me to create words which will be filtered and ignored. I am writing a simple spam filter. Accent on simple –  deviDave May 10 '12 at 7:27
    
I don't really get it. If you want to write a spam filter you want to detect the words, not generate them. –  Joachim Sauer May 10 '12 at 7:29

3 Answers 3

Instead of building a dictionary of aliases for the same noun, you could instead test if a given word is an alias of this noun.

You could use many algorithm for this, the simplest one being the Levenshtein distance algorithm. This algorithm computes the distance between two words, for instance a word in a mail and a word in a dictionary. For instance the distance between viagra and vi.agra is 1.

You could then define a threshold below which two words are assumed to be equal (for example, if the distance is lower than 30% of the size of the words). You could enhance the distance algorithm to give lower weights for special characters (like a dash or underscore).

Another algorithm worth looking is the Damerau-Lenvenshtein distance algorithm, which is used to detect spelling mistakes.

share|improve this answer
    
Any implemented libraries for Java or PHP? I do not need a miracle, just a mediocre filter. –  deviDave May 10 '12 at 7:26
1  
I don't know if there are any existing lib already implemented on the net, but the two algorithms I mentionned are very basic. I implemented them once in under 10 minutes. –  XGouchet May 10 '12 at 7:27
    
Oh, then I'll give it a try. Thanks –  deviDave May 10 '12 at 7:28

Welcome to the wonderful world of pattern recognition! This is an extremely hard task to get right. Whatever algorithm you use, the spammers will subvert it and somehow push messages that people recognize, but your program doesn't. You recognize letter substitutions, they move to numbers. You generalize over all characters, they use images. You use OCR, they invent something different.

It may not look it, but this is actually very near the absolute center of what artificial intelligence is about. If you had an algorithm so good that it equals human recognition, you shouldn't be working as a developer - you should get a tenured professorship at Harvard. Seriously.

share|improve this answer
    
I do not need nothing so complicated. Just a basic thing as I just need to prevent most of people pushing their words into comments. I know I cannot fight pros nor I want to. –  deviDave May 10 '12 at 7:25
1  
Harvard. Or Google. –  mouviciel May 10 '12 at 7:26
    
@mouviciel, nah. Genetic algorithms, if done right, have shown to even surpass human recognition (albeit not by much). Granted, it may not be what he's looking for because it would definitely be slower, but just emphasizing that it's possible. –  Neil May 10 '12 at 8:39

The bad news: if you want a spam filter, looking up words is definitely a bad approach.

For instance, you can have a perfectly valid and long message where at some point the word "fuck" is used. Likewise, you can have spam messages full of "valid" words.

The good news: spam filtering is a pattern recognition classic.

Just lookup "spam filter" and "classification" and you should get plenty of results. A good starting approach would be: http://en.wikipedia.org/wiki/Bayesian_spam_filtering

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.