I thought I'd resurrect this thread for the purpose of gathering some input on the best approach to an issue that has been bothering me.
In a case like this usually I'd go with option #5 myself: don't worry about the potential problem too much until it becomes an actual problem. Or in other words, make all the script edits you want and then check how much space your new text takes up; if it's <= the original script size (possibly after adjusting the compression based on your new letter frequencies), then you don't have a problem!
However, given the size of the script, how little extra space is already available, and how likely you are to produce a script that is larger than the original, you probably are in trouble
For the benefit of anybody who's interested, Dragon Warrior IV's script is quite large for a NES game, weighing in at approximately 160 KB uncompressed or 95 KB compressed, so they achieved a compression ratio of nearly 40%, which is about the best you can expect from the usual compression methods on the NES (if you managed to implement LZMA decompression on the NES, you could drop the compressed size down to around 50 KB, but 7-Zip says you would need 18 MB of RAM for decompression, which is about 9000 times more RAM than the console comes with, so... good luck with that!).
That being the case, you might like option #6: convert the game to a different mapper (e.g. MMC5) and then you can expand the ROM to have lots of space.
These options aren't as good, but I'll toss them out here anyway:
7. Write your script to take advantage of the compression. For DW4's Huffman tree, that means spaces and the letter e are your best friends (3 bits), followed by of a/n/o/s/t (4 bits) and then h/i/l/r/u (5 bits), etc.
8. Create free space by optimizing the existing code/data. My experience with the NES Dragon Warrior games has been that they are generally pretty tightly coded, so creating free space in this way would probably be the most work for the least gain.
While I agree with your other two points, I'm not so sure about this one. It's easiest to explain my use of this format with an alternate example:
"Pull Excalibur from the stone, young Arthur, and then, you shall be king."
I'm sure we would agree that adding an article before "king" in that sentence would not improve it. It would take away some of the weight of the kingship if Arthur were to simply become "a king." I think the same can be said for "hero" in the sentence you cited. That all said, I'm open to further discussion on this if you feel it's warranted.
I see where you're trying to go, but the lack of an article in "I will recognize you as hero" definitely feels weird here.
pro tip: with some luck, you can beat the dragon at a much lower level than what most people suggest. I did it at level 10!
After you've finished the game, you might be interested in seeing what's possible with a *lot* of luck