Programming Techniques: Regular expression search algorithm (1968)

• myrex

  4 4 10.0 Elixir

  Match regular expressions using NFA process networks (Elixir)

This is Thompson's Construction.

There is a nice description given by Russ Cox:

https://swtch.com/~rsc/regexp/regexp1.html

This project has an interesting implementation in Elixir, which converts the NFA directy into a process network:

https://github.com/mike-french/myrex

The network runs all possible traversals concurrently, and automatically scales to use all cores (Erlang BEAM runtime). Multiple input strings can also be processed concurrenty. It can also generate matching strings concurrently (Monte Carlo). It implements captures and Unicode character sets.

While it is designed for concurrency, it is not meant to be the fastest regex implementation. There is an example of a highly ambiguous match that launches 900k traversals and reports all capture results in about 10s.

• InfluxDB

  www.influxdata.com featured

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

Suggest a related project