dict/stopper.cpp

Go to the documentation of this file.

/* =================
 Include Files and Type Defines
 ==================== */
#include "stopper.h"
#include "emalloc.h"
#include "matchdefs.h"
#include "debug.h"
#include "callcpp.h"
#include "permute.h"
#include "context.h"
#include "permnum.h"
#include "danerror.h"
#include "const.h"
#include "freelist.h"
#include "efio.h"
#include "globals.h"
#include "scanutils.h"

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#ifdef __UNIX__
#include <assert.h>
#endif

/* these are kludges - add appropriate .h file later */
extern float CertaintyScale;     /* from subfeat.h */

#define MAX_WERD_SIZE   100
#define MAX_AMBIG_SIZE    3

#define DANGEROUS_AMBIGS  "tessdata/DangAmbigs"

typedef LIST AMBIG_TABLE;

typedef struct
{
  UINT8 Class;
  UINT16 NumChunks;
  float Certainty;
} CHAR_CHOICE;

typedef struct
{
  float Rating;
  float Certainty;
  FLOAT32 AdjustFactor;
  int Length;
  CHAR_CHOICE Blob[1];
} VIABLE_CHOICE_STRUCT;

typedef VIABLE_CHOICE_STRUCT *VIABLE_CHOICE;

typedef struct
{
  VIABLE_CHOICE Choice;
  float ChunkCertainty[MAX_NUM_CHUNKS];
  UINT8 ChunkClass[MAX_NUM_CHUNKS];
} EXPANDED_CHOICE;

/* =================
          Macros
 ==================== */
#define BestCertainty(Choices)  (((VIABLE_CHOICE) first (Choices))->Certainty)
#define BestRating(Choices) (((VIABLE_CHOICE) first (Choices))->Rating)
#define BestFactor(Choices) (((VIABLE_CHOICE) first (Choices))->AdjustFactor)

#define AmbigThreshold(F1,F2) (((F2) - (F1)) * AmbigThresholdGain - \
            AmbigThresholdOffset)

/*---------------------------------------------------------------------------
          Private Function Prototoypes
----------------------------------------------------------------------------*/
void AddNewChunk(VIABLE_CHOICE Choice, int Blob);

int AmbigsFound(char *Word,
                char *CurrentChar,
                const char *Tail,
                LIST Ambigs,
                DANGERR *fixpt);

int ChoiceSameAs(A_CHOICE *Choice, VIABLE_CHOICE ViableChoice);

int CmpChoiceRatings(void *arg1,   //VIABLE_CHOICE         Choice1,
                     void *arg2);  //VIABLE_CHOICE         Choice2);

void ExpandChoice(VIABLE_CHOICE Choice, EXPANDED_CHOICE *ExpandedChoice);

AMBIG_TABLE *FillAmbigTable();

int FreeBadChoice(void *item1,   //VIABLE_CHOICE                 Choice,
                  void *item2);  //EXPANDED_CHOICE                       *BestChoice);

int LengthOfShortestAlphaRun(register char *Word);

VIABLE_CHOICE NewViableChoice (A_CHOICE * Choice,
FLOAT32 AdjustFactor, float Certainties[]);

void PrintViableChoice(FILE *File, const char *Label, VIABLE_CHOICE Choice);

void ReplaceDuplicateChoice (VIABLE_CHOICE OldChoice,
A_CHOICE * NewChoice,
FLOAT32 AdjustFactor, float Certainties[]);

int StringSameAs(const char *String, VIABLE_CHOICE ViableChoice);

int UniformCertainties(CHOICES_LIST Choices, A_CHOICE *BestChoice);

/* =================
        Global Data Definitions and Declarations
 ==================== */
static const char *DangerousAmbigs = DANGEROUS_AMBIGS;

static char *WordToDebug = NULL;

BOOL8 KeepWordChoices = TRUE;

static FLOAT32 RejectOffset = 0.0;

static VIABLE_CHOICE BestRawChoice = NULL;
static LIST BestChoices = NIL;
static PIECES_STATE CurrentSegmentation;

