lzindex/position.c

   1
   2 // This code implements the data structure to get
   3 // "real" text positions at search time.
   4
   5 #include "position.h"
   6 #include "lztrie.h"
   7 #include <math.h>
   8
   9
  10 position createPosition(void *Taux, uint text_length)
  11  {
  12     position P;
  13     lztrie T = (lztrie) Taux;
  14     uint *Offset;
  15     ulong n, M, superblock_size, current_superblock,
  16           starting_pos, i, depth, pos;
  17     trieNode node;
  18
  19     P = malloc(sizeof(struct tpos));
  20     n = T->n;
  21     P->SBlock_size = 32;//bits(n-1); // superblock size is log n
  22     P->nbitsSB     = bits(text_length-1);
  23     P->nSuperBlock = (ulong)ceil((double)n/P->SBlock_size); // number of superblocks
  24     P->SuperBlock  = malloc(((P->nbitsSB*P->nSuperBlock+W-1)/W)*sizeof(uint));
  25     P->Tlength     = text_length;
  26     M = 0; // maximum superblock size (in number of characters)
  27
  28     current_superblock = 0;
  29     superblock_size    = 0;
  30     starting_pos       = 0;
  31     P->nOffset         = n;
  32     Offset = malloc(n*sizeof(uint)); // array for temporary use
  33
  34     bitput(P->SuperBlock, 0, P->nbitsSB, 0);
  35
  36     for (i = 0, pos = 0; i < n; i++) {
  37        node = mapto(T->Node, i);
  38        depth = depthLZTrie(T, node);
  39        pos += depth;
  40
  41        superblock_size++;
  42
  43        if ((superblock_size > P->SBlock_size) || (i==0)) {
  44           if (i)
  45              bitput(P->SuperBlock,P->nbitsSB*(++current_superblock),P->nbitsSB,pos);
  46           if (i!=0 && Offset[i-1]>M) M = Offset[i-1];
  47           superblock_size = 1;
  48           starting_pos = pos;
  49        }
  50
  51        Offset[i] = pos-starting_pos;
  52     }
  53
  54     if (Offset[i-1]>M) M = Offset[i-1];
  55
  56     P->nbitsOffs = bits(M-1);
  57     P->Offset    = malloc(((P->nOffset*P->nbitsOffs+W-1)/W)*sizeof(uint));
  58     for (i = 0; i < n; i++)
  59        bitput(P->Offset, i*P->nbitsOffs, P->nbitsOffs, Offset[i]);
  60
  61     free(Offset);
  62
  63     return P;
  64  }
  65
  66
  67 // given a phrase id, gets the corresponding text position
  68
  69 ulong getPosition(position P, uint id)
  70  {
  71      if (id > P->nOffset) return P->Tlength;
  72      else {
  73        ulong posSB = (id-1)>>5;///P->SBlock_size;//(ulong)ceil((double)id/P->SBlock_size)-1;
  74        return bitget(P->SuperBlock,posSB*P->nbitsSB,P->nbitsSB)
  75             + bitget(P->Offset,(id-1)*P->nbitsOffs,P->nbitsOffs);
  76      }
  77  }
  78
  79
  80 // given a text position, gets the identifier of the
  81 // LZ78 phrase containing that position
  82
  83 ulong getphrasePosition(position P, ulong text_pos)
  84  {
  85     ulong li, ls, nbits, elem, med, SB, temp, i;
  86
  87     li = 0;
  88     ls = P->nSuperBlock-1;
  89     nbits = P->nbitsSB;
  90     while ((ls-li+1) > 0) {
  91        med  = (li+ls)/2;
  92        elem = bitget(P->SuperBlock,med*nbits,nbits);
  93        if (elem == text_pos) break;
  94        if (elem < text_pos) li = med+1;
  95        else ls = med - 1;
  96     }
  97     if (elem > text_pos && med) med--;
  98     SB = bitget(P->SuperBlock,med*nbits,nbits);
  99
 100     temp = li;
 101     li = med*P->SBlock_size;
 102
 103     if (med+1 == P->nSuperBlock)
 104        ls = P->nOffset-1;
 105     else
 106        ls = (med+1)*P->SBlock_size - 1;
 107
 108     nbits = P->nbitsOffs;
 109
 110     while ((ls-li+1) > 8) {
 111        med  = (li+ls)/2;
 112        elem = bitget(P->Offset,med*nbits,nbits)+SB;
 113        if (elem == text_pos) break;
 114        if (elem < text_pos) li = med+1;
 115        else ls = med-1;
 116     }
 117
 118     for (i = li; i <= ls; i++)
 119       if ((elem=bitget(P->Offset,i*nbits,nbits) + SB) >= text_pos) break;
 120
 121     if (elem > text_pos) i--;
 122
 123     return i+(elem>text_pos);
 124  }
 125
 126
 127 ulong sizeofPosition(position P)
 128  {
 129     return sizeof(struct tpos)
 130           + ((P->nbitsSB*P->nSuperBlock+W-1)/W)*sizeof(uint)
 131           + ((P->nOffset*P->nbitsOffs+W-1)/W)*sizeof(uint);
 132  }
 133
 134 void destroyPosition(position P)
 135  {
 136     if (!P) return;
 137     free(P->SuperBlock);
 138     free(P->Offset);
 139  }
 140
 141
 142 position loadPosition(FILE *f, uint text_length)
 143  {
 144     position P;
 145     uint aux;
 146
 147     P = malloc (sizeof(struct tpos));
 148
 149     if (fread(&P->nSuperBlock,sizeof(uint),1,f) != 1) {
 150        fprintf(stderr,"Error: Cannot read LZTrie from file\n");
 151        exit(1);
 152     }
 153
 154     P->nbitsSB = bits(text_length-1);
 155     aux = (((unsigned long long) P->nbitsSB*P->nSuperBlock+W-1)/W);
 156     P->SuperBlock  = malloc(aux*sizeof(uint));
 157
 158     if (fread(P->SuperBlock,sizeof(uint),aux,f) != aux) {
 159        fprintf(stderr,"Error: Cannot read LZTrie from file\n");
 160        exit(1);
 161     }
 162
 163     P->SBlock_size = 32;
 164
 165     P->Tlength = text_length;
 166
 167     if (fread(&P->nOffset,sizeof(uint),1,f) != 1) {
 168        fprintf(stderr,"Error: Cannot read LZTrie from file\n");
 169        exit(1);
 170     }
 171
 172     if (fread(&P->nbitsOffs,sizeof(uint),1,f) != 1) {
 173        fprintf(stderr,"Error: Cannot read LZTrie from file\n");
 174        exit(1);
 175     }
 176
 177     aux = (((unsigned long long)P->nOffset*P->nbitsOffs+W-1)/W);
 178     P->Offset    = malloc(aux*sizeof(uint));
 179     if (fread(P->Offset,sizeof(uint),aux,f) != aux) {
 180        fprintf(stderr,"Error: Cannot read LZTrie from file\n");
 181        exit(1);
 182     }
 183
 184     return P;
 185  }
 186
 187
 188 void savePosition(FILE *f, position P)
 189  {
 190     uint aux;
 191
 192     if (fwrite(&P->nSuperBlock,sizeof(uint),1,f) != 1) {
 193        fprintf(stderr,"Error: Cannot write LZTrie on file\n");
 194        exit(1);
 195     }
 196
 197     aux = (((unsigned long long) P->nbitsSB*P->nSuperBlock+W-1)/W);
 198
 199     if (fwrite(P->SuperBlock,sizeof(uint),aux,f) != aux) {
 200        fprintf(stderr,"Error: Cannot write LZTrie on file\n");
 201        exit(1);
 202     }
 203
 204     if (fwrite(&P->nOffset,sizeof(uint),1,f) != 1) {
 205        fprintf(stderr,"Error: Cannot write LZTrie on file\n");
 206        exit(1);
 207     }
 208
 209     if (fwrite(&P->nbitsOffs,sizeof(uint),1,f) != 1) {
 210        fprintf(stderr,"Error: Cannot write LZTrie on file\n");
 211        exit(1);
 212     }
 213
 214     aux = (((unsigned long long)P->nOffset*P->nbitsOffs+W-1)/W);
 215
 216     if (fwrite(P->Offset,sizeof(uint),aux,f) != aux) {
 217        fprintf(stderr,"Error: Cannot write LZTrie on file\n");
 218        exit(1);
 219     }
 220  }
 221
 222
 223