TCImplementation.cpp

   1 /******************************************************************************
   2  *   Copyright (C) 2006-2008 by Veli Mäkinen and Niko Välimäki                *
   3  *                                                                            *
   4  *                                                                            *
   5  *   This program is free software; you can redistribute it and/or modify     *
   6  *   it under the terms of the GNU Lesser General Public License as published *
   7  *   by the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                      *
   9  *                                                                            *
  10  *   This program is distributed in the hope that it will be useful,          *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
  13  *   GNU Lesser General Public License for more details.                      *
  14  *                                                                            *
  15  *   You should have received a copy of the GNU Lesser General Public License *
  16  *   along with this program; if not, write to the                            *
  17  *   Free Software Foundation, Inc.,                                          *
  18  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.            *
  19  *****************************************************************************/
  20 #include "TCImplementation.h"
  21
  22 //#include "HeapProfiler.h" // FIXME remove
  23
  24 #include <iostream>
  25 #include <map>
  26 #include <set>
  27 #include <vector>
  28 #include <utility>
  29 #include <stdexcept>
  30 #include <cassert>
  31 #include <cstring> // For strlen()
  32 using std::vector;
  33 using std::pair;
  34 using std::make_pair;
  35 using std::map;
  36
  37 namespace SXSI
  38 {
  39
  40 // Save file version info
  41 const uchar TCImplementation::versionFlag = 4;
  42
  43 /**
  44  * Constructor inits an empty dynamic FM-index.
  45  * Samplerate defaults to TEXTCOLLECTION_DEFAULT_SAMPLERATE.
  46  */
  47 TCImplementation::TCImplementation(uchar * bwt, ulong length, unsigned samplerate_, unsigned numberOfTexts_, ulong maxTextLength_)
  48     : n(length), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0),
  49       suffixDocId(0), numberOfTexts(numberOfTexts_), maxTextLength(maxTextLength_), Doc(0)
  50 {
  51     makewavelet(bwt); // Deletes bwt!
  52     bwt = 0;
  53
  54     // Make sampling tables
  55     maketables();
  56 }
  57
  58 bool TCImplementation::EmptyText(DocId k) const
  59 {
  60     assert(k < (DocId)numberOfTexts);
  61     return false; // Empty texts are not indexed
  62 }
  63
  64 uchar* TCImplementation::GetText(DocId k) const
  65 {
  66     assert(k < (DocId)numberOfTexts);
  67     TextPosition i = k;
  68
  69     string result;
  70     // Reserve average string length to avoid reallocs
  71     result.reserve(n/numberOfTexts);
  72
  73     uchar c = alphabetrank->access(i);
  74     while (c != '\0')
  75     {
  76         result.push_back(c);
  77         i = C[c]+alphabetrank->rank(c,i)-1;
  78
  79         c = alphabetrank->access(i); // "next" char.
  80     }
  81
  82     // Convert to uchar (FIXME return string?)
  83     i = result.size();
  84     uchar* res = new uchar[i+1];
  85     res[i] = '\0';
  86     for (ulong j = 0; j < i; ++j)
  87         res[i-j-1] = result[j];
  88     return res;
  89 }
  90 /*
  91  * Not supported
  92 uchar* TCImplementation::GetText(DocId k, TextPosition i, TextPosition j) const
  93 {
  94     assert(k < (DocId)numberOfTexts);
  95     assert(j < (*textLength)[k]);
  96     assert(i <= j);
  97
  98     ulong textRank = 0;
  99
 100     // Start position of k'th text
 101     ulong start = (*textStartPos)[k];
 102
 103     return Substring(i + start, j-i+1);
 104     }*/
 105
 106 /******************************************************************
 107  * Existential queries
 108  */
 109 bool TCImplementation::IsPrefix(uchar const * pattern) const
 110 {
 111     TextPosition m = strlen((char *)pattern);
 112     if (m == 0)
 113         return true;
 114
 115     TextPosition sp = 0, ep = 0;
 116     Search(pattern, m, &sp, &ep);
 117
 118     // Check for end-marker(s) in result interval
 119     if (CountEndmarkers(sp, ep))
 120         return true;
 121     return false;
 122 }
 123
 124 bool TCImplementation::IsPrefix(uchar const * pattern, DocId begin, DocId end) const
 125 {
 126     TextPosition m = strlen((char *)pattern);
 127     if (m == 0)
 128         return true;
 129
 130     TextPosition sp = 0, ep = 0;
 131     Search(pattern, m, &sp, &ep);
 132
 133     // Check for end-marker(s) in result interval
 134     if (CountEndmarkers(sp, ep, begin, end))
 135         return true;
 136     return false;
 137 }
 138
 139
 140 bool TCImplementation::IsSuffix(uchar const *pattern) const
 141 {
 142     // Here counting is as fast as IsSuffix():
 143     if (CountSuffix(pattern) > 0)
 144         return true;
 145     return false;
 146 }
 147
 148 bool TCImplementation::IsSuffix(uchar const *pattern, DocId begin, DocId end) const
 149 {
 150     // Here counting is as fast as IsSuffix():
 151     if (CountSuffix(pattern, begin, end) > 0)
 152         return true;
 153     return false;
 154 }
 155
 156 bool TCImplementation::IsEqual(uchar const *pattern) const
 157 {
 158     TextPosition m = std::strlen((char *)pattern);
 159     if (m == 0)
 160         return false; // No empty texts exists
 161
 162     TextPosition sp = 0, ep = 0;
 163     // Match including end-marker
 164     Search(pattern, m+1, &sp, &ep);
 165
 166     // Check for end-marker(s) in result interval
 167     if (CountEndmarkers(sp, ep))
 168         return true;
 169     return false;
 170 }
 171
 172 bool TCImplementation::IsEqual(uchar const *pattern, DocId begin, DocId end) const
 173 {
 174     TextPosition m = std::strlen((char *)pattern);
 175     if (m == 0)
 176         return false; // No empty texts exists
 177
 178     TextPosition sp = 0, ep = 0;
 179     // Match including end-marker
 180     Search(pattern, m+1, &sp, &ep, begin, end);
 181
 182     // Check for end-marker(s) in result interval
 183     if (CountEndmarkers(sp, ep))
 184         return true;
 185     return false;
 186 }
 187
 188 bool TCImplementation::IsContains(uchar const * pattern) const
 189 {
 190     TextPosition m = strlen((char *)pattern);
 191     if (m == 0)
 192         return true;
 193
 194     TextPosition sp = 0, ep = 0;
 195     // Just check if pattern exists somewhere
 196     ulong count = Search(pattern, m, &sp, &ep);
 197
 198     if (count > 0)
 199         return true;
 200     return false;
 201 }
 202
 203 bool TCImplementation::IsContains(uchar const * pattern, DocId begin, DocId end) const
 204 {
 205     // Here counting is as fast as existential querying
 206     if (CountContains(pattern, begin, end) > 0)
 207         return true; // FIXME No need to filter result set
 208     return false;
 209 }
 210
 211 bool TCImplementation::IsLessThan(uchar const * pattern) const
 212 {
 213     if (CountLessThan(pattern) > 0)
 214         return true;
 215     return false;
 216 }
 217
 218 bool TCImplementation::IsLessThan(uchar const * pattern, DocId begin, DocId end) const
 219 {
 220     if (CountLessThan(pattern, begin, end) > 0)
 221         return true;
 222     return false;
 223 }
 224
 225 /******************************************************************
 226  * Counting queries
 227  */
 228 ulong TCImplementation::Count(uchar const * pattern) const
 229 {
 230     TextPosition m = strlen((char *)pattern);
 231     if (m == 0)
 232         return 0;
 233
 234     TextPosition sp = 0, ep = 0;
 235     unsigned count = (unsigned) Search(pattern, m, &sp, &ep);
 236     return count;
 237 }
 238
 239 unsigned TCImplementation::CountPrefix(uchar const * pattern) const
 240 {
 241     TextPosition m = strlen((char *)pattern);
 242     if (m == 0)
 243         return numberOfTexts;
 244
 245     TextPosition sp = 0, ep = 0;
 246     Search(pattern, m, &sp, &ep);
 247
 248     // Count end-markers in result interval
 249     return CountEndmarkers(sp, ep);
 250 }
 251
 252 unsigned TCImplementation::CountPrefix(uchar const * pattern, DocId begin, DocId end) const
 253 {
 254     TextPosition m = strlen((char *)pattern);
 255     if (m == 0)
 256         return numberOfTexts;
 257
 258     TextPosition sp = 0, ep = 0;
 259     Search(pattern, m, &sp, &ep);
 260
 261     // Count end-markers in result interval
 262     return CountEndmarkers(sp, ep, begin, end);
 263 }
 264
 265 unsigned TCImplementation::CountSuffix(uchar const * pattern) const
 266 {
 267     TextPosition m = strlen((char *)pattern);
 268     if (m == 0)
 269         return numberOfTexts;
 270
 271     TextPosition sp = 0, ep = 0;
 272     // Search with end-marker
 273     unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep);
 274
 275     return count;
 276 }
 277
 278 unsigned TCImplementation::CountSuffix(uchar const * pattern, DocId begin, DocId end) const
 279 {
 280     TextPosition m = strlen((char *)pattern);
 281     if (m == 0)
 282         return numberOfTexts;
 283
 284     TextPosition sp = 0, ep = 0;
 285     // Search with end-marker
 286     unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep, begin, end);
 287
 288     return count;
 289 }
 290
 291 unsigned TCImplementation::CountEqual(uchar const *pattern) const
 292 {
 293     TextPosition m = strlen((char const *)pattern);
 294     if (m == 0)
 295         return 0; // No empty texts.
 296
 297     TextPosition sp = 0, ep = 0;
 298     // Match including end-marker
 299     Search(pattern, m+1, &sp, &ep);
 300
 301     // Count end-markers in result interval
 302     return CountEndmarkers(sp, ep);
 303 }
 304
 305 unsigned TCImplementation::CountEqual(uchar const *pattern, DocId begin, DocId end) const
 306 {
 307     TextPosition m = strlen((char const *)pattern);
 308     if (m == 0)
 309         return 0; // No empty texts.
 310
 311     TextPosition sp = 0, ep = 0;
 312     // Match including end-marker
 313     Search(pattern, m+1, &sp, &ep, begin, end);
 314
 315     // Count end-markers in result interval
 316     return CountEndmarkers(sp, ep); // Already within [begin, end]
 317 }
 318
 319 unsigned TCImplementation::CountContains(uchar const * pattern) const
 320 {
 321     TextPosition m = strlen((char const *)pattern);
 322     if (m == 0)
 323         return numberOfTexts; // Total number of texts.
 324
 325     // Here counting is as slow as fetching the result set
 326     // because we have to filter out occ's that fall within same document.
 327     TextCollection::document_result result = Contains(pattern);
 328     return result.size();
 329 }
 330
 331 unsigned TCImplementation::CountContains(uchar const * pattern, DocId begin, DocId end) const
 332 {
 333     TextPosition m = strlen((char const *)pattern);
 334     if (m == 0)
 335         return numberOfTexts; // Total number of texts.
 336
 337     // Here counting is as slow as fetching the result set
 338     // because we have to filter out occ's that fall within same document.
 339     TextCollection::document_result result = Contains(pattern, begin, end);
 340     return result.size();
 341 }
 342
 343 // Less than or equal
 344 unsigned TCImplementation::CountLessThan(uchar const * pattern) const
 345 {
 346     TextPosition m = strlen((char const *)pattern);
 347     if (m == 0)
 348         return 0; // No empty texts.
 349
 350     TextPosition sp = 0, ep = 0;
 351     SearchLessThan(pattern, m, &sp, &ep);
 352
 353     // Count end-markers in result interval
 354     return CountEndmarkers(sp, ep);
 355 }
 356
 357 unsigned TCImplementation::CountLessThan(uchar const * pattern, DocId begin, DocId end) const
 358 {
 359     TextPosition m = strlen((char const *)pattern);
 360     if (m == 0)
 361         return 0; // No empty texts.
 362
 363     TextPosition sp = 0, ep = 0;
 364     SearchLessThan(pattern, m, &sp, &ep);
 365
 366     // Count end-markers in result interval
 367     return CountEndmarkers(sp, ep, begin, end);
 368 }
 369
 370 /**
 371  * Document reporting queries
 372  */
 373 TextCollection::document_result TCImplementation::Prefix(uchar const * pattern) const
 374 {
 375     TextPosition m = strlen((char *)pattern);
 376     if (m == 0)
 377         return TextCollection::document_result(); // FIXME Should return all 1...k
 378
 379     TextPosition sp = 0, ep = 0;
 380     Search(pattern, m, &sp, &ep);
 381
 382     // Iterate through end-markers in [sp,ep]:
 383     return EnumerateEndmarkers(sp, ep);
 384 }
 385
 386 TextCollection::document_result TCImplementation::Prefix(uchar const * pattern, DocId begin, DocId end) const
 387 {
 388     TextPosition m = strlen((char *)pattern);
 389     if (m == 0)
 390         return TextCollection::document_result(); // FIXME Should return all 1...k
 391
 392     TextPosition sp = 0, ep = 0;
 393     Search(pattern, m, &sp, &ep);
 394
 395     // Return end-markers in [sp,ep] and [begin, end]:
 396     return EnumerateEndmarkers(sp, ep, begin, end);
 397 }
 398
 399 TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) const
 400 {
 401     TextPosition m = strlen((char *)pattern);
 402     if (m == 0)
 403         return TextCollection::document_result(); // FIXME Should return all 1...k
 404
 405     TextPosition sp = 0, ep = 0;
 406     // Search with end-marker
 407     Search(pattern, m+1, &sp, &ep);
 408
 409     TextCollection::document_result result;
 410     result.reserve(ep-sp+1); // Try to avoid reallocation.
 411
 412     ulong sampled_rank_i = 0;
 413     // Check each occurrence
 414     for (; sp <= ep; ++sp)
 415     {
 416         TextPosition i = sp;
 417
 418         uchar c = alphabetrank->access(i);
 419         while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
 420         {
 421             i = C[c]+alphabetrank->rank(c,i)-1;
 422             c = alphabetrank->access(i);
 423         }
 424         // Assert: c == '\0'  OR  sampled->IsBitSet(i)
 425
 426         if (c == '\0')
 427         {
 428             // Rank among the end-markers in BWT
 429             unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
 430             result.push_back(Doc->access(endmarkerRank));
 431         }
 432         else // Sampled position
 433         {
 434             DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
 435             result.push_back(docId);
 436         }
 437     }
 438
 439     return result;
 440 }
 441
 442 TextCollection::document_result TCImplementation::Suffix(uchar const * pattern, DocId begin, DocId end) const
 443 {
 444     TextPosition m = strlen((char *)pattern);
 445     if (m == 0)
 446         return TextCollection::document_result(); // FIXME Should return all 1...k
 447
 448     TextPosition sp = 0, ep = 0;
 449     // Search with end-marker
 450     Search(pattern, m+1, &sp, &ep, begin, end);
 451
 452     TextCollection::document_result result;
 453     result.reserve(ep-sp+1); // Try to avoid reallocation.
 454
 455     ulong sampled_rank_i = 0;
 456     // Check each occurrence, already within [begin, end]
 457     for (; sp <= ep; ++sp)
 458     {
 459         TextPosition i = sp;
 460
 461         uchar c = alphabetrank->access(i);
 462         while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
 463         {
 464             i = C[c]+alphabetrank->rank(c,i)-1;
 465             c = alphabetrank->access(i);
 466         }
 467         // Assert: c == '\0'  OR  sampled->IsBitSet(i)
 468
 469         if (c == '\0')
 470         {
 471             // Rank among the end-markers in BWT
 472             unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
 473             result.push_back(Doc->access(endmarkerRank));
 474         }
 475         else // Sampled position
 476         {
 477             DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
 478             result.push_back(docId);
 479         }
 480     }
 481
 482     return result;
 483 }
 484
 485
 486 TextCollection::document_result TCImplementation::Equal(uchar const *pattern) const
 487 {
 488     TextPosition m = strlen((char const *)pattern);
 489     if (m == 0)
 490         return TextCollection::document_result(); // FIXME Should return all empty texts
 491
 492     TextPosition sp = 0, ep = 0;
 493     // Match including end-marker
 494     Search(pattern, m+1, &sp, &ep);
 495
 496     // Report end-markers in result interval
 497     return EnumerateEndmarkers(sp, ep);
 498 }
 499
 500 TextCollection::document_result TCImplementation::Equal(uchar const *pattern, DocId begin, DocId end) const
 501 {
 502     TextPosition m = strlen((char const *)pattern);
 503     if (m == 0)
 504         return TextCollection::document_result(); // FIXME Should return all empty texts
 505
 506     TextPosition sp = 0, ep = 0;
 507     // Match including end-marker
 508     Search(pattern, m+1, &sp, &ep, begin, end);
 509
 510     // Report end-markers in result interval
 511     return EnumerateEndmarkers(sp, ep, begin, end);
 512 }
 513
 514
 515 TextCollection::document_result TCImplementation::Contains(uchar const * pattern) const
 516 {
 517     TextPosition m = strlen((char *)pattern);
 518     if (m == 0)
 519         return TextCollection::document_result();
 520
 521     TextPosition sp = 0, ep = 0;
 522     // Search all occurrences
 523     Search(pattern, m, &sp, &ep);
 524
 525     // We want unique document indentifiers, using std::set to collect them
 526     std::set<DocId> resultSet;
 527
 528     ulong sampled_rank_i = 0;
 529     // Check each occurrence
 530     for (; sp <= ep; ++sp)
 531     {
 532         TextPosition i = sp;
 533         uchar c = alphabetrank->access(i);
 534         while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
 535         {
 536             i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping
 537             c = alphabetrank->access(i);
 538         }
 539         if (c == '\0')
 540         {
 541             // Rank among the end-markers in BWT
 542             unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
 543             resultSet.insert(Doc->access(endmarkerRank));
 544         }
 545         else
 546         {
 547             DocId di = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
 548             assert((unsigned)di < numberOfTexts);
 549             resultSet.insert(di);
 550         }
 551     }
 552
 553     // Convert std::set to std::vector
 554     TextCollection::document_result result(resultSet.begin(), resultSet.end());
 555     return result;
 556 }
 557
 558 TextCollection::document_result TCImplementation::Contains(uchar const * pattern, DocId begin, DocId end) const
 559 {
 560     TextPosition m = strlen((char *)pattern);
 561     if (m == 0)
 562         return TextCollection::document_result();
 563
 564     TextPosition sp = 0, ep = 0;
 565     // Search all occurrences
 566     Search(pattern, m, &sp, &ep);
 567
 568     // We want unique document indentifiers, using std::set to collect them
 569     std::set<DocId> resultSet;
 570
 571     ulong sampled_rank_i = 0;
 572     // Check each occurrence
 573     for (; sp <= ep; ++sp)
 574     {
 575         TextPosition i = sp;
 576         uchar c = alphabetrank->access(i);
 577         while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
 578         {
 579             i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping
 580             c = alphabetrank->access(i);
 581         }
 582         if (c == '\0')
 583         {
 584             // Rank among the end-markers in BWT
 585             unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
 586             DocId docId = Doc->access(endmarkerRank);
 587             if (docId >= begin && docId <= end)
 588                 resultSet.insert(docId);
 589         }
 590         else
 591         {
 592             DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
 593             assert((unsigned)docId < numberOfTexts);
 594             if (docId >= begin && docId <= end)
 595                 resultSet.insert(docId);
 596         }
 597     }
 598
 599     // Convert std::set to std::vector
 600     TextCollection::document_result result(resultSet.begin(), resultSet.end());
 601     return result;
 602 }
 603
 604 TextCollection::document_result TCImplementation::LessThan(uchar const * pattern) const
 605 {
 606     TextPosition m = strlen((char *)pattern);
 607     if (m == 0)
 608         return TextCollection::document_result(); // empty result set
 609
 610     TextPosition sp = 0, ep = 0;
 611     SearchLessThan(pattern, m, &sp, &ep);
 612
 613     // Report end-markers in result interval
 614     return EnumerateEndmarkers(sp, ep);
 615 }
 616
 617 TextCollection::document_result TCImplementation::LessThan(uchar const * pattern, DocId begin, DocId end) const
 618 {
 619     TextPosition m = strlen((char *)pattern);
 620     if (m == 0)
 621         return TextCollection::document_result(); // empty result set
 622
 623     TextPosition sp = 0, ep = 0;
 624     SearchLessThan(pattern, m, &sp, &ep);
 625
 626     // Iterate through end-markers in [sp,ep] and [begin, end]:
 627     return EnumerateEndmarkers(sp, ep, begin, end);
 628 }
 629
 630 /**
 631  * Full result set queries
 632  */
 633 TextCollection::full_result TCImplementation::FullContains(uchar const * pattern) const
 634 {
 635     TextPosition m = strlen((char *)pattern);
 636     if (m == 0)
 637         return full_result(); // FIXME Throw exception?
 638
 639     TextPosition sp = 0, ep = 0;
 640     // Search all occurrences
 641     Search(pattern, m, &sp, &ep);
 642
 643     full_result result;
 644     result.reserve(ep-sp+1); // Try to avoid reallocation.
 645
 646     ulong sampled_rank_i = 0;
 647     // Report each occurrence
 648     for (; sp <= ep; ++sp)
 649     {
 650         TextPosition i = sp;
 651         TextPosition dist = 0;
 652         uchar c = alphabetrank->access(i);
 653         while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
 654         {
 655             i = C[c]+alphabetrank->rank(c,i)-1;
 656             c = alphabetrank->access(i);
 657             ++ dist;
 658         }
 659         if (c == '\0')
 660         {
 661             // Rank among the end-markers in BWT
 662             unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
 663             DocId docId = Doc->access(endmarkerRank);
 664             result.push_back(make_pair(docId, dist));
 665         }
 666         else
 667         {
 668             TextPosition textPos = (*suffixes)[sampled_rank_i-1]+dist; //sampled->rank(i)-1] + dist;
 669             DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
 670 //            textPos = textPos - (*textStartPos)[docId]; // Offset inside the text
 671
 672             result.push_back(make_pair(docId, textPos));
 673         }
 674     }
 675
 676     return result;
 677 }
 678
 679 TextCollection::full_result TCImplementation::FullContains(uchar const * pattern, DocId begin, DocId end) const
 680 {
 681     TextPosition m = strlen((char *)pattern);
 682     if (m == 0)
 683         return full_result(); // FIXME Throw exception?
 684
 685     TextPosition sp = 0, ep = 0;
 686     // Search all occurrences
 687     Search(pattern, m, &sp, &ep);
 688
 689     full_result result;
 690     result.reserve(ep-sp+1); // Try to avoid reallocation.
 691
 692     ulong sampled_rank_i = 0;
 693     // Report each occurrence
 694     for (; sp <= ep; ++sp)
 695     {
 696         TextPosition i = sp;
 697         TextPosition dist = 0;
 698         uchar c = alphabetrank->access(i);
 699         while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
 700         {
 701             i = C[c]+alphabetrank->rank(c,i)-1;
 702             c = alphabetrank->access(i);
 703             ++ dist;
 704         }
 705         if (c == '\0')
 706         {
 707             // Rank among the end-markers in BWT
 708             unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
 709
 710             // End-marker that we found belongs to the "preceeding" doc in collection:
 711             DocId docId = Doc->access(endmarkerRank);
 712             if (docId >= begin && docId <= end)
 713                 result.push_back(make_pair(docId, dist));
 714         }
 715         else
 716         {
 717             TextPosition textPos = (*suffixes)[sampled_rank_i-1]+dist; //sampled->rank(i)-1] + dist;
 718             DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
 719 //            textPos = textPos - (*textStartPos)[docId]; // Offset inside the text
 720
 721             if (docId >= begin && docId <= end)
 722                 result.push_back(make_pair(docId, textPos));
 723         }
 724     }
 725
 726     return result;
 727 }
 728
 729
 730 /**
 731  * Save index to a file handle
 732  *
 733  * Throws a std::runtime_error exception on i/o error.
 734  * First byte that is saved represents the version number of the save file.
 735  * In version 2 files, the data fields are:
 736  *  uchar versionFlag;
 737     TextPosition n;
 738     unsigned samplerate;
 739     unsigned C[256];
 740     TextPosition bwtEndPos;
 741     static_sequence * alphabetrank;
 742     BSGAP *sampled;
 743     BlockArray *suffixes;
 744     BlockArray *suffixDocId;
 745     unsigned numberOfTexts;
 746     ulong maxTextLength;
 747     static_sequence *docId;
 748  */
 749 void TCImplementation::Save(FILE *file) const
 750 {
 751     // Saving version info:
 752     if (std::fwrite(&versionFlag, 1, 1, file) != 1)
 753         throw std::runtime_error("TCImplementation::Save(): file write error (version flag).");
 754
 755     if (std::fwrite(&(this->n), sizeof(TextPosition), 1, file) != 1)
 756         throw std::runtime_error("TCImplementation::Save(): file write error (n).");
 757     if (std::fwrite(&(this->samplerate), sizeof(unsigned), 1, file) != 1)
 758         throw std::runtime_error("TCImplementation::Save(): file write error (samplerate).");
 759
 760     for(ulong i = 0; i < 256; ++i)
 761         if (std::fwrite(this->C + i, sizeof(unsigned), 1, file) != 1)
 762             throw std::runtime_error("TCImplementation::Save(): file write error (C table).");
 763
 764     if (std::fwrite(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1)
 765         throw std::runtime_error("TCImplementation::Save(): file write error (bwt end position).");
 766
 767     alphabetrank->save(file);
 768     sampled->Save(file);
 769     suffixes->Save(file);
 770     suffixDocId->Save(file);
 771
 772     if (std::fwrite(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
 773         throw std::runtime_error("TCImplementation::Save(): file write error (numberOfTexts).");
 774     if (std::fwrite(&(this->maxTextLength), sizeof(ulong), 1, file) != 1)
 775         throw std::runtime_error("TCImplementation::Save(): file write error (maxTextLength).");
 776
 777     Doc->save(file);
 778     fflush(file);
 779 }
 780
 781
 782 /**
 783  * Load index from a file handle
 784  *
 785  * Throws a std::runtime_error exception on i/o error.
 786  * For more info, see TCImplementation::Save().
 787  */
 788 TCImplementation::TCImplementation(FILE *file, unsigned samplerate_)
 789     : n(0), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0),
 790       suffixDocId(0), numberOfTexts(0), maxTextLength(0), Doc(0)
 791 {
 792     uchar verFlag = 0;
 793     if (std::fread(&verFlag, 1, 1, file) != 1)
 794         throw std::runtime_error("TCImplementation::Load(): file read error (version flag).");
 795     if (verFlag != TCImplementation::versionFlag)
 796         throw std::runtime_error("TCImplementation::Load(): invalid save file version.");
 797
 798     if (std::fread(&(this->n), sizeof(TextPosition), 1, file) != 1)
 799         throw std::runtime_error("TCImplementation::Load(): file read error (n).");
 800     if (std::fread(&samplerate, sizeof(unsigned), 1, file) != 1)
 801         throw std::runtime_error("TCImplementation::Load(): file read error (samplerate).");
 802 // FIXME samplerate can not be changed during load.
 803 //    if (this->samplerate == 0)
 804 //        this->samplerate = samplerate;
 805
 806     for(ulong i = 0; i < 256; ++i)
 807         if (std::fread(this->C + i, sizeof(unsigned), 1, file) != 1)
 808             throw std::runtime_error("TCImplementation::Load(): file read error (C table).");
 809
 810     if (std::fread(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1)
 811         throw std::runtime_error("TCImplementation::Load(): file read error (bwt end position).");
 812
 813     alphabetrank = static_sequence::load(file);
 814     sampled = new BSGAP(file);
 815     suffixes = new BlockArray(file);
 816     suffixDocId = new BlockArray(file);
 817
 818     if (std::fread(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
 819         throw std::runtime_error("TCImplementation::Load(): file read error (numberOfTexts).");
 820     if (std::fread(&(this->maxTextLength), sizeof(ulong), 1, file) != 1)
 821         throw std::runtime_error("TCImplementation::Load(): file read error (maxTextLength).");
 822
 823     Doc = static_sequence::load(file);
 824
 825     // FIXME Construct data structures with new samplerate
 826     //maketables();
 827 }
 828
 829
 830
 831 /**
 832  * Rest of the functions follow...
 833  */
 834
 835
 836
 837 ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const
 838 {
 839     // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
 840     int c = (int)pattern[m-1];
 841     TextPosition i=m-1;
 842     TextPosition sp = C[c];
 843     TextPosition ep = C[c+1]-1;
 844     while (sp<=ep && i>=1)
 845     {
 846 //         printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
 847         c = (int)pattern[--i];
 848         sp = C[c]+alphabetrank->rank(c,sp-1);
 849         ep = C[c]+alphabetrank->rank(c,ep)-1;
 850     }
 851     *spResult = sp;
 852     *epResult = ep;
 853     if (sp<=ep)
 854         return ep - sp + 1;
 855     else
 856         return 0;
 857 }
 858
 859 ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult, DocId begin, DocId end) const
 860 {
 861     // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
 862     int c = (int)pattern[m-1];
 863     assert(c == 0); // Start from endmarkers
 864     TextPosition i=m-1;
 865     TextPosition sp = begin;
 866     TextPosition ep = end;
 867     while (sp<=ep && i>=1)
 868     {
 869 //         printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
 870         c = (int)pattern[--i];
 871         sp = C[c]+alphabetrank->rank(c,sp-1);
 872         ep = C[c]+alphabetrank->rank(c,ep)-1;
 873     }
 874     *spResult = sp;
 875     *epResult = ep;
 876     if (sp<=ep)
 877         return ep - sp + 1;
 878     else
 879         return 0;
 880 }
 881
 882
 883 ulong TCImplementation::SearchLessThan(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const
 884 {
 885     // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
 886     uint c = (int)pattern[m-1];
 887     TextPosition i=m-1;
 888     TextPosition sp = 1;
 889     TextPosition ep = C[c+1]-1;
 890     while (sp<=ep && i>=1)
 891     {
 892 //         printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
 893         c = (int)pattern[--i];
 894         uint result = alphabetrank->rank(c,ep);
 895         if (result == ~0u)
 896             ep = 0;
 897         else
 898             ep = C[c]+result-1;
 899     }
 900     *spResult = sp;
 901     *epResult = ep;
 902     if (sp<=ep)
 903         return ep - sp + 1;
 904     else
 905         return 0;
 906 }
 907
 908
 909 TCImplementation::~TCImplementation() {
 910     delete alphabetrank;
 911     delete sampled;
 912     delete suffixes;
 913     delete suffixDocId;
 914     delete Doc;
 915 }
 916
 917 void TCImplementation::makewavelet(uchar *bwt)
 918 {
 919     ulong i, min = 0,
 920              max;
 921     for (i=0;i<256;i++)
 922         C[i]=0;
 923     for (i=0;i<n;++i)
 924         C[(int)bwt[i]]++;
 925     for (i=0;i<256;i++)
 926         if (C[i]>0) {min = i; break;}
 927     for (i=255;i>=min;--i)
 928         if (C[i]>0) {max = i; break;}
 929
 930     ulong prev=C[0], temp;
 931     C[0]=0;
 932     for (i=1;i<256;i++) {
 933         temp = C[i];
 934         C[i]=C[i-1]+prev;
 935         prev = temp;
 936     }
 937 //    this->codetable = node::makecodetable(bwt,n);
 938 //    alphabetrank = new THuffAlphabetRank(bwt,n, this->codetable,0);
 939 //    delete [] bwt;
 940     //alphabetrank = new RLWaveletTree(bwt, n); // Deletes bwt!
 941 //  std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
 942 //    std::cerr << "max heap usage before WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
 943
 944 //    HeapProfiler::ResetMaxHeapConsumption(); // FIXME remove
 945
 946     alphabet_mapper * am = new alphabet_mapper_none();
 947     static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(8); // FIXME samplerate?
 948 //    static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(16); // FIXME samplerate?
 949     wt_coder * wtc = new wt_coder_binary(bwt,n,am);
 950     alphabetrank = new static_sequence_wvtree(bwt,n,wtc,bmb,am);
 951     delete bmb;
 952     bwt = 0; // already deleted
 953
 954 //    std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
 955 //    std::cerr << "max heap usage after WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
 956 }
 957
 958 void TCImplementation::maketables()
 959 {
 960     // Calculate BWT end-marker position (of last inserted text)
 961     {
 962         ulong i = 0;
 963         uint alphabetrank_i_tmp = 0;
 964         uchar c  = alphabetrank->access(i, alphabetrank_i_tmp);
 965         while (c != '\0')
 966         {
 967             i = C[c]+alphabetrank_i_tmp-1;
 968             c = alphabetrank->access(i, alphabetrank_i_tmp);
 969         }
 970
 971         this->bwtEndPos = i;
 972     }
 973
 974     // Build up arrays for text length and starting positions
 975     // FIXME Temp, remove
 976     //BlockArray* textLength = new BlockArray(numberOfTexts, Tools::CeilLog2(maxTextLength));
 977     BlockArray* textStartPos = new BlockArray(numberOfTexts, Tools::CeilLog2(this->n));
 978     //(*textLength)[0] = l;
 979     (*textStartPos)[0] = 0;
 980
 981     // Construct samples
 982     ulong sampleLength = (n%samplerate==0) ? n/samplerate : n/samplerate+1;
 983     unsigned ceilLog2n = Tools::CeilLog2(n);
 984     BlockArray* positions = new BlockArray(sampleLength, ceilLog2n);
 985     BlockArray* tmpSuffix = new BlockArray(sampleLength, ceilLog2n);
 986
 987     // Mapping from end-markers to doc ID's:
 988     BlockArray *endmarkerDocId = new BlockArray(numberOfTexts, Tools::CeilLog2(numberOfTexts));
 989
 990     ulong *sampledpositions = new ulong[n/W+1];
 991     for (ulong i=0;i<n/W+1;i++)
 992         sampledpositions[i]=0lu;
 993
 994     ulong x,p=bwtEndPos;
 995     ulong sampleCount = 0;
 996     // Keeping track of text position of prev. end-marker seen
 997     ulong posOfSuccEndmarker = n;
 998     DocId textId = numberOfTexts;
 999     ulong ulongmax = 0;
1000     ulongmax--;
1001     uint alphabetrank_i_tmp =0;
1002
1003     //positions:
1004     for (ulong i=n-1;i<ulongmax;i--) { // TODO bad solution with ulongmax?
1005       // i substitutes SA->GetPos(i)
1006         x=(i==n-1)?0:i+1;
1007
1008         if (x % samplerate == 0 && posOfSuccEndmarker - x > samplerate) {
1009             Tools::SetField(sampledpositions,1,p,1);
1010             (*positions)[sampleCount] = p;
1011             (*tmpSuffix)[sampleCount] = x; // FIXME remove
1012             sampleCount ++;
1013         }
1014
1015         uchar c = alphabetrank->access(p, alphabetrank_i_tmp);
1016         if (c == '\0')
1017         {
1018             --textId;
1019
1020             // Record the order of end-markers in BWT:
1021             ulong endmarkerRank = alphabetrank_i_tmp - 1;
1022             (*endmarkerDocId)[endmarkerRank] = textId;
1023
1024             // Store text length and text start position:
1025             if (textId < (DocId)numberOfTexts - 1)
1026             {
1027                 //(*textLength)[textId + 1] = posOfSuccEndmarker - x;
1028                 (*textStartPos)[textId + 1] = x;  // x is the position of end-marker.
1029                 posOfSuccEndmarker = x;
1030             }
1031
1032             // LF-mapping from '\0' does not work with this (pseudo) BWT (see details from Wolfgang's thesis).
1033             p = textId; // Correct LF-mapping to the last char of the previous text.
1034         }
1035         else
1036             p = C[c]+alphabetrank_i_tmp-1;
1037     }
1038     assert(textId == 0);
1039
1040     sampled = new BSGAP(sampledpositions,n,true);
1041     sampleLength = sampled->rank(n-1);
1042     assert(sampleCount == sampleLength);
1043
1044     // Suffixes store an offset from the text start position
1045     suffixes = new BlockArray(sampleLength, Tools::CeilLog2(maxTextLength));
1046     suffixDocId = new BlockArray(sampleLength, Tools::CeilLog2(numberOfTexts));
1047
1048     for(ulong i=0; i<sampleLength; i++) {
1049         assert((*positions)[i] < n);
1050         ulong j = sampled->rank((*positions)[i]);
1051         if (j==0) j=sampleLength;
1052         TextPosition textPos = (*tmpSuffix)[i];
1053         (*suffixDocId)[j-1] = DocIdAtTextPos(textStartPos, textPos);
1054
1055         assert((unsigned)DocIdAtTextPos(textStartPos, textPos) < numberOfTexts);
1056         assert((*suffixDocId)[j-1] < numberOfTexts);
1057         // calculate offset from text start:
1058         (*suffixes)[j-1] = textPos - (*textStartPos)[(*suffixDocId)[j-1]];
1059     }
1060     // FIXME Temp, remove
1061     delete tmpSuffix;
1062     delete positions;
1063 //    delete textLength;
1064     delete textStartPos;
1065
1066
1067     uint *tmp = new uint[numberOfTexts]; // FIXME Silly...
1068 //    cout << "Doc: ";
1069     for (unsigned i = 0; i < numberOfTexts; ++i)
1070     {
1071         tmp[i] = ((*endmarkerDocId)[i] + 1) % numberOfTexts;
1072         //      cout << tmp[i] << ", ";
1073     }
1074 //    cout << endl;
1075     delete endmarkerDocId;
1076     alphabet_mapper * am = new alphabet_mapper_none();
1077     static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(16); // FIXME samplerate?
1078     wt_coder * wtc = new wt_coder_binary(tmp, numberOfTexts, am);
1079     Doc = new static_sequence_wvtree(tmp, numberOfTexts, wtc, bmb, am);
1080     delete bmb;
1081     delete [] tmp;
1082
1083     /*    document_result res = Doc->access(1, 2, 0, 1);
1084     cout << "result: ";
1085     for (document_result::iterator it = res.begin(); it != res.end(); ++it)
1086         cout << *it << ", ";
1087         cout << endl;*/
1088 }
1089
1090
1091 /**
1092  * Finds document identifier for given text position
1093  *
1094  * Starting text position of the document is stored into second parameter.
1095  * Binary searching on text starting positions.
1096  */
1097 TextCollection::DocId TCImplementation::DocIdAtTextPos(BlockArray* textStartPos, TextPosition i) const
1098 {
1099     assert(i < n);
1100
1101     DocId a = 0;
1102     DocId b = numberOfTexts - 1;
1103     while (a < b)
1104     {
1105         DocId c = a + (b - a)/2;
1106         if ((*textStartPos)[c] > i)
1107             b = c - 1;
1108         else if ((*textStartPos)[c+1] > i)
1109             return c;
1110         else
1111             a = c + 1;
1112     }
1113
1114     assert(a < (DocId)numberOfTexts);
1115     assert(i >= (*textStartPos)[a]);
1116     assert(i < (a == (DocId)numberOfTexts - 1 ? n : (*textStartPos)[a+1]));
1117     return a;
1118 }
1119
1120
1121 } // namespace SXSI
1122