You may find work from my colleagues interesting: Parallel Lossless Data Compression on the GPU: http://www.idav.ucdavis.edu/publications/print_pub?pub_id=10... Fast Parallel Suffix Array on the GPU: http://escholarship.org/uc/item/83r7w305 I think built on top of the second paper (suffix array paper), there should be fast compression library. We have one implementation in our library CUDPP 2.0, you can try it out if you like: https://github.com/cudpp/cudpp/blob/master/src/cudpp/app/sa_...