link-grammar-5.8.0/link-grammar/parse/prune.c
/** The return value is the number of disjuncts deleted.
 *  Implementation notes:
 *  Normally tracons are memory shared (with the exception that
 *  tracons that start with a shallow connectors are not shared with
 *  ones starting with a deep connector). For further details on tracon
 *  sharing, see the comment on them in disjunct-utils.c.
 *
 *  The refcount of each connector serves as its reference count in the
 *  power table. Each time a connector that cannot match is
 *  discovered, its reference count is decreased, and the nearest_word
 *  field of its jet is assigned BAD_WORD. Due to the tracon memory
 *  sharing, each change of the reference count and the nearest_word
 *  field affects simultaneously all the identical tracons (and the
 *  corresponding connectors in the power table). The corresponding
 *  disjuncts are discarded on the fly, and additional disjuncts with jets
 *  so marked with BAD_WORD are discarded when encountered without a
 *  further check. Each tracon is handled only once in the same main loop
 *  pass by marking their connectors with the pass number in their
 *  prune_pass field.
 *
 *  Null words (words w/o disjuncts) are detected on the fly (the initial
 *  ones are detected on the first pass). When the number of the null
 *  words indicates there will be no parse with the given pc->null_links,
 *  return -1. Else return the number of discarded disjuncts.
 */
The return value is the number of disjuncts deleted.
Implementation notes:
Normally tracons are memory shared (with the exception that
tracons that start with a shallow connectors are not shared with
ones starting with a deep connector). For further details on tracon
sharing, see the comment on them in disjunct-utils.c.

The refcount of each connector serves as its reference count in the
power table. Each time a connector that cannot match is
discovered, its reference count is decreased, and the nearest_word
field of its jet is assigned BAD_WORD. Due to the tracon memory
sharing, each change of the reference count and the nearest_word
field affects simultaneously all the identical tracons (and the
corresponding connectors in the power table). The corresponding
disjuncts are discarded on the fly, and additional disjuncts with jets
so marked with BAD_WORD are discarded when encountered without a
further check. Each tracon is handled only once in the same main loop
pass by marking their connectors with the pass number in their
prune_pass field.

