Fitting a regular expression to a list of words
2 days ago
- grep can search a list of words using the `-f` flag for file input and `-F` for fixed strings, e.g., with ICD-10 diagnosis codes.
- ripgrep may fail with a 'Compiled regex exceeds size limit' error when given many patterns via `-f`, due to regex size constraints.
- Combining multiple search words into a single regex can be optimized by sharing common prefixes using a trie data structure.
- The Python library `trieregex` generates compact regex patterns from a list of words, e.g., 'blue(?:shield|cross|y)' for words beginning with 'blue'.
- Trie-based optimization works for common prefixes but not for common suffixes; e.g., 'javascript' and 'typescript' are not compressed.
- For HCPCS codes, ripgrep processed a 17,198-character regex containing 8,725 codes about 1,000 times faster than grep (0.078s vs 73.426s).
- Perl's regex engine natively optimizes alternations via trie-izing, making manual compression unnecessary for runtime efficiency.