Next: Long User Key Operation Extension Types, Up: Extensions [Contents][Index]
The extention allows overriding a few methods in the operation of long keys, to allow an alternative storage of the latter.
See The Large Stores.
Some of the library interfaces (i.e. functions) may not (yet) observe the extension.
The long key overridden methods include the creation, disposal and retrieval methods.
The extension was first meant to help with construction suffix trees over nonblonde tables, specifically, by removing the requirement that the keys are stored. As the sum of the suffix lengths for an N bytes long text is N * N / 2, storing all the suffixes as distinct keys is not only very redundant, it is impossibly prohibitive.
The extension allows the long keys to be kept as offsets (the actual definition of the overriding methods is the domain of the application using this library), making the space requirement linear in the size of input. The size of the resulting suffix tree and its backing table would still be larger than the input. Experiments showed long keys may be stored as offsets for as few as 10, 12 bytes on average, less than 16 including overhead and block padding.
The internal long keys operation is not affected by the extension.
The functions observing the overrideable methods include:
The extension has not been tested much, it may not work well.