suffix_tree.c

Language, Script, and Encoding Identification with String Kernel Classifiers

				pos->edge_pos	= 0;
				chars_found		= 1;
			}
		}
		/*
		2. last character matched is NOT the last of its edge
		*/
		else
		{
			/*trace only last symbol of str, search in the 
			CURRENT edge (node).*/
			if(tree->tree_string[pos->node->edge_label_start+pos->edge_pos+1] == tree->tree_string[str.end])
			{
				pos->edge_pos++;
				chars_found	= 1;
			}
		}
	}

	/*If whole string was found - rule 3 applies.*/
	if(chars_found == str.end - str.begin + 1)
	{
		*rule_applied = 3;
		/*If there is an internal node that has no suffix 
		link yet (only one may exist) - create a suffix link
		from it to the father-node of the current position 
		in the tree (pos)*/
		if(suffixless != 0)
		{
			create_suffix_link(suffixless, pos->node->father);
			/*marks that no internal node with no suffix 
			link exists.*/
			suffixless = 0;
		}

		#ifdef DEBUG	
			printf("rule 3 (%lu,%lu)\n",str.begin,str.end);
		#endif
		return;
	}
	
	/*if last char found is the last char of an edge - add 
	a character at the next edge*/
	if(is_last_char_in_edge(tree,pos->node,pos->edge_pos) || pos->node == tree->root)
	{
		/*decide whether to apply rule 2 (new_son) or rule 1.*/
		if(pos->node->sons != 0)
		{
			/*apply extension rule 2 new son - a new leaf 
			is created and returned by apply_extension_rule_2.*/
			apply_extension_rule_2(pos->node, str.begin+chars_found, str.end, path_pos, 0, new_son);
			*rule_applied = 2;
			/*If there is an internal node that has no suffix
			link yet (only one may exist) - create a suffix link
			from it to the father-node of the current position 
			in the tree (pos)*/
			if(suffixless != 0)
			{
				create_suffix_link(suffixless, pos->node);
				/*marks that no internal node with no suffix 
				link exists.*/
				suffixless = 0;
			}
		}
	}
	else
	{
		/*apply extension rule 2 split - a new node is created 
		and returned by apply_extension_rule_2.*/
		tmp = apply_extension_rule_2(pos->node, str.begin+chars_found, str.end, path_pos, pos->edge_pos, split);
		if(suffixless != 0)
			create_suffix_link(suffixless, tmp);
		/*link root's sons with a single character to the root*/
		if(get_node_label_length(tree,tmp) == 1 && tmp->father == tree->root)
		{
			tmp->suffix_link = tree->root;
			/*marks that no internal node with no suffix link 
			exists.*/
			suffixless = 0;
		}
		else
			/*mark tmp as waiting for a link.*/
			suffixless = tmp;
		
		/*Pepare pos for the next extension.*/
		pos->node = tmp;
		*rule_applied = 2;
	}
}

/**************************************************************/
/**************************************************************/

/*Performs all insertion of a single phase by calling function 
SEA starting from the first extension that does not already 
exist in the tree and ending at the first extension that 
already exists in the tree. 

  Input :The tree, pos - the node and position in its incoming
         edge where extension begins, the phase number, the 
		 first extension number of that phase, a flag signaling 
		 whether the extension is the first of this phase, 
		 after the last phase ended with rule 3. If so - extension
		 will be executed again in this phase, and thus its 
		 suffix link would not be followed.

  Output:The extension number that was last executed on this 
         phase. Next phase will start from it and not from 1.*/


/**************************************************************/
void SPA(	/*the tree*/
		    SUFFIX_TREE*	tree,				
			/*current node*/
			POS*			pos,				
			/*current phase number.*/
			DBL_WORD		phase,				
			/*the last extension performed in the 
			previous phase.*/
			DBL_WORD		*extension,			
			/*1 if the last rule applied is 3*/
			char *			repeated_extension)	
{
	/*no such rule (0). Used for entering the loop.*/
	DBL_WORD	rule_applied = 0;	
	PATH		str;
	
	/*Leafs Trick: Apply implicit extensions 1 through 
	prev_phase.*/
	tree->e = phase+1;

	/*Apply explicit extensions untill last extension 
	of this phase is reached or */
	/*extension rule 3 is applied once.*/
	while(*extension <= phase+1)				
	{
		str.begin		= *extension;
		str.end			= phase+1;
		
		/*Call single-extension-algorithm*/
		SEA(tree, pos, str, &rule_applied, *repeated_extension);
		
		/*check if rule 3 was applied for the current 
		extension*/
		if(rule_applied == 3)
		{
			/*Signaling that the next phase's first 
			extension will not follow a suffix link 
			because same extension is repeated.*/
			*repeated_extension = 1;
			break;
		}
		*repeated_extension = 0;
		(*extension)++;
	}
	return;
}

