developerWorks: Inversion Lists with Perl

“I first learned about inversion lists in relation to Perl 6
Unicode programming. In Unicode programming, inversion lists are
essential for storing binary properties of character ranges. Dr.
Mark Davis, the president of the Unicode consortium, was kind
enough to point me to some C implementations of inversion lists. He
said (paraphrased):

‘I first started using inversion lists in about 1985. They are
compact for most data, have fast lookup, and allow fast boolean
operations. I don’t know of any pre-existing implementations, but
it is simple enough that it could well have been developed multiple
times.’

“In addition, Richard Gillam’s book ‘Unicode Demystified’
contained helpful information about inversion lists, in addition to
many other fascinating topics. I recommend it highly for anyone
interested in Unicode programming…”

Complete Story