make_float_var (NonDictCertainty, -2.50, MakeNonDictCertainty,
17, 2, SetNonDictCertainty,
"Certainty threshold for non-dict words");

make_float_var (RejectCertaintyOffset, 1.0, MakeRejectCertaintyOffset,
17, 3, SetRejectCertaintyOffset, "Reject certainty offset");

make_int_var (SmallWordSize, 2, MakeSmallWordSize,
17, 4, SetSmallWordSize,
"Size of dict word to be treated as non-dict word");

make_float_var (CertaintyPerChar, -0.50, MakeCertaintyPerChar,
17, 5, SetCertaintyPerChar,
"Certainty to add for each dict char above SmallWordSize");

make_float_var (CertaintyVariation, 3.0, MakeCertaintyVariation,
17, 6, SetCertaintyVariation,
"Max certaintly variation allowed in a word (in sigma)");

make_int_var (StopperDebugLevel, 0, MakeStopperDebugLevel,
17, 7, SetStopperDebugLevel, "Stopper debug level");

make_float_var (AmbigThresholdGain, 8.0, MakeAmbigThresholdGain,
17, 8, SetAmbigThresholdGain,
"Gain factor for ambiguity threshold");

make_float_var (AmbigThresholdOffset, 1.5, MakeAmbigThresholdOffset,
17, 9, SetAmbigThresholdOffset,
"Certainty offset for ambiguity threshold");

//extern char *demodir;
extern int first_pass;
INT_VAR (tessedit_truncate_wordchoice_log, 10, "Max words to keep in list");
/* =================
              Public Code
 ==================== */
/* =============================== */
int AcceptableChoice(CHOICES_LIST Choices,
                     A_CHOICE *BestChoice,
                     A_CHOICE *RawChoice,
                     DANGERR *fixpt) {
  float CertaintyThreshold = NonDictCertainty;
  int WordSize;

  if (fixpt != NULL)
    fixpt->index = -1;
  if ((BestChoice == NULL) || (class_string (BestChoice) == NULL))
    return (FALSE);

  if (StopperDebugLevel >= 1)
    cprintf ("\nStopper:  %s (word=%c, case=%c, punct=%c)\n",
      class_string (BestChoice),
      (valid_word (class_string (BestChoice)) ? 'y' : 'n'),
    (case_ok (class_string (BestChoice)) ? 'y' : 'n'),
    ((punctuation_ok (class_string (BestChoice)) !=
    -1) ? 'y' : 'n'));

  if (valid_word (class_string (BestChoice)) &&
    case_ok (class_string (BestChoice)) &&
  punctuation_ok (class_string (BestChoice)) != -1) {
    WordSize = LengthOfShortestAlphaRun (class_string (BestChoice));
    WordSize -= SmallWordSize;
    if (WordSize < 0)
      WordSize = 0;
    CertaintyThreshold += WordSize * CertaintyPerChar;
  }
  else if (stopper_numbers_on && valid_number (class_string (BestChoice))) {
    CertaintyThreshold += stopper_numbers_on * CertaintyPerChar;
  }

  if (StopperDebugLevel >= 1)
    cprintf ("Stopper:  Certainty = %4.1f, Threshold = %4.1f\n",
      class_certainty (BestChoice), CertaintyThreshold);

  if (NoDangerousAmbig (class_string (BestChoice), fixpt)
    && class_certainty (BestChoice) > CertaintyThreshold &&
    UniformCertainties (Choices, BestChoice))
    return (TRUE);
  else
    return (FALSE);

}                                /* AcceptableChoice */


