wordrec/bestfirst.h File Reference

#include "oldheap.h"
#include "closed.h"
#include "choicearr.h"
#include "associate.h"
#include "choices.h"
#include "states.h"
#include "stopper.h"
#include "blobs.h"
#include "tessclas.h"
#include "seam.h"

Go to the source code of this file.

Classes

• struct SEARCH_RECORD

  Holds all information on one segmentation search. More...
  

Defines

• #define chunks_gap(chunk_widths, last_chunk)

  Return the width of several of the chunks, if they were joined together.
  

Functions

• void best_first_search (CHUNKS_RECORD *chunks_record, A_CHOICE *best_choice, A_CHOICE *raw_choice, STATE *state, DANGERR *fixpt, STATE *best_state, INT32 pass)

  Find the best segmentation by doing a best first search of the solution space.
  

• int chunks_width (WIDTH_RECORD *width_record, int start_chunk, int last_chunk)

  Return the width of several of the chunks (if they were joined together.
  

• void delete_search (SEARCH_RECORD *the_search)

  Terminate the current search and free all the memory involved.
  

• CHOICES_LIST evaluate_chunks (CHUNKS_RECORD *chunks_record, SEARCH_STATE search_state, STATE *this_state, STATE *best_state, INT32 pass)

  Since a particular word level segmentation has been chosen, evaluate this to find the word list that corresponds to it.
  

• INT16 evaluate_state (CHUNKS_RECORD *chunks_record, SEARCH_RECORD *the_search, DANGERR *fixpt, STATE *best_state, INT32 pass)

  Evaluate the segmentation that is represented by this state in the best first search & add this state to the "states_seen" list.
  

• void expand_node (CHUNKS_RECORD *chunks_record, SEARCH_RECORD *the_search)

  Create the states that are attached to this one.
  

• void init_bestfirst_vars ()

  Create and initialize references to debug variables that control operations in this file.
  

• SEARCH_RECORD * new_search (CHUNKS_RECORD *chunks_record, int num_joints, A_CHOICE *best_choice, A_CHOICE *raw_choice, STATE *state)

  Create and initialize a new search record.
  

• STATE * pop_queue (HEAP *queue)

  Get this state from the priority queue.
  

• void push_queue (HEAP *queue, STATE *state, FLOAT32 priority)

  Add this state into the priority queue.
  

• CHOICES_LIST rebuild_current_state (TBLOB *blobs, SEAMS seam_list, STATE *state, CHOICES_LIST old_choices, int fx)

  Evaluate the segmentation that is represented by this state in the best first search & add this state to the "states_seen" list.
  

• void replace_char_widths (CHUNKS_RECORD *chunks_record, SEARCH_STATE state)

  Replace the value of the char_width field in the chunks_record with the updated width measurements from the last_segmentation.
  

Variables

• int num_popped
• int num_seg_states

---

Define Documentation

#define chunks_gap	(	chunk_widths,
		last_chunk		)

Value:

((last_chunk < (chunk_widths)->num_chars - 1) ?  \
   ((chunk_widths)->widths[last_chunk * 2 + 1]) :  \
   (0))

Return the width of several of the chunks, if they were joined together.

Definition at line 77 of file bestfirst.h.

Referenced by evaluate_chunks(), and state_char_widths().

---

Function Documentation

void best_first_search	(	CHUNKS_RECORD *	chunks_record,
		A_CHOICE *	best_choice,
		A_CHOICE *	raw_choice,
		STATE *	state,
		DANGERR *	fixpt,
		STATE *	best_state,
		INT32	pass
	)

Find the best segmentation by doing a best first search of the solution space.

Definition at line 76 of file bestfirst.cpp.

References SEARCH_RECORD::best_state, blob_skip, SEARCH_RECORD::closed_states, delete_search(), evaluate_state(), expand_node(), free_state(), hash_add(), hash_lookup(), matrix_dimension, new_search(), num_joints, num_popped, num_seg_states, SEARCH_RECORD::num_states, SEARCH_RECORD::open_states, STATE::part1, STATE::part2, pop_queue(), CHUNKS_RECORD::ratings, save_best_state(), start_recording(), stop_recording(), and SEARCH_RECORD::this_state.

