3 ms·

How Mailinator searches for the word "pen1s" in 185 emails every second

24 points by zinxq 19y ago

tlrobinson 19y ago
But instead, let's say we start off by hopping ahead 5 positions and instead look for the "s" at the end of "pen1s". Of course we don't find it, but then instead of checking the next spot, we again skip ahead 5 and look for "s". In fact, because we'll get zero matches, we can skip ahead 5 each time. XXXXXXXXXXXXXXXXXXXXXXX ^ ^ ^ .... s? s? s? ... if we don't find the 's' in any of those positions, that immediately rules out the possibility that "pen1s" precedes it. So instead of 1000 comparisons - we only do 200 ! Uhhh, no... consider the string to be searched: Xpen1sXXXXXXXXXXXXXXXXX ^ ^ ^ .... s? s? s? ... Obviously you can't just skip 5 characters just because there's no "s" at position 5. The Boyer-Moore algorithm says you can skip those 5 characters because there's no X in the target string.
- henryw 19y ago
  "The algorithm has more complexity to it than I've illustrated (like what happens if you encounter an 'e' in one of the hops?) ..."
  - tlrobinson 19y ago
    His statement is still incorrect.
    - mojuba 19y ago
      Agreed, I, too, had the feeling that he didn't get the algorithm. In fact, you have to compare every 5th position with all 5 letters of the pattern - p, e, n, 1 and s, (edit) or the other way around, like you said, which can be done nicely by using character sets like in Pascal or bitmaps in C++. Which brings up a question whether this method is any better than, for example, the Intel x86 instruction for linearly scanning strings (the SCAS family, if I'm not mistaken).
daniel-cussen 19y ago
You could mark as ugly every word with a non-alphabetic symbol in the middle, weird punctuation, or weird capitalization. Sure, there's like a quadrillion ways of spelling "peπi$", but how often do those symbols appear in the middle of the words in a ham email? You never tell your friends to mEeT yOu at th3 &4r? Srsly, why even give words with numbers and symbols in them the benefit of the doubt? There's be few exceptions, including: emails (email@site.top-level domain) Myspace names that are annoyingly decorated with symbols (although...) Serial codes tokens, passwords, technical names (i386, ISO9660) etc They might be few enough to make into a dictionary and even allow for common misspellings. So, first you take all the emails Mailinator gets, you put the ones with weird words in custody, and you let the ones with safe words go by. The remaining emails will mostly be spam. You can further refine the process by getting the computer to find and replace numbers and symbols with letters. 1 l, i, I, 3 e, E, 4 a, A $ s, S π n, r, etc. You then get some ambiguity. To take Paul's example, "pen1s" can become "penls" or "penis". You can safely assume it's "penis", or use Bayesian functions to mark it down, or whatever. If you have two weird symbols, (say you have p3n1s) you might get four results. But if the list of possibilities includes bad words, it increases the likelihood the email is spam. Season to taste with Bayesian filtering. You weight words according to the company they keep, so pretty soon latex gets on the list of words to watch out for, along with "princess" and "offshore." Finally, you can pluck emails out of the inboxes of users if you find out they're spam after the fact. You would have to figure out how to reconcile ex post facto filtering with user privacy first. In any case, suppose 1,000,000 Mailinator users receive the same email from a porn site, and you notice that the first 1000 users who read it delete it as soon as they see it in their inbox. If the response from the users who see the site goes above a certain threshold of marking it as spam, you pluck it out of the inboxes of users who haven't seen it yet. You can then tell them about it and let them see it if they like, etc. But everyone would benefit from having a few people delete it from the inbox. Then, you could mark as questionable any email that has more than a certain number of recipients. These are generally spam. Even if they're from people you know, they're generally spam. I hate it when people put me on their mailing list. You can put these emails in a special part of the inbox,, put them in a memo folder instead of the inbox, or something along those lines. You can then treat email that you're not sure of as second-class email. You can set up the inbox so it's sorted by rank (like a news aggregator) instead of by date. You might combine the two and plot them using two dimensions, like vertical position and color. So a very recent memo goes to the bottom and has a bright color, and an old, personalized email from your friend goes on top, in a darker color.
antirez 19y ago
185 emails / second seems very slow...
- immad 19y ago
  185*60 = 10,800 emails a minute = 648,000 emails an hour = 15,552,000 emails a day. Its not too bad
- imsteve 19y ago
  I'm pretty sure grep could do 185000 if it the data is pre-cached...
derefr 19y ago
"It's not about the content (although unlawful or hate stuff can stay away thanks)" So does this mean that mailinator filters for "unlawful or hate stuff"? I'd like to receive my daily insults, thanks.
curi 19y ago
so you build his graph thing at the end. and if you go part way down, then dead end (no match), then don't you have to go back to the 2nd char of the non-match and try to match a word from there? and thus do a lot more comparisons than the number of bytes. the reason is when you put 100+ words in the tree, they'll share some substrings.
gscott 19y ago
Thats almost as fast as a one of those guys looking for action at a bathhouse