/* =============================== */
int AcceptableResult(A_CHOICE *BestChoice, A_CHOICE *RawChoice) { 
  float CertaintyThreshold = NonDictCertainty - RejectOffset;
  int WordSize;

  if (StopperDebugLevel >= 1)
    cprintf ("\nRejecter: %s (word=%c, case=%c, punct=%c, unambig=%c)\n",
      class_string (BestChoice),
      (valid_word (class_string (BestChoice)) ? 'y' : 'n'),
    (case_ok (class_string (BestChoice)) ? 'y' : 'n'),
    ((punctuation_ok (class_string (BestChoice)) != -1) ? 'y' : 'n'),
    ((rest (BestChoices) != NIL) ? 'n' : 'y'));

  if ((BestChoice == NULL) ||
    (class_string (BestChoice) == NULL) || CurrentWordAmbig ())
    return (FALSE);

  if (valid_word (class_string (BestChoice)) &&
    case_ok (class_string (BestChoice)) &&
  punctuation_ok (class_string (BestChoice)) != -1) {
    WordSize = LengthOfShortestAlphaRun (class_string (BestChoice));
    WordSize -= SmallWordSize;
    if (WordSize < 0)
      WordSize = 0;
    CertaintyThreshold += WordSize * CertaintyPerChar;
  }

  if (StopperDebugLevel >= 1)
    cprintf ("Rejecter: Certainty = %4.1f, Threshold = %4.1f   ",
      class_certainty (BestChoice), CertaintyThreshold);

  if (class_certainty (BestChoice) > CertaintyThreshold) {
    if (StopperDebugLevel >= 1)
      cprintf ("ACCEPTED\n");
    return (TRUE);
  }
  else {
    if (StopperDebugLevel >= 1)
      cprintf ("REJECTED\n");
    return (FALSE);
  }
}                                /* AcceptableResult */


/* =============================== */
int AlternativeChoicesWorseThan(FLOAT32 Threshold) { 
  LIST Alternatives;
  VIABLE_CHOICE Choice;

  Alternatives = rest (BestChoices);
  iterate(Alternatives) {
    Choice = (VIABLE_CHOICE) first (Alternatives);
    if (Choice->AdjustFactor <= Threshold)
      return (FALSE);
  }

  return (TRUE);

}                                /* AlternativeChoicesWorseThan */


/* =============================== */
int CurrentBestChoiceIs(const char *Word) { 
  return (BestChoices != NIL &&
    StringSameAs (Word, (VIABLE_CHOICE) first (BestChoices)));

}                                /* CurrentBestChoiceIs */


/* =============================== */
FLOAT32 CurrentBestChoiceAdjustFactor() { 
  VIABLE_CHOICE BestChoice;

  if (BestChoices == NIL)
    return (MAX_FLOAT32);

  BestChoice = (VIABLE_CHOICE) first (BestChoices);
  return (BestChoice->AdjustFactor);

}                                /* CurrentBestChoiceAdjustFactor */


/* =============================== */
int CurrentWordAmbig() { 
  return (rest (BestChoices) != NIL);

}                                /* CurrentWordAmbig */


/* =============================== */
void DebugWordChoices() { 
  LIST Choices;
  int i;
  char LabelString[80];

  if (StopperDebugLevel >= 1 ||
    WordToDebug && BestChoices &&
  StringSameAs (WordToDebug, (VIABLE_CHOICE) first (BestChoices))) {
    if (BestRawChoice)
      PrintViableChoice (stdout, "\nBest Raw Choice:   ", BestRawChoice);

    i = 1;
    Choices = BestChoices;
    if (Choices)
      cprintf ("\nBest Cooked Choices:\n");
    iterate(Choices) {
      sprintf (LabelString, "Cooked Choice #%d:  ", i);
      PrintViableChoice (stdout, LabelString,
        (VIABLE_CHOICE) first (Choices));
      i++;
    }
  }
}                                /* DebugWordChoices */


/* =============================== */
void FilterWordChoices() { 
  EXPANDED_CHOICE BestChoice;

  if (BestChoices == NIL || second (BestChoices) == NIL)
    return;

  /* compute certainties and class for each chunk in best choice */
  ExpandChoice ((VIABLE_CHOICE_STRUCT *) first (BestChoices), &BestChoice);

  set_rest (BestChoices, delete_d (rest (BestChoices),
    &BestChoice, FreeBadChoice));

}                                /* FilterWordChoices */


