A bitstring that can't be represented numerically? Any bitstring can be *represented* numerically. I guess you mean your bitstrings are stored as binary data which can't be printed as is without producing garbage on the screen

To answer your question, no, perl doesn't do memory optimization for hashes. There might be a module for that, but I doubt the general case is so easy to deal with

I think an example would have helped. Do the similarities in strings start at the same position in the bitstring? Or do similarities at least start at the same position, but the position varies? If they are not encoded as raw binary data, how are they encoded?

Generally your problem is to find common subexpressions fast. If a very suboptimal packing is enough you could pack always from the start of a bitstring and always the same length. Then a simple HashOfHashes can use all the common subexpressions as keys and the subtree as values. Even a few such HoHs with different lengths and starting bits would be possible. But then you either have to be careful to always add to and search in them in the same sequence or can't short circuit a search when you found a subexpression and no value.

You probably found above solution already yourself, but when giving general information you usually get general solutions