/**************************************************************/
/**************************************************************/

/*Allocates memory for the tree and starts Ukkonen's construction
 algorithm by calling SPA n times, where n is the length of 
 the source string.

  Input : The source string and its length. The string is a 
          sequence of unsigned characters (maximum of 256 different
		  symbols) and not null-terminated. The only symbol that 
		  must not appear in the string is $ (the dollar sign). 
		  It is used as a unique symbol by the algorithm ans is 
		  appended automatically at the end of the string (by 
		  the program, not by the user !). The meaning of the $
		  sign is connected to the implicit/explicit suffix tree
		  transformation, detailed in Ukkonen's algorithm.

  Output: A pointer to the newly created tree. Keep this pointer
          in order to perform operations like search and delete 
		  on that tree. Obviously, no de-allocating of the tree 
		  space could be done if this pointer is lost, as the
          tree is allocated dynamically on the heap.*/


/**************************************************************/
SUFFIX_TREE* ST_CreateTree(const unsigned char*	str, DBL_WORD length)
{
	SUFFIX_TREE		*tree;
	DBL_WORD		phase,
					extension;
	char			repeated_extension = 0;
	POS				pos;

	if(str == 0)
		return 0;

	/*Allocating the tree.*/
	tree					= (SUFFIX_TREE *)malloc(sizeof(SUFFIX_TREE));
	if(tree == 0)
	{
		printf("\nOut of memory.\n");
		exit(0);
	}
	heap+=sizeof(SUFFIX_TREE);

	/*Calculating string length (with an ending $ sign).*/
	tree->length			= length+1;
	ST_ERROR				= length+10;
	
	/*Allocating the only real string of the tree.*/
	tree->tree_string = (unsigned char *)malloc((tree->length+1)*sizeof(unsigned char));
	if(tree->tree_string == 0)
	{
		printf("\nOut of memory.\n");
		exit(0);
	}
	heap+=(tree->length+1)*sizeof(unsigned char);

	memcpy(tree->tree_string+sizeof(unsigned char),str,length*sizeof(unsigned char));
	/*$ is considered a uniqe symbol*/
	tree->tree_string[tree->length] = '$';
	
	/*Allocating the tree root node.*/
	tree->root				= create_node(0, 0, 0, 0);
	tree->root->suffix_link = 0;

	/*Initializing algorithm parameters*/
	extension = 2;
	phase = 2;
	
	/*Allocating first node, son of the root (phase 0), the 
	longest path node*/
	tree->root->sons = create_node(tree->root, 1, tree->length, 1);
	suffixless		 = 0;
	pos.node		 = tree->root;
	pos.edge_pos	 = 0;

	/*Ukkonen's algorithm begins here.*/
	for(; phase < tree->length; phase++)
	{
		/*Perform Single Phase Algorithm*/
		SPA(tree, &pos, phase, &extension, &repeated_extension);
	}
	return tree;
}

/**************************************************************/
/**************************************************************/

/*Deletes a subtree that is under node. It recoursively calls 
itself for all of node's right sons and then 
deletes node.

  Input : The node that is the root of the subtree to be deleted.

  Output: None.*/


/**************************************************************/
void ST_DeleteSubTree(NODE* node)
{
	/*Recoursion stoping condition*/
	if(node == 0)
		return;
	/*Recoursive call for right sibling.*/
	if(node->right_sibling!=0)
		ST_DeleteSubTree(node->right_sibling);
	/*Recoursive call for first son.*/
	if(node->sons!=0)
		ST_DeleteSubTree(node->sons);
	/*Delete node itself, after its whole tree was deleted
	as well.*/
	free(node);
}

/**************************************************************/
/**************************************************************/

/*Deletes a whole suffix tree by starting a recoursive call to 
ST_DeleteSubTree from the root. After all of the nodes have 
been deleted, the function deletes the structure that represents
the tree.

  Input : The tree to be deleted.

  Output: None.*/