/* =============================== */
void
FindClassifierErrors (FLOAT32 MinRating,
FLOAT32 MaxRating,
FLOAT32 RatingMargin, FLOAT32 Thresholds[]) {
  EXPANDED_CHOICE BestRaw;
  VIABLE_CHOICE Choice;
  int i, j, Chunk;
  FLOAT32 AvgRating;
  int NumErrorChunks;

  assert (BestChoices != NIL);
  assert (BestRawChoice != NULL);

  ExpandChoice(BestRawChoice, &BestRaw);
  Choice = (VIABLE_CHOICE) first (BestChoices);

  for (i = 0, Chunk = 0; i < Choice->Length; i++, Thresholds++) {
    AvgRating = 0.0;
    NumErrorChunks = 0;

    for (j = 0; j < Choice->Blob[i].NumChunks; j++, Chunk++)
    if (Choice->Blob[i].Class != BestRaw.ChunkClass[Chunk]) {
      AvgRating += BestRaw.ChunkCertainty[Chunk];
      NumErrorChunks++;
    }

    if (NumErrorChunks > 0) {
      AvgRating /= NumErrorChunks;
      *Thresholds = (AvgRating / -CertaintyScale) * (1.0 - RatingMargin);
    }
    else
      *Thresholds = MaxRating;

    if (*Thresholds > MaxRating)
      *Thresholds = MaxRating;
    if (*Thresholds < MinRating)
      *Thresholds = MinRating;
  }
}                                /* FindClassifierErrors */


/* =============================== */
void InitStopperVars() { 
  VALUE dummy;

  string_variable (DangerousAmbigs, "DangerousAmbigs", DANGEROUS_AMBIGS);
  string_variable (WordToDebug, "WordToDebug", "");

  MakeNonDictCertainty();
  MakeRejectCertaintyOffset();
  MakeSmallWordSize();
  MakeCertaintyPerChar();
  MakeCertaintyVariation();
  MakeStopperDebugLevel();
  MakeAmbigThresholdGain();
  MakeAmbigThresholdOffset();
}                                /* InitStopperVars */


/* =============================== */
void InitChoiceAccum() { 
  BLOB_WIDTH *BlobWidth, *End;

  if (BestRawChoice)
    memfree(BestRawChoice);

  if (BestChoices)
    destroy_nodes(BestChoices, memfree);

  BestRawChoice = NULL;
  BestChoices = NIL;
  EnableChoiceAccum();

  for (BlobWidth = CurrentSegmentation,
    End = CurrentSegmentation + MAX_NUM_CHUNKS;
    BlobWidth < End; *BlobWidth++ = 1);

}                                /* InitChoiceAccum */


/* =============================== */
void
LogNewRawChoice (A_CHOICE * Choice, FLOAT32 AdjustFactor, float Certainties[]) {
  if (!KeepWordChoices)
    return;

  if (!BestRawChoice)
    BestRawChoice = NewViableChoice (Choice, AdjustFactor, Certainties);
  else if (class_probability (Choice) < BestRawChoice->Rating) {
    if (ChoiceSameAs (Choice, BestRawChoice))
      ReplaceDuplicateChoice(BestRawChoice, Choice, AdjustFactor, Certainties);
    else {
      memfree(BestRawChoice);
      BestRawChoice = NewViableChoice (Choice, AdjustFactor, Certainties);
    }
  }
}                                /* LogNewRawChoice */

/* =============================== */
void LogNewSegmentation(PIECES_STATE BlobWidth) { 
  BLOB_WIDTH *Segmentation;

  for (Segmentation = CurrentSegmentation; *BlobWidth != 0;
    BlobWidth++, Segmentation++)
  *Segmentation = *BlobWidth;
  *Segmentation = 0;

}                                /* LogNewSegmentation */


