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.

I have a requirement to filter profanity out of users' submissions in a Java-based web application. The client is aware of both the Scunthorpe Problem and the Clbuttic Problem and have accepted the consequences. Please, I don't desire a debate on the merits of lack thereof of censorship.

There are two bits of data:

  1. The user's submission, which can potentially contain 500 words or so;
  2. A single-column database table containing words that are disallowed. There may be many thousands of records in this table.

The present solution seems wrong to me:

  1. The entire table is loaded into a static String[] on startup into a Singleton (thus residing in memory).
  2. For each user submission we loop through the array and do a .indexOf() to see if any given word in the String[] appears in the submission.
  3. If it appears, we replace with %$#@%-style characters. This is done by tokenizing the user submission, looping through the entire user submission as tokens (again), and replacing each instance of the found word.

There may be brilliance in this solution, but I'm skeptical. And having looked at it for a while I can't find my way past it.

Questions is, what is a solution that will give good performance and hopefully be reasonably sane for future developers to maintain after I get fired for failing to filter out some obscure word I've never heard of?

share|improve this question
    
You say it seems wrong to you, without telling us why you think it is wrong. Then you ask for a performant solution, without telling us, in which way the current solution isn't sufficient. How many texts per second do you get, how many of them can you process? –  user unknown Jul 9 '11 at 3:50
    
I thought the solution was wrong, primarily because the codebase I'm working in is inadequate and sloppy. Given my bias, I didn't trust my own mistrust. I felt that the opinion of others would be beneficial. Things that set off alarms for me were the String[] (what, is this 1999?), looping over the very large String[] instead of the much smaller set of data the user submits, nesting a loop inside the String[] loop with tokenized user submission, and so on. Expected utilization is unspecified, ideally an elegant solution with reasonable performance would be lovely. –  bluegoldfish Jul 12 '11 at 23:14
    
'Reasonable performance' can mean anything. If you don't have a concrete goal, you can't know whether you reached it. If you speed up a process, such that it is 100 times faster - is this a goal? If the user is waiting 1ms or 1/10s? The user will not benefit from your work. –  user unknown Jul 13 '11 at 0:14
add comment

migrated from stackoverflow.com Jul 9 '11 at 11:07

This question came from our site for professional and enthusiast programmers.

5 Answers

up vote 14 down vote accepted

The only way to do a word filter intelligently is to use a phonic matching system. I wrote a very effective profanity filter for a very popular massively multi-player online game for tweens and teens a few years ago in Java.

It was based on a highly modified Double MetaPhone algorithm that was tweaked to be more accurate instead of the default which is to match as many things as possible. It was so extremely effective since it picked up mis-spellings and phonetic spellings just the same as the actual words. I added l33t speak and txt speak to the MetaPhone algorithm as well, making it more of a Triple/Quad Metaphone algorithm.

It featured a pre-processor that compressed running letters and detected things like the kids putting things like w o r d s by intelligently compressing the letters together and eliminating running duplicates like wwoorrddss, it was very specialized for English only.

It was fast enough 8 years ago to be used in a real-time chat system stream without any noticable latency with tens of thousands of users on the system.

We had a list of words that were Metaphone encoded in a table in the database, and it was loaded into a static Map that was surprisingly small and we never had to do anything special to access the list of banned words, I was able to add phrase detection using the same techniques for almost free.

Of course I had a running log of all the chats from thousands of kids trying to break the system in real time so I had a pretty comprehensive set of data to work against. The way I did the logging was when someone triggered the filter with a positive, I logged the next few chat messages that didn't trigger the filter from them, that way if they did find a way around a particular word or phrase, I could adapt my system and catch that. I was pretty bullet proof after just a couple of weeks.

share|improve this answer
3  
This solution appears to be best. Problem is (or was at this point) that I had to solve it in an afternoon. If there is sufficient time, I'll either take the Double MetaPhone approach, or hire you to do it. :-) –  bluegoldfish Jul 12 '11 at 22:41
    
So, I guess half the people will stop playing the game now :D –  Davor Ždralo Jul 13 '11 at 16:47
add comment

If you want to do the matching efficiently, the Aho Corasick algorithm is a pretty good option (I'm sure you can find a Java implementation floating around).

Of course you'll probably want to pre-process the submission to replace any spelling irregularities ('$' -> 's', '@' -> 'a', '|<' -> 'k', etc.)

share|improve this answer
    
Precisely what I was looking for, thanks! Here is a Java implementation : hkn.eecs.berkeley.edu/~dyoo/java –  Rémi M Jul 2 '13 at 14:57
add comment

Instead of loading into a static String[], utilize the HashMap[] or some other type of binary tree (if you wanted to improve searching) making the string your key in the hash. Split your String by spaces and remove punctuation. Then you can query the HashMap for each word in your string split; if the hashmap comes back with non null then you know you have a bad word.

The thing that fails here is the Clbuttic problem where someone adds random characters around the bad word ex. bhassda

share|improve this answer
    
I think that last caveat is what makes this solution pretty much useless - there is no way to extend it to anything but whole-word matches. –  Dmitri Jul 9 '11 at 1:50
    
That is a fair statement; but it becomes hard to capture every possible thing that the human mind can come up with to evade a profanity filter. You could always create a huge regular expression with OR statements to combine all of the options and then match the regex against the input. OR you could do a select from the database with the "bad word field" from the database with an RLIKE against the input. Return indicates bad word and will also return the bad word. –  Suroot Jul 9 '11 at 1:53
    
@Suroot it isn't hard to capture just about any word or phrase with phonetic matching like my question talks about. Absolute matches will never work or scale, but phonetic matching works as close to 100% of the time once you tune as you can possibly get. –  Jarrod Roberson Jul 9 '11 at 15:29
add comment

What you want to do in a case like this is determine which of the two lists of words is the smaller one. Say your "verboten" list contains 2000 words and the maximum user submission is 500 words. In that case, you'll iterate through the list of words in the user submission and look them up one by one in the list of forbidden words and vice versa.

The other change I would make is that you don't keep the list of forbidden words in a String[] - if you search in the array you've got an O(n) search per word in the user submission. That's pretty bad. I'd try to put the data structure that you're looking up in into some sort of associative container or tree structure that has a better lookup performance (log n instead of n). The challenge here would be that if you put the user submission into this container, you'll have to keep track of the word position so you can either reconstruct the input or update the input string if you have a search hit.

share|improve this answer
add comment

Using a phonic system isn't the only solution by any means, but it might be the simplest since there are plenty of open source libraries that do that sort of thing.

The hard part is always going to be the matching portion of any algorithm and it sounds like your match is pretty slow and naive. You can't assume that indexOf will match correctly without some form of auxiliary check.

In addition, you'll end up looping over the entire String N times, where N is the number of words on your blacklist. The suggestions to use Set or HashMap are definitely going to improve things somewhat.

In most cases, a linear state based algorithm is best and fastest. I wrote the solution for Clean Speak and it uses this type of algorithm with a pre-process phonic matching system. This was the only solution that didn't get complicated when profanity is embedded (if foo is profanity, embedding is foosucker) and was able to retain a high level of performance. It also scales nicely for other languages without implementations of new codexes.

Lastly, pre-processing of any form is generally something to avoid. In most cases you can do the same thing in a linear fashion as you handle each of the characters in the string.

Of course, I'd suggest looking at other solutions in the long term because in most applications handling user-generated content is more complex than just profanity filtering. Often you want to also filter personal information such as emails and social security numbers and sometimes things like URLs. Plus, we have found that most applications need some form of moderation system and content searching. These increase complexity considerably.

share|improve this answer
add comment

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.