/**************************************************************/
void ST_DeleteTree(SUFFIX_TREE* tree)
{
	if(tree == 0)
		return;
	ST_DeleteSubTree(tree->root);
/* Canasai's addition begin */
	free( tree->tree_string );
/* Canasai's addition end */
	free(tree);
}

/**************************************************************/
/**************************************************************/

/*Prints a subtree under a node of a certain tree-depth.

  Input : The tree, the node that is the root of the subtree, 
          and the depth of that node. The depth is used for 
		  printing the branches that are coming from higher
          nodes and only then the node itself is printed. This 
		  gives the effect of a tree on screen. In each 
		  recoursive call, the depth is increased.
  
  Output: A printout of the subtree to the screen.*/


/**************************************************************/
void ST_PrintNode(SUFFIX_TREE* tree, NODE* node1, long depth)
{
	NODE *node2 = node1->sons;
	long d = depth,start = node1->edge_label_start, end;
	end = get_node_label_end(tree, node1);

	if(depth>0)
	{
		/*Print the branches coming from higher nodes.*/
		while(d>1)
		{
			printf("|");
			d--;
		}
		printf("+");
		/*Print the node itself.*/
		while(start<=end)
		{
			printf("%c",tree->tree_string[start]);
			start++;
		}
		#ifdef DEBUG
		printf("  \t\t\t(%lu,%lu | %lu)",node1->edge_label_start,end,node1->path_position);
		#endif
		printf("\n");
	}
	/*Recoursive call for all node1's sons.*/
	while(node2!=0)
	{
		ST_PrintNode(tree,node2, depth+1);
		node2 = node2->right_sibling;
	}
}

/**************************************************************/
/**************************************************************/

/*This function prints the full path of a node, starting from 
the root. It calls itself recoursively and than prints the 
last edge.

  Input : the tree and the node its path is to be printed.

  Output: Prints the path to the screen, no return value.*/


/**************************************************************/
void ST_PrintFullNode(SUFFIX_TREE* tree, NODE* node)
{
	long start, end;
	if(node==NULL)
		return;
	/*Calculating the begining and ending of the last edge.*/
	start	= node->edge_label_start;
	end		= get_node_label_end(tree, node);
	
	/*Stoping condition - the root*/
	if(node->father!=tree->root)
		ST_PrintFullNode(tree,node->father);
	/*Print the last edge*/
	while(start<=end)
	{
		printf("%c",tree->tree_string[start]);
		start++;
	}
}


/**************************************************************/
/**************************************************************/

/*This function prints the tree. It simply starts the recoursive 
function ST_PrintNode from the root

  Input : The tree to be printed.
  
  Output: A print out of the tree to the screen.*/


/**************************************************************/
void ST_PrintTree(SUFFIX_TREE* tree)
{
	printf("\nroot\n");
	/*Starts a recoursive call to ST_PrintNode with 
	depth 0 (the root).*/
	ST_PrintNode(tree, tree->root, 0);
}

/**************************************************************/
/**************************************************************/

/*Self test of the tree - search for all substrings of the 
main string. See testing paragraph in the 
readme.txt files.

  Input : The tree to test.

  Output: 1 for success and 0 for failure.
  		  Prints a result message to the screen.*/


/**************************************************************/
DBL_WORD ST_SelfTest(SUFFIX_TREE* tree)
{
	DBL_WORD k,j,i;

#ifdef STATISTICS
	DBL_WORD old_counter = counter;
#endif

	/*Loop for all the prefixes of he tree source string.*/
	for(k = 1; k<tree->length; k++)
	{
		/*Loop for each suffix of each prefix.*/
		for(j = 1; j<=k; j++)
		{

#ifdef STATISTICS
			counter = 0;
#endif

			/*Search the current suffix in the tree.*/
			i = ST_FindSubstring(tree, (unsigned char*)(tree->tree_string+j), k-j+1);
			if(i == ST_ERROR)
			{
				printf("\n\nTest Results: Fail in string (%lu,%lu).\n\n",j,k);
				return 0;
			}
		}
	}
	
#ifdef STATISTICS
	counter = old_counter;
#endif

	/*If we are here, no search has failed, thus, the 
	test has passed successfuly.*/
	printf("\n\nTest Results: Success.\n\n");
	return 1;
}