/* =============================== */
void LogNewSplit(int Blob) { 
  LIST Choices;

  if (BestRawChoice) {
    AddNewChunk(BestRawChoice, Blob);
  }

  Choices = BestChoices;
  iterate(Choices) {
    AddNewChunk ((VIABLE_CHOICE) first (Choices), Blob);
  }

}                                /* LogNewSplit */


/* =============================== */
void
LogNewWordChoice (A_CHOICE * Choice,
FLOAT32 AdjustFactor, float Certainties[]) {
  VIABLE_CHOICE NewChoice;
  LIST Choices;
  FLOAT32 Threshold;

  if (!KeepWordChoices)
    return;

  /* throw out obviously bad choices to save some work */
  if (BestChoices != NIL) {
    Threshold = AmbigThreshold (BestFactor (BestChoices), AdjustFactor);
    if (Threshold > -AmbigThresholdOffset)
      Threshold = -AmbigThresholdOffset;
    if (class_certainty (Choice) - BestCertainty (BestChoices) < Threshold)
      return;
  }

  /* see if a choice with the same text string has already been found */
  NewChoice = NULL;
  Choices = BestChoices;
  iterate(Choices) {
    if (ChoiceSameAs (Choice, (VIABLE_CHOICE) first (Choices)))
      if (class_probability (Choice) < BestRating (Choices))
        NewChoice = (VIABLE_CHOICE) first (Choices);
    else
      return;
  }

  if (NewChoice) {
    ReplaceDuplicateChoice(NewChoice, Choice, AdjustFactor, Certainties);
    BestChoices = delete_d (BestChoices, NewChoice, is_same_node);
  }
  else {
    NewChoice = NewViableChoice (Choice, AdjustFactor, Certainties);
  }

  BestChoices = s_adjoin (BestChoices, NewChoice, CmpChoiceRatings);
  if (StopperDebugLevel >= 2)
    PrintViableChoice (stdout, "New Word Choice:  ", NewChoice);
  if (count (BestChoices) > tessedit_truncate_wordchoice_log) {
    Choices =
      (LIST) nth_cell (BestChoices, tessedit_truncate_wordchoice_log);
    destroy_nodes (rest (Choices), Efree);
    set_rest(Choices, NIL);
  }

}                                /* LogNewWordChoice */


/* =============================== */
static AMBIG_TABLE *AmbigFor = NULL;

int NoDangerousAmbig(const char *Word, DANGERR *fixpt) {

  char NewWord[MAX_WERD_SIZE];
  char *NextNewChar;
  int bad_index = 0;

  if (!AmbigFor)
    AmbigFor = FillAmbigTable ();

  NextNewChar = NewWord;
  while (*Word)
  if (AmbigsFound (NewWord, NextNewChar, Word + 1, AmbigFor[*Word], fixpt)) {
    if (fixpt != NULL)
      fixpt->index = bad_index;
    return (FALSE);
  }
  else {
    *NextNewChar++ = *Word++;
    bad_index++;
  }

  return (TRUE);

}                                /* NoDangerousAmbig */

void EndDangerousAmbigs() {
  if (AmbigFor != NULL) {
    for (int i = 0; i <= MAX_CLASS_ID; ++i) {
      destroy_nodes(AmbigFor[i], Efree);
    }
    Efree(AmbigFor);
    AmbigFor = NULL;
  }
}

/* =============================== */
void SettupStopperPass1() { 
  RejectOffset = 0.0;
}                                /* SettupStopperPass1 */


/* =============================== */
void SettupStopperPass2() { 
  RejectOffset = RejectCertaintyOffset;
}                                /* SettupStopperPass2 */


/* =================
              Private Code
 ==================== */
/* =============================== */
void AddNewChunk(VIABLE_CHOICE Choice, int Blob) { 
  int i, LastChunk;

  for (i = 0, LastChunk = 0; i < Choice->Length; i++) {
    LastChunk += Choice->Blob[i].NumChunks;
    if (Blob < LastChunk) {
      (Choice->Blob[i].NumChunks)++;
      return;
    }
  }
  mem_tidy (1);
  cprintf ("AddNewChunk failed:Choice->Length=%d, LastChunk=%d, Blob=%d\n",
    Choice->Length, LastChunk, Blob);
  assert(FALSE);  /* this should never get executed */

}                                /* AddNewChunk */


