lzindex/lztrie.c

   1
   2
   3 // Implements the LZtrie data structure
   4
   5 #include "lztrie.h"
   6
   7         // creates a lztrie structure from a parentheses bitstring,
   8         // a letter array in preorder, and an id array in preorder,
   9         // all of which except the latter become owned
  10         // n is the total number of nodes (n letters/ids, 2n parentheses)
  11
  12 lztrie createLZTrie(uint *string, byte *letters, uint *Node, uint n, uint text_length)
  13  {
  14     lztrie T;
  15     int i;
  16     T = malloc(sizeof(struct slztrie));
  17     T->data = string;
  18     T->pdata = createParentheses(string,2*n,true);
  19     T->n = n;
  20     T->nbits = bits(n-1);
  21     T->letters = letters;
  22     T->Node = createNodemap(Node, n, n);
  23     T->TPos = createPosition(T, text_length);
  24     T->text_length = text_length;
  25     // boost first access
  26     T->boost   = malloc(256*sizeof(trieNode));
  27     for (i=0;i<256;i++) T->boost[i] = NULLT;
  28     i = 1; // shortcut for first child of root
  29     while (i != 2*n-1) { // shortcut for its closing parenthesis
  30        T->boost[T->letters[i-rank(T->pdata->bdata,i)]] = i;
  31        // shortcut for leftrankLZTrie
  32        i = findclose(T->pdata,i)+1;
  33     }
  34     return T;
  35  }
  36
  37 // builds an lztrie from a text. "s" is the text terminator.
  38 lztrie buildLZTrie(byte *text, byte s, uint text_length)
  39  {
  40     trie T;
  41     uint n;
  42     uint *parent;
  43     byte *letters;
  44     lztrie LZT;
  45     uint *Node;
  46     // first creates a full trie T
  47     T = createTrie();
  48     do {
  49        text = insertTrie(T,text);
  50     }
  51     while (text[-1] != s);
  52     // now compresses it
  53     n           = T->nid;
  54     parent = malloc(((2*n+W-1)/W)*sizeof(uint));
  55     letters = malloc(n*sizeof(byte));
  56     // Aqui pedir espacio para Node, ver como lo voy a construir en vez de sacar solo los ids
  57     Node = malloc(n*sizeof(uint));
  58     representTrie(T,parent,letters,Node);
  59
  60     destroyTrie(T);
  61     LZT = createLZTrie(parent,letters,Node,n,text_length);
  62
  63     free(Node); Node = 0;
  64     return LZT;
  65  }
  66
  67
  68
  69         // frees LZTrie structure, including the owned data
  70
  71 void destroyLZTrie(lztrie T)
  72  {
  73     destroyParentheses(T->pdata);
  74     free(T->letters);
  75     destroyNodemap(T->Node);
  76     destroyPosition(T->TPos);
  77     free(T->boost);
  78
  79     free(T);
  80  }
  81
  82         // stores lztrie T on file f
  83
  84 void saveLZTrie (lztrie T, FILE *f)
  85  {
  86     if (fwrite (&T->n,sizeof(uint),1,f) != 1) {
  87        fprintf (stderr,"Error: Cannot write LZTrie on file\n");
  88        exit(1);
  89     }
  90     if (fwrite (T->data,sizeof(uint),(2*T->n+W-1)/W,f) != (2*T->n+W-1)/W) {
  91        fprintf (stderr,"Error: Cannot write LZTrie on file\n");
  92        exit(1);
  93     }
  94     if (fwrite (T->letters,sizeof(byte),T->n,f) != T->n) {
  95        fprintf (stderr,"Error: Cannot write LZTrie on file\n");
  96        exit(1);
  97     }
  98
  99     saveNodemap(f, T->Node);
 100     fwrite(&T->text_length, sizeof(uint), 1, f);
 101     savePosition(f, T->TPos);
 102  }
 103
 104         // loads lztrie T from file f
 105
 106 lztrie loadLZTrie (FILE *f)
 107  {
 108     lztrie T;
 109     int i;
 110     T = malloc (sizeof(struct slztrie));
 111     if (fread (&T->n,sizeof(uint),1,f) != 1) {
 112        fprintf (stderr,"Error: Cannot read LZTrie from file\n");
 113        exit(1);
 114     }
 115     T->data = malloc (((2*T->n+W-1)/W)*sizeof(uint));
 116     if (fread (T->data,sizeof(uint),(2*T->n+W-1)/W,f) != (2*T->n+W-1)/W) {
 117        fprintf (stderr,"Error: Cannot read LZTrie from file\n");
 118        exit(1);
 119     }
 120     T->pdata = createParentheses (T->data,2*T->n,true);
 121     T->nbits = bits(T->n-1);
 122     T->letters = malloc (T->n*sizeof(byte));
 123     if (fread (T->letters,sizeof(byte),T->n,f) != T->n) {
 124        fprintf (stderr,"Error: Cannot read LZTrie from file\n");
 125        exit(1);
 126     }
 127
 128     T->Node = loadNodemap(f);
 129     fread(&T->text_length, sizeof(uint), 1, f);
 130     T->TPos = loadPosition(f, T->text_length);
 131
 132     // boost first access
 133     T->boost = malloc(256*sizeof(trieNode));
 134     for (i=0;i<256;i++) T->boost[i] = NULLT;
 135     i = 1; // shortcut for first child of root
 136     while (i != 2*T->n-1) { // shortcut for its closing parenthesis
 137        T->boost[T->letters[i-rank(T->pdata->bdata,i)]] = i;
 138       // shortcut for leftrankLZTrie
 139        i = findclose(T->pdata,i)+1;
 140     }
 141
 142     return T;
 143  }
 144
 145
 146         // letter by which node i descends
 147
 148 byte letterLZTrie (lztrie T, trieNode i)
 149  {
 150     return T->letters[i-rank(T->pdata->bdata,i)]; // shortcut leftrankLZTrie
 151  }
 152
 153         // go down by letter c, if possible
 154
 155
 156 trieNode childLZTrie (lztrie T, trieNode i, byte c)
 157  {
 158     trieNode j;
 159     byte tc;
 160     j = i+1;
 161     while (!bitget1(T->data,j)) { // there is a child here
 162        tc = T->letters[j-rank(T->pdata->bdata,j)];
 163        // shortcut for leftrankLZTrie: is a child by letter c?
 164        if (tc > c) break;
 165        if (tc == c) return j;
 166        j = findclose(T->pdata,j)+1;
 167     }
 168     return NULLT; // no child to go down by c
 169  }
 170
 171         // go up, if possible
 172
 173 trieNode parentLZTrie (lztrie T, trieNode i)
 174  {
 175     if (i == ROOT) return NULLT; // parent of root
 176     if (T->boost[T->letters[i-rank(T->pdata->bdata,i)]] == i) return ROOT;
 177     return _enclose (T->pdata,i);
 178  }
 179
 180         // subtree size
 181
 182 uint subtreesizeLZTrie (lztrie T, trieNode i)
 183  {
 184     trieNode j;
 185     j = findclose (T->pdata,i);
 186     return (j-i+1)/2;
 187  }
 188
 189         // depth
 190
 191 uint depthLZTrie (lztrie T, trieNode i)
 192  {
 193     return excess (T->pdata,i);
 194  }
 195
 196         // smallest rank in subtree
 197
 198 uint leftrankLZTrie (lztrie T, trieNode i)
 199
 200    { return i-rank(T->pdata->bdata,i);
 201    }
 202
 203         // largest rank in subtree
 204
 205 uint rightrankLZTrie (lztrie T, trieNode i)
 206  {
 207     trieNode j;
 208     j = findclose (T->pdata,i);
 209     return j-rank(T->pdata->bdata,j)-1;
 210  }
 211
 212         // is node i ancestor of node j?
 213
 214 bool ancestorLZTrie (lztrie T, trieNode i, trieNode j)
 215  {
 216     return (i <= j) && (j < findclose (T->pdata,i));
 217  }
 218
 219         // next node from i, in preorder, adds/decrements depth accordingly
 220         // assumes it *can* go on!
 221
 222 trieNode nextLZTrie (lztrie T, trieNode i, uint *depth)
 223  {
 224     uint *data = T->data;
 225     i++;
 226     while (bitget1(data,i)) { i++; (*depth)--; }
 227     (*depth)++;
 228     return i;
 229  }
 230
 231
 232 // extracts text from position "from" up to position "to".
 233 // Parameter "snippet_length" is the actual length of the snippet extracted.
 234 // The extracted text is stored in array "snippet".
 235 //
 236 void extract(lztrie T,
 237              ulong from,
 238              ulong to,
 239              byte **snippet,
 240              ulong *snippet_length)
 241  {
 242     ulong snpp_pos, posaux, idaux;
 243     uint idfrom,idto;
 244     trieNode p;
 245     byte *snppt;
 246     nodemap Node = T->Node;
 247
 248     if (to > (T->text_length-1)) to = T->text_length-1;
 249     if (from > (T->text_length-1)) from = T->text_length-1;
 250
 251     *snippet_length = to-from+1;
 252     *snippet = malloc(*snippet_length);
 253
 254     idfrom = getphrasePosition(T->TPos, from);
 255     idto   = getphrasePosition(T->TPos, to+1);
 256    // *snippet_length = to-from+1;
 257
 258     posaux = getPosition(T->TPos, idto+1)-1;
 259     p = mapto(Node, idto);
 260
 261     while (p&&(posaux > to)) {
 262        p = parentLZTrie(T, p);
 263        posaux--;
 264     }
 265
 266     snpp_pos = (*snippet_length)-1;
 267     snppt = *snippet;
 268
 269     for (idaux = idto; idaux != idfrom;) {
 270        while (p) {
 271           snppt[snpp_pos--] = letterLZTrie(T, p);
 272           p = parentLZTrie(T, p);
 273        }
 274        p = mapto(Node, --idaux);
 275     }
 276     if (idfrom != idto) posaux = getPosition(T->TPos, idfrom+1)-(from!=0);
 277     while (p && (posaux >= from)) {
 278        snppt[snpp_pos--] = letterLZTrie(T, p);
 279        p = parentLZTrie(T, p);
 280        posaux--;
 281     }
 282  }
 283
 284 uint sizeofLZTrie(lztrie T)
 285  {
 286     return sizeof(struct slztrie) +
 287            sizeofParentheses(T->pdata) +
 288            T->n*sizeof(byte) +
 289            sizeofNodemap(T->Node) +
 290            sizeofPosition(T->TPos);
 291  }