When he wrote the video chat app I was wondering if 'middle-out' compression would even work for a video stream.. you'd have to buffer some amount of the data in order to get to the 'middle'.
"Top-down" and "bottom-up" in compression usually refer to which direction you build the prefix tree. In Shannon-Fano coding (top-down), you start with the set of all symbols and their frequency distributions and then recursively divide them into roughly even-sized subsets, assigning a 0 as the prefix to the first and a 1 as the prefix to the second. In Huffman coding (bottom-up), you start with a priority queue of each individual symbol/frequency pair, and then merge the two lowest frequency nodes together, building the tree from the bottom up. In middle-out coding, presumably, the algorithm decides at runtime whether to merge two existing codes into a single prefix tree, or to split an existing prefix tree in some other way. There's some speculation [1] that this is done in a probabilistic way.
All of these algorithms require known frequency distributions, which requires that you have the full data available. In typical DEFLATE compressors (gzip, pkzip, zlib, etc.), this is handled by dividing the input stream into blocks and compressing each block individually.
A similar approach could be used for video - you could easily make the block size a single packet - but in practice, you'd rarely want to use a lossless compression algorithm for video chat anyway. Most video compression is lossy; you can drop a lot of detail before the human eye notices. That's how you can stream a full widescreen movie (which has an uncompressed size of 2 megapixel * 4 bytes/pixel * 30 frames/second = 240 MB/sec) over a typical 5 Mb/sec broadband connection.