/* =============================== */
int AmbigsFound(char *Word,
                char *CurrentChar,
                const char *Tail,
                LIST Ambigs,
                DANGERR *fixpt) {
  char *AmbigSpec;
  const char *UnmatchedTail;
  int Matches;
  int bad_length;

  iterate(Ambigs) {
    AmbigSpec = (char *) first (Ambigs);
    bad_length = 1;
    UnmatchedTail = Tail;
    Matches = TRUE;

    while (*AmbigSpec != ' ' && Matches)
    if (*AmbigSpec == *UnmatchedTail) {
      AmbigSpec++;
      UnmatchedTail++;
      bad_length++;
    }
    else
      Matches = FALSE;

    if (Matches) {
      AmbigSpec++;               /* skip over the space */
                                 /* insert replacement string */
      strcpy(CurrentChar, AmbigSpec);
                                 /* add tail */
      strcat(Word, UnmatchedTail);
      if (valid_word (Word)) {
        if (StopperDebugLevel >= 1)
          cprintf ("Stopper:  Possible ambiguous word = %s\n", Word);
        if (fixpt != NULL) {
          fixpt->good_length = strlen (AmbigSpec);
          fixpt->bad_length = bad_length;
        }
        return (TRUE);
      }
    }
  }
  return (FALSE);

}                                /* AmbigsFound */


/* =============================== */
int ChoiceSameAs(A_CHOICE *Choice, VIABLE_CHOICE ViableChoice) { 
  return (StringSameAs (class_string (Choice), ViableChoice));

}                                /* ChoiceSameAs */


/* =============================== */
int CmpChoiceRatings(void *arg1,
                     void *arg2) {
  float R1, R2;
  VIABLE_CHOICE Choice1 = (VIABLE_CHOICE) arg1;
  VIABLE_CHOICE Choice2 = (VIABLE_CHOICE) arg2;

  R1 = Choice1->Rating;
  R2 = Choice2->Rating;

  if (R1 < R2)
    return (-1);
  else
    return (1);

}                                /* CmpChoiceRatings */


/* =============================== */
void ExpandChoice(VIABLE_CHOICE Choice, EXPANDED_CHOICE *ExpandedChoice) { 
  int i, j, Chunk;

  ExpandedChoice->Choice = Choice;
  for (i = 0, Chunk = 0; i < Choice->Length; i++)
  for (j = 0; j < Choice->Blob[i].NumChunks; j++, Chunk++) {
    ExpandedChoice->ChunkCertainty[Chunk] = Choice->Blob[i].Certainty;
    ExpandedChoice->ChunkClass[Chunk] = Choice->Blob[i].Class;
  }
}                                /* ExpandChoice */


/* =============================== */
AMBIG_TABLE *FillAmbigTable() { 
  FILE *AmbigFile;
  AMBIG_TABLE *NewTable;
  int i;
  char TestString[256];
  char ReplacementString[256];
  char name[1024];
  char *AmbigSpec;
  int AmbigSize;

  strcpy(name, demodir);
  strcat(name, DangerousAmbigs);
  AmbigFile = Efopen (name, "r");
  NewTable = (AMBIG_TABLE *) Emalloc (sizeof (LIST) * (MAX_CLASS_ID + 1));

  for (i = 0; i <= MAX_CLASS_ID; i++)
    NewTable[i] = NIL;

  while (fscanf (AmbigFile, "%s", TestString) == 1 &&
  fscanf (AmbigFile, "%s", ReplacementString) == 1) {
    if (strlen (TestString) > MAX_AMBIG_SIZE ||
      strlen (ReplacementString) > MAX_AMBIG_SIZE)
      DoError (0, "Illegal ambiguity specification!");

    AmbigSize = strlen (TestString) + strlen (ReplacementString) + 1;
    AmbigSpec = (char *) Emalloc (sizeof (char) * AmbigSize);

    strcpy (AmbigSpec, &(TestString[1]));
    strcat (AmbigSpec, " ");
    strcat(AmbigSpec, ReplacementString);
    NewTable[TestString[0]] =
      push_last (NewTable[TestString[0]], AmbigSpec);
  }
  fclose(AmbigFile);
  return (NewTable);

}                                /* FillAmbigTable */


