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     return LZT;
  63  }
  64
  65
  66
  67         // frees LZTrie structure, including the owned data
  68
  69 void destroyLZTrie(lztrie T)
  70  {
  71     destroyParentheses(T->pdata);
  72     free(T->letters);
  73     destroyNodemap(T->Node);
  74     destroyPosition(T->TPos);
  75     free(T->boost);
  76     free(T);
  77  }
  78
  79         // stores lztrie T on file f
  80
  81 void saveLZTrie (lztrie T, FILE *f)
  82  {
  83     if (fwrite (&T->n,sizeof(uint),1,f) != 1) {
  84        fprintf (stderr,"Error: Cannot write LZTrie on file\n");
  85        exit(1);
  86     }
  87     if (fwrite (T->data,sizeof(uint),(2*T->n+W-1)/W,f) != (2*T->n+W-1)/W) {
  88        fprintf (stderr,"Error: Cannot write LZTrie on file\n");
  89        exit(1);
  90     }
  91     if (fwrite (T->letters,sizeof(byte),T->n,f) != T->n) {
  92        fprintf (stderr,"Error: Cannot write LZTrie on file\n");
  93        exit(1);
  94     }
  95
  96     saveNodemap(f, T->Node);
  97     fwrite(&T->text_length, sizeof(uint), 1, f);
  98     savePosition(f, T->TPos);
  99  }
 100
 101         // loads lztrie T from file f
 102
 103 lztrie loadLZTrie (FILE *f)
 104  {
 105     lztrie T;
 106     int i;
 107     T = malloc (sizeof(struct slztrie));
 108     if (fread (&T->n,sizeof(uint),1,f) != 1) {
 109        fprintf (stderr,"Error: Cannot read LZTrie from file\n");
 110        exit(1);
 111     }
 112     T->data = malloc (((2*T->n+W-1)/W)*sizeof(uint));
 113     if (fread (T->data,sizeof(uint),(2*T->n+W-1)/W,f) != (2*T->n+W-1)/W) {
 114        fprintf (stderr,"Error: Cannot read LZTrie from file\n");
 115        exit(1);
 116     }
 117     T->pdata = createParentheses (T->data,2*T->n,true);
 118     T->nbits = bits(T->n-1);
 119     T->letters = malloc (T->n*sizeof(byte));
 120     if (fread (T->letters,sizeof(byte),T->n,f) != T->n) {
 121        fprintf (stderr,"Error: Cannot read LZTrie from file\n");
 122        exit(1);
 123     }
 124
 125     T->Node = loadNodemap(f);
 126     fread(&T->text_length, sizeof(uint), 1, f);
 127     T->TPos = loadPosition(f, T->text_length);
 128
 129     // boost first access
 130     T->boost = malloc(256*sizeof(trieNode));
 131     for (i=0;i<256;i++) T->boost[i] = NULLT;
 132     i = 1; // shortcut for first child of root
 133     while (i != 2*T->n-1) { // shortcut for its closing parenthesis
 134        T->boost[T->letters[i-rank(T->pdata->bdata,i)]] = i;
 135        // shortcut for leftrankLZTrie
 136        i = findclose(T->pdata,i)+1;
 137     }
 138
 139     return T;
 140  }
 141
 142
 143         // letter by which node i descends
 144
 145 byte letterLZTrie (lztrie T, trieNode i)
 146  {
 147     return T->letters[i-rank(T->pdata->bdata,i)]; // shortcut leftrankLZTrie
 148  }
 149
 150         // go down by letter c, if possible
 151
 152
 153 trieNode childLZTrie (lztrie T, trieNode i, byte c)
 154  {
 155     trieNode j;
 156     byte tc;
 157     j = i+1;
 158     while (!bitget1(T->data,j)) { // there is a child here
 159        tc = T->letters[j-rank(T->pdata->bdata,j)];
 160        // shortcut for leftrankLZTrie: is a child by letter c?
 161        if (tc > c) break;
 162        if (tc == c) return j;
 163        j = findclose(T->pdata,j)+1;
 164     }
 165     return NULLT; // no child to go down by c
 166  }
 167
 168         // go up, if possible
 169
 170 trieNode parentLZTrie (lztrie T, trieNode i)
 171  {
 172     if (i == ROOT) return NULLT; // parent of root
 173     if (T->boost[T->letters[i-rank(T->pdata->bdata,i)]] == i) return ROOT;
 174     return enclose (T->pdata,i);
 175  }
 176
 177         // subtree size
 178
 179 uint subtreesizeLZTrie (lztrie T, trieNode i)
 180  {
 181     trieNode j;
 182     j = findclose (T->pdata,i);
 183     return (j-i+1)/2;
 184  }
 185
 186         // depth
 187
 188 uint depthLZTrie (lztrie T, trieNode i)
 189  {
 190     return excess (T->pdata,i);
 191  }
 192
 193         // smallest rank in subtree
 194
 195 uint leftrankLZTrie (lztrie T, trieNode i)
 196
 197    { return i-rank(T->pdata->bdata,i);
 198    }
 199
 200         // largest rank in subtree
 201
 202 uint rightrankLZTrie (lztrie T, trieNode i)
 203  {
 204     trieNode j;
 205     j = findclose (T->pdata,i);
 206     return j-rank(T->pdata->bdata,j)-1;
 207  }
 208
 209         // is node i ancestor of node j?
 210
 211 bool ancestorLZTrie (lztrie T, trieNode i, trieNode j)
 212  {
 213     return (i <= j) && (j < findclose (T->pdata,i));
 214  }
 215
 216         // next node from i, in preorder, adds/decrements depth accordingly
 217         // assumes it *can* go on!
 218
 219 trieNode nextLZTrie (lztrie T, trieNode i, uint *depth)
 220  {
 221     uint *data = T->data;
 222     i++;
 223     while (bitget1(data,i)) { i++; (*depth)--; }
 224     (*depth)++;
 225     return i;
 226  }
 227
 228
 229 // extracts text from position "from" up to position "to".
 230 // Parameter "snippet_length" is the actual length of the snippet extracted.
 231 // The extracted text is stored in array "snippet".
 232 //
 233 void extract(lztrie T,
 234              ulong from,
 235              ulong to,
 236              byte **snippet,
 237              ulong *snippet_length)
 238  {
 239     ulong snpp_pos, posaux, idaux;
 240     uint idfrom,idto;
 241     trieNode p;
 242     byte *snppt;
 243     nodemap Node = T->Node;
 244
 245     if (to > (T->text_length-1)) to = T->text_length-1;
 246     if (from > (T->text_length-1)) from = T->text_length-1;
 247
 248     *snippet_length = to-from+1;
 249     *snippet = malloc(*snippet_length);
 250
 251     idfrom = getphrasePosition(T->TPos, from);
 252     idto   = getphrasePosition(T->TPos, to+1);
 253    // *snippet_length = to-from+1;
 254
 255     posaux = getPosition(T->TPos, idto+1)-1;
 256     p = mapto(Node, idto);
 257
 258     while (p&&(posaux > to)) {
 259        p = parentLZTrie(T, p);
 260        posaux--;
 261     }
 262
 263     snpp_pos = (*snippet_length)-1;
 264     snppt = *snippet;
 265
 266     for (idaux = idto; idaux != idfrom;) {
 267        while (p) {
 268           snppt[snpp_pos--] = letterLZTrie(T, p);
 269           p = parentLZTrie(T, p);
 270        }
 271        p = mapto(Node, --idaux);
 272     }
 273     if (idfrom != idto) posaux = getPosition(T->TPos, idfrom+1)-(from!=0);
 274     while (p && (posaux >= from)) {
 275        snppt[snpp_pos--] = letterLZTrie(T, p);
 276        p = parentLZTrie(T, p);
 277        posaux--;
 278     }
 279  }
 280
 281 uint sizeofLZTrie(lztrie T)
 282  {
 283     return sizeof(struct slztrie) +
 284            sizeofParentheses(T->pdata) +
 285            T->n*sizeof(byte) +
 286            sizeofNodemap(T->Node) +
 287            sizeofPosition(T->TPos);
 288  }