Suppose you want to search for a list of words. If you’re using grep, you can add the -f flag provide a file of regular expressions, and you can add the -F to tell it that the regular expressions are in fact just words. I did something like this a couple days ago when searching for diagnosis codes.
grep -w -F -o -f icd10codes.txt notes.txt
Now you might want to combine your list of words into a singular regular expression, for efficiency or possibly for some other reason. Apparently ripgrep does this because when I tried replacing grep with ripgrep in the command above I got an error saying “Compiled regex exceeds size limit of 104857600 bytes.”
Beating brute force
Say you wanted to search for the strings “bluecross”, “blueshield”, and “bluey”. You could simply form the brute force regular expression
bluecross|blueshied|bluey
but that doesn’t take advantage of the fact that all three strings begin with “blue.” A smaller regular expression would be
blue(shield|cross|y)
Finding the shortest regular expression that matches a list of words is a hard problem, but finding a regular expression that’s shorter than brute force is not. The Python package trieregex will do this. According to the documentation,
trieregex creates efficient regular expressions (regexes) by storing a list of words in a trie structure, and translating the trie into a more compact pattern.
Let’s try our blue example with trieregex.
import re from trieregex import TrieRegEx as TRE words = ['bluecross', 'blueshield', 'bluey'] tre = TRE(*words) print(tre.regex())
This produces the same regular expression as above, except it adds ?: to make the parentheses non-capturing.
blue(?:shield|cross|y)
Prefixes versus suffixes
The library builds a trie data structure using common prefixes. That works well in the example above, but the result is disappointing when we have common suffixes rather than common prefixes. The following code
words = ['javascript', 'typescript'] tre = TRE(*words) print(tre.regex())
produces the regular expression
(?:javascript|typescript)
which is no better than brute force, whereas we might have hoped for
(?:java|type)script
HCPCS examples
As mentioned at the top of the post, ripgrep failed to search on a list of ICD-10 codes. The list of HCPCS codes is about 10x smaller, and more compressible. Ripgrep was able to fit all HCPCS codes into a single regex and was able to search the test file much faster than grep. The command
grep -w -F -o -f hcpcs.txt notes.txt
took 73.426 seconds to execute, while the command
rg -w -F -o -f hcpsc.txt notes.txt
took 0.078 seconds, three orders of magnitude faster.
The following code will read a list of HCPCS codes from a file and create a regular expression.
tre = TRE()
with open('hcpcs.txt', 'r') as file:
for line in file:
tre.add(line.strip())
print(len(tre.regex()))
This shows that the resulting regular expression has 17,198 characters. The file of codes has 8725 five-character codes, so the regex compresses the code characters by roughly a ratio of 5 to 2.
Unlike Python, the Perl regex engine has a trie-izing optimization pass built in, which means that the pattern /bluecross|blueshield|bluey/ compiles down to the same internal program as the pattern /blue(?:cross|shield|y)/, so for *efficiency* purposes there’s no benefit to pre-processing the one into the other (it only matters if you care about the length of your regex’s textual representation).
Minor typo.
I think the examples of using grep and of using ripgrep (rg) in the second part of the article should use ‘hcpcs.txt’ as a file to read fixed string patterns from, rather than ‘icd10codes.txt’.
Thanks Jakub.
You might call out use of egrep. It’s essentially grep with the -E flag. It’s more convenient for typing expressions with alternations such as matching both the words this and that.
You might find this project interesting and relevant to this and other recent posts about matching a list of terms efficiently: https://github.com/timbray/quamina