Google\’s RE2 regular expression library

2010-05-30 239 words 2 mins read

\"Image
Image via CrunchBase

?

<a class="zem_slink freebase/en/google" title="Google" rel="homepage" href="http://google.com">Google has announced the release of its RE2 library under a BSDish license. &#8221;At Google, we use <a class="zem_slink freebase/en/regular_expression" title="Regular expression" rel="wikipedia" href="http://en.wikipedia.org/wiki/Regular_expression">regular expressions as part of the interface to many external and internal systems, including Code Search, <a class="zem_slink freebase/en/sawzall" title="Sawzall (programming language)" rel="wikipedia" href="http://en.wikipedia.org/wiki/Sawzall_%28programming_language%29">Sawzall, and <a class="zem_slink" title="Bigtable" rel="homepage" href="http://labs.google.com/papers/bigtable.html">Bigtable. Those systems process large amounts of <a class="zem_slink freebase/en/data" title="Data" rel="wikipedia" href="http://en.wikipedia.org/wiki/Data">data; exponential <a class="zem_slink freebase/en/runtime" title="Run time (computing)" rel="wikipedia" href="http://en.wikipedia.org/wiki/Run_time_%28computing%29">run time would be a serious problem. On a more practical note, these are <a class="zem_slink freebase/en/thread" title="Thread (computer science)" rel="wikipedia" href="http://en.wikipedia.org/wiki/Thread_%28computer_science%29">multithreaded <a class="zem_slink freebase/en/cplusplus" title="C++" rel="wikipedia" href="http://en.wikipedia.org/wiki/C%2B%2B">C++ programs with fixed-size stacks: the unbounded stack usage in typical regular expression implementations leads to stack overflows and server crashes. To solve both problems, we&#8217;ve built a new regular expression engine, called RE2, which is based on <a class="zem_slink freebase/en/automata_theory" title="Automata theory" rel="wikipedia" href="http://en.wikipedia.org/wiki/Automata_theory">automata theory and guarantees that searches complete in <a class="zem_slink freebase/en/linear_time" title="Linear time" rel="wikipedia" href="http://en.wikipedia.org/wiki/Linear_time">linear time with respect to the size of the input and in a fixed amount of stack space.&#8221; More information can be found on the <a href="http://code.google.com/p/re2/" target="_blank">RE2 project page.<h6 class="zemanta-related-title">Related articles by Zemanta <ul class="zemanta-article-ul"> <li class="zemanta-article-ul-li"><a href="http://glinden.blogspot.com/2010/03/gfs-and-its-evolution.html">GFS and its evolution (glinden.blogspot.com) <li class="zemanta-article-ul-li"><a href="http://research.swtch.com/2010/03/regular-expression-article-3.html">Regular Expression Article #3 (research.swtch.com) <div class="zemanta-pixie"><a class="zemanta-pixie-a" title="Reblog this post [with Zemanta]" href="http://reblog.zemanta.com/zemified/456fa268-f416-4aec-ae05-4d1a9c9c2712/"><img class="zemanta-pixie-img" src="http://blog.amit-agarwal.co.in/wp-content/uploads/2010/08/reblog_b65.png" alt="Reblog this post [with Zemanta]" /><span class="zem-script more-related more-info pretty-attribution paragraph-reblog">


author

Authored By Amit Agarwal

Amit Agarwal, Linux and Photography are my hobbies.Creative Commons Attribution 4.0 International License.

We notice you're using an adblocker. If you like our webite please keep us running by whitelisting this site in your ad blocker. We’re serving quality, related ads only. Thank you!

I've whitelisted your website.

Not now
This website uses cookies to ensure you get the best experience on our website. Learn more Got it