Referenced by word_associator().

                                   {
  SEARCH_RECORD *the_search;
  INT16 keep_going;
  STATE guided_state;

  num_joints = matrix_dimension (chunks_record->ratings) - 1;
  the_search = new_search (chunks_record, num_joints,
    best_choice, raw_choice, state);

#ifndef GRAPHICS_DISABLED
  save_best_state(chunks_record); 
#endif
  start_recording(); 

  guided_state = *state;
  do {
                                 /* Look for answer */
    if (!hash_lookup (the_search->closed_states, the_search->this_state)) {

      if (blob_skip) {
        free_state (the_search->this_state);
        break;
      }

      guided_state = *(the_search->this_state);
      keep_going =
        evaluate_state(chunks_record, the_search, fixpt, best_state, pass); 

      hash_add (the_search->closed_states, the_search->this_state);

      if (!keep_going ||
      (the_search->num_states > num_seg_states) || (blob_skip)) {
        free_state (the_search->this_state);
        break;
      }

      expand_node(chunks_record, the_search); 
    }

    free_state (the_search->this_state);
    num_popped++;
    the_search->this_state = pop_queue (the_search->open_states);
  }
  while (the_search->this_state);

  state->part1 = the_search->best_state->part1;
  state->part2 = the_search->best_state->part2;
  stop_recording(); 
  delete_search(the_search); 
}

int chunks_width	(	WIDTH_RECORD *	width_record,
		int	start_chunk,
		int	last_chunk
	)

