Published October 27th, 2003 by Jim O'Halloran
Neat Algorithm: Inversion Lists
Teodor Zlatanov explains the wonders of Inversion lists.
So what are inversion lists? Inversion lists are best described as a condensed summary of a bit string. They are similar to a simple run-length encoding of data, though there are some differences.
Let’s look at an illustrative example. Suppose you want to encode the bit string “1110011.” An inversion list would store a list of three numbers: 0, 3, 5. All we store is the start position of the 1s, then the start position of the 0s, then the position of 1s again, and so on until the bit string is over.
Neat idea.