5 ms·
what about the opposite? given a large block of previously unseen text: check if the text contains a word in a given list of bad words. I'm thinking ... profani
by zemo 6y ago
what about the opposite? given a large block of previously unseen text: check if the text contains a word in a given list of bad words. I'm thinking ... profanity filtering, for example. So user inputs a page or two of text, we check it for profanity.
- andyjpb 6y agoThis is a much easier problem as the input is large but streamable and the database is small. However, you would still need to use some of the tokenisation steps that he talks about such as finding word boundaries and stemming. The performance of your problem would be bounded by the size of your unseen text. Something like the The Knuth-Morris-Pratt string-search algorithm would be useful.
- zemo 6y agothanks this is a good reference, this was the type of term I was looking for. I can implement this off of a paper. it's a bit tougher than regular string matching because of homoglyph attacks (i.e., people trying to subvert the matching by writing f_ck or f0ck or fȗck or whatever) but I can probably do a pretty straightforward tokenization at ingest time to clean that up.
- 082349872349872 6y agoIf your users don't ever discuss places such as Scunthorpe, England or Fucking, Austria, the tokenisation may be effective.
- crawdog 6y agoYou could build a bloom filter with the profane words, then check your tokens for the page against that filter.
- teraflop 6y agoThat would make sense if your list of expletives was too large to fit in memory, which would be... impressive, to say the least.
- GordonS 6y agoI'm Scottish, and I'll say it's definitely possible :p
- Keyframe 6y agoif profanities were single words only. What if they weren’t? You’d have to have a giant list of permutations and build a huge-ass bloom filter. Still doable though, but then spelling errors (or not)...
- sanxiyn 6y agoThis is a classic use case for Aho-Corasick algorithm.
- zemo 6y agoah, perfect. yeah this is what I had in my head: taking the word list and making a big trie and walking it as I read the input. I figured there was some prior art here but was struggling to google it. thanks!