/* =============================== */
int FreeBadChoice(void *item1,    //VIABLE_CHOICE       Choice,
                  void *item2) {  //EXPANDED_CHOICE     *BestChoice)
  int i, j, Chunk;
  FLOAT32 Threshold;
  VIABLE_CHOICE Choice;
  EXPANDED_CHOICE *BestChoice;

  Choice = (VIABLE_CHOICE) item1;
  BestChoice = (EXPANDED_CHOICE *) item2;

  Threshold = AmbigThreshold (BestChoice->Choice->AdjustFactor,
    Choice->AdjustFactor);

  for (i = 0, Chunk = 0; i < Choice->Length; i++)
    for (j = 0; j < Choice->Blob[i].NumChunks; j++, Chunk++)
      if (Choice->Blob[i].Class != BestChoice->ChunkClass[Chunk] &&
    Choice->Blob[i].Certainty - BestChoice->ChunkCertainty[Chunk] <
      Threshold) {
        memfree(Choice);
    return (TRUE);
  }

  return (FALSE);

}                                /* FreeBadChoice */


/* =============================== */
int LengthOfShortestAlphaRun(register char *Word) { 
  register int Shortest = MAXINT;
  register int Length;

  for (; *Word; Word++)
  if (isalpha (*Word)) {
    for (Length = 1, Word++; isalpha (*Word); Word++, Length++);
    if (Length < Shortest)
      Shortest = Length;

    if (*Word == 0)
      break;
  }
  if (Shortest == MAXINT)
    Shortest = 0;

  return (Shortest);

}                                /* LengthOfShortestAlphaRun */


/* =============================== */
VIABLE_CHOICE
NewViableChoice (A_CHOICE * Choice, FLOAT32 AdjustFactor, float Certainties[]) {
  VIABLE_CHOICE NewChoice;
  int Length;
  char *Word;
  CHAR_CHOICE *NewChar;
  BLOB_WIDTH *BlobWidth;

  Length = strlen (class_string (Choice));
  assert (Length <= MAX_NUM_CHUNKS && Length > 0);

  NewChoice = (VIABLE_CHOICE) Emalloc (sizeof (VIABLE_CHOICE_STRUCT) +
    (Length - 1) * sizeof (CHAR_CHOICE));

  NewChoice->Rating = class_probability (Choice);
  NewChoice->Certainty = class_certainty (Choice);
  NewChoice->AdjustFactor = AdjustFactor;
  NewChoice->Length = Length;

  for (Word = class_string (Choice),
    NewChar = &(NewChoice->Blob[0]),
    BlobWidth = CurrentSegmentation;
  *Word; Word++, NewChar++, Certainties++, BlobWidth++) {
    NewChar->Class = *Word;
    NewChar->NumChunks = *BlobWidth;
    NewChar->Certainty = *Certainties;
  }

  return (NewChoice);

}                                /* NewViableChoice */


