Fitting a list of words to a a regular expression

John D. Cook Consulting seems to do the manner of work that regular programmers like me only dream of doing, and their blog entries are uniformly interesting, educational and somehow esoteric. I’m amazed by them.

John D. Cook Consulting’s blog published a post Fitting a regular expression to a list of words where (apparently!) John Cook himself shows how to use a Python library to combine several strings into a regular expression that, when interpreted by a program like grep, will match all those strings.

I’ve done this sort of thing by hand (mostly for fun, but also for a little utility) to look for months of the year (3 character abbreviations, “Jan”, “Feb”, “Mar”, …), or days of the week (“Sun”, “Mon”, “Tue”…). Something like that, I can’t remember. What I do remember is that the regular expressions matched more than I initially assumed. As I recall, the expression matched a few more lines of text than I had assumed it would, so I merely had to edit out a few extraneous items. The effort saved by grepping for stuff more than compensated for the extra effort required to make a cool regular expression plus the editing effort.

I’ve also used fancier regular expressions to solve Wordle, but the regular expressions I wrote almost always matched more 5-letter dictionary words than the answer to the day’s puzzle.

Here’s a simple example of matching more words than desired.

All 50 of the USA states have a 2-character postal abbreviation. Once you’ve got those 50 abbreviations in a file, you can create a regular expression that will match at least all 50 abbreviations:

$ cut -c1 abbreviations.txt | sort | uniq > first
$ cut -c2 abbreviations.txt | sort | uniq > second
$ awk '{ together = together$1;} END {printf "[%s]\n", together}' first > regexp
$ awk '{ together = together$1;} END {printf "[%s]\n", together}' second | paste -d '' regexp -        
[ACDFGHIKLMNOPRSTUVW][ACDEHIJKLMNORSTVXYZ]

Look at that - 19 unique letters in both positions, and I created the regular expression with only standard shell commands. This regular expression (a true regular expression, not a “PCRE” or a “regexp”) matches all 50 statue abbreviations:

$ cat abbreviations.txt | grep '[ACDFGHIKLMNOPRSTUVW][ACDEHIJKLMNORSTVXYZ]' | wc -l
50

But it also matches 19*19 = 361 out of all 676 2-letter strings:

for X in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
do
	for Y in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
	do
		echo $X$Y
	done
done | grep '[ACDFGHIKLMNOPRSTUVW][ACDEHIJKLMNORSTVXYZ]' | wc -l
361

That’s a lot more than 50, but I hand rolled the regular expression. Does the Python trieregex package Cook mentions do better?

It certainly creates an esoteric looking regular expression:

(?:M[ADEINOST]|N[CDEHJMVY]|A[KLRZ]|I[ADLN]|W[AIVY]|C[AOT]|O[HKR]|K[SY]|S[CD]|T[NX]|V[AT]|DE|FL|GA|HI|LA|PA|RI|UT)

for X in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
do
	for Y in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
	do
		echo $X$Y
	done
done | grep -E '(M[ADEINOST]|N[CDEHJMVY]|A[KLRZ]|I[ADLN]|W[AIVY]|C[AOT]|O[HKR]|K[SY]|S[CD]|T[NX]|V[AT]|DE|FL|GA|HI|LA|PA|RI|UT)' | wc -l
50

Good for trieregex! It matches all and only the 50 state abbreviations. trieregex would not have helped me with Wordle puzzles. Wordle gives you yellow letters, which are hints meaning “this letter appears in the solution, but not in the position you guessed”. A regular expression has to complement character classes to match Wordle yellow-letter-hints.

trieregex also doesn’t create great regular expressions for lists of words with common prefixes, as John Cook notes. But what about lists of words with suffixes that have structure?

trieregex doesn’t do so well on a simple example. I chose “aaa”, “aba”, “aca” as a simple example. Actually, I chose it as the starting point for more complicated examples, but I didn’t need to go further.

trieregex creates a(?:aa|ba|ca). It could have created a(a|b|c)a, or even a[abc]a.

If I choose “aaa”, “aba”, “aca”, “aab”, “abb”, “acb” as the word list, trieregex creates a(?:a[ab]|b[ab]|c[ab]), which works, but it’s a good deal more complicated than a[abc][ab]. I think I’m asking too much of trieregex. I’ll probably put in more effort to combine suffixes next time I have to find some set of strings in a file, based on Cook’s benchmarking, and I may even use trieregex.