24 points by zinxq 19y ago

But instead, let's say we start off by hopping ahead 5 positions and instead look for the "s" at the end of "pen1s". Of course we don't find it, but then instead of checking the next spot, we again skip ahead 5 and look for "s". In fact, because we'll get zero matches, we can skip ahead 5 each time. XXXXXXXXXXXXXXXXXXXXXXX ^ ^ ^ .... s? s? s? ... if we don't find the 's' in any of those positions, that immediately rules out the possibility that "pen1s" precedes it. So instead of 1000 comparisons - we only do 200 ! Uhhh, no... consider the string to be searched: Xpen1sXXXXXXXXXXXXXXXXX ^ ^ ^ .... s? s? s? ... Obviously you can't just skip 5 characters just because there's no "s" at position 5. The Boyer-Moore algorithm says you can skip those 5 characters because there's no X in the target string.

henryw 19y ago
"The algorithm has more complexity to it than I've illustrated (like what happens if you encounter an 'e' in one of the hops?) ..."
- tlrobinson 19y ago
  His statement is still incorrect.
  - mojuba 19y ago
    Agreed, I, too, had the feeling that he didn't get the algorithm. In fact, you have to compare every 5th position with all 5 letters of the pattern - p, e, n, 1 and s, (edit) or the other way around, like you said, which can be done nicely by using character sets like in Pascal or bitmaps in C++. Which brings up a question whether this method is any better than, for example, the Intel x86 instruction for linearly scanning strings (the SCAS family, if I'm not mistaken).

daniel-cussen 19y ago

You could mark as ugly every word with a non-alphabetic symbol in the middle, weird punctuation, or weird capitalization. Sure, there's like a quadrillion ways of spelling "peπi$", but how often do those symbols appear in the middle of the words in a ham email? You never tell your friends to mEeT yOu at th3 &4r? Srsly, why even give words with numbers and symbols in them the benefit of the doubt? There's be few exceptions, including: emails (email@site.top-level domain) Myspace names that are annoyingly decorated with symbols (although...) Serial codes tokens, passwords, technical names (i386, ISO9660) etc They might be few enough to make into a dictionary and even allow for common misspellings. So, first you take all the emails Mailinator gets, you put the ones with weird words in custody, and you let the ones with safe words go by. The remaining emails will mostly be spam. You can further refine the process by getting the computer to find and replace numbers and symbols with letters. 1 l, i, I, 3 e, E, 4 a, A $ s, S π n, r, etc. You then get some ambiguity. To take Paul's example, "pen1s" can become "penls" or "penis". You can safely assume it's "penis", or use Bayesian functions to mark it down, or whatever. If you have two weird symbols, (say you have p3n1s) you might get four results. But if the list of possibilities includes bad words, it increases the likelihood the email is spam. Season to taste with Bayesian filtering. You weight words according to the company they keep, so pretty soon latex gets on the list of words to watch out for, along with "princess" and "offshore." Finally, you can pluck emails out of the inboxes of users if you find out they're spam after the fact. You would have to figure out how to reconcile ex post facto filtering with user privacy first. In any case, suppose 1,000,000 Mailinator users receive the same email from a porn site, and you notice that the first 1000 users who read it delete it as soon as they see it in their inbox. If the response from the users who see the site goes above a certain threshold of marking it as spam, you pluck it out of the inboxes of users who haven't seen it yet. You can then tell them about it and let them see it if they like, etc. But everyone would benefit from having a few people delete it from the inbox. Then, you could mark as questionable any email that has more than a certain number of recipients. These are generally spam. Even if they're from people you know, they're generally spam. I hate it when people put me on their mailing list. You can put these emails in a special part of the inbox,, put them in a memo folder instead of the inbox, or something along those lines. You can then treat email that you're not sure of as second-class email. You can set up the inbox so it's sorted by rank (like a news aggregator) instead of by date. You might combine the two and plot them using two dimensions, like vertical position and color. So a very recent memo goes to the bottom and has a bright color, and an old, personalized email from your friend goes on top, in a darker color.

antirez 19y ago

185 emails / second seems very slow...

immad 19y ago
185*60 = 10,800 emails a minute = 648,000 emails an hour = 15,552,000 emails a day. Its not too bad
imsteve 19y ago
I'm pretty sure grep could do 185000 if it the data is pre-cached...

derefr 19y ago

"It's not about the content (although unlawful or hate stuff can stay away thanks)" So does this mean that mailinator filters for "unlawful or hate stuff"? I'd like to receive my daily insults, thanks.

curi 19y ago

so you build his graph thing at the end. and if you go part way down, then dead end (no match), then don't you have to go back to the 2nd char of the non-match and try to match a word from there? and thus do a lot more comparisons than the number of bytes. the reason is when you put 100+ words in the tree, they'll share some substrings.

gscott 19y ago

Thats almost as fast as a one of those guys looking for action at a bathhouse