1 /* FILE: sub_min.cpp 2 * DATE MODIFIED: 31-Aug-07 3 * DESCRIPTION: Part of the SREC graph compiler project source files. 4 * 5 * Copyright 2007, 2008 Nuance Communciations, Inc. * 6 * * 7 * Licensed under the Apache License, Version 2.0 (the 'License'); * 8 * you may not use this file except in compliance with the License. * 9 * * 10 * You may obtain a copy of the License at * 11 * http://www.apache.org/licenses/LICENSE-2.0 * 12 * * 13 * Unless required by applicable law or agreed to in writing, software * 14 * distributed under the License is distributed on an 'AS IS' BASIS, * 15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 16 * See the License for the specific language governing permissions and * 17 * limitations under the License. * 18 * * 19 *---------------------------------------------------------------------------*/ 20 21 #include <iostream> 22 #include <string> 23 #include <assert.h> 24 #include <cstdio> 25 26 #include "sub_grph.h" 27 28 #define SYMBOL_COMPARE(x,y) (arc[x]->CompareSymbol(arc[y])) 29 #define COMPARE(x,y) (arc[x]->Compare(arc[y])) 30 31 // Minimization to facilitate moving output symbols - mainly for phoneme networks 32 // Check partial merge 33 // Move the output symbol if only one node 34 35 /* 36 static int checkEntry (int *itemList, int count, int item); 37 38 static int checkEntry (int *itemList, int count, int item) 39 { 40 for (int ii= 0; ii < count; ii++) 41 if (item == itemList[ii]) 42 return ii; 43 return -1; 44 } 45 */ 46 47 void SubGraph::ViewNode (int currId) 48 { 49 int rix; 50 51 printf ("Node: %d\n", currId); 52 rix= FindFromIndex (currId); 53 if (rix < 0) 54 return; 55 while (rix < numArc && arc[forwardList[rix]]->GetFromId() == currId) { 56 arc[forwardList[rix]]->Print(); 57 rix++; 58 } 59 return; 60 } 61 62 63 bool SubGraph::EquivalenceTestForward (int firstId, int secondId, int *equivMap) 64 { 65 int fix, six, fnxt, snxt, tof, tos, count; 66 67 assert (firstId != secondId); 68 fix= FindFromIndex (firstId); 69 six= FindFromIndex (secondId); 70 if (fix < 0 || six < 0) 71 return false; 72 73 count= 0; 74 do { 75 76 // Move to next valid transitions 77 while (fix < numArc && arc[forwardList[fix]]->GetFromId() == firstId 78 && arc[forwardList[fix]]->GetToId() == DISCARD_LABEL) 79 fix++; 80 if (fix < numArc && arc[forwardList[fix]]->GetFromId() == firstId) 81 fnxt= arc[forwardList[fix]]->GetFromId(); 82 else 83 fnxt= -1; 84 85 while (six < numArc && arc[forwardList[six]]->GetFromId() == secondId 86 && arc[forwardList[six]]->GetToId() == DISCARD_LABEL) 87 six++; 88 if (six < numArc && arc[forwardList[six]]->GetFromId() == secondId) 89 snxt= arc[forwardList[six]]->GetFromId(); 90 else 91 snxt= -1; 92 93 if (fnxt != firstId && snxt != secondId) 94 return true; 95 else if (fnxt != firstId || snxt != secondId) 96 return false; 97 98 tos= arc[forwardList[six]]->GetToId(); 99 tof= arc[forwardList[fix]]->GetToId(); 100 // printf ("Debug inner %d %d, %d %d\n", tof, tos, equivMap[tof], equivMap[tos]); 101 // if (tof >= 0) bogus assert 102 // assert (tof == equivMap[tof]); 103 // if (tos >= 0) 104 // assert (tos == equivMap[tos]); 105 106 // Test 107 if (!arc[forwardList[fix]]->HasSameLabels (arc[forwardList[six]]) 108 || tos != tof) 109 return false; 110 count++; 111 112 fix++; 113 six++; 114 115 } while (fnxt >= 0 && snxt >= 0); 116 117 return false; 118 } 119 120 void SubGraph::IdentifyEquivalence (int *depthMap, int *equivMap) 121 { 122 int ii, jj, dd, maxDepth, count, itCnt; 123 124 maxDepth= 0; 125 for (ii= 0; ii < numVertex; ii++) { 126 if (maxDepth < depthMap[ii]) 127 maxDepth= depthMap[ii]; 128 } 129 130 itCnt= 0; 131 do { 132 count= 0; 133 for (dd= 0; dd <= maxDepth; dd++) 134 for (ii= 0; ii < numVertex; ii++) 135 if (depthMap[ii] == dd && ii == equivMap[ii]) { 136 CheckForChangeAndResort (ii, equivMap); 137 for (jj= ii+1; jj < numVertex; jj++) 138 if (depthMap[jj] == dd && jj == equivMap[jj]) { 139 // Equivalence test 140 CheckForChangeAndResort (jj, equivMap); 141 // printf ("Try %d %d, ", ii, jj); 142 if (EquivalenceTestForward (ii, jj, equivMap)) { 143 equivMap[jj]= ii; 144 // printf ("Merged %d %d\n", ii, jj); 145 count++; 146 } 147 } 148 } 149 150 itCnt++; 151 // printf ("Total %d mergers\n", count); 152 } while (count > 0 && itCnt < MAXITS); 153 154 return; 155 } 156 157 void SubGraph::CheckForChangeAndResort (int currId, int *mapList) 158 { 159 int rix, rixBegin, nextId; 160 bool needSort; 161 162 needSort= false; 163 rixBegin= rix= FindFromIndex (currId); 164 if (rix < 0) 165 return; 166 while (rix < numArc && arc[forwardList[rix]]->GetFromId() == currId) { 167 nextId= arc[forwardList[rix]]->GetToId(); 168 if (nextId >= 0 && mapList[nextId] != nextId) { 169 needSort= true; 170 arc[forwardList[rix]]->AssignToId(mapList[nextId]); 171 } 172 rix++; 173 } 174 175 // Resort 176 if (needSort) 177 RemoveDuplicatesAtNode (rixBegin, rix); 178 179 return; 180 } 181 182 void SubGraph::DeterminizeAtVertex (int baseId, DetCache *cache) 183 { 184 int fix, six, firstId, secondId, vertEnd; 185 186 fix= FindFromIndex (baseId); 187 if (fix < 0) 188 return; 189 190 // Remove duplicates 191 vertEnd= fix; 192 six= -1; 193 while (vertEnd < sortNum && arc[forwardList[vertEnd]]->GetFromId() == baseId) { 194 vertEnd++; 195 } 196 vertEnd++; 197 198 // Iteration over first node 199 firstId= -1; 200 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == baseId) { 201 202 // Iterator for firstId 203 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == baseId 204 && (arc[forwardList[fix]]->GetToId() == firstId 205 || arc[forwardList[fix]]->GetInput() == TERMINAL_LABEL 206 || arc[forwardList[fix]]->GetInput() == DISCARD_LABEL)) 207 fix++; 208 209 // Terminal Condition 210 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId) 211 break; 212 else 213 firstId= arc[forwardList[fix]]->GetToId(); 214 215 // Iteration over second node 216 six= fix; 217 secondId= firstId; 218 while (six < sortNum && arc[forwardList[six]]->GetFromId() == baseId) { 219 220 // Iterator for secondId 221 while (six < sortNum && arc[forwardList[six]]->GetFromId() == baseId 222 && (arc[forwardList[six]]->GetToId() == secondId 223 || arc[forwardList[six]]->GetInput() == TERMINAL_LABEL 224 || arc[forwardList[six]]->GetInput() == DISCARD_LABEL)) 225 six++; 226 227 // Terminal condition 228 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != baseId) 229 break; 230 else 231 secondId= arc[forwardList[six]]->GetToId(); 232 233 // Now we have both Ids worked out 234 assert (firstId >= 0); 235 assert (secondId >= 0); 236 assert (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL); 237 assert (arc[forwardList[six]]->GetInput() != DISCARD_LABEL); 238 239 if (PairwiseDeterminize (baseId, firstId, fix, secondId, six, cache) > 0) { 240 SortLanguageAtSortIndices (fix, vertEnd); 241 242 // Are we done with the first node? 243 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == baseId 244 && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL) 245 fix++; 246 247 // Terminal condition 248 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId 249 || arc[forwardList[fix]]->GetToId() != firstId) 250 break; 251 } 252 } 253 } 254 return; 255 } 256 257 int SubGraph::PairwiseDeterminize (int baseId, int firstId, int fixStart, int secondId, 258 int sixStart, DetCache *cache) 259 { 260 int fix, six, fmiss, smiss, nmatch, symTst, newId; 261 bool isCached; 262 263 fix= fixStart; 264 six= sixStart; 265 266 assert (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL); 267 assert (arc[forwardList[six]]->GetInput() != DISCARD_LABEL); 268 269 // Count 270 isCached= false; 271 fmiss= smiss= nmatch= 0; 272 newId= -1; 273 while (six < sortNum && fix < sortNum) { 274 275 assert (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL); 276 assert (arc[forwardList[six]]->GetInput() != DISCARD_LABEL); 277 278 symTst= SYMBOL_COMPARE (forwardList[fix], forwardList[six]); 279 if (symTst == 0) { 280 if (newId == -1) { 281 newId= cache->QueryEntry (firstId, secondId); 282 if (newId < 0) 283 newId= NewVertexId (); 284 else 285 isCached= true; 286 // printf ("Forming %d with %d and %d at %d\n", newId, firstId, secondId, baseId); 287 } 288 289 // Assign second to new Vertex 290 arc[forwardList[six]]->AssignToId (newId); 291 292 // Assign first to DISCARD Index 293 arc[forwardList[fix]]->AssignInput (DISCARD_LABEL); 294 295 // Increment to next 296 do { 297 fix++; 298 } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL); 299 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId 300 || arc[forwardList[fix]]->GetToId() != firstId) 301 fix= sortNum; 302 303 do { 304 six++; 305 } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL); 306 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != baseId 307 || arc[forwardList[six]]->GetToId() != secondId) 308 six= sortNum; 309 310 nmatch++; 311 } 312 else if (symTst < 0) { 313 do { 314 fix++; 315 } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL); 316 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId 317 || arc[forwardList[fix]]->GetToId() != firstId) 318 fix= sortNum; 319 fmiss++; 320 } 321 else if (symTst > 0) { 322 do { 323 six++; 324 } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL); 325 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != baseId 326 || arc[forwardList[six]]->GetToId() != secondId) 327 six= sortNum; 328 smiss++; 329 } 330 } 331 332 // SortLanguageAtSortIndices (fixStart, fix); 333 334 if (newId >= 0) { 335 if (isCached == false) { 336 // numLast= numArc; 337 MergeVertices (newId, firstId, secondId); 338 cache->AddEntry (newId, firstId, secondId); 339 // UpdateVisitationCache (numLast); 340 } 341 assert (nmatch > 0); 342 } 343 344 // Update fan-in count 345 if (nmatch > 0) { 346 // printf ("Merging %d %d to create %d\n", firstId, secondId, newId); 347 for (int ii= 0; ii < nmatch; ii++) { 348 // IncNodeProperty (newId); 349 IncVisitationCache (newId); 350 DecVisitationCache (firstId); 351 DecVisitationCache (secondId); 352 } 353 } 354 return nmatch; 355 } 356 357 void SubGraph::MergeVertices (int newId, int firstId, int secondId) 358 { 359 int fix, six, symTst, numStart; 360 NUANArc *arcOne; 361 362 numStart= numArc; 363 fix= FindFromIndex (firstId); 364 six= FindFromIndex (secondId); 365 if (fix < 0 || six < 0) { 366 if (fix >= 0) 367 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == firstId) { 368 if (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL) 369 InheritArc (arc[forwardList[fix]], newId); 370 fix++; 371 } 372 else if (six >= 0) 373 while (six < sortNum && arc[forwardList[six]]->GetFromId() == secondId) { 374 if (arc[forwardList[six]]->GetInput() != DISCARD_LABEL) 375 InheritArc (arc[forwardList[six]], newId); 376 six++; 377 } 378 } 379 else { 380 while (six < sortNum && fix < sortNum) { 381 382 symTst= SYMBOL_COMPARE (forwardList[fix], forwardList[six]); 383 384 if (symTst == 0) { 385 if (arc[forwardList[fix]]->GetToId() == firstId 386 && arc[forwardList[six]]->GetToId() == secondId) { 387 arcOne= InheritArc (arc[forwardList[fix]], newId); 388 arcOne->AssignToId (newId); 389 } 390 else if (arc[forwardList[fix]]->GetToId() 391 == arc[forwardList[six]]->GetToId()) { 392 InheritArc (arc[forwardList[fix]], newId); 393 } 394 else { 395 InheritArc (arc[forwardList[fix]], newId); 396 InheritArc (arc[forwardList[six]], newId); 397 } 398 399 // Increment to next 400 do { 401 fix++; 402 } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL); 403 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != firstId 404 || arc[forwardList[fix]]->GetFromId() != firstId) 405 fix= sortNum; 406 407 do { 408 six++; 409 } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL); 410 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != secondId) 411 six= sortNum; 412 } 413 else if (symTst < 0) { 414 InheritArc (arc[forwardList[fix]], newId); 415 do { 416 fix++; 417 } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL); 418 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != firstId 419 || arc[forwardList[fix]]->GetFromId() != firstId) 420 fix= sortNum; 421 } 422 else if (symTst > 0) { 423 InheritArc (arc[forwardList[six]], newId); 424 do { 425 six++; 426 } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL); 427 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != secondId 428 || arc[forwardList[six]]->GetFromId() != secondId) 429 six= sortNum; 430 } 431 } 432 433 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == firstId) { 434 if (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL) 435 InheritArc (arc[forwardList[fix]], newId); 436 fix++; 437 } 438 439 while (six < sortNum && arc[forwardList[six]]->GetFromId() == secondId) { 440 if (arc[forwardList[six]]->GetInput() != DISCARD_LABEL) 441 InheritArc (arc[forwardList[six]], newId); 442 six++; 443 } 444 } 445 446 // Update the sort list 447 UpdateSortForLanguage (); 448 // RemoveDuplicatesAtNode (numStart, numArc); 449 // ViewNode (newId); 450 assert (CheckSort()); 451 452 // printf ("Merging %d %d to create %d\n", firstId, secondId, newId); 453 454 return; 455 } 456 457 void SubGraph::SetupVisitationCache () 458 { 459 int ii; 460 461 CreateNodeProperty (); 462 for (ii= 0; ii < numArc; ii++) 463 if (arc[ii]->GetInput() != DISCARD_LABEL && arc[ii]->GetToId() >= 0) 464 IncNodeProperty (arc[ii]->GetToId()); 465 return; 466 } 467 468 void SubGraph::ClearVisitationCache () 469 { 470 DeleteNodeProperty (); 471 return; 472 } 473 474 void SubGraph::UpdateVisitationCache (int startNo) 475 { 476 int ii; 477 478 for (ii= startNo; ii < numArc; ii++) 479 if (arc[ii]->GetInput() != DISCARD_LABEL && arc[ii]->GetToId() >= 0) { 480 IncNodeProperty (arc[ii]->GetToId()); 481 // std::cout << " (" << arc[ii]->GetToId() << " " << QueryNodeProperty (arc[ii]->GetToId()) << ") "; 482 } 483 // std::cout << std::endl; 484 return; 485 } 486 487 void SubGraph::DecVisitationCache (int currId) 488 { 489 int rix; 490 491 DecNodeProperty (currId); 492 // std::cout << " [" << currId << " " << QueryNodeProperty (currId) << "] "; 493 if (QueryNodeProperty (currId) <= 0) { 494 // std::cout << " [" << currId << "] "; 495 rix= FindFromIndex (currId); 496 if (rix < 0) 497 return; 498 while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) { 499 if (arc[forwardList[rix]]->GetInput() != DISCARD_LABEL 500 && arc[forwardList[rix]]->GetToId() >= 0) { 501 if (arc[forwardList[rix]]->GetFromId() == arc[forwardList[rix]]->GetToId()) 502 DecNodeProperty (currId); 503 else if (QueryNodeProperty (arc[forwardList[rix]]->GetToId()) > 0) 504 DecVisitationCache (arc[forwardList[rix]]->GetToId()); 505 } 506 rix++; 507 } 508 } 509 return; 510 } 511 512 void SubGraph::IncVisitationCache (int currId) 513 { 514 int rix; 515 516 if (QueryNodeProperty (currId) <= 0) { 517 IncNodeProperty (currId); 518 // std::cout << " (" << currId << ") "; 519 rix= FindFromIndex (currId); 520 if (rix < 0) 521 return; 522 while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) { 523 if (arc[forwardList[rix]]->GetInput() != DISCARD_LABEL 524 && arc[forwardList[rix]]->GetToId() >= 0) { 525 // IncNodeProperty (arc[forwardList[rix]]->GetToId()); 526 // if (currId != arc[forwardList[rix]]->GetToId()) 527 IncVisitationCache (arc[forwardList[rix]]->GetToId()); 528 } 529 rix++; 530 } 531 } 532 else 533 IncNodeProperty (currId); 534 // std::cout << " (" << currId << " " << QueryNodeProperty (currId) << ") "; 535 return; 536 } 537 538 int SubGraph::VisitationConsistencyCheck () 539 { 540 int ii, failCount; 541 542 int *nodeCount= new int [numVertex]; 543 544 UpdateVertexCount (0); 545 546 // std::cout << "Count: "; 547 for (ii= 0; ii <numVertex; ii++) { 548 // std::cout << ii << " (" << vertexProp[ii] << ") "; 549 nodeCount[ii]= 0; 550 } 551 // std::cout << std::endl; 552 for (ii= 0; ii <numArc; ii++) 553 if (arc[ii]->GetInput() != DISCARD_LABEL && arc[ii]->GetToId() >= 0 554 && (vertexProp[arc[ii]->GetFromId()] > 0 || arc[ii]->GetFromId() == startId)) 555 nodeCount[arc[ii]->GetToId()]++; 556 failCount= 0; 557 // std::cout << "Failure list: "; 558 for (ii= 0; ii <numVertex; ii++) 559 if (vertexProp[ii] != nodeCount[ii]) { 560 // std::cout << ii << " (" << vertexProp[ii] << " " << nodeCount[ii] << ") "; 561 failCount++; 562 } 563 // std::cout << std::endl; 564 565 // return failCount; 566 delete [] nodeCount; 567 568 return 0; 569 } 570
