For starters, you'd get better compressing using one of the numerous compression modules on CPAN. (Some sample queries: Compress, gzip, zip)

The technique used by the code you posted is useful to save space on disk when dealing with lots of small numbers. It takes fewer bytes to save small numbers, and an extra byte to save very large numbers. It's advantage over general purpose compression algorithms is that you can seek to known and unknown positions into the file.

1 byte:                       0..127
2 bytes:                    128..etc
3 bytes:                 16_384
4 bytes:              2_097_152
5 bytes:            268_435_456
6 bytes:         34_359_738_368
7 bytes:      4_398_046_511_104
8 bytes:    562_949_953_421_312
9 bytes: 72_057_594_037_927_936
[download]

Depending on the size of the ints on your system and the precision of floats on your system, some of the above aren't available or more than the above is available.

Untested:

sub compress_uint {
   my ($uint) = @_;
   my $compressed = '';
   while ($uint >= 128) {
      $compressed .= chr(($uint & 127) | 128);
      $uint >>= 7;
   }
   $compressed .= chr($uint);
}

for (100, 1000, 100000) {
   print $fh compress_uint($_);
}
[download]

sub decompress_uint {
   our $compressed; local *compressed = \($_[0]);
   my $bytes_read = 0;
   my $uint = 0;
   for (;;) {
      die if length($compressed) == $bytes_read;
      my $byte = ord(substr($compressed, $bytes_read++, 1));
      $uint = ($uint << 7) | ($byte & 127);
      last if $byte & 128;
   }
   $compressed = substr($compressed, $bytes_read);
}

my $raw = do { local $/; <$fh> };
my @nums;
while (length($raw)) {
   push @nums, decompress_uint($raw);
}
[download]

Update: Fixed some typos in text and code.

Had you posted a link to the pdf describing the algorithm and it's performance advantages, you might not be coping the flack and "you don't wanna be doing that"s, that you're getting.

With regard to the algorithm, you will not realise those performance benefits if you code this in Perl.

With regard to your problem:

• How big are your indexes?

  Ie. How many offsets do they contain? (How many documents are you indexing?)

• How big are your offsets?

  IOWs, how big is your largest document?

• How are you writing your indexes?

  If you're not writing them in binary (ie. packing them), then you are wasting large amounts of space and time.

Answer those questions and we may be able to help you.

because its too complex for me

Search CPAN for compress and see if anything usefull turns up

For small number of documents is quiet fast but not for large ...

Which means that your code almost certainly runs in some form of exponetial time. I don't see how compression will not help you in either the short term as the overhead of the compression/decompression will hurt you or the long term as I can't see how your fundamental algorithmic problem is addressed by compression. An algorithm is still On^2 with or without compression.

In broad terms compression will only speed up an application if it lets you pass data faster through a narrow bandwidth chokepoint where the time price of compression/decompression has a worthwhile payoff.

If you have already observed that your code grinds to a halt on large data sets you need to fix the fundamental why of that issue. If you explained your problem more clearly it is possible that you may get a useful solution. I am almost certain that compression is not the solution you need.

Cheers

tachyon

Not to get all pedantic on you, but a solution is to use a database. There are other solutions.

<–radiant.matrix–>
Ramblings and references
The Code that can be seen is not the true Code
I haven't found a problem yet that can't be solved by a well-placed trebuchet

If you will read below...you will see that i am using a database....:)

sub GammaCode
{
    my $n = $_[0];
    my $gammaCode;
    my $mystring;
    my $log = int(log2($n));
    return 1 if $n==1;
    for(1 .. $log)
    {
        $gammaCode .="1";
    }
    $gammaCode .="0";
    $mystring = dec2bin($n);
    $mystring =~ s/^\w{1}//; 

    $gammaCode .=$mystring;
    return $gammaCode;
}
sub log2 {
    my $n = shift;
    return log($n)/log(2);
    }



sub dec2bin {
    my $str = unpack("B32", pack("N", shift));
    $str =~ s/^0+(?=\d)//;   # otherwise you'll get leading zeros
    return $str;
}

sub bin2dec {
    return unpack("N", pack("B32", substr("0" x 32 . shift, -32)));
}
my $number=11;

print "The Gamma reprasentation of $number is\t",GammaCode($number),"\
+n";
[download]

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."

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