[3365] | 1 | /**************************************************************************
|
---|
| 2 | *
|
---|
| 3 | * ivf.pass1.cpp -- Memory efficient pass 1 inversion
|
---|
| 4 | * Copyright (C) 1999 Rodger McNab
|
---|
| 5 | *
|
---|
| 6 | * This program is free software; you can redistribute it and/or modify
|
---|
| 7 | * it under the terms of the GNU General Public License as published by
|
---|
| 8 | * the Free Software Foundation; either version 2 of the License, or
|
---|
| 9 | * (at your option) any later version.
|
---|
| 10 | *
|
---|
| 11 | * This program is distributed in the hope that it will be useful,
|
---|
| 12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 14 | * GNU General Public License for more details.
|
---|
| 15 | *
|
---|
| 16 | * You should have received a copy of the GNU General Public License
|
---|
| 17 | * along with this program; if not, write to the Free Software
|
---|
| 18 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
---|
| 19 | *
|
---|
| 20 | **************************************************************************/
|
---|
| 21 |
|
---|
| 22 | #include "UCArray.h"
|
---|
| 23 | #include "sysfuncs.h"
|
---|
| 24 | #include "mg_files.h"
|
---|
| 25 | #include "invf.h"
|
---|
| 26 | #include "mg.h"
|
---|
| 27 | #include "build.h"
|
---|
| 28 | #include "locallib.h"
|
---|
| 29 | #include "bitio_m_stdio.h"
|
---|
| 30 | #include "bitio_gen.h"
|
---|
| 31 | #include <stdio.h>
|
---|
| 32 | #include "words.h"
|
---|
| 33 | #include "messages.h"
|
---|
| 34 | #include "netorder.h"
|
---|
| 35 | #include "FIvfLevelInfo.h"
|
---|
| 36 |
|
---|
| 37 | #include "longlong.h"
|
---|
| 38 |
|
---|
| 39 | #if defined(GSDL_USE_OBJECTSPACE)
|
---|
| 40 | # include <ospace\std\map>
|
---|
| 41 | #elif defined(GSDL_USE_STL_H)
|
---|
| 42 | # include <map.h>
|
---|
| 43 | #else
|
---|
| 44 | # include <map>
|
---|
| 45 | #endif
|
---|
| 46 |
|
---|
| 47 | // a fragment corresponds to the index level (word-level is the
|
---|
| 48 | // minimum index level)
|
---|
| 49 |
|
---|
| 50 |
|
---|
| 51 | // structure to determine level information
|
---|
| 52 | struct LevelWorker {
|
---|
| 53 | unsigned long lastLevelDocNum;
|
---|
| 54 | unsigned long count;
|
---|
| 55 |
|
---|
| 56 | LevelWorker () {
|
---|
| 57 | lastLevelDocNum = count = 0;
|
---|
| 58 | }
|
---|
| 59 | };
|
---|
| 60 |
|
---|
| 61 |
|
---|
| 62 | // note: the word is stored in the map
|
---|
| 63 | struct IvfWordInfo {
|
---|
| 64 | unsigned long wordCount; // word frequency
|
---|
| 65 | unsigned long fragCount; // number of fragments that contain the word
|
---|
| 66 | unsigned long lastFragNum; // last fragment to contain the word
|
---|
| 67 | unsigned long chunkWordCount; // word frequency within this chunk
|
---|
| 68 | unsigned long chunkFragCount; // number of fragments within this chunk that
|
---|
| 69 | // contain the word
|
---|
| 70 |
|
---|
| 71 | LevelWorker *levels; // level info for this word
|
---|
| 72 |
|
---|
| 73 | IvfWordInfo ();
|
---|
| 74 | ~IvfWordInfo ();
|
---|
| 75 | void Clear (); // will delete levels
|
---|
| 76 | };
|
---|
| 77 |
|
---|
| 78 | typedef map<UCArray, IvfWordInfo, DictLTUCArray> IvfWordInfoMap;
|
---|
| 79 | typedef vector<IvfWordInfoMap::iterator> IvfWordInfoItArray;
|
---|
| 80 |
|
---|
| 81 | // tags don't require as much information
|
---|
| 82 | struct IvfTagInfo {
|
---|
| 83 | unsigned long tagCount; // tag frequency
|
---|
| 84 | unsigned long fragCount; // number of fragments that contain the tag
|
---|
| 85 | unsigned long lastFragNum; // last fragment to contain the tag
|
---|
| 86 | unsigned long chunkFragCount; // number of fragments within this chunk that
|
---|
| 87 | // contain the tag
|
---|
| 88 |
|
---|
| 89 | IvfTagInfo ();
|
---|
| 90 | void Clear ();
|
---|
| 91 | };
|
---|
| 92 |
|
---|
| 93 | typedef map<UCArray, IvfTagInfo, DictLTUCArray> IvfTagInfoMap;
|
---|
| 94 | typedef vector<IvfTagInfoMap::iterator> IvfTagInfoItArray;
|
---|
| 95 |
|
---|
| 96 |
|
---|
| 97 | #define INIT_CHECK_FRAC 0.10
|
---|
| 98 | #define CHECK_FRAC 0.75
|
---|
| 99 | #define CHECK_CLOSE 0.999
|
---|
| 100 | #define CHECK_DIV 1.5
|
---|
| 101 |
|
---|
| 102 |
|
---|
| 103 | static FILE *ic; // the invf chunk file
|
---|
| 104 | static stdio_bitio_buffer icb;
|
---|
| 105 |
|
---|
| 106 | IvfWordInfoMap ivfWordInfo;
|
---|
| 107 | IvfWordInfoItArray ivfWordInfoOccurOrder;
|
---|
| 108 | IvfTagInfoMap ivfTagInfo;
|
---|
| 109 | IvfTagInfoItArray ivfTagInfoOccurOrder;
|
---|
| 110 |
|
---|
| 111 | static unsigned long chunksWritten;
|
---|
| 112 | static unsigned long maxMemNeeded;
|
---|
| 113 |
|
---|
| 114 | static unsigned long numDocs;
|
---|
| 115 | static unsigned long numChunkDocs;
|
---|
| 116 |
|
---|
| 117 | static unsigned long numFrags;
|
---|
| 118 | static unsigned long numChunkFrags;
|
---|
| 119 |
|
---|
| 120 | static unsigned long numWords;
|
---|
| 121 |
|
---|
| 122 | // the number of document numbers in the inverted file
|
---|
| 123 | static unsigned long numChunkEntries;
|
---|
| 124 |
|
---|
| 125 | // next entry in the inverted file to check memory
|
---|
| 126 | // requirements for the current chunk
|
---|
| 127 | static unsigned long entryCheckPoint;
|
---|
| 128 |
|
---|
| 129 | // information about all the different levels
|
---|
| 130 | static FIvfLevel ivfLevel;
|
---|
| 131 |
|
---|
| 132 |
|
---|
| 133 |
|
---|
| 134 | IvfWordInfo::IvfWordInfo () {
|
---|
| 135 | levels = NULL;
|
---|
| 136 | Clear();
|
---|
| 137 | }
|
---|
| 138 |
|
---|
| 139 | IvfWordInfo::~IvfWordInfo () {
|
---|
| 140 | if (levels != NULL) delete [] levels;
|
---|
| 141 | }
|
---|
| 142 |
|
---|
| 143 | void IvfWordInfo::Clear () {
|
---|
| 144 | wordCount = 0;
|
---|
| 145 | chunkWordCount = 0;
|
---|
| 146 | lastFragNum = 0;
|
---|
| 147 | fragCount = 0;
|
---|
| 148 | chunkFragCount = 0;
|
---|
| 149 |
|
---|
| 150 | if (levels != NULL) {
|
---|
| 151 | delete [] levels;
|
---|
| 152 | levels = NULL;
|
---|
| 153 | }
|
---|
| 154 | }
|
---|
| 155 |
|
---|
| 156 |
|
---|
| 157 | IvfTagInfo::IvfTagInfo () {
|
---|
| 158 | Clear();
|
---|
| 159 | }
|
---|
| 160 |
|
---|
| 161 | void IvfTagInfo::Clear () {
|
---|
| 162 | tagCount = 0;
|
---|
| 163 | lastFragNum = 0;
|
---|
| 164 | fragCount = 0;
|
---|
| 165 | chunkFragCount = 0;
|
---|
| 166 | }
|
---|
| 167 |
|
---|
| 168 |
|
---|
| 169 |
|
---|
| 170 | int init_ivf_1 (const TagInfo &tagInfo, char *file_name) {
|
---|
| 171 | // set up the chunk file
|
---|
| 172 | if (!(ic = create_file (file_name, INVF_CHUNK_SUFFIX, "wb",
|
---|
| 173 | MAGIC_CHUNK, MG_MESSAGE)))
|
---|
| 174 | return COMPERROR;
|
---|
| 175 | fwrite (" ", sizeof (u_long), 1, ic); // Space for the maxmem
|
---|
| 176 | icb.attachFile (ic);
|
---|
| 177 | icb.encodeStart();
|
---|
| 178 |
|
---|
| 179 | // reset global variables
|
---|
| 180 | ivfWordInfo.erase (ivfWordInfo.begin(), ivfWordInfo.end());
|
---|
| 181 | ivfWordInfoOccurOrder.erase (ivfWordInfoOccurOrder.begin(), ivfWordInfoOccurOrder.end());
|
---|
| 182 | ivfTagInfo.erase (ivfTagInfo.begin(), ivfTagInfo.end());
|
---|
| 183 | ivfTagInfoOccurOrder.erase (ivfTagInfoOccurOrder.begin(), ivfTagInfoOccurOrder.end());
|
---|
| 184 |
|
---|
| 185 | chunksWritten = 0;
|
---|
| 186 | maxMemNeeded = 0;
|
---|
| 187 |
|
---|
| 188 | numDocs = 0;
|
---|
| 189 | numChunkDocs = 0;
|
---|
| 190 |
|
---|
| 191 | numFrags = 0;
|
---|
| 192 | numChunkFrags = 0;
|
---|
| 193 |
|
---|
| 194 | numWords = 0;
|
---|
| 195 |
|
---|
| 196 | numChunkEntries = 0;
|
---|
| 197 | entryCheckPoint = (unsigned long) ((invf_buffer_size * INIT_CHECK_FRAC) / CHECK_DIV);
|
---|
| 198 |
|
---|
| 199 | // init the level information
|
---|
| 200 | ivfLevel.Clear();
|
---|
| 201 | ivfLevel.docTag = tagInfo.docTag;
|
---|
| 202 | ivfLevel.indexLevel = tagInfo.indexLevel;
|
---|
| 203 | IvfLevelInfo blankLevel;
|
---|
| 204 | UCArraySet::const_iterator levelHere = tagInfo.levelTags.begin();
|
---|
| 205 | UCArraySet::const_iterator levelEnd = tagInfo.levelTags.end();
|
---|
| 206 | while (levelHere != levelEnd) {
|
---|
| 207 | blankLevel.levelTag = *levelHere;
|
---|
| 208 | ivfLevel.levelInfo[*levelHere] = blankLevel;
|
---|
[9613] | 209 | ++levelHere;
|
---|
[3365] | 210 | }
|
---|
| 211 |
|
---|
| 212 | return COMPALLOK;
|
---|
| 213 | }
|
---|
| 214 |
|
---|
| 215 | static void ProcessOpenTag (const TagInfo &tagInfo, const TextEl &el,
|
---|
| 216 | bool &inFrag) {
|
---|
| 217 | bool wordLevelIndex = tagInfo.indexLevel.empty();
|
---|
| 218 |
|
---|
| 219 | // check for start of next fragment
|
---|
| 220 | if (!wordLevelIndex && el.tagName == tagInfo.indexLevel) {
|
---|
[9613] | 221 | ++numFrags;
|
---|
| 222 | ++numChunkFrags;
|
---|
[3365] | 223 | inFrag = true;
|
---|
| 224 | }
|
---|
| 225 |
|
---|
| 226 | // update tag stats
|
---|
| 227 | IvfTagInfo &i = ivfTagInfo[el.tagName];
|
---|
| 228 | if (i.tagCount == 0) {
|
---|
| 229 | // new tag, add to list of iterators
|
---|
| 230 | IvfTagInfoMap::iterator iIt = ivfTagInfo.find (el.tagName);
|
---|
| 231 | ivfTagInfoOccurOrder.push_back (iIt);
|
---|
| 232 | }
|
---|
[9613] | 233 | ++i.tagCount;
|
---|
[3365] | 234 |
|
---|
| 235 | // all open tags count as new tags
|
---|
[9613] | 236 | ++numChunkEntries;
|
---|
| 237 | ++i.fragCount;
|
---|
| 238 | ++i.chunkFragCount;
|
---|
[3365] | 239 | i.lastFragNum = numFrags;
|
---|
| 240 |
|
---|
| 241 | // update level information
|
---|
| 242 | IvfLevelInfoMap::iterator levelIt = ivfLevel.levelInfo.find (el.tagName);
|
---|
| 243 | if (levelIt != ivfLevel.levelInfo.end()) {
|
---|
| 244 | // is a level tag
|
---|
[9613] | 245 | ++levelIt->second.numEntries;
|
---|
| 246 | levelIt->second.workInLevel = true;
|
---|
[3365] | 247 | }
|
---|
| 248 | }
|
---|
| 249 |
|
---|
| 250 | static void ProcessCloseTag (const TagInfo &tagInfo, const TextEl &el,
|
---|
| 251 | bool &inFrag) {
|
---|
| 252 | bool wordLevelIndex = tagInfo.indexLevel.empty();
|
---|
| 253 |
|
---|
| 254 | // check for end of fragment
|
---|
| 255 | if (!wordLevelIndex && el.tagName == tagInfo.indexLevel) {
|
---|
| 256 | inFrag = false;
|
---|
| 257 | }
|
---|
| 258 |
|
---|
| 259 | // update level information
|
---|
| 260 | IvfLevelInfoMap::iterator levelIt = ivfLevel.levelInfo.find (el.tagName);
|
---|
| 261 | if (levelIt != ivfLevel.levelInfo.end()) {
|
---|
| 262 | // is a level tag
|
---|
| 263 | (*levelIt).second.workInLevel = false;
|
---|
| 264 | }
|
---|
| 265 | }
|
---|
| 266 |
|
---|
| 267 | static void ProcessText (const TagInfo &tagInfo, const TextEl &el,
|
---|
| 268 | bool &inFrag) {
|
---|
| 269 | bool wordLevelIndex = tagInfo.indexLevel.empty();
|
---|
| 270 |
|
---|
| 271 | // make sure this text is to be indexed
|
---|
| 272 | if (!wordLevelIndex && !inFrag) return;
|
---|
| 273 |
|
---|
| 274 | const unsigned char *textHere = &(el.text[0]);
|
---|
| 275 | const unsigned char *textEnd = &(el.text[el.text.size() - 1]);
|
---|
| 276 | UCArray word;
|
---|
| 277 |
|
---|
| 278 | if (!inaword (textHere, textEnd))
|
---|
| 279 | ParseNonindexWord (textHere, textEnd);
|
---|
| 280 |
|
---|
| 281 |
|
---|
| 282 | // Alternately parse off words and non-words from the input
|
---|
| 283 | // Each token is then inserted into the set if it does
|
---|
| 284 | // not exist or has it's frequency count incremented if it does.
|
---|
| 285 |
|
---|
| 286 | while (textHere <= textEnd) {
|
---|
| 287 | textHere = ParseIndexWord (textHere, textEnd, word);
|
---|
| 288 | textHere = ParseNonindexWord (textHere, textEnd);
|
---|
| 289 |
|
---|
| 290 | if (!word.empty()) {
|
---|
[9613] | 291 | ++numWords;
|
---|
[3365] | 292 |
|
---|
| 293 | if (wordLevelIndex) {
|
---|
[9613] | 294 | ++numFrags;
|
---|
| 295 | ++numChunkFrags;
|
---|
[3365] | 296 | }
|
---|
| 297 |
|
---|
| 298 | // update word stats
|
---|
| 299 |
|
---|
| 300 | IvfWordInfo &i = ivfWordInfo[word];
|
---|
| 301 | if (i.wordCount == 0) {
|
---|
| 302 | // new word
|
---|
| 303 | // add to list of iterators
|
---|
| 304 | IvfWordInfoMap::iterator iIt = ivfWordInfo.find (word);
|
---|
| 305 | ivfWordInfoOccurOrder.push_back (iIt);
|
---|
| 306 |
|
---|
| 307 | // add level information array
|
---|
| 308 | if (ivfLevel.levelInfo.size() > 0)
|
---|
| 309 | i.levels = new LevelWorker [ivfLevel.levelInfo.size()];
|
---|
| 310 | }
|
---|
| 311 |
|
---|
[9613] | 312 | ++i.wordCount;
|
---|
| 313 | ++i.chunkWordCount;
|
---|
[3365] | 314 | if (numFrags > i.lastFragNum) {
|
---|
[9613] | 315 | ++numChunkEntries;
|
---|
| 316 | ++i.fragCount;
|
---|
| 317 | ++i.chunkFragCount;
|
---|
[3365] | 318 | i.lastFragNum = numFrags;
|
---|
| 319 | }
|
---|
| 320 |
|
---|
| 321 | // update level information for this word
|
---|
| 322 | if (i.levels != NULL) {
|
---|
| 323 | IvfLevelInfoMap::iterator levelHere = ivfLevel.levelInfo.begin();
|
---|
| 324 | IvfLevelInfoMap::iterator levelEnd = ivfLevel.levelInfo.end();
|
---|
| 325 | LevelWorker *levelWorkerPtr = i.levels;
|
---|
| 326 | while (levelHere != levelEnd) {
|
---|
| 327 |
|
---|
| 328 | // check to make sure the level encompases this fragment
|
---|
| 329 | if (!(*levelHere).second.workInLevel) {
|
---|
| 330 | cerr << "Level tag <" << (*levelHere).first
|
---|
| 331 | << "> does not encompass all fragments\n";
|
---|
| 332 | exit (1);
|
---|
| 333 | }
|
---|
| 334 |
|
---|
| 335 | if ((*levelHere).second.numEntries > (*levelWorkerPtr).lastLevelDocNum) {
|
---|
| 336 | (*levelWorkerPtr).lastLevelDocNum = (*levelHere).second.numEntries;
|
---|
[9613] | 337 | ++levelWorkerPtr->count;
|
---|
[3365] | 338 | }
|
---|
| 339 |
|
---|
[9613] | 340 | ++levelHere;
|
---|
| 341 | ++levelWorkerPtr;
|
---|
[3365] | 342 | }
|
---|
| 343 | }
|
---|
| 344 | }
|
---|
| 345 | }
|
---|
| 346 | }
|
---|
| 347 |
|
---|
| 348 |
|
---|
| 349 | static unsigned long MemoryRequired (bool wordLevelIndex) {
|
---|
| 350 | register unsigned long total = 0;
|
---|
| 351 |
|
---|
| 352 | // add memory required for word entries
|
---|
| 353 | IvfWordInfoMap::const_iterator wordHere = ivfWordInfo.begin();
|
---|
| 354 | IvfWordInfoMap::const_iterator wordEnd = ivfWordInfo.end();
|
---|
| 355 | while (wordHere != wordEnd) {
|
---|
| 356 | register const IvfWordInfo &info = (*wordHere).second;
|
---|
| 357 | if (info.chunkFragCount > 0) {
|
---|
| 358 | total += BIO_Bblock_Bound (numChunkFrags, info.chunkFragCount);
|
---|
| 359 | if (!wordLevelIndex) {
|
---|
| 360 | total += info.chunkWordCount;
|
---|
| 361 | }
|
---|
| 362 | }
|
---|
| 363 |
|
---|
[9613] | 364 | ++wordHere;
|
---|
[3365] | 365 | }
|
---|
| 366 |
|
---|
| 367 | // add memory required for tag entries
|
---|
| 368 | IvfTagInfoMap::const_iterator tagHere = ivfTagInfo.begin();
|
---|
| 369 | IvfTagInfoMap::const_iterator tagEnd = ivfTagInfo.end();
|
---|
| 370 | while (tagHere != tagEnd) {
|
---|
| 371 | register const IvfTagInfo &info = (*tagHere).second;
|
---|
| 372 | if (info.chunkFragCount > 0) {
|
---|
| 373 | // two d entries for each frag entry
|
---|
| 374 | unsigned long pTag = info.chunkFragCount*2;
|
---|
| 375 | total += BIO_Bblock_Bound (numChunkFrags+pTag, pTag);
|
---|
| 376 | }
|
---|
| 377 |
|
---|
[9613] | 378 | ++tagHere;
|
---|
[3365] | 379 | }
|
---|
| 380 |
|
---|
| 381 | total = (total + 7) >> 3;
|
---|
| 382 | return total;
|
---|
| 383 | }
|
---|
| 384 |
|
---|
| 385 |
|
---|
| 386 | /*
|
---|
| 387 | static void PrintChunkInfo (unsigned long mem) {
|
---|
| 388 | cout << "Chunk Number: " << chunksWritten << "\n";
|
---|
| 389 | cout << "numChunkDocs " << numChunkDocs << "\n";
|
---|
| 390 | cout << "numChunkFrags " << numChunkFrags << "\n";
|
---|
| 391 | cout << "mem " << mem << "\n";
|
---|
| 392 | cout << "numWords " << ivfWordInfo.size() << "\n";
|
---|
| 393 | cout << "numTags " << ivfTagInfo.size() << "\n\n";
|
---|
| 394 |
|
---|
| 395 | // output debug tag information in dictionary order
|
---|
| 396 | IvfTagInfoMap::iterator tagMapHere = ivfTagInfo.begin();
|
---|
| 397 | IvfTagInfoMap::iterator tagMapEnd = ivfTagInfo.end();
|
---|
| 398 | unsigned long tagNum = 0;
|
---|
| 399 | while (tagMapHere != tagMapEnd) {
|
---|
| 400 | cout << (*tagMapHere).first << " " << tagNum
|
---|
| 401 | << " " << (*tagMapHere).second.chunkFragCount << "\n";
|
---|
[9613] | 402 | ++tagNum;
|
---|
| 403 | ++tagMapHere;
|
---|
[3365] | 404 | }
|
---|
| 405 | }
|
---|
| 406 | */
|
---|
| 407 |
|
---|
| 408 | static void OutputChunkInfo (unsigned long mem, bool /*wordLevelIndex*/) {
|
---|
[9613] | 409 | ++chunksWritten;
|
---|
[3365] | 410 |
|
---|
| 411 | // sanity check
|
---|
| 412 | if (ivfWordInfo.size() != ivfWordInfoOccurOrder.size()) {
|
---|
| 413 | Message ("ERROR: Word information size mismatch: %u vs %u\n",
|
---|
| 414 | (unsigned int)ivfWordInfo.size(),
|
---|
| 415 | (unsigned int)ivfWordInfoOccurOrder.size());
|
---|
| 416 | exit (1);
|
---|
| 417 | }
|
---|
| 418 | if (ivfTagInfo.size() != ivfTagInfoOccurOrder.size()) {
|
---|
| 419 | Message ("ERROR: Tag information size mismatch: %u vs %u\n",
|
---|
| 420 | (unsigned int)ivfTagInfo.size(),
|
---|
| 421 | (unsigned int)ivfTagInfoOccurOrder.size());
|
---|
| 422 | exit (1);
|
---|
| 423 | }
|
---|
| 424 |
|
---|
| 425 | icb.gamma_encode (numChunkDocs + 1, NULL);
|
---|
| 426 | icb.gamma_encode (numChunkFrags + 1, NULL);
|
---|
| 427 | icb.gamma_encode (mem + 1, NULL);
|
---|
| 428 | icb.gamma_encode (ivfWordInfo.size() + 1, NULL);
|
---|
| 429 | icb.gamma_encode (ivfTagInfo.size() + 1, NULL);
|
---|
| 430 |
|
---|
| 431 | /* PrintChunkInfo (mem);*/
|
---|
| 432 |
|
---|
| 433 | // output word information in occurance order
|
---|
| 434 | IvfWordInfoItArray::iterator wordHere = ivfWordInfoOccurOrder.begin();
|
---|
| 435 | IvfWordInfoItArray::iterator wordEnd = ivfWordInfoOccurOrder.end();
|
---|
| 436 | while (wordHere != wordEnd) {
|
---|
| 437 | register IvfWordInfo &ivfWordInfo = (*(*wordHere)).second;
|
---|
| 438 |
|
---|
| 439 | icb.gamma_encode (ivfWordInfo.chunkWordCount + 1, NULL);
|
---|
| 440 | if (ivfWordInfo.chunkWordCount >= 2) {
|
---|
| 441 | icb.gamma_encode (ivfWordInfo.chunkFragCount, NULL);
|
---|
| 442 | }
|
---|
| 443 |
|
---|
| 444 | ivfWordInfo.lastFragNum = 0;
|
---|
| 445 | ivfWordInfo.chunkWordCount = 0;
|
---|
| 446 | ivfWordInfo.chunkFragCount = 0;
|
---|
| 447 |
|
---|
[9613] | 448 | ++wordHere;
|
---|
[3365] | 449 | }
|
---|
| 450 |
|
---|
| 451 | // output tag information in occurance order
|
---|
| 452 | IvfTagInfoItArray::iterator tagHere = ivfTagInfoOccurOrder.begin();
|
---|
| 453 | IvfTagInfoItArray::iterator tagEnd = ivfTagInfoOccurOrder.end();
|
---|
| 454 | while (tagHere != tagEnd) {
|
---|
| 455 | register IvfTagInfo &ivfTagInfo = (*(*tagHere)).second;
|
---|
| 456 |
|
---|
| 457 | icb.gamma_encode (ivfTagInfo.chunkFragCount + 1, NULL);
|
---|
| 458 |
|
---|
| 459 | ivfTagInfo.lastFragNum = 0;
|
---|
| 460 | ivfTagInfo.chunkFragCount = 0;
|
---|
| 461 |
|
---|
[9613] | 462 | ++tagHere;
|
---|
[3365] | 463 | }
|
---|
| 464 |
|
---|
| 465 | numChunkDocs = 0;
|
---|
| 466 | numChunkFrags = 0;
|
---|
| 467 | numChunkEntries = 0;
|
---|
| 468 | }
|
---|
| 469 |
|
---|
| 470 |
|
---|
| 471 | int process_ivf_1 (const TagInfo &tagInfo, const TextElArray &doc) {
|
---|
| 472 | bool wordLevelIndex = tagInfo.indexLevel.empty();
|
---|
| 473 | bool inFrag = false;
|
---|
| 474 | if (wordLevelIndex) inFrag = true; // unconditional
|
---|
| 475 |
|
---|
[9613] | 476 | ++numDocs;
|
---|
| 477 | ++numChunkDocs;
|
---|
[3365] | 478 |
|
---|
| 479 | // process each text element in this document
|
---|
| 480 | TextElArray::const_iterator here = doc.begin();
|
---|
| 481 | TextElArray::const_iterator end = doc.end();
|
---|
| 482 | while (here != end) {
|
---|
| 483 | if ((*here).elType == OpenTagE)
|
---|
| 484 | ProcessOpenTag (tagInfo, *here, inFrag);
|
---|
| 485 | else if ((*here).elType == CloseTagE)
|
---|
| 486 | ProcessCloseTag (tagInfo, *here, inFrag);
|
---|
| 487 | else if ((*here).elType == TextE)
|
---|
| 488 | ProcessText (tagInfo, *here, inFrag);
|
---|
| 489 |
|
---|
[9613] | 490 | ++here;
|
---|
[3365] | 491 | }
|
---|
| 492 |
|
---|
| 493 | // check the amount of memory needed for this chunk
|
---|
| 494 | if (numChunkEntries >= entryCheckPoint) {
|
---|
| 495 | unsigned long mem = MemoryRequired (wordLevelIndex);
|
---|
| 496 | if (mem >= invf_buffer_size * CHECK_CLOSE) {
|
---|
| 497 | if (mem > maxMemNeeded) maxMemNeeded = mem;
|
---|
| 498 | OutputChunkInfo (mem, wordLevelIndex);
|
---|
| 499 | entryCheckPoint = (unsigned long)
|
---|
| 500 | ((invf_buffer_size * INIT_CHECK_FRAC) / CHECK_DIV);
|
---|
| 501 |
|
---|
| 502 | } else {
|
---|
| 503 | entryCheckPoint = (unsigned long)
|
---|
| 504 | (entryCheckPoint * ((CHECK_FRAC * (invf_buffer_size - mem)) / mem) +
|
---|
| 505 | entryCheckPoint);
|
---|
| 506 | if (entryCheckPoint <= numChunkEntries)
|
---|
| 507 | entryCheckPoint = numChunkEntries + 1;
|
---|
| 508 | }
|
---|
| 509 | }
|
---|
| 510 |
|
---|
| 511 | return COMPALLOK;
|
---|
| 512 | }
|
---|
| 513 |
|
---|
| 514 |
|
---|
| 515 | static void CalcInvfDictSize (unsigned long &totalBytes,
|
---|
| 516 | unsigned long &indexStringBytes) {
|
---|
| 517 | totalBytes = 0; // The sum of the length of all words, including
|
---|
| 518 | // the length byte
|
---|
| 519 | indexStringBytes = 0; // The amount of space required to store the
|
---|
| 520 | // words in the diction, this takes into account
|
---|
| 521 | // the prefixes
|
---|
| 522 | const UCArray *lastWord = NULL;
|
---|
| 523 |
|
---|
| 524 | // calculate size of word information
|
---|
| 525 | IvfWordInfoMap::iterator wordHere = ivfWordInfo.begin();
|
---|
| 526 | IvfWordInfoMap::iterator wordEnd = ivfWordInfo.end();
|
---|
| 527 | while (wordHere != wordEnd) {
|
---|
| 528 | unsigned long wordSize = (*wordHere).first.size();
|
---|
| 529 | totalBytes += wordSize + 1;
|
---|
| 530 | indexStringBytes += wordSize + 2;
|
---|
| 531 | if (lastWord != NULL)
|
---|
| 532 | indexStringBytes -= PrefixLen (*lastWord, (*wordHere).first);
|
---|
| 533 | lastWord = &((*wordHere).first);
|
---|
| 534 |
|
---|
[9613] | 535 | ++wordHere;
|
---|
[3365] | 536 | }
|
---|
| 537 |
|
---|
| 538 | // calculate size of tag information
|
---|
| 539 | lastWord = NULL;
|
---|
| 540 | IvfTagInfoMap::iterator tagHere = ivfTagInfo.begin();
|
---|
| 541 | IvfTagInfoMap::iterator tagEnd = ivfTagInfo.end();
|
---|
| 542 | while (tagHere != tagEnd) {
|
---|
| 543 | unsigned long tagSize = (*tagHere).first.size();
|
---|
| 544 | totalBytes += tagSize + 1;
|
---|
| 545 | indexStringBytes += tagSize + 2;
|
---|
| 546 | if (lastWord != NULL)
|
---|
| 547 | indexStringBytes -= PrefixLen (*lastWord, (*tagHere).first);
|
---|
| 548 | lastWord = &((*tagHere).first);
|
---|
| 549 |
|
---|
[9613] | 550 | ++tagHere;
|
---|
[3365] | 551 | }
|
---|
| 552 | }
|
---|
| 553 |
|
---|
| 554 |
|
---|
| 555 | // OutputInvfDict ():
|
---|
| 556 | // writes out the stemmed dictionary file
|
---|
| 557 | // in the following format
|
---|
| 558 | // lookback value (int)
|
---|
| 559 | // totalbytes value (int)
|
---|
| 560 | // indexstringbytes (int)
|
---|
| 561 | // for each word
|
---|
| 562 | // wordlen (4 bits)
|
---|
| 563 | // prefix match (4 bits)
|
---|
| 564 | // word (wordlen bytes)
|
---|
| 565 | // word frequency (int)
|
---|
| 566 | // word count (int)
|
---|
| 567 | //
|
---|
| 568 | // Accesses outside variables:
|
---|
| 569 | //
|
---|
| 570 | // Return value...:
|
---|
| 571 | static void OutputInvfDict (char *filename) {
|
---|
| 572 | // create the dictionary header
|
---|
| 573 | invf_dict_header idh;
|
---|
| 574 | idh.word_dict_size = ivfWordInfo.size();
|
---|
| 575 | idh.tag_dict_size = ivfTagInfo.size();
|
---|
| 576 | idh.num_docs = numDocs;
|
---|
| 577 | idh.num_frags = numFrags;
|
---|
| 578 | idh.num_words = numWords;
|
---|
| 579 | idh.num_levels = ivfLevel.levelInfo.size();
|
---|
| 580 | CalcInvfDictSize (idh.total_bytes, idh.index_string_bytes);
|
---|
| 581 |
|
---|
| 582 | // create the inverted dictionary file
|
---|
| 583 | FILE *sp;
|
---|
| 584 | if (!(sp = create_file (filename, INVF_DICT_SUFFIX, "wb", MAGIC_STEM_BUILD,
|
---|
| 585 | MG_MESSAGE)))
|
---|
| 586 | return;
|
---|
| 587 |
|
---|
| 588 | // write out the dictionary header
|
---|
| 589 | if (!idh.Write (sp)) { fclose (sp); return; }
|
---|
| 590 |
|
---|
| 591 | // remember where the word dictionary starts
|
---|
| 592 | idh.word_dict_start = ftell (sp);
|
---|
| 593 |
|
---|
| 594 | // output the word dictionary
|
---|
| 595 | const UCArray *lastWord = NULL;
|
---|
| 596 | IvfWordInfoMap::iterator wordHere = ivfWordInfo.begin();
|
---|
| 597 | IvfWordInfoMap::iterator wordEnd = ivfWordInfo.end();
|
---|
| 598 | while (wordHere != wordEnd) {
|
---|
| 599 | // get the prefix and suffix lengths
|
---|
| 600 | const UCArray &thisWord = (*wordHere).first;
|
---|
| 601 | WritePreSufStr (sp, lastWord, thisWord);
|
---|
| 602 |
|
---|
| 603 | // output the number of fragments the word appeared in and the
|
---|
| 604 | // number of times the word appeared
|
---|
| 605 | WriteUL (sp, (*wordHere).second.fragCount);
|
---|
| 606 | WriteUL (sp, (*wordHere).second.wordCount);
|
---|
| 607 |
|
---|
| 608 | // output frequency information for each level
|
---|
| 609 | // note that we are expecting every word to have
|
---|
| 610 | // level information
|
---|
| 611 | LevelWorker *lwHere = (*wordHere).second.levels;
|
---|
| 612 | LevelWorker *lwEnd = lwHere + idh.num_levels;
|
---|
| 613 | while (lwHere != lwEnd) {
|
---|
| 614 | WriteUL (sp, (*lwHere).count);
|
---|
[9613] | 615 | ++lwHere;
|
---|
[3365] | 616 | }
|
---|
| 617 |
|
---|
| 618 | lastWord = &thisWord;
|
---|
[9613] | 619 | ++wordHere;
|
---|
[3365] | 620 | }
|
---|
| 621 |
|
---|
| 622 | // remember where the tag dictionary starts
|
---|
| 623 | idh.tag_dict_start = ftell (sp);
|
---|
| 624 |
|
---|
| 625 | // output the tag dictionary
|
---|
| 626 | const UCArray *lastTag = NULL;
|
---|
| 627 | IvfTagInfoMap::iterator tagHere = ivfTagInfo.begin();
|
---|
| 628 | IvfTagInfoMap::iterator tagEnd = ivfTagInfo.end();
|
---|
| 629 | while (tagHere != tagEnd) {
|
---|
| 630 | // get the prefix and suffix lengths
|
---|
| 631 | const UCArray &thisTag = (*tagHere).first;
|
---|
| 632 | WritePreSufStr (sp, lastTag, thisTag);
|
---|
| 633 |
|
---|
| 634 | // output the number of fragments the tag appeared in and the
|
---|
| 635 | // number of times the tag appeared
|
---|
| 636 | WriteUL (sp, (*tagHere).second.fragCount);
|
---|
| 637 | WriteUL (sp, (*tagHere).second.tagCount);
|
---|
| 638 |
|
---|
| 639 | lastTag = &thisTag;
|
---|
[9613] | 640 | ++tagHere;
|
---|
[3365] | 641 | }
|
---|
| 642 |
|
---|
| 643 | // write out the updated header
|
---|
| 644 | fseek (sp, sizeof (u_long), SEEK_SET);
|
---|
| 645 | if (!idh.Write (sp)) { fclose (sp); return; }
|
---|
| 646 |
|
---|
| 647 | fclose (sp);
|
---|
| 648 | }
|
---|
| 649 |
|
---|
| 650 | static void OutputLevelFile (char *filename) {
|
---|
| 651 | // create the level file
|
---|
| 652 | FILE *f;
|
---|
| 653 | if (!(f = create_file (filename, INVF_LEVEL_SUFFIX, "wb", MAGIC_INVF_LEVELS,
|
---|
| 654 | MG_MESSAGE)))
|
---|
| 655 | return;
|
---|
| 656 |
|
---|
| 657 | // write out the information
|
---|
| 658 | ivfLevel.Write (f);
|
---|
| 659 |
|
---|
| 660 | // close the file
|
---|
| 661 | fclose (f);
|
---|
| 662 | }
|
---|
| 663 |
|
---|
| 664 | static void OutputTransFile (char *filename) {
|
---|
| 665 | // save the word number (in lastFragNum :-/)
|
---|
| 666 | int i = 0;
|
---|
| 667 | IvfWordInfoMap::iterator wordHere = ivfWordInfo.begin();
|
---|
| 668 | IvfWordInfoMap::iterator wordEnd = ivfWordInfo.end();
|
---|
| 669 | while (wordHere != wordEnd) {
|
---|
| 670 | (*wordHere).second.lastFragNum = i;
|
---|
[9613] | 671 | ++i; ++wordHere;
|
---|
[3365] | 672 | }
|
---|
| 673 |
|
---|
| 674 | // save the tag number (in lastFragNum :-/)
|
---|
| 675 | i = 0;
|
---|
| 676 | IvfTagInfoMap::iterator tagHere = ivfTagInfo.begin();
|
---|
| 677 | IvfTagInfoMap::iterator tagEnd = ivfTagInfo.end();
|
---|
| 678 | while (tagHere != tagEnd) {
|
---|
| 679 | (*tagHere).second.lastFragNum = i;
|
---|
[9613] | 680 | ++i; ++tagHere;
|
---|
[3365] | 681 | }
|
---|
| 682 |
|
---|
| 683 | // create the translation file
|
---|
| 684 | FILE *f;
|
---|
| 685 | if (!(f = create_file (filename, INVF_CHUNK_TRANS_SUFFIX, "wb",
|
---|
| 686 | MAGIC_CHUNK_TRANS, MG_MESSAGE)))
|
---|
| 687 | return;
|
---|
| 688 |
|
---|
| 689 | stdio_bitio_buffer buffer(f);
|
---|
| 690 | buffer.encodeStart();
|
---|
| 691 |
|
---|
| 692 | // write out the word translation table
|
---|
| 693 | unsigned long wordDictSize = ivfWordInfoOccurOrder.size();
|
---|
| 694 | IvfWordInfoItArray::iterator wordItHere = ivfWordInfoOccurOrder.begin();
|
---|
| 695 | IvfWordInfoItArray::iterator wordItEnd = ivfWordInfoOccurOrder.end();
|
---|
| 696 | unsigned long oN = 0;
|
---|
| 697 | while (wordItHere != wordItEnd) {
|
---|
| 698 | register IvfWordInfo &ivfWordInfo = (*(*wordItHere)).second;
|
---|
| 699 | buffer.binary_encode (ivfWordInfo.lastFragNum + 1, wordDictSize + 1, NULL);
|
---|
[9613] | 700 | ++oN;
|
---|
| 701 | ++wordItHere;
|
---|
[3365] | 702 | }
|
---|
| 703 |
|
---|
| 704 | // write out the tag translation table
|
---|
| 705 | unsigned long tagDictSize = ivfTagInfoOccurOrder.size();
|
---|
| 706 | IvfTagInfoItArray::iterator tagItHere = ivfTagInfoOccurOrder.begin();
|
---|
| 707 | IvfTagInfoItArray::iterator tagItEnd = ivfTagInfoOccurOrder.end();
|
---|
| 708 | while (tagItHere != tagItEnd) {
|
---|
| 709 | register IvfTagInfo &ivfTagInfo = (*(*tagItHere)).second;
|
---|
| 710 | buffer.binary_encode (ivfTagInfo.lastFragNum + 1, tagDictSize + 1, NULL);
|
---|
[9613] | 711 | ++oN;
|
---|
| 712 | ++tagItHere;
|
---|
[3365] | 713 | }
|
---|
| 714 |
|
---|
| 715 | // finish encoding and close the file
|
---|
| 716 | buffer.encodeDone();
|
---|
| 717 | fclose (f);
|
---|
| 718 | }
|
---|
| 719 |
|
---|
| 720 | #ifndef SILENT
|
---|
| 721 | static void PrintStats () {
|
---|
| 722 | Message ("Inverted buffer size: %8u bytes\n", invf_buffer_size);
|
---|
| 723 | Message ("Max memory needed for 1 chunk: %8u bytes\n", maxMemNeeded);
|
---|
| 724 |
|
---|
| 725 | Message ("Number of chunks written: %8u\n", chunksWritten);
|
---|
| 726 | Message ("Number of documents: %8u\n", numDocs);
|
---|
| 727 | Message ("Number of fragments: %8u\n", numFrags);
|
---|
| 728 | Message ("Number of words: %8u\n", numWords);
|
---|
| 729 |
|
---|
| 730 | Message ("Size of word dictionary: %8u\n", ivfWordInfo.size());
|
---|
| 731 | Message ("Size of tag dictionary: %8u\n", ivfTagInfo.size());
|
---|
| 732 | }
|
---|
| 733 | #endif
|
---|
| 734 |
|
---|
| 735 | int done_ivf_1 (const TagInfo &tagInfo, char * filename) {
|
---|
| 736 | bool wordLevelIndex = tagInfo.indexLevel.empty();
|
---|
| 737 |
|
---|
| 738 | char *temp_str = msg_prefix;
|
---|
| 739 | msg_prefix = "ivf.pass1";
|
---|
| 740 |
|
---|
| 741 | // output the last chunk
|
---|
| 742 | if (numChunkDocs > 0) {
|
---|
| 743 | unsigned long mem = MemoryRequired (wordLevelIndex);
|
---|
| 744 | OutputChunkInfo (mem, wordLevelIndex);
|
---|
| 745 | if (mem > maxMemNeeded) maxMemNeeded = mem;
|
---|
| 746 | }
|
---|
| 747 |
|
---|
| 748 | // write out and encoded 1 to say there are no more chunks
|
---|
| 749 | icb.gamma_encode (1, NULL);
|
---|
| 750 | icb.encodeDone ();
|
---|
| 751 |
|
---|
| 752 | // write out the maximum memory required and close the file
|
---|
| 753 | fseek (ic, sizeof (long), 0);
|
---|
| 754 | WriteUL (ic, maxMemNeeded);
|
---|
| 755 | fclose (ic);
|
---|
| 756 |
|
---|
| 757 | // output the inverted dictionary
|
---|
| 758 | OutputInvfDict (filename);
|
---|
| 759 |
|
---|
| 760 | // write out the translation file
|
---|
| 761 | OutputTransFile (filename);
|
---|
| 762 |
|
---|
| 763 | // output the level information
|
---|
| 764 | OutputLevelFile (filename);
|
---|
| 765 |
|
---|
| 766 | // output statistics
|
---|
| 767 | #ifndef SILENT
|
---|
| 768 | PrintStats ();
|
---|
| 769 | #endif
|
---|
| 770 |
|
---|
| 771 | msg_prefix = temp_str;
|
---|
| 772 |
|
---|
| 773 | return COMPALLOK;
|
---|
| 774 | }
|
---|
| 775 |
|
---|