dyadic_gsearch.c File Reference

Best non-decreasing dyadic partition search. More...

#include "libftsh.h"

Defines
#define	ENTEREXIT   0
Functions
int	dyadic_gsearch (Dyadic_Gsearch_Save *dy_gs_save)
void	dyadic_gsearch_init (Dyadic_Gsearch_Save *dy_gs_save, int num_levels)
void	dyadic_gsearch_free (Dyadic_Gsearch_Save *dy_gs_save)

---

Detailed Description

Best non-decreasing dyadic partition search.

Summary:

• dyadic_gsearch is the actual search
• dyadic_gsearch_init initializes a structure
• dyadic_gsearch_free frees this structure

The memory for all the objects used in the search are held in a structure of type Dyadic_Gsearch_Save. Declare one of these:

Dyadic_Gsearch_Save dy_gs_save;

To initialize this structure, call

dyadic_gsearch_init(&dy_gs_save,num_levels);

with num_levels the number of dyadic levels to use.

Then compute whatever basis you are using and load in the costs: costfull[level][within] should contain the full bell cost of the within^th interval the level^th level (2^level intervals on level). Similarly for costasym.

Then call this routine to do the search itself. Returns the minimal cost, which is also stored in dy_gs_save.costfull[dy_gs_save.best_level][0].

dyadic_gsearch(&dy_gs_save);

You can then do other basis expansions (with the same num_levels) and searchs.

When you are ready to free the memory, call

dyadic_gsearch_free(&dy_gs_save);

---

Function Documentation

int dyadic_gsearch

(

Dyadic_Gsearch_Save *

dy_gs_save

)

This routine implements a `best non-decreasing dyadic partition' search. It finds the partition with lowest cost under the restriction that an interval's right neighbor is either the same size or one size (2x) larger. Generally this is to be used with local cosine. When an interval's left neighbor is the same size, we use a regular full sized bell and put the cost of this expansion in .cost_full[][]. When the left neighbor is smaller we shrink the left edge of the bell, making it asymmetric and yielding .cost_asym[][].

The search tree is grown from the left, with an interval having children its allowed right neighbors. The cost of a partition is the cost of a path from the left edge to the right edge. Since each interval has two costs, the path into an interval is also important.

   | _--------------O                   |        
   |/                                   |                     
  /|  _-----O-------|--------->O        |                       
 O-|-/           _--|--------/          |
  \|       |    /   |         |         |                     
   |~--O---|-->O----|--->O----|---->O   |                        

The generic decision step is: assume the current node's children contain the minimal cost of a path from them to the right. Compare these costs and ADD the smaller to the full and asym costs of the current node. We process intervals in order of the x-coordinate of their center, starting at the right.

INPUTS: dy_gs_save -- a structure holding memory for the costs, branching and ordering of interval. See the declaration of the structure Dyadic_Gsearch_Save for the full description of its fields.

OUTPUTS: returns the minimal cost, and also stores it in dy_gs_save.costfull[dy_gs_save.best_level][0]. To determine the partition chosen, start at [best_level][0] and follow .branching[][], which has values one of {RIGHTEDGE=0, SAMESIZE=1, UPSIZE=2}

Here is the caller graph for this function:

void dyadic_gsearch_free

(

Dyadic_Gsearch_Save *

dy_gs_save

)

This function frees the structure Dyadic_Gsearch_Save used by dyadic_gsearch and initialized by dyadic_gsearch_init.

INPUTS: dy_gs_save -- a pointer to the structure to free

OUTPUT: none

Here is the caller graph for this function:

void dyadic_gsearch_init	(	Dyadic_Gsearch_Save *	dy_gs_save,
		int	num_levels
	)

This function initializes the structure Dyadic_Gsearch_Save for use by dyadic_gsearch. Memory can be freed by dyadic_gsearch_free.

INPUTS:

• dy_gs_save -- a pointer to the structure to fill in
• num_levels -- the number of dyadic levels to use

OUTPUT: dy_gs_save -- memory is allocated and some things filled in.

Here is the caller graph for this function: