A novel reversible data-hiding scheme is proposed to embed secret data into a side-matched-vector-quantization- (SMVQ-) compressed image and achieve lossless reconstruction of a vector-quantization- (VQ-) compressed image. The rather random distributed histogram of a VQ-compressed image can be relocated to locations close to zero by SMVQ prediction. With this strategy, fewer bits can be utilized to encode SMVQ indices with very small values. Moreover, no indicator is required to encode these indices, which yields extrahiding space to hide secret data. Hence, high embedding capacity and low bit rate scenarios are deposited. More specifically, in terms of the embedding rate, the bit rate, and the embedding capacity, experimental results show that the performance of the proposed scheme is superior to those of the former data hiding schemes for VQ-based, VQ/SMVQ-based, and search-order-coding- (SOC-) based compressed images.