Link Details

Link 1016635 thumbnail
User 448255 avatar

By dotCore
via pvk.ca
Submitted: Aug 18 2013 / 10:02

This post describes how graph and automata theory can help compile a regular expression like “ab(cd|e)*fg” into the following asymptotically (linear-time) and practically (around 8 cycles/character on my E5-4617) efficient machine code. The technique is easily amenable to SSE or AVX-level vectorisation, and doesn’t rely on complicated bit slicing tricks nor on scanning multiple streams in parallel.
  • 2
  • 0
  • 60
  • 12

Add your comment


Html tags not supported. Reply is editable for 5 minutes. Use [code lang="java|ruby|sql|css|xml"][/code] to post code snippets.

Voters For This Link (2)



Voters Against This Link (0)



    Debugging JavaScript
    Written by: Ashutosh Sharma
    Featured Refcardz: Top Refcardz:
    1. Design Patterns
    2. OO JS
    3. Cont. Delivery
    4. Java EE7
    5. HTML5 Mobile
    1. Java EE7
    2. Spring Annotations
    3. Git
    4. Java
    5. REST