A method facilitating random access to segments of compressed data stored in memory includes the steps of receiving a series of data segments, encoding the series of data segments into a series of compressed data segments of variable segment sizes, storing the series of compressed data segments in a memory, and generating a locator for each of the compressed data segments. Each locator is indicative of the location of an associated compressed data segment in the memory. A method for randomly accessing a segment of compressed data includes receiving a request for a compressed data segment, retrieving a locator associated with the requested segment, using the retrieved locator to locate the requested segment in the memory, and retrieving the requested segment from the memory. Thus, compressed data segments can be decoded in a different order than the order they were encoded in. Systems for implementing the methods are also disclosed.