Re^2: Compress positive integers

You can save about 60% of the space by storing this data in binary. The following assumes that your each of your documents can be upto 4GB (hence the 'N' pack format). (This is very tersely coded just for a quick test):

#! perl -slw
use strict;
use List::Util qw[ sum ];
use Math::Random::MT qw[ rand ];
use Data::Dump qw[ pp ]; $Data::Dump::MAX_WIDTH = 1000;

use constant NO_OF_DOCS         => 10000;
use constant DOC_PER_WORD       => NO_OF_DOCS / 2;
use constant OCCURANCES_PER_DOC => 20;

## Build some test data
my @words = qw[ the quick brown fox jumps over a lazy dog twice ];
my %index = map{ $_ => {} } @words;

for my $word ( keys %index ) {
    for my $doc ( map{ int rand NO_OF_DOCS } 1 .. DOC_PER_WORD ) {
        my $docName = sprintf "Doc%05d", $doc;
        $index{ $word }{ $docName }
            = [ map{ int rand 2**32 } 1 .. OCCURANCES_PER_DOC ]
    }
}
##pp \%index;

## Building the posting lists in ASCII
my @postings = map {
    my $wordHash = $_;
    join ' ', map{
        "$_ " . join ':', @{ $wordHash->{ $_ } };
    } keys %{ $wordHash };
} values %index;
## pp \@postings;

printf "ASCII uses %d bytes\n", sum map length, @postings;

## Doing them in binary
my @binPostings = map {
    my $wordHash = $_;
    pack '(N/A*)*', map {
        pack 'C/A* A*', $_, pack 'N*', @{ $wordHash->{ $_ } };
    } keys %{ $wordHash };
} values %index;

printf "Binary uses %d bytes\n", sum map length, @binPostings;
#pp \@binPostings;

<>;

## Unpack the packed binary
my $wordIndex = 0;
for my $wordData ( @binPostings ) {
    print $words[ $wordIndex ++ ];
    for my $docData ( unpack '(N/A*)*', $wordData ) {
        my( $doc, $posns ) = unpack 'C/A* A*', $docData;
        print "\t$doc: ", join ', ', unpack 'N*', $posns;
    }
}
__END__
## Output for 10 words appearing 20 times in each of 
## half of 10,000 4GB documents at random positions.
C:\test>678848
ASCII uses  8,801,314 bytes
Binary uses 3,656,853 bytes
[download]

But don't stop reading yet.

If you are storing these records in an RDBMS, you are wasting the potential of that tool. Doing it this way (in either ASCII or binary), to find all the documents that contain 2 words, you are having to retrieve and unpack all the positions for both words in every document in which they appear, and then doing the union of the document sets in Perl.

RDBMSs exist to do set algebra. Doing it in Perl and having to retrieve and unpack all that data to do it is silly. You'd be far better off changing your schema to allow the RDBMS to give you only those offsets for those documents that contain the words or words you require. But you'll need a DBA, or at least someone who SQL skills are a lot more current than my own to set you straight on that.

A schema something like:

TABLE words
word-id     MEDIUMINT   primary key
word        VARCHAR

TABLE docs
doc-id      INTEGER     primary key
docname     VARCHAR     

TABLE word-doc
word-id     MEDIUMINT   REFERENCES words( word-id)     } primary key
doc-id      INTEGER     REFERENCES docs( doc-id )      }
posns       MEDIUMBLOB
[download]

Should be far more compact and allow you to issue queries that find (for example) all the documents contain two (or more) given words and only return the offsets for those words in those documents. Far more of the work done by the RDBMS and far less data to be read, transmitted and unpacked.

You could then go a step further and investingate bitstring fields and boolean algebra.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Comment on Re^2: Compress positive integers Select or Download Code

