Google\’s RE2 regular expression library

2010-05-30 0 min read bash
\"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">

comments powered by Disqus