Return the width of several of the chunks (if they were joined together.

Definition at line 139 of file bestfirst.cpp.

References WIDTH_RECORD::widths.

Referenced by evaluate_chunks(), and state_char_widths().

                                                                              { 
  int result = 0;
  int x;

  for (x = start_chunk * 2; x <= last_chunk * 2; x++)
    result += width_record->widths[x];

  return (result);
}

void delete_search

(

SEARCH_RECORD *

the_search

)

Terminate the current search and free all the memory involved.

Definition at line 154 of file bestfirst.cpp.

References SEARCH_RECORD::before_best, SEARCH_RECORD::best_state, SEARCH_RECORD::closed_states, SEARCH_RECORD::first_state, free_hash_table, free_state(), FreeHeapData(), hamming_distance(), memfree(), SEARCH_RECORD::num_joints, SEARCH_RECORD::num_states, SEARCH_RECORD::open_states, and record_search_status().

Referenced by best_first_search().

                                              { 
  float closeness;

  closeness = (the_search->num_joints ?
    (hamming_distance ((unsigned long *) the_search->first_state,
    (unsigned long *) the_search->best_state,
    2) / (float) the_search->num_joints) : 0.0);

  record_search_status (the_search->num_states,
    the_search->before_best, closeness);

  free_state (the_search->first_state);
  free_state (the_search->best_state);

  free_hash_table (the_search->closed_states);
  FreeHeapData (the_search->open_states, (void_dest) free_state);

  memfree(the_search); 
}

CHOICES_LIST evaluate_chunks	(	CHUNKS_RECORD *	chunks_record,
		SEARCH_STATE	search_state,
		STATE *	this_state,
		STATE *	best_state,
		INT32	pass
	)

Since a particular word level segmentation has been chosen, evaluate this to find the word list that corresponds to it.

Definition at line 180 of file bestfirst.cpp.

References array_free, array_push(), best_certainty, best_probability, blob_skip, CHUNKS_RECORD::chunk_widths, CHUNKS_RECORD::chunks, chunks_gap, chunks_width(), count_blobs(), CHUNKS_RECORD::fx, get_piece_rating(), last_segmentation, new_choice_list, NIL, NULL, CHUNKS_RECORD::ratings, and CHUNKS_RECORD::splits.

Referenced by evaluate_state().

                                         {
  CHOICES_LIST char_choices;
  CHOICES this_choice;
  int i;
  int x = 0;
  int y;

  char_choices = new_choice_list ();
  /* Iterate sub-paths */
  for (i = 1; i <= search_state[0] + 1; i++) {
    if (i > search_state[0])
      y = count_blobs (chunks_record->chunks) - 1;
    else
      y = x + search_state[i];

    if (blob_skip) {
      array_free(char_choices); 
      return (NULL);
    }                            /* Process one square */
    /* Classify if needed */
    this_choice = get_piece_rating (chunks_record->ratings,
      chunks_record->chunks,
      chunks_record->splits,
      x, y,
      chunks_record->fx,
      this_state, best_state, pass, i - 1);

    if (this_choice == NIL) {
      array_free(char_choices); 
      return (NULL);
    }
    /* Add permuted ratings */
    last_segmentation[i - 1].certainty = best_certainty (this_choice);
    last_segmentation[i - 1].match = best_probability (this_choice);

    last_segmentation[i - 1].width =
      chunks_width (chunks_record->chunk_widths, x, y);
    last_segmentation[i - 1].gap =
      chunks_gap (chunks_record->chunk_widths, y);

    char_choices = array_push (char_choices, this_choice);
    x = y + 1;
  }
  return (char_choices);
}

INT16 evaluate_state	(	CHUNKS_RECORD *	chunks_record,
		SEARCH_RECORD *	the_search,
		DANGERR *	fixpt,
		STATE *	best_state,
		INT32	pass
	)

Evaluate the segmentation that is represented by this state in the best first search & add this state to the "states_seen" list.

Definition at line 236 of file bestfirst.cpp.

References AcceptableChoice(), array_free, SEARCH_RECORD::before_best, SEARCH_RECORD::best_choice, SEARCH_RECORD::best_state, bin_to_chunks(), bin_to_pieces(), CHUNKS_RECORD::chunks, class_probability, display_segmentation(), display_segmentations, evaluate_chunks(), FALSE, DANGERR::index, LogNewSegmentation(), memfree(), NULL, SEARCH_RECORD::num_joints, SEARCH_RECORD::num_states, STATE::part1, STATE::part2, permute_characters(), SEARCH_RECORD::raw_choice, replace_char_widths(), segm_window, SEARCH_RECORD::this_state, TRUE, and window_wait().

Referenced by best_first_search().

                                 {
  CHOICES_LIST char_choices;
  SEARCH_STATE chunk_groups;
  float rating_limit = class_probability (the_search->best_choice);
  INT16 keep_going = TRUE;
  PIECES_STATE widths;

  the_search->num_states++;
  chunk_groups = bin_to_chunks (the_search->this_state,
    the_search->num_joints);
  bin_to_pieces (the_search->this_state, the_search->num_joints, widths);
  LogNewSegmentation(widths); 

  rating_limit = class_probability (the_search->best_choice);

  char_choices =
    evaluate_chunks (chunks_record, chunk_groups, the_search->this_state,
    best_state, pass);
  if (char_choices != NULL) {
    permute_characters (char_choices,
      rating_limit,
      the_search->best_choice, the_search->raw_choice);
    if (AcceptableChoice (char_choices, the_search->best_choice,
      the_search->raw_choice, fixpt))
      keep_going = FALSE;
    array_free(char_choices); 
  }

#ifndef GRAPHICS_DISABLED
  if (display_segmentations) {
    display_segmentation (chunks_record->chunks, chunk_groups);
    if (display_segmentations > 1)
      window_wait(segm_window); 
  }
#endif

  if (rating_limit != class_probability (the_search->best_choice)) {
    the_search->before_best = the_search->num_states;
    the_search->best_state->part1 = the_search->this_state->part1;
    the_search->best_state->part2 = the_search->this_state->part2;
    replace_char_widths(chunks_record, chunk_groups); 
  }
  else if (char_choices != NULL)
    fixpt->index = -1;

  memfree(chunk_groups); 

  return (keep_going);
}

void expand_node	(	CHUNKS_RECORD *	chunks_record,
		SEARCH_RECORD *	the_search
	)

Create the states that are attached to this one.

Check to see that each one has not already been visited. If not add it to the priority queue.

Definition at line 366 of file bestfirst.cpp.

References SEARCH_RECORD::closed_states, hash_lookup(), SEARCH_RECORD::num_joints, SEARCH_RECORD::open_states, STATE::part1, STATE::part2, prioritize_state(), push_queue(), and SEARCH_RECORD::this_state.

Referenced by best_first_search().

                                                                          { 
  STATE old_state;
  int x;
  int mask = 1 << (the_search->num_joints - 1 - 32);

  old_state.part1 = the_search->this_state->part1;
  old_state.part2 = the_search->this_state->part2;

  for (x = the_search->num_joints; x > 32; x--) {
    the_search->this_state->part1 = mask ^ old_state.part1;
    if (!hash_lookup (the_search->closed_states, the_search->this_state))
      push_queue (the_search->open_states,
        the_search->this_state,
        prioritize_state (chunks_record, the_search, &old_state));
    mask >>= 1;
  }

  if (the_search->num_joints > 32) {
    mask = 1 << 31;
  }
  else {
    mask = 1 << (the_search->num_joints - 1);
  }

  while (x--) {
    the_search->this_state->part2 = mask ^ old_state.part2;
    if (!hash_lookup (the_search->closed_states, the_search->this_state))
      push_queue (the_search->open_states,
        the_search->this_state,
        prioritize_state (chunks_record, the_search, &old_state));
    mask >>= 1;
  }
}

void init_bestfirst_vars

(

)

Create and initialize references to debug variables that control operations in this file.

Definition at line 65 of file bestfirst.cpp.

Referenced by init_ms_debug().

                           { 
  make_seg_states(); 
  make_worst_state(); 
}

SEARCH_RECORD* new_search	(	CHUNKS_RECORD *	chunks_record,
		int	num_joints,
		A_CHOICE *	best_choice,
		A_CHOICE *	raw_choice,
		STATE *	state
	)

Create and initialize a new search record.

Definition at line 405 of file bestfirst.cpp.

References SEARCH_RECORD::before_best, SEARCH_RECORD::best_choice, SEARCH_RECORD::best_state, SEARCH_RECORD::closed_states, cprintf(), SEARCH_RECORD::first_state, MakeHeap(), memalloc(), new_hash_table(), new_state(), SEARCH_RECORD::num_joints, num_seg_states, SEARCH_RECORD::num_states, SEARCH_RECORD::open_states, SEARCH_RECORD::raw_choice, and SEARCH_RECORD::this_state.

Referenced by best_first_search().

                                        {
  SEARCH_RECORD *this_search;

  this_search = (SEARCH_RECORD *) memalloc (sizeof (SEARCH_RECORD));

  this_search->open_states = MakeHeap (num_seg_states * 20);
  this_search->closed_states = new_hash_table ();

  if (state)
    this_search->this_state = new_state (state);
  else
    cprintf ("error: bad initial state in new_search\n");

  this_search->first_state = new_state (this_search->this_state);
  this_search->best_state = new_state (this_search->this_state);

  this_search->best_choice = best_choice;
  this_search->raw_choice = raw_choice;

  this_search->num_joints = num_joints;
  this_search->num_states = 0;
  this_search->before_best = 0;

  return (this_search);
}

STATE* pop_queue

(

HEAP *

queue

)

Get this state from the priority queue.

It should be the state that has the greatest urgency to be evaluated.

Definition at line 442 of file bestfirst.cpp.

References cprintf(), HEAPENTRY::Data, display_segmentations, GetTopOfHeap(), HEAPENTRY::Key, NULL, num_joints, OK, and print_state().

Referenced by best_first_search().

                              { 
  HEAPENTRY entry;

  if (GetTopOfHeap (queue, &entry) == OK) {
#ifndef GRAPHICS_DISABLED
    if (display_segmentations) {
      cprintf ("eval state: %8.3f ", entry.Key);
      print_state ("", (STATE *) entry.Data, num_joints);
    }
#endif
    return ((STATE *) entry.Data);
  }
  else {
    return (NULL);
  }
}

void push_queue	(	HEAP *	queue,
		STATE *	state,
		FLOAT32	priority
	)

Add this state into the priority queue.

Definition at line 464 of file bestfirst.cpp.

References HEAPENTRY::Data, HeapStore(), HEAPENTRY::Key, MaxSizeOfHeap, new_state(), num_pushed, and SizeOfHeap.

Referenced by expand_node().

                                                             { 
  HEAPENTRY entry;

  if (SizeOfHeap (queue) < MaxSizeOfHeap (queue) && priority < worst_state) {
    entry.Data = (char *) new_state (state);
    num_pushed++;
    entry.Key = priority;
    HeapStore(queue, &entry); 
  }
}

CHOICES_LIST rebuild_current_state	(	TBLOB *	blobs,
		SEAMS	seam_list,
		STATE *	state,
		CHOICES_LIST	old_choices,
		int	fx
	)

Evaluate the segmentation that is represented by this state in the best first search & add this state to the "states_seen" list.

Definition at line 296 of file bestfirst.cpp.

References array_count, array_push(), array_value, bin_to_chunks(), classify_blob(), count_blobs(), free_all_choices, join_pieces(), memfree(), new_choice_list, blobstruct::next, NULL, num_joints, oldblob(), and Orange.

Referenced by chop_word_main().

                                           {
  CHOICES_LIST char_choices;
  SEARCH_STATE search_state;
  int i;
  int num_joints = array_count (seam_list);
  int x = 0;
  int blobindex;                 /*current blob */
  TBLOB *p_blob;
  TBLOB *blob;
  TBLOB *next_blob;
  int y;

  search_state = bin_to_chunks (state, num_joints);

  char_choices = new_choice_list ();
  /* Iterate sub-paths */
  for (i = 1; i <= search_state[0]; i++) {
    y = x + search_state[i];
    x = y + 1;
    char_choices = array_push (char_choices, NULL);
  }
  char_choices = array_push (char_choices, NULL);

  y = count_blobs (blobs) - 1;
  for (i = search_state[0]; i >= 0; i--) {
    if (x == y) {                /*single fragment */
      array_value (char_choices, i) = array_value (old_choices, x);
                                 /*grab the list */
      array_value (old_choices, x) = NULL;
    }
    else {
      join_pieces(blobs, seam_list, x, y); 
      for (blob = blobs, blobindex = 0, p_blob = NULL; blobindex < x;
      blobindex++) {
        p_blob = blob;
        blob = blob->next;
      }
      while (blobindex < y) {
        next_blob = blob->next;
        blob->next = next_blob->next;
        oldblob(next_blob);  /*junk dead blobs */
        blobindex++;
      }
      array_value (char_choices, i) =
        (char *) classify_blob (p_blob, blob, blob->next, NULL, fx,
        "rebuild", Orange, NULL, NULL, 0, 0);
    }

    y = x - 1;
    x = y - search_state[i];
  }

  memfree(search_state); 
  free_all_choices(old_choices, x); 
  return (char_choices);

}

void replace_char_widths	(	CHUNKS_RECORD *	chunks_record,
		SEARCH_STATE	state
	)

Replace the value of the char_width field in the chunks_record with the updated width measurements from the last_segmentation.

Definition at line 481 of file bestfirst.cpp.

References CHUNKS_RECORD::char_widths, free_widths, last_segmentation, memalloc(), WIDTH_RECORD::num_chars, and WIDTH_RECORD::widths.

Referenced by evaluate_state().

                                                                           { 
  WIDTH_RECORD *width_record;
  int num_blobs;
  int i;

  free_widths (chunks_record->char_widths);

  num_blobs = state[0] + 1;
  width_record = (WIDTH_RECORD *) memalloc (sizeof (int) * num_blobs * 2);
  width_record->num_chars = num_blobs;

  for (i = 0; i < num_blobs; i++) {

    width_record->widths[2 * i] = last_segmentation[i].width;

    if (i + 1 < num_blobs)
      width_record->widths[2 * i + 1] = last_segmentation[i].gap;
  }
  chunks_record->char_widths = width_record;
}

---

Variable Documentation

int num_popped

Definition at line 47 of file bestfirst.cpp.

Referenced by best_first_search(), and write_cooked_text().

int num_seg_states

Referenced by best_first_search(), init_metrics(), new_search(), program_editup2(), record_search_status(), set_pass1(), and set_pass2().

---