Replies are listed 'Best First'.
Re^3: Compress positive integers by MimisIVI (Acolyte) on Apr 08, 2008 at 12:49 UTC
Hi again, I am afraid that you didnt understand the shema that i use... One more time... Document Collection: 5000 documents Average size of each document(nr of words): 554 words Number of individual words that appear in the colection: 15000 Now for each word that appears in the collection (in this case 15000 times) i save in the DBMS 15000 posting lists...like below... word="Gratis" --> word id=15 column word Id ==> 15 column Posting List ==> "1 2;3;4; 2 5;2; 3 1;15;...... word="Twee" --> word id=10 column word Id ==> 10 column Posting List ==> "10 20;3 21 2; 43 100;105;...... Like this way for each of the 15000 words.... So if the user will give the query -> "gratis twee" i will fetch the two above posting lists and i merge them to find wich documents have the both terms and i will rank higher the docs which have the terms knear to each other by checking their positions(proximity score) i am afraid that your solution isnt what i actually i look for, ..but anyway thanks for your time.. As i wrote in previous post i found a way to encode postive integers not matter how big they are by using the Elias gamma code... An example of the code is like below... `Number(ASCI) --> Gamma representation(BITS) 1 = 1 2 = 010 3 = 011 4 = 00100 e.t.c...` [download] My first question is how can translate the below string as bit string... posting list==> "1110001110101011111101101111011" and my last question when i will fetch this string how i will unpack it and read one BIT per time..? The decode process is like that: 1. Read and count 1s from the stream until you reach the first 0. Call this count of ones N. 2.read the next N bits of the stream and translate them in ASCI.. (f.e. 101 = 5 ) 3.So to decode the number i sum N to the 2 power with the number of the step 2. So the first number is the 9 = 1110001. The second is the 6 = 11010...and e.t.c. I hope you can help me .... Regards Mimis	[reply] [d/l]
Re^4: Compress positive integers by tachyon-II (Chaplain) on Apr 09, 2008 at 00:35 UTC
You don't seem to be listening. What you are trying to do will never work at scale. You need to do all the heavy lifting on the RDBMS side. The heart of the problem is this: `column Posting List ==> "10 20;3 21 2; 43 100;105;......` [download] The core problem with this format is that you MUST pull it back into perl to manipulate it. The more documents you have and the more words per document the more data you need to pull to process your query. This will never scale. Not today, not tomorrow, not never. Compression will only vaguely paper over the cracks, if it helps at all (because of the overhead price). The table format suggested by BrowerUk is not optimal but is along the lines of what you want as it indicates the need for 3 basic tables. For best speed you want to avoid BLOB and VARCHAR ie anything that is not fixed width as this makes indexing much harder and it is the indexing that is going to provide the speed/scalability in the same way a hash allows you to have fast "random" access to a large array. The basic unit of data you want to store consists of `WORD IN_DOCUMENT AT_POSITION` [download] To efficiently store this you will want to store this unit of data in a compressed form. The compressed form you really want is one where the WORD becomes a WORD_ID and the IN_DOCUMENT becomes a DOC_ID. If you think about a search you want to input words to search for, thus the words table needs to rapidly convert a WORD to a WORD_ID. Using this we will look in our basic unit data table and get back some DOC_IDs which we then need to convert back to IN_DOCUMENT. Thus the tables you need are: `TABLE words word CHAR(32) PRIMARY KEY word_id INT TABLE docs doc_id INT PRIMARY KEY doc_name VARCHAR TABLE word_doc word_id INT doc_id INT pos INT` [download] To complete this we must create an index on the word_doc table. This table as it stands is just a big array. When we create an index on it it effectively becomes a big hash that we can get rapid random access to `CREATE INDEX warpspeed ON word_doc (word_id)` [download] With this structure in place you can then make a query into the word_doc table that will return the data you want. The basic query will be: `SELECT doc_id FROM word_doc WHERE word_id = ? INTERSECT SELECT doc_id FROM word_doc WHERE word_id = ?` [download] This will work but will still be slow. The problem is that it is a big task and we can't use the index to go straight to the data we want. The solution to this is to predict and cache.	[reply] [d/l] [select]
Re^5: Compress positive integers by MimisIVI (Acolyte) on Apr 09, 2008 at 13:19 UTC
Hi tachyon-II, First of all i have a question to you... Have you ever try to do these things that you say in practice??? Have you ever try to do the intersection that you propose to me in a table with 2000000000 records??? If you did it and the perfomance was sutisfied , i cant say anything... but because before end up in this shema i spend 4 months tried all these shema that you said with MySQL and the results wasnt sutisfied...(i read all the optimizations tips about MySQl query and believe me the perfomance wasnt good) i can say for sure that the shema with the posting lists is the best for large documents collections...(by the way Lucene somehow has the same index shema too...) NOw about the tables that you propose, the first is the very famous LEXICON and offcourse i use it in my application... The same happends with the second one where i save the path or the adress of the each document that i am indexing... Now one thing that i want to test is to use the file system to create my index instead of the DBMS(SQL SERVER 2005) but i dont know if i will be efficient to use in binmode files to save all the required info that i need.. One last question for me is how can i read from a bit string one bit per time... i fetch from the DBMS a binary compressed string with all the docids for one term.. To decode the string i use the below code wich is extremely fast... `my $decode = unpack "b",$compressed;` [download] But because i need to read from the string a bit per time and the below code is very slow ... `my @bits = split(//, unpack("b", $compressed));` i want to ask if there is anyway to read from the compressed or the decode string a bit per time... Thanks for your Time.. Mimis	[reply] [d/l] [select]
Re^6: Compress positive integers by tachyon-II (Chaplain) on Apr 09, 2008 at 14:59 UTC
Re^7: Compress positive integers by MimisIVI (Acolyte) on Apr 09, 2008 at 16:32 UTC
Some notes below your chosen depth have not been shown here
Re^4: Compress positive integers by BrowserUk (Patriarch) on Apr 09, 2008 at 19:07 UTC
The problem with the Elias gamma encoding is that even if you implement the bit-twiddling in C, because the fields span byte boundaries, the process of compressing and decompressing your posting lists is slower than unpacking your ASCII representation using pack/unpack. So, whilst you might achieve a few percent more compression than with the simple binary packing I showed elsewhere, the time saved in reading and transmitting that slightly smaller volume of data, is negated by the time it takes to decompress it. The algorithm you posted in your OP, that is taken from the Buettcher paper seeks to address that problem, by only packing to whole byte boundaries. The problem with it is that the code show in the paper for compression and decompression is uselessly incomplete. Eg. Compression code given: `int outPos = 0, previous = 0; for (int inPos = 0; inPos < n; inPos++) { int delta = uncompressed[inPos] - previous; while (delta >= 128) { compressed[outPos++] = (delta & 127) \| 128; delta = delta >> 7; } compressed[outPos++] = delta; }` [download] Note: `n` in the for loop is never set. This can be derived from the length of the input. However, notice that `previous` is initialised to 0, and subtracted from each input number, but it is never set to any value other than zero! Decompression code given: `int outPos = 0, previous = 0; for (int outPos = 0; outPos < n; outPos++) { for (int shift = 0; ; shift += 7) { int temp = compressed[inPos++]; previous += ((temp & 127) << shift); if (temp < 128) break; } uncompressed[outPos] = previous; }` [download] Note: Again, `n` is never set. But this time, you cannot derive it from the input. The input is a bit-stream--ie. a string of bytes--but you cannot use `strlen` as the string will contain embed nulls. So, one algorithm is costs more than it saves and the other that seeks to address that is incomplete, and would probably still cost too much if implemented in Perl. The major costs of your schema are: the volume of data you are transferring for each 'hit'. The time taken to unpack that data. The time taken to sub-select the small number of relevant sets of document offsets from the large number you are retrieving. Each time, you are having to unpack/decompress the document offsets for every document that contains a particular word, in order to gain access to just those that match your complete query. Using your numbers: 5,000 docs * 554 words/doc / 15,000 unique words = each word appears in (on average) 185 documents. That means you read, transfer and unpacked/decompressed all the offsets for 185 documents for each word . But probabilistically, for any given 2 word query, you only need the data for 7 documents. So you've had to handle the data for 370 documents, but then discard it for 356 of them. If you went with the schema I presented, you only read, transfer and unpack/decompress the data for those 7 documents that contain both words. That's 14/370*100 = less than 4% of the data to be manipulated. That saving will far exceed any addition compression you might get from using any of the methods you've mooted. Or any other compression mechanism. I don't think that breaking the schema down beyond the word-doc-offsets (plural) I suggested, to word-doc-offset (singular), will help much. You still need to transfer all the offsets for each word-doc pairing anyway, and the explosion in the size of the indexes will probably slow things. I think tachyon's point about variable length fields is a good one, except that it only affects the performance of indexes, if the variable length data is a part of the index. In the schema I outlined this is not the case. But, I'm not a DBA. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply] [d/l] [select]