Re: fast static alphabetic (order preserving) compression algorithms/implementations


<bryan@xxxxxxxxxx> wrote in message
news:1184074144.652912.275520@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Jul 9, 3:29 pm, John Reiser <jrei...@xxxxxxxxxxxx> wrote:
I am looking to identify a fast static alphabetic (order preserving)
compression algorithm for database indices (B+Trees) ...

"Lossless" did not appear in your list of requirements.
In other words, hashing is OK. Therefore, select an ordered subset
of the original bits, such as:
the even-numbered bits, or
the prime-numbered bits, or
the Fibonacci-numbered bits, etc.
Across all possible distributions of inputs, this is as good
as possible anyway.

--

Can it be order preserving if it is lossy?


this depends...

with this scheme, it is possible that important bits would be missed,
leading to a broken order if it is possible to add new keys later (this
would seem to be a non-trivial problem).

I would probably opt with a lossless approach, such as huffman, or stick
with raw bytes.



.

Relevant Pages