Cultured Perl: Inversion lists with Perl (IBM developerWorks)

[Posted October 24, 2003 by cook]

Teodor Zlatanov explains inversion lists as applied to Unicode, on IBM's developerWorks. "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."

(Log in to post comments)