/* =============================== */
void PrintViableChoice(FILE *File, const char *Label, VIABLE_CHOICE Choice) { 
  int i, j;

  fprintf (File, "%s", Label);

  fprintf (File, "(R=%5.1f, C=%4.1f, F=%4.2f)  ",
    Choice->Rating, Choice->Certainty, Choice->AdjustFactor);

  for (i = 0; i < Choice->Length; i++)
    fprintf (File, "%c", Choice->Blob[i].Class);
  fprintf (File, "\n");

  for (i = 0; i < Choice->Length; i++) {
    fprintf (File, "  %c", Choice->Blob[i].Class);
    for (j = 0; j < Choice->Blob[i].NumChunks - 1; j++)
      fprintf (File, "   ");
  }
  fprintf (File, "\n");

  for (i = 0; i < Choice->Length; i++) {
    for (j = 0; j < Choice->Blob[i].NumChunks; j++)
      fprintf (File, "%3d", (int) (Choice->Blob[i].Certainty * -10.0));
  }
  fprintf (File, "\n");

}                                /* PrintViableChoice */


/* =============================== */
void
ReplaceDuplicateChoice (VIABLE_CHOICE OldChoice,
A_CHOICE * NewChoice,
FLOAT32 AdjustFactor, float Certainties[]) {
  char *Word;
  CHAR_CHOICE *NewChar;
  BLOB_WIDTH *BlobWidth;

  OldChoice->Rating = class_probability (NewChoice);
  OldChoice->Certainty = class_certainty (NewChoice);
  OldChoice->AdjustFactor = AdjustFactor;

  for (Word = class_string (NewChoice),
    NewChar = &(OldChoice->Blob[0]),
    BlobWidth = CurrentSegmentation;
  *Word; Word++, NewChar++, Certainties++, BlobWidth++) {
    NewChar->NumChunks = *BlobWidth;
    NewChar->Certainty = *Certainties;
  }
}                                /* ReplaceDuplicateChoice */


/* =============================== */
int StringSameAs(const char *String, VIABLE_CHOICE ViableChoice) { 
  CHAR_CHOICE *Char;
  int i;

  for (Char = &(ViableChoice->Blob[0]), i = 0;
    i < ViableChoice->Length; String++, Char++, i++)
  if (*String != Char->Class)
    return (FALSE);

  if (*String == 0)
    return (TRUE);
  else
    return (FALSE);

}                                /* StringSameAs */


/* =============================== */
int UniformCertainties(CHOICES_LIST Choices, A_CHOICE *BestChoice) { 
  int i;
  CHOICES CharChoices;
  float Certainty;
  float WorstCertainty = MAX_FLOAT32;
  float CertaintyThreshold;
  FLOAT64 TotalCertainty;
  FLOAT64 TotalCertaintySquared;
  FLOAT64 Variance;
  FLOAT32 Mean, StdDev;
  int WordLength;

  WordLength = array_count (Choices);
  if (WordLength < 3)
    return (TRUE);

  TotalCertainty = TotalCertaintySquared = 0.0;
  for_each_choice(Choices, i) {
    CharChoices = (CHOICES) array_index (Choices, i);
    Certainty = best_certainty (CharChoices);
    TotalCertainty += Certainty;
    TotalCertaintySquared += Certainty * Certainty;
    if (Certainty < WorstCertainty)
      WorstCertainty = Certainty;
  }

  /* subtract off worst certainty from statistics */
  WordLength--;
  TotalCertainty -= WorstCertainty;
  TotalCertaintySquared -= WorstCertainty * WorstCertainty;

  Mean = TotalCertainty / WordLength;
  Variance = ((WordLength * TotalCertaintySquared -
    TotalCertainty * TotalCertainty) /
    (WordLength * (WordLength - 1)));
  if (Variance < 0.0)
    Variance = 0.0;
  StdDev = sqrt (Variance);

  CertaintyThreshold = Mean - CertaintyVariation * StdDev;
  if (CertaintyThreshold > NonDictCertainty)
    CertaintyThreshold = NonDictCertainty;

  if (class_certainty (BestChoice) < CertaintyThreshold) {
    if (StopperDebugLevel >= 1)
      cprintf
        ("Stopper:  Non-uniform certainty = %4.1f (m=%4.1f, s=%4.1f, t=%4.1f)\n",
        class_certainty (BestChoice), Mean, StdDev, CertaintyThreshold);
    return (FALSE);
  }
  else
    return (TRUE);

}                                /* UniformCertainties */

---