Google\’s RE2 regular expression library

2010-05-30 0 min read bash
Image via CrunchBase


<a class="zem_slink freebase/en/google" title="Google" rel="homepage" href="">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="">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="">Sawzall, and <a class="zem_slink" title="Bigtable" rel="homepage" href="">Bigtable. Those systems process large amounts of <a class="zem_slink freebase/en/data" title="Data" rel="wikipedia" href="">data; exponential <a class="zem_slink freebase/en/runtime" title="Run time (computing)" rel="wikipedia" href="">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="">multithreaded <a class="zem_slink freebase/en/cplusplus" title="C++" rel="wikipedia" href="">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="">automata theory and guarantees that searches complete in <a class="zem_slink freebase/en/linear_time" title="Linear time" rel="wikipedia" href="">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="" 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="">GFS and its evolution ( <li class="zemanta-article-ul-li"><a href="">Regular Expression Article #3 ( <div class="zemanta-pixie"><a class="zemanta-pixie-a" title="Reblog this post [with Zemanta]" href=""><img class="zemanta-pixie-img" src="" alt="Reblog this post [with Zemanta]" /><span class="zem-script more-related more-info pretty-attribution paragraph-reblog">

comments powered by Disqus