2 * Copyright (C) 2011, Antonio Fariña and Eduardo Rodriguez, all rights reserved.
4 * icsa.c: Implementation of the interface "../intIndex/interfaceIntIndex.h"
5 * that permits to represent a sequence of uint32 integers with an iCSA:
6 * An integer-oriented Compressed Suffix Array.
7 * Such representation will be handled as a "ticsa" data structure, that
8 * the WCSA self-index will use (as an opaque type) to
9 * create/save/load/search/recover/getSize of the representation of the
11 * Suffix sorting is done via Larson/Sadakane suffix sort algorithm
12 * from the char-based csa.
14 * Ref: Larsson, N. J. and Sadakane, K. 2007. Faster suffix sorting. Theoretical
15 * Computer Science 387, 3, 258–272.
18 * See more details in:
19 * Antonio Fariña, Nieves Brisaboa, Gonzalo Navarro, Francisco Claude, Ángeles Places,
20 * and Eduardo Rodríguez. Word-based Self-Indexes for Natural Language Text. ACM
21 * Transactions on Information Systems (TOIS), 2012.
22 * http://vios.dc.fi.udc.es/indexing/wsi/publications.html
23 * http://www.dcc.uchile.cl/~gnavarro/ps/tois11.pdf
25 * This library is free software; you can redistribute it and/or
26 * modify it under the terms of the GNU Lesser General Public
27 * License as published by the Free Software Foundation; either
28 * version 2.1 of the License, or (at your option) any later version.
30 * This library is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
33 * Lesser General Public License for more details.
35 * You should have received a copy of the GNU Lesser General Public
36 * License along with this library; if not, write to the Free Software
37 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
44 #define KEY(p) (V[*(p)+(h)])
45 #define SWAP(p, q) (tmp=*(p), *(p)=*(q), *(q)=tmp)
46 #define MED3(a, b, c) (KEY(a)<KEY(b) ? \
47 (KEY(b)<KEY(c) ? (b) : KEY(a)<KEY(c) ? (c) : (a)) \
48 : (KEY(b)>KEY(c) ? (b) : KEY(a)>KEY(c) ? (c) : (a)))
50 static int *I, /* group array, ultimately suffix array.*/
51 *V, /* inverse array, ultimately inverse of I.*/
52 r, /* number of symbols aggregated by transform.*/
53 h; /* length of already-sorted prefixes.*/
55 /* Subroutine for select_sort_split and sort_split. Sets group numbers for a
56 group whose lowest position in I is pl and highest position is pm.*/
58 static void update_group(int *pl, int *pm)
62 g=pm-I; /* group number.*/
63 V[*pl]=g; /* update group number of first position.*/
65 *pl=-1; /* one element, sorted group.*/
67 do /* more than one element, unsorted group.*/
68 V[*++pl]=g; /* update group numbers.*/
72 /* Quadratic sorting method to use for small subarrays. To be able to update
73 group numbers consistently, a variant of selection sorting is used.*/
75 static void select_sort_split(int *p, int n) {
76 int *pa, *pb, *pi, *pn;
79 pa=p; /* pa is start of group being picked out.*/
80 pn=p+n-1; /* pn is last position of subarray.*/
82 for (pi=pb=pa+1, f=KEY(pa); pi<=pn; ++pi)
84 f=v; /* f is smallest key found.*/
85 SWAP(pi, pa); /* place smallest element at beginning.*/
86 pb=pa+1; /* pb is position for elements equal to f.*/
87 } else if (v==f) { /* if equal to smallest key.*/
88 SWAP(pi, pb); /* place next to other smallest elements.*/
91 update_group(pa, pb-1); /* update group values for new group.*/
92 pa=pb; /* continue sorting rest of the subarray.*/
94 if (pa==pn) { /* check if last part is single element.*/
96 *pa=-1; /* sorted group.*/
100 /* Subroutine for sort_split, algorithm by Bentley & McIlroy.*/
102 static int choose_pivot(int *p, int n) {
106 pm=p+(n>>1); /* small arrays, middle element.*/
110 if (n>40) { /* big arrays, pseudomedian of 9.*/
112 pl=MED3(pl, pl+s, pl+s+s);
113 pm=MED3(pm-s, pm, pm+s);
114 pn=MED3(pn-s-s, pn-s, pn);
116 pm=MED3(pl, pm, pn); /* midsize arrays, median of 3.*/
121 /* Sorting routine called for each unsorted group. Sorts the array of integers
122 (suffix numbers) of length n starting at p. The algorithm is a ternary-split
123 quicksort taken from Bentley & McIlroy, "Engineering a Sort Function",
124 Software -- Practice and Experience 23(11), 1249-1265 (November 1993). This
125 function is based on Program 7.*/
127 static void sort_split(int *p, int n)
129 int *pa, *pb, *pc, *pd, *pl, *pm, *pn;
132 if (n<7) { /* multi-selection sort smallest arrays.*/
133 select_sort_split(p, n);
137 v=choose_pivot(p, n);
140 while (1) { /* split-end partition.*/
141 while (pb<=pc && (f=KEY(pb))<=v) {
148 while (pc>=pb && (f=KEY(pc))>=v) {
162 if ((s=pa-p)>(t=pb-pa))
164 for (pl=p, pm=pb-s; s; --s, ++pl, ++pm)
166 if ((s=pd-pc)>(t=pn-pd-1))
168 for (pl=pb, pm=pn-s; s; --s, ++pl, ++pm)
175 update_group(p+s, p+n-t-1);
177 sort_split(p+n-t, t);
180 /* Bucketsort for first iteration.
182 Input: x[0...n-1] holds integers in the range 1...k-1, all of which appear
183 at least once. x[n] is 0. (This is the corresponding output of transform.) k
184 must be at most n+1. p is array of size n+1 whose contents are disregarded.
186 Output: x is V and p is I after the initial sorting stage of the refined
187 suffix sorting algorithm.*/
189 static void bucketsort(int *x, int *p, int n, int k)
193 for (pi=p; pi<p+k; ++pi)
194 *pi=-1; /* mark linked lists empty.*/
195 for (i=0; i<=n; ++i) {
196 x[i]=p[c=x[i]]; /* insert in linked list.*/
199 for (pi=p+k-1, i=n; pi>=p; --pi) {
200 d=x[c=*pi]; /* c is position, d is next in list.*/
201 x[c]=g=i; /* last position equals group number.*/
202 if (d>=0) { /* if more than one element in group.*/
203 p[i--]=c; /* p is permutation for the sorted x.*/
205 d=x[c=d]; /* next in linked list.*/
206 x[c]=g; /* group number in x.*/
207 p[i--]=c; /* permutation in p.*/
210 p[i--]=-1; /* one element, sorted group.*/
214 /* Transforms the alphabet of x by attempting to aggregate several symbols into
215 one, while preserving the suffix order of x. The alphabet may also be
216 compacted, so that x on output comprises all integers of the new alphabet
217 with no skipped numbers.
219 Input: x is an array of size n+1 whose first n elements are positive
220 integers in the range l...k-1. p is array of size n+1, used for temporary
221 storage. q controls aggregation and compaction by defining the maximum value
222 for any symbol during transformation: q must be at least k-l; if q<=n,
223 compaction is guaranteed; if k-l>n, compaction is never done; if q is
224 INT_MAX, the maximum number of symbols are aggregated into one.
226 Output: Returns an integer j in the range 1...q representing the size of the
227 new alphabet. If j<=n+1, the alphabet is compacted. The global variable r is
228 set to the number of old symbols grouped into one. Only x[n] is 0.*/
230 static int transform(int *x, int *p, int n, int k, int l, int q)
232 int b, c, d, e, i, j, m, s;
235 for (s=0, i=k-l; i; i>>=1)
236 ++s; /* s is number of bits in old symbol.*/
237 e=INT_MAX>>s; /* e is for overflow checking.*/
238 for (b=d=r=0; r<n && d<=e && (c=d<<s|(k-l))<=q; ++r) {
239 b=b<<s|(x[r]-l+1); /* b is start of x in chunk alphabet.*/
240 d=c; /* d is max symbol in chunk alphabet.*/
242 m=(1<<(r-1)*s)-1; /* m masks off top old symbol from chunk.*/
243 x[n]=l-1; /* emulate zero terminator.*/
244 if (d<=n) { /* if bucketing possible, compact alphabet.*/
245 for (pi=p; pi<=p+d; ++pi)
246 *pi=0; /* zero transformation table.*/
247 for (pi=x+r, c=b; pi<=x+n; ++pi) {
248 p[c]=1; /* mark used chunk symbol.*/
249 c=(c&m)<<s|(*pi-l+1); /* shift in next old symbol in chunk.*/
251 for (i=1; i<r; ++i) { /* handle last r-1 positions.*/
252 p[c]=1; /* mark used chunk symbol.*/
253 c=(c&m)<<s; /* shift in next old symbol in chunk.*/
255 for (pi=p, j=1; pi<=p+d; ++pi)
257 *pi=j++; /* j is new alphabet size.*/
258 for (pi=x, pj=x+r, c=b; pj<=x+n; ++pi, ++pj) {
259 *pi=p[c]; /* transform to new alphabet.*/
260 c=(c&m)<<s|(*pj-l+1); /* shift in next old symbol in chunk.*/
262 while (pi<x+n) { /* handle last r-1 positions.*/
263 *pi++=p[c]; /* transform to new alphabet.*/
264 c=(c&m)<<s; /* shift right-end zero in chunk.*/
266 } else { /* bucketing not possible, don't compact.*/
267 for (pi=x, pj=x+r, c=b; pj<=x+n; ++pi, ++pj) {
268 *pi=c; /* transform to new alphabet.*/
269 c=(c&m)<<s|(*pj-l+1); /* shift in next old symbol in chunk.*/
271 while (pi<x+n) { /* handle last r-1 positions.*/
272 *pi++=c; /* transform to new alphabet.*/
273 c=(c&m)<<s; /* shift right-end zero in chunk.*/
275 j=d+1; /* new alphabet size.*/
277 x[n]=0; /* end-of-string symbol is zero.*/
278 return j; /* return new alphabet size.*/
281 /* Makes suffix array p of x. x becomes inverse of p. p and x are both of size
282 n+1. Contents of x[0...n-1] are integers in the range l...k-1. Original
283 contents of x[n] is disregarded, the n-th symbol being regarded as
284 end-of-string smaller than all other symbols.*/
286 void suffixsort(int *x, int *p, int n, int k, int l)
291 V=x; /* set global values.*/
294 if (n>=k-l) { /* if bucketing possible,*/
295 j=transform(V, I, n, k, l, n);
296 bucketsort(V, I, n, j); /* bucketsort on first r positions.*/
298 transform(V, I, n, k, l, INT_MAX);
300 I[i]=i; /* initialize I with suffix numbers.*/
302 sort_split(I, n+1); /* quicksort on first r positions.*/
304 h=r; /* number of symbols aggregated by transform.*/
307 pi=I; /* pi is first position of group.*/
308 sl=0; /* sl is negated length of sorted groups.*/
311 pi-=s; /* skip over sorted group.*/
312 sl+=s; /* add negated length to sl.*/
315 *(pi+sl)=sl; /* combine sorted groups before pi.*/
318 pk=I+V[s]+1; /* pk-1 is last position of unsorted group.*/
319 sort_split(pi, pk-pi);
320 pi=pk; /* next group.*/
323 if (sl) /* if the array ends with a sorted group.*/
324 *(pi+sl)=sl; /* combine sorted groups at end of I.*/
325 h=2*h; /* double sorted-depth.*/
328 for (i=0; i<=n; ++i) /* reconstruct suffix array from inverse.*/
333 //ticsa *createIntegerCSA(uint **intVector, uint textSize, char *build_options) {
334 int buildIntIndex (uint *intVector, uint n, char *build_options, void **index ){
337 myicsa = (ticsa *) malloc (sizeof (ticsa));
338 uint *Psi, *SAI, *C, vocSize;
342 parametersCSA(myicsa, build_options);
344 nsHUFF=myicsa->tempNSHUFF;
346 // Almacenamos o valor dalguns parametros
348 myicsa->suffixArraySize = textSize;
349 myicsa->D = (uint*) malloc (sizeof(uint) * ((textSize+31)/32));
351 myicsa->samplesASize = (textSize + myicsa->T_A - 1) / myicsa->T_A + 1; //--> última pos siempre sampleada!
352 // myicsa->samplesASize = (textSize + myicsa->T_A - 1) / myicsa->T_A ;//+ 1;
353 myicsa->samplesA = (uint *)malloc(sizeof(uint) * myicsa->samplesASize);
354 myicsa->samplesA[myicsa->samplesASize-1] = 0000;
355 myicsa->BA = (uint*) malloc (sizeof(uint) * ((textSize+31)/32));
356 myicsa->samplesAInvSize = (textSize + myicsa->T_AInv - 1) / myicsa->T_AInv;
357 myicsa->samplesAInv = (uint *)malloc(sizeof(int) * myicsa->samplesAInvSize);
359 // CONSTRUIMOS A FUNCION C
361 for(i=0;i<textSize;i++) if(intVector[i]>vocSize) vocSize = intVector[i];
362 C = (uint *) malloc(sizeof(uint) * (vocSize + 1)); // Para contar o 0 terminador
363 for(i=0;i<vocSize;i++) C[i] = 0;
364 for(i=0;i<textSize;i++) C[intVector[i]]++;
365 for (i=0,j=0;i<=vocSize;i++) {
369 for(i=vocSize;i>0;i--) C[i] = C[i-1];
372 // Reservamos espacio para os array de sufijos
373 Psi = (uint *) malloc (sizeof(uint) * (textSize+1));
374 printf("\n\t *BUILDING THE SUFFIX ARRAY over %d integers... (with larsson-sadakane)", textSize);fflush(stdout);
376 /* Makes suffix array p of x. x becomes inverse of p. p and x are both of size
377 n+1. Contents of x[0...n-1] are integers in the range l...k-1. Original
378 contents of x[n] is disregarded, the n-th symbol being regarded as
379 end-of-string smaller than all other symbols.*/
380 //void suffixsort(int *x, int *p, int n, int k, int l)
382 //suffixsort((int *)intVector, (int *)Psi, n, vocSize+1, 1);
383 suffixsort((int *)intVector, (int *)Psi, n-1, vocSize+1, 1);
384 //*Psi = *Psi++; // Con esto temos o array de sufixos desde a primeira posición (sen o terminador)
385 printf("\n\t ...... ended.");
389 // CONSTRUIMOS A INVERSA DO ARRAY DE SUFIXOS
390 //SAI = (uint *) malloc (sizeof(uint) * (textSize + 1)); // +1 para repetir na ultima posición. Evitamos un if
391 //for(i=0;i<textSize;i++) SAI[Psi[i]] = i;
392 //SAI[textSize] = SAI[0];
396 SAI = (uint *) malloc (sizeof(uint) * (textSize + 1)); // +1 para repetir na ultima posición. Evitamos un if
397 for(i=0;i<textSize;i++) SAI[i] = intVector[i];
398 SAI[textSize] = SAI[0];
400 //SAI[textSize] = SAI[0];
402 // ALMACENAMOS AS MOSTRAS DO ARRAY DE SUFIXOS
403 for(i=0;i<((textSize+31)/32);i++) myicsa->BA[i] = 0;
404 for(i=0; i<textSize; i+=myicsa->T_A) bitset(myicsa->BA, SAI[i]);
405 bitset(myicsa->BA, SAI[textSize-1]); // A ultima posicion sempre muestreada
406 //printf("TextSize = %d\n", textSize);
407 myicsa->bBA = createBitmap(myicsa->BA, textSize);
408 for(i=0,j=0; i<textSize; i++) if(bitget(myicsa->BA, i)) myicsa->samplesA[j++] = Psi[i];
410 // ALMACENAMOS AS MOSTRAS DA INVERSA DO ARRAY DE SUFIXOS
411 for(i=0,j=0;i<textSize;i+=myicsa->T_AInv) myicsa->samplesAInv[j++] = SAI[i];
413 // CONSTRUIMOS E COMPRIMIMOS PSI
414 printf("\n\t Creating compressed Psi...");
415 for(i=0;i<textSize;i++) Psi[i] = SAI[Psi[i]+1];
417 //FILE *ff = fopen("psi.log","w");
418 //for (i=0;i<textSize;i++) fprintf(ff,"%d::%u",i,Psi[i]);
424 #ifdef PSI_HUFFMANRLE
425 myicsa->hcPsi = huffmanCompressPsi(Psi,textSize,myicsa->T_Psi,nsHUFF);
428 myicsa->gcPsi = gonzaloCompressPsi(Psi,textSize,myicsa->T_Psi,nsHUFF);
430 #ifdef PSI_DELTACODES
431 myicsa->dcPsi = deltaCompressPsi(Psi,textSize,myicsa->T_Psi);
437 for(i=0;i<((textSize+31)/32);i++) myicsa->D[i] = 0;
438 for(i=0;i<=vocSize;i++) bitset(myicsa->D, C[i]);
439 myicsa->bD = createBitmap(myicsa->D,textSize);
442 // VARIABLE GLOBAL QUE ALMACENA O ESTADO DOS DISPLAYS (IMPORTANTE PARA DISPLAY SECUENCIAL)
443 // Almacena a última posición do array de sufixos que mostramos con display ou displayNext
444 // Se nos piden un displayNext, aplicamos PSI sobre esta posición e obtemos a seguinte,
445 // coa que podemos obter o símbolo pedido, e actualizamos displayState
446 myicsa->displayCSAState = 0;
447 myicsa->displayCSAPrevPosition = -2; //needed by DisplayCSA(position)
449 //aintVector = intVector;
450 // Liberamos o espacio non necesario
458 //Returns number of elements in the indexed sequence of integers
459 int sourceLenIntIndex(void *index, uint *numInts){
460 ticsa *myicsa = (ticsa *) index;
461 *numInts= myicsa->suffixArraySize;
462 return 0; //no error;
465 int saveIntIndex(void *index, char *pathname) {
466 //void storeStructsCSA(ticsa *myicsa, char *basename) {
468 ticsa *myicsa = (ticsa *) index;
469 char *basename=pathname;
474 // Reservamos espacio para o nome do ficheiro
475 filename = (char *)malloc(sizeof(char)*MAX_FILENAME_LENGTH);
477 // Ficheiro co n�mero de elementos indexados (enteiros do texto orixinal)
478 strcpy(filename, basename);
479 strcat(filename, ".");
480 strcat(filename, NUMBER_OF_ELEMENTS_FILE_EXT);
482 if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
483 printf("Cannot open file %s\n", filename);
486 write(file, &(myicsa->suffixArraySize), sizeof(int));
489 strcpy(filename, basename);
490 strcat(filename, ".");
491 strcat(filename, PSI_COMPRESSED_FILE_EXT);
493 #ifdef PSI_HUFFMANRLE
494 storeHuffmanCompressedPsi(&(myicsa->hcPsi), filename);
497 storeGonzaloCompressedPsi(&(myicsa->gcPsi), filename);
499 #ifdef PSI_DELTACODES
500 storeDeltaCompressedPsi(&(myicsa->dcPsi), filename);
503 // Ficheiro co vector de bits D
504 strcpy(filename, basename);
505 strcat(filename, ".");
506 strcat(filename, D_FILE_EXT);
508 if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
509 printf("Cannot open file %s\n", filename);
512 write(file, myicsa->D, sizeof(int)*((myicsa->suffixArraySize+31)/32));
515 // Directorio de rank para D
516 // Almacenamos o n�mero de superbloques seguido dos superbloques
517 // E logo o n�mero de bloques seguido dos bloques
518 strcpy(filename, basename);
519 strcat(filename, ".");
520 strcat(filename, D_RANK_DIRECTORY_FILE_EXT);
521 saveBitmap(filename,myicsa->bD);
523 // Ficheiro coas mostras de A
524 strcpy(filename, basename);
525 strcat(filename, ".");
526 strcat(filename, SAMPLES_A_FILE_EXT);
528 if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
529 printf("Cannot open file %s\n", filename);
532 write(file, myicsa->samplesA, sizeof(int) * (myicsa->samplesASize));
535 // Ficheiro co vector BA (marca as posicions de A muestreadas)
536 strcpy(filename, basename);
537 strcat(filename, ".");
538 strcat(filename, BA_FILE_EXT);
540 if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
541 printf("Cannot open file %s\n", filename);
544 write(file, myicsa->BA, sizeof(int)*((myicsa->suffixArraySize+31)/32));
547 // Directorio de rank para BA
548 strcpy(filename, basename);
549 strcat(filename, ".");
550 strcat(filename, BA_RANK_DIRECTORY_FILE_EXT);
551 saveBitmap(filename, myicsa->bBA);
553 // Ficheiro coas mostras de A inversa
554 strcpy(filename, basename);
555 strcat(filename, ".");
556 strcat(filename, SAMPLES_A_INV_FILE_EXT);
558 if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
559 printf("Cannot open file %s\n", filename);
562 write(file, myicsa->samplesAInv, sizeof(int) * (myicsa->samplesAInvSize));
565 // Ficheiro co periodo de muestreo de A e A inversa
566 strcpy(filename, basename);
567 strcat(filename, ".");
568 strcat(filename, SAMPLING_PERIOD_A_FILE_EXT);
570 if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
571 printf("Cannot open file %s\n", filename);
574 write(file, &(myicsa->T_A), sizeof(int));
575 write(file, &(myicsa->T_AInv), sizeof(int));
577 write(file, &(myicsa->psiSearchFactorJump), sizeof(uint));
581 return 0; //no error.
584 //Returns the size (in bytes) of the index over the sequence of integers.
585 //uint CSA_size(ticsa *myicsa) {
586 int sizeIntIndex(void *index, uint *numBytes) {
587 ticsa *myicsa = (ticsa *) index;
589 size +=(sizeof (ticsa) * 1);
590 size += sizeof(uint)*((myicsa->suffixArraySize+31)/32) ; //D vector
591 size += myicsa->bD->mem_usage;
592 size += sizeof(uint) * myicsa->samplesASize ; // samples A
593 size += sizeof(uint) * myicsa->samplesAInvSize ; // samples A^{-1}
594 size += sizeof(uint)*((myicsa->suffixArraySize+31)/32) ; //BA vector
595 size += myicsa->bBA->mem_usage;
596 #ifdef PSI_HUFFMANRLE
597 size +=myicsa->hcPsi.totalMem;
600 size +=myicsa->gcPsi.totalMem;
602 #ifdef PSI_DELTACODES
603 size +=myicsa->dcPsi.totalMem;
606 return 0; //no error.
610 //ticsa *loadCSA(char *basename) {
611 int loadIntIndex(char *pathname, void **index){
613 char *basename=pathname;
620 uint suffixArraySize;
623 myicsa = (ticsa *) malloc (sizeof (ticsa) * 1);
626 // VARIABLE GLOBAL QUE ALMACENA O ESTADO DOS DISPLAYS (IMPORTANTE PARA DISPLAY SECUENCIAL)
627 // Almacena a �ltima posici�n do array de sufixos que mostramos con display ou displayNext
628 // Se nos piden un displayNext, aplicamos PSI sobre esta posici�n e obtemos a seguinte,
629 // coa que podemos obter o s�mbolo pedido, e actualizamos displayState
630 myicsa->displayCSAState = 0;
631 myicsa->displayCSAPrevPosition = -2; //needed by DisplayCSA(position)
633 // Reservamos espacio para o nome do ficheiro
634 filename = (char *)malloc(sizeof(char)*MAX_FILENAME_LENGTH);
636 // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O NUMERO DE ELEMENTOS INDEXADOS
637 strcpy(filename, basename);
638 strcat(filename, ".");
639 strcat(filename, NUMBER_OF_ELEMENTS_FILE_EXT);
640 if( (file = open(filename, O_RDONLY)) < 0) {
641 printf("Cannot read file %s\n", filename);exit(0);
643 read(file, &suffixArraySize, sizeof(uint));
644 myicsa->suffixArraySize = suffixArraySize;
645 printf("Number of indexed elements (suffix array size) = %d\n", suffixArraySize);
647 // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA PSI COMPRIMIDA
648 strcpy(filename, basename);
649 strcat(filename, ".");
650 strcat(filename, PSI_COMPRESSED_FILE_EXT);
651 #ifdef PSI_HUFFMANRLE
652 myicsa->hcPsi = loadHuffmanCompressedPsi(filename);
655 myicsa->gcPsi = loadGonzaloCompressedPsi(filename);
657 #ifdef PSI_DELTACODES
658 myicsa->dcPsi = loadDeltaCompressedPsi(filename);
661 // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA D
662 strcpy(filename, basename);
663 strcat(filename, ".");
664 strcat(filename, D_FILE_EXT);
665 if( (file = open(filename, O_RDONLY)) < 0) {
666 printf("Cannot read file %s\n", filename); exit(0);
668 myicsa->D = (uint *) malloc (sizeof(uint)*((suffixArraySize+31)/32));
669 read(file, myicsa->D, sizeof(uint)*((suffixArraySize+31)/32));
670 printf("Bit vector D loaded (%d bits)\n", suffixArraySize);
672 // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O DIRECTORIO DE RANK1 PARA D
673 strcpy(filename, basename);
674 strcat(filename, ".");
675 strcat(filename, D_RANK_DIRECTORY_FILE_EXT);
676 myicsa->bD = loadBitmap(filename,myicsa->D,suffixArraySize);
678 ns = myicsa->bD->sSize;
679 nb = myicsa->bD->bSize;
680 myicsa->bD->data = myicsa->D;
681 printf("Rank1 Directory for D loaded (%d superblocks, %d blocks)\n", ns, nb);
684 // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA SAMPLES A
685 strcpy(filename, basename);
686 strcat(filename, ".");
687 strcat(filename, SAMPLES_A_FILE_EXT);
688 if( (file = open(filename, O_RDONLY)) < 0) {
689 printf("Cannot read file %s\n", filename); exit(0);
691 if( fstat(file, &f_stat) < 0) {
692 printf("Cannot read information from file %s\n", filename); exit(0);
694 myicsa->samplesASize = (f_stat.st_size)/sizeof(uint);
695 myicsa->samplesA = (uint *)malloc(sizeof(uint) * myicsa->samplesASize);
696 read(file, myicsa->samplesA, sizeof(uint) * myicsa->samplesASize);
697 printf("Suffix array samples loaded (%d samples)\n", myicsa->samplesASize);
699 // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA BA
700 strcpy(filename, basename);
701 strcat(filename, ".");
702 strcat(filename, BA_FILE_EXT);
703 if( (file = open(filename, O_RDONLY)) < 0) {
704 printf("Cannot read file %s\n", filename); exit(0);
706 myicsa->BA = (uint *) malloc (sizeof(uint)*((suffixArraySize+31)/32));
707 read(file, myicsa->BA, sizeof(uint)*((suffixArraySize+31)/32));
708 printf("Bit vector BA loaded (%d bits)\n", suffixArraySize);
710 // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O DIRECTORIO DE RANK1 PARA BA
711 strcpy(filename, basename);
712 strcat(filename, ".");
713 strcat(filename, BA_RANK_DIRECTORY_FILE_EXT);
714 myicsa->bBA = loadBitmap(filename,myicsa->BA,suffixArraySize);
716 ns = myicsa->bBA->sSize;
717 nb = myicsa->bBA->bSize;
718 myicsa->bBA->data = myicsa->BA;
719 printf("Rank1 Directory for BA loaded (%d superblocks, %d blocks)\n", ns, nb);
722 // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA SAMPLES A INVERSA
723 strcpy(filename, basename);
724 strcat(filename, ".");
725 strcat(filename, SAMPLES_A_INV_FILE_EXT);
726 if( (file = open(filename, O_RDONLY)) < 0) {
727 printf("Cannot read file %s\n", filename); exit(0);
729 if( fstat(file, &f_stat) < 0) {
730 printf("Cannot read information from file %s\n", filename); exit(0);
732 myicsa->samplesAInvSize = (f_stat.st_size)/(sizeof(uint));
733 myicsa->samplesAInv = (uint *)malloc(sizeof(uint) * myicsa->samplesAInvSize);
734 read(file, myicsa->samplesAInv, sizeof(uint) * myicsa->samplesAInvSize);
735 printf("Suffix array inverse samples loaded (%d samples)\n", myicsa->samplesAInvSize);
737 // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O PERIODO DE MUESTREO DO ARRAY DE SUFIXOS E DA INVERSA
738 strcpy(filename, basename);
739 strcat(filename, ".");
740 strcat(filename, SAMPLING_PERIOD_A_FILE_EXT);
741 if( (file = open(filename, O_RDONLY)) < 0) {
742 printf("Cannot read file %s\n", filename); exit(0);
744 read(file, &(myicsa->T_A), sizeof(uint));
745 read(file, &(myicsa->T_AInv), sizeof(uint));
746 printf("Sampling A Period T = %d, Sampling A inv Period TInv = %d\n", myicsa->T_A, myicsa->T_AInv);
748 read(file, &(myicsa->psiSearchFactorJump), sizeof(uint));
749 printf("Psi Bin Search Factor-Jump is = %d\n", myicsa->psiSearchFactorJump);
760 //uint destroyStructsCSA(ticsa *myicsa) {
761 int freeIntIndex(void *index) {
762 ticsa *myicsa = (ticsa *) index;
763 // Liberamos o espacio reservado
765 if (!myicsa) return 0;
767 size_t total=0, totaltmp=0;
769 uint nbytes;sizeIntIndex(index, &nbytes);
771 total +=(sizeof (ticsa) * 1);;
773 #ifdef PSI_HUFFMANRLE
774 total+= totaltmp = myicsa->hcPsi.totalMem;
775 destroyHuffmanCompressedPsi(&(myicsa->hcPsi));
778 total+= totaltmp = myicsa->gcPsi.totalMem;
779 destroyGonzaloCompressedPsi(&(myicsa->gcPsi));
781 #ifdef PSI_DELTACODES
782 total+= totaltmp = myicsa->dcPsi.totalMem;
783 destroyDeltaCodesCompressedPsi(&(myicsa->dcPsi));
785 printf("\n\t[destroying SA: compressed PSI structure] ...Freed %zu bytes... RAM", totaltmp);
787 free(myicsa->D); total+= totaltmp = (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
788 printf("\n\t[destroying SA: D vector] ...Freed %zu bytes... RAM",totaltmp);
789 free(myicsa->samplesA); total+= totaltmp = (sizeof(uint) * myicsa->samplesASize);
790 printf("\n\t[destroying Samples A: A ] ...Freed %zu bytes... RAM",totaltmp);
791 free(myicsa->samplesAInv); total+= totaltmp = (sizeof(uint) * myicsa->samplesAInvSize);
792 printf("\n\t[destroying Samples AInv: A ] ...Freed %zubytes... RAM",totaltmp);
793 printf("\n\t[destroying rank bit D ] ...Freed %zu bytes... RAM", (size_t)myicsa->bD->mem_usage);
794 free(myicsa->BA); total+= totaltmp = (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
795 printf("\n\t[destroying SA: BA vector] ...Freed %zu bytes... RAM",totaltmp);
797 total += myicsa->bD->mem_usage;
798 destroyBitmap(myicsa->bD);
799 total += myicsa->bBA->mem_usage;
800 destroyBitmap(myicsa->bBA);
802 printf("\n\t**** [the whole iCSA ocuppied ... %zu bytes... RAM",total);
803 printf("\n\t**** iCSA size = %zu bytes ", (size_t) nbytes);
808 return 0; //no error.
811 // Shows detailed summary info of the self-index (memory usage of each structure)
812 int printInfoIntIndex(void *index, const char tab[]) {
813 ticsa *myicsa = (ticsa *) index;
814 if (!myicsa) return 0;
816 uint structure, totalpsi, totalD, totalBD, totalSA,totalSAinv, totalBA,totalBBA;
818 structure=sizeof(ticsa);
820 #ifdef PSI_HUFFMANRLE
821 totalpsi = myicsa->hcPsi.totalMem;
824 totalpsi = myicsa->gcPsi.totalMem;
826 #ifdef PSI_DELTACODES
827 totalpsi = myicsa->dcPsi.totalMem;
830 totalD = (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
831 totalBD = myicsa->bD->mem_usage;
832 totalSA = (sizeof(uint) * myicsa->samplesASize);
833 totalSAinv = (sizeof(uint) * myicsa->samplesAInvSize);
834 totalBA = (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
835 totalBBA = myicsa->bBA->mem_usage;
837 uint nbytes; sizeIntIndex(index, &nbytes); //whole self-index
839 printf("\n ===================================================:");
840 printf("\n%sSummary Self-index on integers (icsa) layer:",tab);
841 printf("\n%s icsa structure = %d bytes",tab, structure);
842 printf("\n%s psi = %8d bytes",tab, totalpsi);
843 printf("\n%s D (bitmap) = %8d bytes",tab, totalD);
844 printf("\n%s rank for D = %8d bytes",tab, totalBD);
845 printf("\n%s SA(sampled) = %8d bytes",tab, totalSA);
846 printf("\n%s SAinv(samp) = %8d bytes",tab, totalSAinv);
847 printf("\n%s BA (bitmap) = %8d bytes",tab, totalBA);
848 printf("\n%s rank for BA = %8d bytes",tab, totalBBA);
849 printf("\n%sTotal = ** %9d bytes (in RAM) ** ",tab, nbytes);
852 return 0; //no error.
858 // BUSCA BINARIA SOBRE MOSTRAS + 2 BUSCAS EXPONENCIAIS + 2 BUSCAS BINARIAS
859 // 1º Busca binaria sobre o array de sufixos, elexindo como pivote un múltiplo de bin_search_psi_skip_interval (que orixinalmente foi pensado para igualar co valor de Psi).
860 // 2º Esta busca pode deterse por:
861 // a) O pivote repítese entre dúas iteracións -> As ocorrencias están entre o pivote e a seguinte mostra (pivote + bin_search_psi_skip_interval) -> facemos dúas buscas binarias
862 // b) O pivote é unha ocorrencia do patrón -> Faise unha busca exponencial sobre mostras hacia a esquerda e outra hacia a dereita, ata atopar a unha mostra á esquerda e outra
863 // á dereita do intervalo de ocorrencias. Entre cada unha destas e a inmediatamente anterior da busca exponencial, faise unha busca binaria para atopar os extremos do intervalo.
865 int countIntIndex(void *index, uint *pattern, uint length, ulong *numocc, ulong *left, ulong *right){
866 //unsigned int countCSA(ticsa *myicsa, uint *pattern, uint patternSize, uint *left, uint *right) {
868 uint patternSize = length;
869 ticsa *myicsa = (ticsa *) index;
871 register unsigned long l, r, i;
872 register long comp, p, previousP;
873 //register unsigned int l, r, i;
874 //register int comp, p, previousP;
875 register uint bin_search_psi_skip_interval = myicsa->psiSearchFactorJump;
877 //fprintf(stderr,"\n psiSearchFactor = %d",myicsa->psiSearchFactorJump);
880 r = (myicsa->suffixArraySize+bin_search_psi_skip_interval-2)/bin_search_psi_skip_interval*bin_search_psi_skip_interval;
881 p = ((l+r)/2)/bin_search_psi_skip_interval * bin_search_psi_skip_interval;
884 // BUSCA BINARIA SOBRE MOSTRAS
885 while( (p != previousP) && (comp = SadCSACompare(myicsa, pattern, patternSize, p)) ) {
889 p = ((l+r)/2)/bin_search_psi_skip_interval*bin_search_psi_skip_interval;
894 // BUSCA BINARIA ENTRE O PIVOTE E A SEGUINTE MOSTRA
896 r = previousP+bin_search_psi_skip_interval;
897 if(r > myicsa->suffixArraySize) r = myicsa->suffixArraySize - 1;
900 if(SadCSACompare(myicsa, pattern, patternSize, p) <= 0) r = p;
904 if(SadCSACompare(myicsa, pattern, patternSize, r)) {
909 return 0; //no error.
914 r = previousP+bin_search_psi_skip_interval;
915 if(r > myicsa->suffixArraySize) r = myicsa->suffixArraySize - 1;
918 if(SadCSACompare(myicsa, pattern, patternSize, p) >= 0) l = p;
925 previousP = p; // En previousP poñemos o p atopado na busca sobre as mostras
927 // BUSCA EXPONENCIAL HACIA ATRÁS
929 p -= bin_search_psi_skip_interval;
930 while(p>0 && !SadCSACompare(myicsa, pattern, patternSize, p)) {
932 p = previousP-(i*bin_search_psi_skip_interval);
934 // Busca binaria entre as duas ultimas mostras da exponencial
935 if(previousP > i*bin_search_psi_skip_interval) l = previousP-(i*bin_search_psi_skip_interval);
938 r = previousP-(i*bin_search_psi_skip_interval);
941 if(SadCSACompare(myicsa, pattern, patternSize, p) <= 0) r = p;
946 // BUSCA EXPONENCIAL HACIA ADIANTE
948 p = previousP+bin_search_psi_skip_interval;
949 while(p<myicsa->suffixArraySize && !SadCSACompare(myicsa, pattern, patternSize, p)) {
951 p = previousP+(i*bin_search_psi_skip_interval);
953 // Busca binaria entre as duas ultimas mostras da exponencial
954 if(p < myicsa->suffixArraySize) r = previousP+(i*bin_search_psi_skip_interval);
955 else r = myicsa->suffixArraySize-1;
957 l = previousP+(i*bin_search_psi_skip_interval);
960 if(SadCSACompare(myicsa, pattern, patternSize, p) >= 0) l = p;
966 //return *right-*left+1;
967 *numocc = (uint) *right-*left+1;
971 // Version inicial de busca binaria
972 unsigned int countCSABin(ticsa *myicsa, uint *pattern, uint patternSize, uint *left, uint *right) {
973 register ulong l, r, p;
976 r = myicsa->suffixArraySize-1;
980 if(SadCSACompare(myicsa, pattern, patternSize, p) <= 0) r = p;
984 // SE SON DISTINTOS O PATRON NON APARECE NO TEXTO E DEVOLVEMOS 0
985 if(SadCSACompare(myicsa, pattern, patternSize, r)) {
991 // Almacenamos o limite esquerdo
994 // SE SON IGUALES (O PATRON APARECE NO TEXTO), BUSCAMOS AGORA O LIMITE DEREITO, QUE ALMACENAREMOS EN right
995 // NOTA: INICIAMOS A BUSQUEDA A PARTIR DO ESQUERDO...
997 r = myicsa->suffixArraySize-1;
1001 if(SadCSACompare(myicsa, pattern, patternSize, p) >= 0) l = p;
1005 // Gardamos o limite dereito
1008 return (uint) *right-*left+1;
1011 int locateIntIndex(void *index, uint *pattern, uint length, ulong **occ, ulong *numocc) {
1012 //unsigned int *locateCSA(ticsa *myicsa, uint *pattern, uint patternSize, uint *occ) {
1014 ticsa *myicsa = (ticsa *) index;
1015 uint patternSize = length;
1018 register ulong left, right;
1020 //occurrences = countCSA(myicsa, pattern, patternSize, &left, &right);
1022 err = countIntIndex((void *) myicsa, pattern, patternSize, &occurrences, &left, &right);
1023 *numocc = occurrences;
1026 register ulong idx = 0;
1027 positions = (ulong*) malloc(sizeof(ulong) * occurrences);
1028 while(left<=right) positions[idx++] = A(myicsa,left++);
1036 return 0; //no error, but no occurrences.
1041 // Devolve o enteiro do texto que ocupa a posicion dada,
1042 // e fixa o estado para poder seguir obtendo os seguintes enteiros con displayNext();
1044 int displayIntIndex(void *index, ulong position, uint *value){
1045 //uint displayCSA(ticsa *myicsa, uint position) {
1046 ticsa *myicsa = (ticsa *) index;
1047 if (position == (myicsa->displayCSAPrevPosition +1)) {
1048 myicsa->displayCSAPrevPosition = position;
1049 //return displayCSANext(myicsa);
1050 *value = displayCSANext(myicsa);
1053 myicsa->displayCSAPrevPosition = position;
1054 //return displayCSAFirst(myicsa, position);
1055 *value = displayCSAFirst(myicsa, position);
1057 return 0; //no error
1061 /**********************************************************************/
1063 // Devolve o enteiro do texto que ocupa a posicion dada, e fixa o estado
1064 // para poder seguir obtendo os seguintes enteiros con displayNext();
1065 uint displayCSAFirst(ticsa *myicsa, uint position) {
1067 register uint positionAux, index;
1068 register uint T_AInv = myicsa->T_AInv;
1070 positionAux = myicsa->samplesAInv[position / T_AInv];
1071 for(index = 0; index < position%T_AInv; index++) {
1072 #ifdef PSI_HUFFMANRLE
1073 positionAux=getHuffmanPsiValue(&(myicsa->hcPsi),positionAux);
1076 positionAux=getGonzaloPsiValue(&(myicsa->gcPsi),positionAux);
1078 #ifdef PSI_DELTACODES
1079 positionAux=getDeltaPsiValue(&(myicsa->dcPsi),positionAux);
1083 // Fijamos a variable global para a chamada a displayNext
1084 myicsa->displayCSAState = positionAux;
1086 // return rank1(D, Dir, positionAux) - 1;
1087 return rank(myicsa->bD, positionAux) - 1;
1091 // Devolve o seguinte enteiro do texto (a partir do estado)
1092 unsigned int displayCSANext(ticsa *myicsa) {
1093 #ifdef PSI_HUFFMANRLE
1094 myicsa->displayCSAState=getHuffmanPsiValue(&(myicsa->hcPsi),myicsa->displayCSAState);
1097 myicsa->displayCSAState = getGonzaloPsiValue(&(myicsa->gcPsi),myicsa->displayCSAState);
1099 #ifdef PSI_DELTACODES
1100 myicsa->displayCSAState = getDeltaPsiValue(&(myicsa->dcPsi),myicsa->displayCSAState);
1102 return rank(myicsa->bD, myicsa->displayCSAState) - 1;
1106 // Mostra as estructuras creadas
1107 void showStructsCSA(ticsa *myicsa) {
1111 // ESTRUCTURAS PARA CSA
1112 printf("Basic CSA structures:\n\n");
1114 // VALORES DA FUNCI�N PSI (decodificando)
1115 printf("\tPSI: (Sampling period = %d)\n", myicsa->T_Psi);
1116 for(index=0; index < myicsa->suffixArraySize; index++)
1117 #ifdef PSI_HUFFMANRLE
1118 printf("\tPsi[%d] = %d\n", index, getHuffmanPsiValue(&(myicsa->hcPsi),index));
1121 printf("\tPsi[%d] = %d\n", index, getGonzaloPsiValue(&(myicsa->gcPsi),index));
1123 #ifdef PSI_DELTACODES
1124 printf("\tPsi[%d] = %d\n", index, getDeltaPsiValue(&(myicsa->dcPsi),index));
1128 // VECTOR D DE SADAKANE CO DIRECTORIO DE RANK ASOCIADO
1130 showBitVector(myicsa->D, myicsa->suffixArraySize);
1131 printf("\n\nSuperbloques de D:\n");
1134 ns = myicsa->bD->sSize;
1135 nb= myicsa->bD->bSize;
1136 for(index=0; index<ns; index++) {
1137 //printf("\tDs[%d] = %d\n", index, Dir.Ds[index]);
1138 printf("\tDs[%d] = %d\n", index, myicsa->bD->sdata[index]);
1140 printf("\nBloques de D:\n");
1142 for(index=0; index<nb; index++) {
1143 //printf("\tDb[%d] = %d\n", index, Dir.Db[index]);
1144 printf("\tDb[%d] = %d\n", index, myicsa->bD->bdata[index]);
1148 // ESTRUCTURAS PARA ACCEDER O ARRAY DE SUFIXOS E A SUA INVERSA
1149 printf("Suffix Array Sampling Structures: (Sampling period = %d)\n", myicsa->T_A);
1150 printf("\tSuffix Array Samples:\n");
1151 for(index=0; index < myicsa->samplesASize; index++)
1152 printf("\tSamplesA[%d] = %d\n", index, myicsa->samplesA[index]);
1154 printf("\tInverse Suffix Array Samples:\n");
1155 for(index=0; index < myicsa->samplesASize; index++)
1156 printf("\tSamplesAInv[%d] = %d\n", index, myicsa->samplesAInv[index]);
1162 // Comparacion de Sadakane entre un patron (pattern) y el sufijo en la posicion p del array de sufijos
1163 // IMPORTANTE EVITAR ULTIMA CHAMADA A PSI
1164 int SadCSACompare(ticsa *myicsa, uint *pattern, uint patternSize, uint p) {
1166 register unsigned int j, i, currentInteger, diff;
1172 currentInteger = rank(myicsa->bD, i) - 1;
1173 diff = pattern[j++] - currentInteger;
1174 if(diff) return diff;
1175 if(j == patternSize) return 0;
1177 #ifdef PSI_HUFFMANRLE
1178 i=getHuffmanPsiValue(&(myicsa->hcPsi),i);
1181 i=getGonzaloPsiValue(&(myicsa->gcPsi),i);
1183 #ifdef PSI_DELTACODES
1184 i=getDeltaPsiValue(&(myicsa->dcPsi),i);
1191 // Acceso a array de sufixos A
1192 inline uint A(ticsa *myicsa, uint position) {
1194 register uint timesPsi, sampleValue;
1195 register uint T_A = myicsa->T_A;
1197 uint proba = position;
1200 while(!bitget(myicsa->BA, position)) {
1202 #ifdef PSI_HUFFMANRLE
1203 position=getHuffmanPsiValue(&(myicsa->hcPsi),position);
1206 position=getGonzaloPsiValue(&(myicsa->gcPsi),position);
1208 #ifdef PSI_DELTACODES
1209 position=getDeltaPsiValue(&(myicsa->dcPsi),position);
1214 sampleValue = myicsa->samplesA[rank(myicsa->bBA, position)-1];
1216 return sampleValue - timesPsi;
1221 // Acceso 'a inversa do array de sufixos
1222 inline uint inverseA(ticsa *myicsa, uint offset) {
1224 register uint index, inverseValue;
1225 register uint T_AInv = myicsa->T_AInv;
1227 inverseValue = myicsa->samplesAInv[offset/T_AInv];
1228 for(index=0; index<(offset%T_AInv); index++)
1229 #ifdef PSI_HUFFMANRLE
1230 inverseValue=getHuffmanPsiValue(&(myicsa->hcPsi),inverseValue);
1233 inverseValue = getGonzaloPsiValue(&(myicsa->gcPsi),inverseValue);
1235 #ifdef PSI_DELTACODES
1236 inverseValue = getDeltaPsiValue(&(myicsa->dcPsi),inverseValue);
1238 return inverseValue;
1242 // Initializes the parameters of the index.
1243 uint parametersCSA(ticsa *myicsa, char *build_options){
1244 char delimiters[] = " =;";
1245 int j,num_parameters;
1247 int ssA,ssAinv,ssPsi,nsHuff,psiSearchFactor;
1249 ssA = DEFAULT_A_SAMPLING_PERIOD;
1250 ssAinv = DEFAULT_A_INV_SAMPLING_PERIOD;
1251 ssPsi = DEFAULT_PSI_SAMPLING_PERIOD;
1252 nsHuff = DEFAULT_nsHUFF;
1253 psiSearchFactor = DEFAULT_PSI_BINARY_SEARCH_FACTOR;
1255 if (build_options != NULL) {
1256 parse_parameters(build_options,&num_parameters, ¶meters, delimiters);
1257 for (j=0; j<num_parameters;j++) {
1259 if ((strcmp(parameters[j], "sA") == 0 ) && (j < num_parameters-1) ) {
1260 ssA=atoi(parameters[j+1]);
1262 if ((strcmp(parameters[j], "sAinv") == 0 ) && (j < num_parameters-1) ) {
1263 ssAinv=atoi(parameters[j+1]);
1265 if ((strcmp(parameters[j], "sPsi") == 0 ) && (j < num_parameters-1) ) {
1266 ssPsi=atoi(parameters[j+1]);
1268 if ((strcmp(parameters[j], "nsHuff") == 0 ) && (j < num_parameters-1) ) {
1269 nsHuff=atoi(parameters[j+1]);
1272 if ((strcmp(parameters[j], "psiSF") == 0 ) && (j < num_parameters-1) ) {
1273 psiSearchFactor=atoi(parameters[j+1]);
1277 free_parameters(num_parameters, ¶meters);
1281 myicsa->T_AInv = ssAinv;
1282 myicsa->T_Psi = ssPsi;
1283 myicsa->tempNSHUFF = nsHuff;
1284 myicsa->psiSearchFactorJump = psiSearchFactor * ssPsi;
1286 printf("\n\t parameters for iCSA: sampleA=%d, sampleAinv=%d, samplePsi=%d",ssA,ssAinv,ssPsi);
1287 printf("\n\t : nsHuff=%d, psiSearchFactor = %d --> jump = %d", nsHuff,psiSearchFactor, myicsa->psiSearchFactorJump);