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