|laziness, impatience, and hubris|
I have done a quick test. Quick because of your blazing fast algorithm. My runtimes for 3 to 200 strings is given below. The times come from the Time::HiRes::gettimeofday function in your program. I set $subStrSize = 256.
These results are from a second copy of your program that I created. It appears my first copy still has a bug.
Yes, there must be a bug in my original copy. Running my full data set with my backup copy of your program gave a runtime of 14.759568. I'd say that's a little better than three years! I'll check the results to see how they compare with some of my old results from limited data sets. That check could take a little time :-)
The problem could be with the way PerlIDE runs scripts. All the times above are from the command line (Win2000).
I ran the full data set with the second copy of the program from PerlIDE and got a runtime of 15.147881. So the problem is with my first copy of your program.
I really like your algorithm. It's speed will allow me to modify my original data and test a couple of theories. You've got a real winner.
Perl is Huffman encoded by design.