Hidden Markov Models are among the most prominent tools in bioinformatics for segmenting observation sequences, e.g. for finding copy number aberrations in cancer genomes. It is well known that fully Bayesian inference techniques like Forward-Backward Gibbs Sampling outperform frequentist approaches, at the cost of increased running time. Their use becomes prohibitive for experimental platforms such as high-density SNP arrays or next-generation sequencing, with sequences of 100,000 of observations. To address this problem, we develop a data structure for a dynamically adaptive compression scheme based on Haar wavelet shrinkage, and derive an automated method to determine its hyperparameters, greatly accelerating the sampling.