slope_util.c

Vector Quantization压缩算法

/******************************************************************************
 * Name
 *    slope_util.c
 *    J. R. Goldschneider some of this is based on code from the ftp site
 *        at Stanford. I do not know who is responsible for it.
 *    February 1994
 *    Last Revision
 *        December 1994, add a test to slope() to make sure that a node
 *        cannot be added to the tree unless it has a minimum number of
 *        nodes.  This tries to ensure that each codeword has at least
 *        DEF_min_vectors training vectors per codeword.
 *
 * SYNOPSIS
 *    void      update_rate(maxslopenode,bits,distortion)
 *    DISTTYPE  slope(node)
 *    BOOLEAN   conditional_insert(node)
 *    BOOLEAN   forced_insert(node)
 *    BOOLEAN   initialize_slopelist()
 *    void      delete_slopelist(list_element)
 *    SlopeList *find_maxslope()
 *    SlopeList *find_oldest_entry()
 *
 * DESCRIPTION
 *    update_rate recomputes bits and distortion given that the node pointed
 *    to by maxslopenode is being replaced by its two children.
 *
 *    slope computes the change in distortion one would achieve if the node
 *    was replaced by its two children.
 *
 *    conditional_insert creates a SlopeList element pointing to the node and
 *    inserts it into slist only if the slope is non-zero. This should be
 *    used for unbalanced trees.
 *
 *    forced_insert creates a SlopeList element pointing to the node and
 *    inserts it into slist regardless of the slope.  This should be used
 *    for balanced trees.
 *
 *    initialize_slopelist creates the slist with a dummy element that
 *    heads slist and will never be selected.
 *
 *    delete_slopelist removes the list_element from the slist.
 *
 *    find_maxslope searches slist to find the node with the largest slope.
 *    This should be used for an unbalanced tree.
 *
 *    find_oldest_entry searches slist to find the oldest node.  This should
 *    be used for a balanced tree.
 *
 * RETURN VALUE
 *    update_rate returns no value, but bits and distortion are modified.
 *
 *    slope returns the change in distortion due to replacing node with
 *    its children.
 *
 *    conditiional_insert returns TRUE if successful, FALSE if not successful.
 *
 *    forced_insert returns TRUE if successful, FALSE if not successful.
 *
 *    initialize_slopelist returns TRUE if successful, FALSE if not successful.
 *
 *    delete_slopelist returns no value.
 *
 *    find_maxslope returns the list element pointing to the node with
 *    the maximum slope.
 *
 *    find_oldest_entry returns the list element pointing to the node
 *    that was entered before all the others.
 *
 * PARAMETERS
 *    maxslopenode is pointer to the node being replaced.
 *    bits is the total number of bits used to encode the training sequence.
 *    distortion is the result from encoding the training sequence.
 *
 *    node is the node that may be replaced be its children.
 *
 *    node is the node to which the SlopeList element should point.
 *
 *    list_element is the element to be removed from slist.
 *
 * CALLS
 *
 *****************************************************************************/
#include "tsvq.h"

char      *programname;
SlopeList *slist;

void update_rate(maxslopenode,bits,distortion)
     SlopeList *maxslopenode;
     long      *bits;
     DISTTYPE  *distortion;
{
  /* the distortion is the same as the old distortion less the distortion
     due to the node being replaced plus the distortion due to the
     two nodes just added */
  *distortion +=  maxslopenode->node->left_child->avmse *
    ((DISTTYPE) maxslopenode->node->left_child->count) +
      maxslopenode->node->right_child->avmse *
	((DISTTYPE) maxslopenode->node->right_child->count) -
	  maxslopenode->node->avmse * ((DISTTYPE) maxslopenode->node->count);

  /* when the very last nodes are added, the distortion is -0.0 */
  if (*distortion <= 0) *distortion = 0;

  /* the number of bits is the same as the old number plus count since
     this is just a replacement of one node by its two children */
  *bits += maxslopenode->node->count;
}

DISTTYPE slope(node)
     TreeNode *node;
{
  DISTTYPE distnode;
  DISTTYPE probleft = 0.0;
  DISTTYPE probright = 0.0;

  if(node->count < DEF_min_vectors) return( (DISTTYPE) 0.0 );

  probleft = ((DISTTYPE) (node->left_child->count)) /
    ((DISTTYPE) node->count);
  probright = ((DISTTYPE) (node->right_child->count)) /
    ((DISTTYPE) node->count);

  distnode = (node->avmse) -
    (probleft * (node->left_child->avmse)) -
      (probright * (node->right_child->avmse));

  /* slope is (change in distortion)/(change in rate) and (change in rate)
     is equal to count, so it is not necessary to multiply distnode by
     count */
  return(distnode);
}

BOOLEAN conditional_insert(node)
     TreeNode *node;

{
  if (slope(node) > 0) {
    return(forced_insert(node));
  }
  else {
    return(TRUE);
  }
}

BOOLEAN forced_insert(node)
     TreeNode *node;
{
  SlopeList *tempnode;

  if(!(tempnode = (SlopeList *) calloc(1,sizeof(SlopeList)))) {
    fprintf(stderr,"%s: %s\n",programname,NOMEMORY);
    return(FALSE);
  }

  /* insert the newest node at the beginning of the list */
  slist->next->previous = tempnode;
  tempnode->next=slist->next;
  slist->next = tempnode;
  tempnode->previous = slist;
  tempnode->slope = slope(node);
  tempnode->node = node;
  return(TRUE);
}

BOOLEAN initialize_slopelist()
{
  if(!(slist = (SlopeList *) calloc(1,sizeof(SlopeList)))) {
    fprintf(stderr,"%s: %s\n",programname,NOMEMORY);
    return(FALSE);
  }

  /* the slope of 0.0 ensures that there is always one entry in the list
     and that it will never be chosen */
  slist->previous = slist;
  slist->next = slist;
  slist->slope = 0.0;
  slist->node = NULL;
  return(TRUE);
}


void delete_slopelist(list_element)
     SlopeList *list_element;
{
  list_element->previous->next = list_element->next;
  list_element->next->previous = list_element->previous;
  free((char *) list_element);
}

SlopeList *find_maxslope()
{
  SlopeList *i;
  SlopeList *currentbest;
  DISTTYPE max;

  if(!(i = (SlopeList *) calloc(1,sizeof(SlopeList))) ||
     !(currentbest = (SlopeList *) calloc(1,sizeof(SlopeList)))) {
    fprintf(stderr,"%s: %s\n",programname,NOMEMORY);
    return(NULL);
  }

  /* the first node is a dummy node */
  max = 0.0;
  currentbest = slist;

  /* search the list for the largest slope */
  for (i = slist->next; i != slist; i = i->next) {
    if (i->slope > max)	{
      max = i->slope;
      currentbest = i;
    }
  }

  return(currentbest);
}

SlopeList *find_oldest_entry()
{
  /* this should be used for a balanced tree, return the oldest entry */
  return(slist->previous);
}