Many data compression techniques rely on the low entropy and/or the large degree of autocorrelation exhibited by stationary signals. In non-stationary signals, however, these characteristics are not constant, resulting in reduced data compression efficiency. An adaptive scheme is developed that divides non-stationary signals into smaller locally stationary segments, thereby improving overall efficiency. Two principal issues arise in implementing this procedure. The first is practical; an exhaustive search of all possible segmentations is in general computationally prohibitive. The concept of dynamic programming is applied to reduce the expense of such a search. The second involves choosing a cost function that is appropriate for a particular compression method. Two cost functions are employed here, one based on entropy and the other on correlation. It is shown that by using an appropriate cost function, an adaptively segmented signal offers better data compression efficiency than an unsegmented or arbitrarily segmented signal.