Null words (words w/o disjuncts) are detected on the fly (the initial
ones are detected on the first pass). When the number of the null
words indicates there will be no parse with the given pc->null_links,
return -1. Else return the number of discarded disjuncts.
The return value is the number of disjuncts deleted . Implementation notes : Normally tracons are memory shared ( with the exception that tracons that start with a shallow connectors are not shared with ones starting with a deep connector ) . For further details on tracon sharing see the comment on them in disjunct - utils . c . The refcount of each connector serves as its reference count in the power table . Each time a connector that cannot match is discovered its reference count is decreased and the nearest_word field of its jet is assigned BAD_WORD . Due to the tracon memory sharing each change of the reference count and the nearest_word field affects simultaneously all the identical tracons ( and the corresponding connectors in the power table ) . The corresponding disjuncts are discarded on the fly and additional disjuncts with jets so marked with BAD_WORD are discarded when encountered without a further check . Each tracon is handled only once in the same main loop pass by marking their connectors with the pass number in their prune_pass field . Null words ( words w / o disjuncts ) are detected on the fly ( the initial ones are detected on the first pass ) . When the number of the null words indicates there will be no parse with the given pc - > null_links return - 1 . Else return the number of discarded disjuncts .
static int power_prune(Sentence sent, prune_context *pc, Parse_Options opts)
{
	int total_deleted = 0;
	bool extra_null_word = false;
	power_table *pt = pc->pt;
	pc->N_changed = 1;      
	do
	{
		pc->pass_number++;
		for (WordIdx w = 0; w < sent->length; w++)
		{
			for (Disjunct **dd = &sent->word[w].d; *dd != NULL; )
			{
				Disjunct *d = *dd; 
				if (d->left == NULL)
				{
					dd = &d->next;  
					continue;
				}
				bool bad = is_bad(d->left);
				if (bad || left_connector_list_update(pc, d->left, w, true) < 0)
				{
					mark_jet_for_dequeue(d->left, true);
					mark_jet_for_dequeue(d->right, false);
					*dd = d->next; 
					pc->N_deleted[(int)bad]++;
					continue;
				}
				mark_jet_as_good(d->left, pc->pass_number);
				dd = &d->next; 
			}
			if (check_null_word(pc, w)) extra_null_word = true;
			clean_table(pt->r_table_size[w], pt->r_table[w]);
		}
		if (pruning_pass_end(pc, "l->r", &total_deleted)) break;
		for (WordIdx w = sent->length-1; w != (WordIdx) -1; w--)
		{
			for (Disjunct **dd = &sent->word[w].d; *dd != NULL; )
			{
				Disjunct *d = *dd; 
				if (d->right == NULL)
				{
					dd = &d->next;  
					continue;
				}
				bool bad = is_bad(d->right);
				if (bad || right_connector_list_update(pc, d->right, w, true) >= sent->length)
				{
					mark_jet_for_dequeue(d->right, true);
					mark_jet_for_dequeue(d->left, false);
					*dd = d->next; 
					pc->N_deleted[(int)bad]++;
					continue;
				}
				mark_jet_as_good(d->right, pc->pass_number);
				dd = &d->next; 
			}
			if (check_null_word(pc, w)) extra_null_word = true;
			clean_table(pt->l_table_size[w], pt->l_table[w]);
		}
		if (pruning_pass_end(pc, "r->l", &total_deleted)) break;
		pc->ml = NULL;
	}
	while (!extra_null_word || pc->always_parse);
	char found_nulls[32] = "";
	if ((verbosity >= D_USER_TIMES) && !extra_null_word && (pc->null_words > 0))
		snprintf(found_nulls, sizeof(found_nulls), ", found %u", pc->null_words);
	print_time(opts, "power pruned (for %u null%s%s%s)",
	           pc->null_links, (pc->null_links != 1) ? "s" : "",
	           extra_null_word ? ", extra null" : "", found_nulls);
	if (verbosity_level(D_PRUNE))
	{
		prt_error("\n\\");
		prt_error("Debug: Power prune cost: %d\n", pc->power_cost);
		prt_error("Debug: After power_pruning (for %u null%s, sent->null_count %u):\n\\",
		          pc->null_links, (pc->null_links != 1) ? "s" : "", pc->sent->null_count);
		print_disjunct_counts(pc->sent);
	}
#ifdef DEBUG
	for (WordIdx w = 0; w < sent->length; w++)
	{
		for (Disjunct *d = sent->word[w].d; NULL != d; d = d->next)
		{
			for (int dir = 0; dir < 2; dir++)
			{
				Connector *c = (dir) ? (d->left) : (d->right);
				for (; NULL != c; c = c->next)
				{
					assert(c->nearest_word != BAD_WORD, "dir %d w %zu", dir, w);
					assert(c->refcount > 0, "dir %d w %zu", dir, w);
				}
			}
		}
	}
#endif
	if (extra_null_word && !pc->always_parse) return -1;
	return total_deleted;
}
static int power_prune ( Sentence sent , prune_context * pc , Parse_Options opts ) { int total_deleted = 0 ; bool extra_null_word = false ; power_table * pt = pc -> pt ; pc -> N_changed = 1 ; do { pc -> pass_number ++ ; for ( WordIdx w = 0 ; w < sent -> length ; w ++ ) { for ( Disjunct * * dd = & sent -> word [ w ] . d ; * dd != NULL ; ) { Disjunct * d = * dd ; if ( d -> left == NULL ) { dd = & d -> next ; continue ; } bool bad = is_bad ( d -> left ) ; if ( bad || left_connector_list_update ( pc , d -> left , w , true ) < 0 ) { mark_jet_for_dequeue ( d -> left , true ) ; mark_jet_for_dequeue ( d -> right , false ) ; * dd = d -> next ; pc -> N_deleted [ ( int ) bad ] ++ ; continue ; } mark_jet_as_good ( d -> left , pc -> pass_number ) ; dd = & d -> next ; } if ( check_null_word ( pc , w ) ) extra_null_word = true ; clean_table ( pt -> r_table_size [ w ] , pt -> r_table [ w ] ) ; } if ( pruning_pass_end ( pc , " " , & total_deleted ) ) break ; for ( WordIdx w = sent -> length - 1 ; w != ( WordIdx ) - 1 ; w -- ) { for ( Disjunct * * dd = & sent -> word [ w ] . d ; * dd != NULL ; ) { Disjunct * d = * dd ; if ( d -> right == NULL ) { dd = & d -> next ; continue ; } bool bad = is_bad ( d -> right ) ; if ( bad || right_connector_list_update ( pc , d -> right , w , true ) >= sent -> length ) { mark_jet_for_dequeue ( d -> right , true ) ; mark_jet_for_dequeue ( d -> left , false ) ; * dd = d -> next ; pc -> N_deleted [ ( int ) bad ] ++ ; continue ; } mark_jet_as_good ( d -> right , pc -> pass_number ) ; dd = & d -> next ; } if ( check_null_word ( pc , w ) ) extra_null_word = true ; clean_table ( pt -> l_table_size [ w ] , pt -> l_table [ w ] ) ; } if ( pruning_pass_end ( pc , " " , & total_deleted ) ) break ; pc -> ml = NULL ; } while ( ! extra_null_word || pc -> always_parse ) ; char found_nulls [ 32 ] = " " ; if ( ( verbosity >= D_USER_TIMES ) && ! extra_null_word && ( pc -> null_words > 0 ) ) snprintf ( found_nulls , sizeof ( found_nulls ) , " " , pc -> null_words ) ; print_time ( opts , " " , pc -> null_links , ( pc -> null_links != 1 ) ? " " : " " , extra_null_word ? " " : " " , found_nulls ) ; if ( verbosity_level ( D_PRUNE ) ) { prt_error ( " \n \\ " ) ; prt_error ( " \n " , pc -> power_cost ) ; prt_error ( " \n \\ " , pc -> null_links , ( pc -> null_links != 1 ) ? " " : " " , pc -> sent -> null_count ) ; print_disjunct_counts ( pc -> sent ) ; } #ifdef DEBUG for ( WordIdx w = 0 ; w < sent -> length ; w ++ ) { for ( Disjunct * d = sent -> word [ w ] . d ; NULL != d ; d = d -> next ) { for ( int dir = 0 ; dir < 2 ; dir ++ ) { Connector * c = ( dir ) ? ( d -> left ) : ( d -> right ) ; for ( ; NULL != c ; c = c -> next ) { assert ( c -> nearest_word != BAD_WORD , " " , dir , w ) ; assert ( c -> refcount > 0 , " " , dir , w ) ; } } } } #endif if ( extra_null_word && ! pc -> always_parse ) return -1 ; return total_deleted ; }
The return value is the number of disjuncts deleted.
The return value is the number of disjuncts deleted .
/* forces it always to make at least two passes */ /* Left-to-right pass. */ /* See: NEXT */ /* just for convenience */ /* NEXT */ /* Discard the current disjunct. */ /* NEXT - set current disjunct to the next one */ /* NEXT */ /* Right-to-left pass. */ /* See: NEXT */ /* just for convenience */ /* NEXT */ /* Discard the current disjunct. */ /* NEXT - set current disjunct to the next one */ /* NEXT */ /* The verbose debug printouts revealed that the xlink counter is
		 * never set after the first 2 passes. So neutralize the mlink table
		 * here to save a slight overhead. */ /* The rest of the code has a critical dependency on the correctness of
	 * the pruning. */