In a data storage system, a prior set S of prefix codes for pseudo-dynamic compression as well as data compressed utilizing prior set S are stored. While data compressed utilizing prior set S are stored in the data storage system, the number of prefix codes utilized by the data storage system for pseudo-dynamic compression are augmented. Augmenting the number of codes includes determining a new set S’ of prefix codes for pseudo-dynamic compression from a training data set selected from a workload of the data storage system and storing the new set S’ in the data storage system with the prior set S.