suffix_tree.c

suffix tree suffix tree suffix tree

      #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;
      
      /* Prepare pos for the next extension */
      pos->node = tmp;
      *rule_applied = 2;
   }
}

/******************************************************************************/
/*
   SPA :
   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;
}

/******************************************************************************/
/*
   ST_CreateTree :
   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 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 = 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 = malloc((tree->length+1)*sizeof(char));
   if(tree->tree_string == 0)
   {
      printf("\nOut of memory.\n");
      exit(0);
   }
   heap+=(tree->length+1)*sizeof(char);

   memcpy(tree->tree_string+sizeof(char),str,length*sizeof(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;
}

/******************************************************************************/
/*
   ST_DeleteSubTree :
   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);
}

/******************************************************************************/
/*
   ST_DeleteTree :
   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);
   free(tree);
}

/******************************************************************************/
/*
   ST_PrintNode :
   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;
   }
}

/******************************************************************************/
/*
   ST_PrintFullNode :
   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++;
   }
}


/******************************************************************************/
/*
   ST_PrintTree :
   This function prints the tree. It simply starts the recoursive function 
   ST_PrintNode with depth 0 (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");
   ST_PrintNode(tree, tree->root, 0);
}

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

   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 the 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, (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 and the test passed successfuly */
   printf("\n\nTest Results: Success.\n\n");
   return 1;
}