Could this be used as an alternative to a bloom filter ?
Python code to solve xkcd 1313 by Peter Norvig
41–50 of 75 posts
Re: Python code to solve xkcd 1313 by Peter Norvig
#42Earlier quoted context omitted.
Almost any regex containing a common English phrase of a few words, like /of course/, would give you a very high accuracy rate on a large enough dataset and a very low false positive rate. English has low entropy per bit.
That strategy would return results for any phrase not containing "of course". Which would be rather a lot of results in any document. I am envisioning a regex that plucks hashes from emails, for example. Some parts English, some parts cryptographic "noise". Pick the noise from the English (note the inspiration was a nefarious regex scanner for finding bitcoin hashes. I have no intention of building such a thing, but…
I had to recognize English for a cryptography project in college. This was my entire strategy, which the professor advised for rejecting non-English (it turns out recognizing non-English is easier than recognizing English), and works well:
1. Parse the full text of some long book available on Project Gutenberg. Record every trigram that occurs. Frequency is irrelevant; we just want to know whether a trigram occurs or not.
2. Go through your text, counting the number of trigrams that didn't exist in the sample text. If the number of strange trigrams exceeds a threshold (for my project I used a threshold of 3, but you can tune this), reject the text as non-English.
Given the constant finite threshold I used, that does amount to a regex, but I don't recommend trying to write it out explicitly.
Re: Python code to solve xkcd 1313 by Peter Norvig
#43What would be a use for finding a minimal discriminating regex? Perhaps understanding the difference between boys' and girls' names?
I know this isn't what you're asking, but I imagine in this case it's because that's one of the challenges of regex golf. Matching regex, as short as possible.
Re: Python code to solve xkcd 1313 by Peter Norvig
#44If you just want to play regex golf this site appeared before Christmas and there was quite a discussion [1] although there are a few more levels now: http://regex.alf.nu/
I'm still not happy with my 214 on Alphabetical including one false match (I was 202 or something with everything correctly matched).
Re: Python code to solve xkcd 1313 by Peter Norvig
#45Earlier quoted context omitted.
That strategy would return results for any phrase not containing "of course". Which would be rather a lot of results in any document. I am envisioning a regex that plucks hashes from emails, for example. Some parts English, some parts cryptographic "noise". Pick the noise from the English (note the inspiration was a nefarious regex scanner for finding bitcoin hashes. I have no intention of building such a thing, but…
If you're after hashes you could just match a string of hexadecimal digits of a specific length (such as [0-9a-f]{16} ); much easier to define than English text.
did not think of that!
might be interesting to see how that stacks up against the other idea thread.
Re: Python code to solve xkcd 1313 by Peter Norvig
#46Is Python Peter Norvig's preferred language (along with Lisp, I suppose)?
It is just a language well-suited for teaching.
Re: Python code to solve xkcd 1313 by Peter Norvig
#47Could this be used as an alternative to a bloom filter ?
If you know everything ahead of time, you could probably just use something like a https://en.wikipedia.org/wiki/Perfect_hash_function
Re: Python code to solve xkcd 1313 by Peter Norvig
#48It's too bad he didn't try to tackle the optimal regexp problem and settled for approximations - it may be a NP-hard problem, but all the example solutions are short enough that the instances might be still tractable. Would've been nice to know for sure.
Re: Python code to solve xkcd 1313 by Peter Norvig
#49Is Python Peter Norvig's preferred language (along with Lisp, I suppose)?
http://norvig.com/python-lisp.html
practical tradeoffs, but yes, his preferred language is Python.
Re: Python code to solve xkcd 1313 by Peter Norvig
#50What would be a use for finding a minimal discriminating regex? Perhaps understanding the difference between boys' and girls' names?
Performance. For example if you are syntax highlighting a programming language with hundreds of keywords, then using a regexp like "(kwd1|kwd2|...|kwdn)" is not very efficient. An optimized regexp can do the same matching much faster.
You would be much better off just generating the DFA of the straightforward regex and minimizing that DFA. This is simpler and faster to generate and faster to execute. Furthermore, in a parser for a programming language you do not want to match some things in one list but not in this other list, you want to match some things in this list and nothing else.