A binary Write Once Memory (WOM) device is a storage mechanism in which a 0-bit can be overwritten much more easily than a 1-bit. A famous example is the flash memory technology, where 0→1 transitions are allowed, but 1 → 0 transitions require a costly erase procedure and are therefore prohibited. A WOM code is a coding scheme that permits multiple writes to the WOM without violating the WOM rule. The properties of WOM attracted attention even before flash memory was invented. Rivest and Shamir [2] proposed an elegant WOM code that uses 3 bits to write two rounds of any combination of 2 bits. As alternative, context sensitive rewriting codes have been considered [1], in which the new information stored in the second round utilizes certain portions of the output of the first round for unambiguous reuse. Some of these encodings are based on Fibonacci Codes, whose primary relevant property is that they contain no adjacent 1-bits, except as suffixes of all of their codewords.

Rewriting codes for flash memory enable the multiple usage of the same storage space, under the constraint that 0-bits can be changed into 1s, but not vice versa. Context sensitive rewriting codes extend this idea by incorporating also information gathered from surrounding bits. Several new and better context sensitive rewriting codes are presented and analyzed. Empirical simulations show a good match with the theoretical results.

Hierarchical Clustering is widely used in Machine Learning and Data Mining. It stores bit-vectors in the nodes of a k-ary tree, usually without trying to compress them. We suggest a double usage of the extorting operations defining the Hamming distance used in the clustering process, extending it also to be used to transform the vector in one node into a more compressible form, as a function of the vector in the parent node. Compression is then achieved by run-length encoding, followed by optional Huffman coding, and we show how the compressed file may be processed directly, without decompression.

In previous work we have suggested a data structure based on pruning a Huffman shaped Wavelet tree according to the underlying skeleton Huffman tree. This pruned Wavelet tree was especially designed to support faster random access and save memory storage, at the price of less effective rank and select operations, as compared to the original Huffman shaped Wavelet tree. In this paper we improve the pruning procedure and give empirical evidence that when memory storage is of main concern, our suggested data structure outperforms other direct access techniques such as those due to Külekci, DACs and sampling, with a slowdown as compared to DACs and fixed length encoding.