Profanity Filter Performance in Java

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.)

Answer 5

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.