4 ms·
Although not a spell checker specifically, I wrote an offensive language filter for a chat system used by the National Hockey League for a period when they host
by bsenftner 10y ago
Although not a spell checker specifically, I wrote an offensive language filter for a chat system used by the National Hockey League for a period when they hosted communal chat rooms during televised games.
The architecture I used is completely different from what is described here, but the goals are very similar. I had to handle any curse word in any language, including curses from one language translated into another language, as well as offensive phrases, and their translated equals, as well as offensive slang, and mispelt offensive slang translated from other languages.
I ended up with an offense dictionary of about 700K words and phrases. This was back in '99, so my memory may not be 100% here, but I remember using Perfect Hash to generate a compiled hash table for the dictionary, and then a trie to organize the dictionary lookups. The entire system was about 150K of a downloaded exe to access the NHL simulcast chat, as all the offensive language filtering occurred on the client side. Chatting anything that could be offensive turned into a series of words with their interiors all asterisk '*', and it ran in something like 500 ms. Fun times. That company and project died with the dot com bust.
- Tloewald 10y agoInteresting. I had to write a badwords filter for a random name generator (for a procedural galaxy generator...) and it's quite a task just for English.
- bsenftner 10y agoIf you've not used a Trie https://en.wikipedia.org/wiki/Trie https://en.wikipedia.org/wiki/Trie I suggest checking them out. Very useful for fuzzy searching.
- majewsky 10y agoIndeed. I did a spell checker for a Haskell university course, and the trie was the recommended data structure. Makes it really easy to eliminate large chunks of the dictionary at once when edit distance gets too large during traversal.
- setheron 10y agoWhen i worked at iTunes they have a mega 'bad_words.txt' file. It was fun to read when bored.
- ThePawnBreak 10y ago> but I remember using Perfect Hash to generate a compiled hash table for the dictionary, and then a trie to organize the dictionary lookups But... but programmers on HN told me that tries are just useless pieces of trivia used to fail people in interviews, and if you need them a library is just going to do it for you in the most efficient possible way.
- OskarS 10y agoTries are lovely little datastructures, don't let anyone tell you any different. It's not like you'll use them every day, but they're nice to have when needed!