Perhaps feed all the strings into Regexp::Assemble (or Regexp::Assemble::Compressed?), and then analyze the regexp it produces to remove "common" information from your existing strings? I've never used the ::Compressed module, so I don't have any feel for how it is different.