[alphaBetaGamma]

Not the author, but I had a similar problem.

If you specify many replacement rules in sed, it will run in O(num_replacements * num_lines). You should be able to use a state machine to do it in O(num_lines), so I google a bit and found this amazing gem: https://unix.stackexchange.com/a/137932

tl;dr: it uses lex to create a custom C program that does "just what you need", compiles it, and runs it on your input. The whole thing wrapped in a bash function. Bonus: it's POSIX compliant.