regrep
an implementation of command-line tool similar to grep
in Golang using trigram and a basic state machine
The current implementation of regrep
is based on automata theory and guarantees that searches
complete in linear time with respect to the size of the input and in a fixed amount of stack space.
regrep
utilizes Trigram-accelerated regex search. This essentially means that each byte is processed
once during index build-up and later during the actual regular expression build - hence the name regrep
A trigram is a substring of 3 consecutive characters, or runes.
For example - The trigrams of trigram are: tri, rig, igr, gra and ram.
Valid regular expressions are able to be converted to a trigram query against the index.
regrep
searches the trigram index for possible matches and then runs the full regular
expression against the possibles. Each regular expressions must match at least one trigram.
Itβs a good idea to think carefully about regular expression queries. The more possible
trigrams matched by a query, the more results are checked against the full regular
expression and the less efficient the query. The reverse, however, is also true.
The more trigrams enforced by the regular expression, the better use regrep
can make
of the index and the smaller the possible results set.
The current distribution requires 'golang' and 'docker' for running the build/test setup. The common options to try out are 'make' or 'make tests'
The default settings use Alpine Linux image [Busybox + musl-libc] for smaller footprint.
-
Trigrams and Regexp. Google RE2
-
From 'The Kubernetes Authors' Golang Build Template
This project was created by Piyush Dewnani