BMDiff - Bentley and Mclroy's compression of long common strings

       A java implementation inspired from BigTable paper[1] description about Bentley and McIlroy’s long string compression scheme[2].

[1] - http://static.googleusercontent.com/media/research.google.com/en/us/archive/bigtable-osdi06.pdf

[2] - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.8470&rep=rep1&type=pdf

Source Code

Github project BMDiff.

Dry run performance numbers

•  JITed version maximum speed Encoding - 35MB/s
  Decoding - 330MB/s
  The speeds reported above are due to tests with following parameters
  a) 3Gz dual core iMac (8GB RAM) with 1GB allotted to the VM(JDK 1.8 preview).
  b) Block length = 32
  c) UTF-8 text file sizes 150KB and 7MB.
  The speed changes when block length changes(smaller block lengths decrease the speed, larger block length decreases compression).
  
• There is scope for speed improvement which is the target for next version as this version the target was to produce correct enc/dec.
• There is a slight twist to the original algorithm in the implementation which is when repeated string occur together then still they are chained and represented using notation but for the decoder to decipher this properly for such cases the encoding is instead.

Related Bugs in the open:

HBASE - https://issues.apache.org/jira/browse/HBASE-2655
Hadoop - https://issues.apache.org/jira/browse/HADOOP-5793