If the substitution table is too large to load into a hash in its entirety, you could load in a portion of it, process the second file, and load in additional portions until it was completed. This way, you would have to make n passes of the secondary file, where the substitution file is loaded into n pieces.

This is, of course, assuming that you can't fit the substitution file entirely into RAM in a hash, and that using a tied hash is out of the question because of speed concerns. However, 130K lookups in a tied hash cannot take that long, so it might be a vialbe solution. If you were processing a file with 130M lines, then you are going to have to think of something else.

A curious observation, though, is that in your example the "output" file is the same as the input file, just reorganized. I'm sure this is because of simplification on your part.