(Sub)bit-fields (Coding with fractions of bits, Part II)

Last week, we used the 6×7×6 palette as an example of very simple fraction-of-a-bit coding¹. However, we can generalize still a bit more to allow single field extraction and modification

Ohta (Colorspaces III)

Let’s continue with lesser known color spaces. In 1980, Yu-Ichi Ohta [1] to segment images based on colors, and to do this, introduced a new colorspace—or more precisely, two variants of the same color space.

Ohta’s concern wasn’t image coding but region separation. He supposed (without much evidence) that a color space with a basis close to the principal components of the colors in the image should be maximally discriminant. He then proposed that the colorspace

Yes? No? Maybe? (Part II)

Last week, we had a look at how to implement a trool, or a tri-valued boolean what accepts true, false, and undefined. We remarked that the storage of an enum likely defaults to int, and that my poc wouldn’t play well with std::vector as that container has no specialization to deal with this new type.

A specialization would be interesting because we can do much better than using an integer to store three different values. We can do much, much better.

Pretty Printing a Tree in a Terminal

More often than I’d like, simple tasks turn out to be not that simple. For example, displaying (beautifully) a binary tree for debugging purpose in a terminal. Of course, one could still use lots of parentheses, but that does not lend itself to a very fast assessment of the tree. We could, however, use box drawing characters, as in DOS’s goode olde tymes, since they’re now part of the Unicode standard.

Serializing Trees

Quite a while ago I discussed using flat arrays and address calculations to store a tree in a simple array. The trick wasn’t new (I think it’s due to Williams, 1964 [1]), but is only really practical when we consider heaps, or otherwise very well balanced trees. If you have a misshapen tree, that trick doesn’t help you. It doesn’t help you either if you try to serialize a misshapen tree to disk.

But what if we do want to serialize arbitrarily-shaped trees to disk? Is it painful? Fortunately, no! Let’s see how.

Interpolation Search

We all know about binary search. It’s been with us such a long time. Knuth thinks it’s first appearance in print is in the Moore School Lectures, in 1946. The technique search for an item in a list by halving, iteratively, the searched portion. Its complexity is for a list of values, making it a very efficient algorithm for searching.

One may even be tempted to think that it’s in fact optimal, that we can’t do significantly better. Is that so?

A Bit About Bit-Fields

Let’s make a detour through low-level programming this week. Let’s talk about bit-fields and some of their quirks.