/* -*-C-*-
********************************************************************************
*
* File: permute.c (Formerly permute.c)
* Description: Choose OCR text given character-probability maps
* for sequences of glyph fragments and a dictionary provided as
* a Dual Acyclic Word Graph.
* In this file, "permute" should be read "combine."
* Author: Mark Seaman, OCR Technology
* Created: Fri Sep 22 14:05:51 1989
* Modified: Thu Jan 3 16:38:46 1991 (Mark Seaman) marks@hpgrlt
* Language: C
* Package: N/A
* Status: Experimental (Do Not Distribute)
*
* (c) Copyright 1989, Hewlett-Packard Company.
** Licensed under the Apache License, Version 2.0 (the "License");
** you may not use this file except in compliance with the License.
** You may obtain a copy of the License at
** http://www.apache.org/licenses/LICENSE-2.0
** Unless required by applicable law or agreed to in writing, software
** distributed under the License is distributed on an "AS IS" BASIS,
** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
** See the License for the specific language governing permissions and
** limitations under the License.
*
*********************************************************************************/
/*----------------------------------------------------------------------
I n c l u d e s
---------------------------------------------------------------------*/
#include <assert.h>
#include <math.h>
#include "const.h"
#include "permute.h"
#include "callcpp.h"
#include "context.h"
#include "conversion.h"
#include "freelist.h"
#include "globals.h"
#include "ndminx.h"
#include "permdawg.h"
#include "permngram.h"
#include "ratngs.h"
#include "stopper.h"
#include "tordvars.h"
#include "tprintf.h"
#include "trie.h"
#include "varable.h"
#include "unicharset.h"
#include "dict.h"
#include "image.h"
#include "ccutil.h"
int permutation_count; // Used in metrics.cpp.
/*----------------------------------------------------------------------
V a r i a b l e s
----------------------------------------------------------------------*/
// TODO(tkielbus) Choose a value for the MAX_NUM_EDGES constant
// (or make it dynamic)
#define MAX_NUM_EDGES 2000000
#define MAX_DOC_EDGES 250000
#define MAX_USER_EDGES 50000
/* Weights for adjustment */
#define NON_WERD 1.25
#define GARBAGE_STRING 1.5
#define MAX_PERM_LENGTH 128
// debugging flags
INT_VAR(fragments_debug, 0, "Debug character fragments");
BOOL_VAR(segment_debug, 0, "Debug the whole segmentation process");
BOOL_VAR(permute_debug, 0, "Debug char permutation process");
// control parameters
double_VAR(bestrate_pruning_factor, 2.0,
"Multiplying factor of current best rate to prune other hypotheses");
BOOL_VAR(permute_script_word, 0,
"Turn on word script consistency permuter");
BOOL_VAR(segment_segcost_rating, 0,
"incorporate segmentation cost in word rating?");
double_VAR(segment_reward_script, 0.95,
"Score multipler for script consistency within a word. "
"Being a 'reward' factor, it should be <= 1. "
"Smaller value implies bigger reward.");
double_VAR(segment_penalty_dict_nonword, NON_WERD,
"Score multiplier for glyph fragment segmentations which do not "
"match a dictionary word (lower is better).");
double_VAR(segment_penalty_garbage, GARBAGE_STRING,
"Score multiplier for poorly cased strings that are not in the "
"dictionary and generally look like garbage (lower is better).");
BOOL_VAR(save_doc_words, 0, "Save Document Words");
BOOL_VAR(doc_dict_enable, 1, "Enable Document Dictionary ");
BOOL_VAR(ngram_permuter_activated, FALSE,
"Activate character-level n-gram-based permuter");
STRING_VAR(global_user_words_suffix, "", "A list of user-provided words.");
// This is an ugly way to incorporate segmentation cost in word rating.
// See comments in incorporate_segcost.
float wordseg_rating_adjust_factor;
int permute_only_top = 0;
#define SIM_CERTAINTY_SCALE -10.0 /* Similarity matcher values */
#define SIM_CERTAINTY_OFFSET -10.0 /* Similarity matcher values */
#define SIMILARITY_FLOOR 100.0 /* Worst E*L product to stop on */
// TODO(daria): If hyphens are different in different languages and can be
// inferred from training data we should load their values dynamically.
static const char kHyphenSymbol[] = "-";
/*----------------------------------------------------------------------
F u n c t i o n s
----------------------------------------------------------------------*/
/**********************************************************************
* get_best_delete_other
*
* Returns the best of two choices and deletes the other (worse) choice.
* A choice is better if it has a non-empty string and has a lower
* rating than the other choice. If the ratings are the same,
* choice2 is preferred over choice1.
**********************************************************************/
WERD_CHOICE *get_best_delete_other(WERD_CHOICE *choice1,
WERD_CHOICE *choice2) {
if (!choice1) return choice2;
if (!choice2) return choice1;
if (choice1->rating() < choice2->rating() || choice2->length() == 0) {
delete choice2;
return choice1;
} else {
delete choice1;
return choice2;
}
}
/**********************************************************************
* good_choice
*
* Return TRUE if a good answer is found for the unknown blob rating.
**********************************************************************/
int good_choice(const WERD_CHOICE &choice) {
register float certainty;
if (tord_similarity_enable) {
if ((choice.rating() + 1) * choice.certainty() > SIMILARITY_FLOOR)
return false;
certainty =
SIM_CERTAINTY_OFFSET + choice.rating() * SIM_CERTAINTY_SCALE;
} else {
certainty = choice.certainty();
}
return (certainty > tord_certainty_threshold) ? true : false;
}
/**********************************************************************
* add_document_word
*
* Add a word found on this document to the document specific
* dictionary.
**********************************************************************/
namespace tesseract {
void Dict::add_document_word(const WERD_CHOICE &best_choice) {
// Do not add hyphenated word parts to the document dawg.
// hyphen_word_ will be non-NULL after the set_hyphen_word() is
// called when the first part of the hyphenated word is
// discovered and while the second part of the word is recognized.
// hyphen_word_ is cleared in cc_recg() before the next word on
// the line is recognized.
if (hyphen_word_) return;
char filename[CHARS_PER_LINE];
FILE *doc_word_file;
int stringlen = best_choice.length();
if (!doc_dict_enable || valid_word(best_choice) ||
CurrentWordAmbig() || stringlen < 2)
return;
if (!good_choice(best_choice) || stringlen == 2) {
if (best_choice.certainty() < permuter_pending_threshold)
return;
if (!pending_words_->word_in_dawg(best_choice)) {
if (stringlen > 2 ||
(stringlen == 2 &&
getUnicharset().get_isupper(best_choice.unichar_id(0)) &&
getUnicharset().get_isupper(best_choice.unichar_id(1)))) {
pending_words_->add_word_to_dawg(best_choice);
}
return;
}
}
if (save_doc_words) {
strcpy(filename, getImage()->getCCUtil()->imagefile.string());
strcat (filename, ".doc");
doc_word_file = open_file (filename, "a");
fprintf (doc_word_file, "%s\n",
best_choice.debug_string(getUnicharset()).string());
fclose(doc_word_file);
}
document_words_->add_word_to_dawg(best_choice);
}
/**********************************************************************
* adjust_non_word
*
* Assign an adjusted value to a string that is a non-word. The value
* that this word choice has is based on case and punctuation rules.
* The adjustment value applied is stored in adjust_factor upon return.
**********************************************************************/
void Dict::adjust_non_word(WERD_CHOICE *word, float *adjust_factor) {
float new_rating;
if (permute_debug)
cprintf("Non-word: %s %4.2f ",
word->debug_string(getUnicharset()).string(), word->rating());
new_rating = word->rating() + RATING_PAD;
if (Context::case_ok(*word, getUnicharset()) && valid_punctuation(*word)) {
new_rating *= segment_penalty_dict_nonword;
*adjust_factor = segment_penalty_dict_nonword;
if (permute_debug) tprintf(", W");
} else {
new_rating *= segment_penalty_garbage;
*adjust_factor = segment_penalty_garbage;
if (permute_debug) {
if (!Context::case_ok(*word, getUnicharset())) tprintf(", C");
if (!valid_punctuation(*word)) tprintf(", P");
}
}
new_rating -= RATING_PAD;
word->set_rating(new_rating);
if (permute_debug)
cprintf (" %4.2f --> %4.2f\n", *adjust_factor, new_rating);
}
/**********************************************************************
* init_permute
*
* Initialize anything that needs to be set up for the permute
* functions.
**********************************************************************/
void Dict::init_permute() {
STRING name;
STRING &lang = getImage()->getCCUtil()->lang;
if (dawgs_.length() != 0) end_permute();
hyphen_unichar_id_ = getUnicharset().unichar_to_id(kHyphenSymbol);
TessdataManager &tessdata_manager =
getImage()->getCCUtil()->tessdata_manager;
// Load dawgs_.
if (global_load_punc_dawg &&
tessdata_manager.SeekToStart(TESSDATA_PUNC_DAWG)) {
dawgs_ += new SquishedDawg(tessdata_manager.GetDataFilePtr(),
DAWG_TYPE_PUNCTUATION, lang, PUNC_PERM);
}
if (global_load_system_dawg &&
tessdata_manager.SeekToStart(TESSDATA_SYSTEM_DAWG)) {
dawgs_ += new SquishedDawg(tessdata_manager.GetDataFilePtr(),
DAWG_TYPE_WORD, lang, SYSTEM_DAWG_PERM);
}
if (global_load_number_dawg &&
tessdata_manager.SeekToStart(TESSDATA_NUMBER_DAWG)) {
dawgs_ +=
new SquishedDawg(tessdata_manager.GetDataFilePtr(),
DAWG_TYPE_NUMBER, lang, NUMBER_PERM);
}
if (((STRING &)global_user_words_suffix).length() > 0) {
Trie *trie_ptr = new Trie(DAWG_TYPE_WORD, lang, USER_DAWG_PERM,
MAX_USER_EDGES, getUnicharset().size());
name = getImage()->getCCUtil()->language_data_path_prefix;
name += global_user_words_suffix;
if (!trie_ptr->read_word_list(name.string(), getUnicharset())) {
tprintf("Error: failed to load %s\n", name.string());
exit(1);
}
dawgs_ += trie_ptr;
}
document_words_ = new Trie(DAWG_TYPE_WORD, lang, DOC_DAWG_PERM,
MAX_DOC_EDGES, getUnicharset().size());
dawgs_ += document_words_;
// This dawg is temporary and should not be searched by letter_is_ok.
pending_words_ = new Trie(DAWG_TYPE_WORD, lang, NO_PERM,
MAX_DOC_EDGES, getUnicharset().size());
// The frequent words dawg is only searched when a word
// is found in any of the other dawgs.
if (tessdata_manager.SeekToStart(TESSDATA_FREQ_DAWG)) {
freq_dawg_ = new SquishedDawg(tessdata_manager.GetDataFilePtr(),
DAWG_TYPE_WORD, lang, FREQ_DAWG_PERM);
}
// Construct a list of corresponding successors for each dawg. Each entry i
// in the successors_ vector is a vector of integers that represent the
// indices into the dawgs_ vector of the successors for dawg i.
successors_.reserve(dawgs_.length());
for (int i = 0; i < dawgs_.length(); ++i) {
const Dawg *dawg = dawgs_[i];
SuccessorList *lst = new SuccessorList();
for (int j = 0; j < dawgs_.length(); ++j) {
const Dawg *other = dawgs_[j];
if (dawg->lang() == other->lang() &&
kDawgSuccessors[dawg->type()][other->type()]) *lst += j;
}
successors_ += lst;
}
}
void Dict::end_permute() {
if (dawgs_.length() == 0)
return; // Not safe to call twice.
dawgs_.delete_data_pointers();
successors_.delete_data_pointers();
dawgs_.clear();
successors_.clear();
document_words_ = NULL;
if (pending_words_ != NULL) delete pending_words_;
pending_words_ = NULL;
if (freq_dawg_ != NULL) delete freq_dawg_;
freq_dawg_ = NULL;
}
/**********************************************************************
* permute_all
*
* Permute all the characters together using all of the different types
* of permuters/selectors available. Each of the characters must have
* a non-NULL choice list.
*
* Note: order of applying permuters does matter, since the latter
* permuter will be recorded if the resulting word ratings are the same.
**********************************************************************/
WERD_CHOICE *Dict::permute_all(const BLOB_CHOICE_LIST_VECTOR &char_choices,
float rating_limit,
WERD_CHOICE *raw_choice) {
WERD_CHOICE *result1;
WERD_CHOICE *result2 = NULL;
BOOL8 any_alpha;
float top_choice_rating_limit = rating_limit;
// Initialize result1 from the result of permute_top_choice.
result1 = permute_top_choice(char_choices, &top_choice_rating_limit,
raw_choice, &any_alpha);
// Enforce script consistency within a word on some scripts
if (permute_script_word &&
!word_script_eq(char_choices, getUnicharset().common_sid()) &&
!word_script_eq(char_choices, getUnicharset().latin_sid())) {
result2 = permute_script_words(char_choices);
// TODO(dsl): incorporate segmentation cost into word rating.
// This should only be turned on for scripts that we have a segmentation
// cost model for, such as CJK.
if (segment_segcost_rating)
incorporate_segcost(result2);
result1 = get_best_delete_other(result1, result2);
}
// Permute character fragments if necessary.
if (result1 == NULL || result1->fragment_mark()) {
result2 = top_fragments_permute_and_select(char_choices,
top_choice_rating_limit);
result1 = get_best_delete_other(result1, result2);
}
// TODO(daria): update ngram permuter code.
if (ngram_permuter_activated) {
tprintf("Error: ngram permuter functionality is not available\n");
exit(1);
// A_CHOICE *ngram_choice =
// ngram_permute_and_select(old_char_choices, rating_limit, word_dawg_);
// return ngram_choice;
}
if (result1 == NULL)
return (NULL);
if (permute_only_top)
return result1;
result2 = dawg_permute_and_select(char_choices, rating_limit);
result1 = get_best_delete_other(result1, result2);
result2 = permute_compound_words(char_choices, rating_limit);
result1 = get_best_delete_other(result1, result2);
return (result1);
}
// Returns the top choice char id. A helper function to make code cleaner.
UNICHAR_ID get_top_choice_uid(BLOB_CHOICE_LIST *blob_list) {
BLOB_CHOICE_IT blob_choice_it;
blob_choice_it.set_to_list(blob_list);
return (blob_choice_it.data()) ? blob_choice_it.data()->unichar_id()
: INVALID_UNICHAR_ID;
}
// Return the "dominant" script ID for the word. By "dominant", the script
// must account for at least half the characters. Otherwise, it returns 0.
int get_top_word_script(const BLOB_CHOICE_LIST_VECTOR &char_choices,
const UNICHARSET &unicharset) {
int max_script = unicharset.get_script_table_size();
int *sid = new int[max_script];
int x;
for (x = 0; x < max_script; x++) sid[x] = 0;
for (x = 0; x < char_choices.length(); ++x) {
BLOB_CHOICE_IT blob_choice_it;
blob_choice_it.set_to_list(char_choices.get(x));
sid[blob_choice_it.data()->script_id()]++;
}
// Note that high script ID overrides lower one on a tie, thus biasing
// towards non-Common script (if sorted that way in unicharset file).
int max_sid = 0;
for (x = 1; x < max_script; x++)
if (sid[x] >= sid[max_sid]) max_sid = x;
if (sid[max_sid] < char_choices.length() / 2)
max_sid = unicharset.null_sid();
delete[] sid;
return max_sid;
}
/**********************************************************************
* Checks whether the dominant word script, if there is one, matches
* the given target script ID.
**********************************************************************/
bool Dict::word_script_eq(const BLOB_CHOICE_LIST_VECTOR &char_choices,
int target_sid) {
int max_sid = get_top_word_script(char_choices, getUnicharset());
// If "Latin" is not a loaded script, then latin_sid() would return 0.
// max_sid could also be 0 if there is no dominant script.
// This is faster than
// strcmp(getUnicharset().get_script_from_script_id(max_sid), "Latin")
return (max_sid > 0 && max_sid == target_sid);
}
/**********************************************************************
* Iterate through all the character choices (for a single blob) and
* return the first that matches the given type, which is one of 'aA0px*',
* for lower, upper, digit, punctuation, other, and 'any', respectively.
* If not match is found, a NULL is returned.
**********************************************************************/
BLOB_CHOICE* find_choice_by_type(
BLOB_CHOICE_LIST *char_choices,
char target_type,
const UNICHARSET &unicharset) {
BLOB_CHOICE_IT c_it;
c_it.set_to_list(char_choices);
for (c_it.mark_cycle_pt(); !c_it.cycled_list(); c_it.forward()) {
bool found = false;
UNICHAR_ID unichar_id = c_it.data()->unichar_id();
switch (target_type) {
case '*': found = true; break;
case 'A': found = unicharset.get_isupper(unichar_id); break;
case 'a': found = unicharset.get_islower(unichar_id); break;
case '0': found = unicharset.get_isdigit(unichar_id); break;
case 'p': found = unicharset.get_ispunctuation(unichar_id); break;
case 'x': found = !unicharset.get_isupper(unichar_id) &&
!unicharset.get_islower(unichar_id) &&
!unicharset.get_isdigit(unichar_id) &&
!unicharset.get_ispunctuation(unichar_id);
break;
}
if (found) return c_it.data();
}
return NULL;
}
/**********************************************************************
* Iterate through all the character choices (for a single blob) and
* return the first that matches the target script ID. If backup_sid
* is not 0, then a match on either the target or backup sid is allowed.
* Note that there is no preference between a target or backup sid.
* To search for another sid only if no target_sid matched, use
* secondary_sid.
* So for example, to find first Han or Common char choice, do
* find_choice_by_script(cchoice, han_sid, common_sid, 0);
* To find first Han choice, but allow Common if none is found, do
* find_choice_by_script(cchoice, han_sid, 0, common_sid);
**********************************************************************/
BLOB_CHOICE* find_choice_by_script(
BLOB_CHOICE_LIST *char_choices,
int target_sid,
int backup_sid,
int secondary_sid) {
BLOB_CHOICE_IT c_it;
c_it.set_to_list(char_choices);
for (c_it.mark_cycle_pt(); !c_it.cycled_list(); c_it.forward()) {
bool found = false;
if (c_it.data()->script_id() == 0) continue;
if (c_it.data()->script_id() == target_sid) found = true;
if (backup_sid > 0 && c_it.data()->script_id() == backup_sid) found = true;
if (found) return c_it.data();
}
if (secondary_sid > 0) {
c_it.set_to_list(char_choices);
for (c_it.mark_cycle_pt(); !c_it.cycled_list(); c_it.forward()) {
if (c_it.data()->script_id() == 0) continue;
if (c_it.data()->script_id() == secondary_sid)
return c_it.data();
}
}
return NULL;
}
/**********************************************************************
* Incorporate segmentation cost into the word rating. This is done
* through a mutliplier wordseg_rating_adjust_factor which is determined
* in bestfirst.cpp during state evaluation. This is not the cleanest
* way to do this. It would be better to reorganize the SEARCH_STATE
* to keep track of associated states, or do the rating adjustment
* outside the permuter in evalaute_state.
**********************************************************************/
void Dict::incorporate_segcost(WERD_CHOICE *word) {
if (!word || wordseg_rating_adjust_factor <= 0) return;
float old_rating = word->rating();
float new_rating = old_rating * wordseg_rating_adjust_factor;
word->set_rating(new_rating);
if (permute_debug)
tprintf("Permute segadjust %f * %f --> %f\n",
old_rating, wordseg_rating_adjust_factor, new_rating);
}
/**********************************************************************
* Try flipping characters in a word to get better script consistency.
* Similar to how upper/lower case checking is done in top_choice_permuter,
* this permuter tries to suggest a more script-consistent choice AND
* modifieds the rating. So it combines both the case_ok check and
* adjust_non_word functionality. However, instead of penalizing an
* inconsistent word with a > 1 multiplier, we reward the script-consistent
* choice with a < 1 multiplier.
**********************************************************************/
WERD_CHOICE* Dict::permute_script_words(
const BLOB_CHOICE_LIST_VECTOR &char_choices) {
if (char_choices.length() > MAX_WERD_LENGTH)
return NULL;
int word_sid = get_top_word_script(char_choices, getUnicharset());
if (word_sid == getUnicharset().null_sid())
return NULL;
if (permute_debug) {
tprintf("\n\nPermuteScript %s\n",
getUnicharset().get_script_from_script_id(word_sid));
print_char_choices_list("", char_choices, getUnicharset(),
permute_debug > 1);
}
WERD_CHOICE *current_word = new WERD_CHOICE(MAX_WERD_LENGTH);
BLOB_CHOICE_IT blob_choice_it;
bool replaced = false;
bool prev_is_consistent = false;
for (int x = 0; x < char_choices.length(); ++x) {
blob_choice_it.set_to_list(char_choices.get(x));
BLOB_CHOICE *first_choice = blob_choice_it.data();
if (!first_choice) return NULL;
UNICHAR_ID unichar_id = first_choice->unichar_id();
bool sid_consistent = (first_choice->script_id() == word_sid);
bool this_is_punct = getUnicharset().get_ispunctuation(unichar_id);
if (!sid_consistent && !this_is_punct && prev_is_consistent) {
// If the previous char is CJK, we prefer a cjk over non-cjk char
if (permute_debug) {
tprintf("Checking %s r%g\n", getUnicharset().id_to_unichar(unichar_id),
first_choice->rating());
print_ratings_list("\t", char_choices.get(x), getUnicharset());
}
// prefer a script consistent choice
BLOB_CHOICE* c_it = find_choice_by_script(char_choices.get(x),
word_sid, 0, 0);
// make this a separate check
// otherwise, prefer a punctuation
if (c_it == NULL)
c_it = find_choice_by_type(char_choices.get(x), 'p', getUnicharset());
if (c_it != NULL) {
if (permute_debug)
tprintf("Replacing %d r%g ==> %d r%g\n",
first_choice->unichar_id(), first_choice->rating(),
c_it->unichar_id(), c_it->rating());
first_choice = c_it;
replaced = true;
}
}
current_word->append_unichar_id_space_allocated(
first_choice->unichar_id(), 1,
first_choice->rating(), first_choice->certainty());
prev_is_consistent = sid_consistent;
}
if (replaced) {
// When we replace a word choice (usually top choice) with
// another for the sake of script consistency, we need to improve its
// rating so that it will replace the best choice. How much we modify
// the rating determines how strong is the script consistency constraint.
// We need a more consistent solution for all contextual constraints
// like case, punct pattern, script, etc. Right now, this does the same
// thing as adjust_non_words for case and punctuation rules.
float rating = current_word->rating();
rating *= segment_reward_script;
current_word->set_rating(rating);
}
current_word->populate_unichars(getUnicharset());
if (permute_debug && replaced)
current_word->print("<== permute_script_word **");
return current_word;
}
/**********************************************************************
* permute_characters
*
* Permute these characters together according to each of the different
* permuters that are enabled.
**********************************************************************/
void Dict::permute_characters(const BLOB_CHOICE_LIST_VECTOR &char_choices,
float limit,
WERD_CHOICE *best_choice,
WERD_CHOICE *raw_choice) {
float old_raw_choice_rating = raw_choice->rating();
permutation_count++; /* Global counter */
if (tord_display_ratings > 1) {
cprintf("\nchar_choices in permute_characters:\n");
print_char_choices_list("\n==> Input CharChoices", char_choices,
getUnicharset(), true);
}
if (char_choices.length() == 1 &&
get_top_choice_uid(char_choices.get(0)) == 0)
return;
WERD_CHOICE *this_choice = permute_all(char_choices, limit, raw_choice);
if (raw_choice->rating() < old_raw_choice_rating) {
// Populate unichars_ and unichar_lengths_ of raw_choice. This is
// needed for various components that still work with unichars rather
// than unichar ids (e.g. AdaptToWord).
raw_choice->populate_unichars(getUnicharset());
}
if (this_choice && this_choice->rating() < best_choice->rating()) {
*best_choice = *this_choice;
// Populate unichars_ and unichar_lengths_ of best_choice. This is
// needed for various components that still work with unichars rather
// than unichar ids (dawg, *_ok functions, various hard-coded hacks).
best_choice->populate_unichars(getUnicharset());
if (tord_display_ratings) {
cprintf("permute_characters: %s\n",
best_choice->debug_string(getUnicharset()).string());
}
}
delete this_choice;
}
/**********************************************************************
* permute_compound_words
*
* Return the top choice for each character as the choice for the word.
**********************************************************************/
WERD_CHOICE *Dict::permute_compound_words(
const BLOB_CHOICE_LIST_VECTOR &char_choices,
float rating_limit) {
BLOB_CHOICE *first_choice;
WERD_CHOICE *best_choice = NULL;
WERD_CHOICE current_word(MAX_WERD_LENGTH);
int first_index = 0;
int x;
BLOB_CHOICE_IT blob_choice_it;
if (char_choices.length() > MAX_WERD_LENGTH) {
WERD_CHOICE *bad_word_choice = new WERD_CHOICE();
bad_word_choice->make_bad();
return bad_word_choice;
}
UNICHAR_ID slash = getUnicharset().unichar_to_id("/");
UNICHAR_ID dash = getUnicharset().unichar_to_id("-");
for (x = 0; x < char_choices.length(); ++x) {
blob_choice_it.set_to_list(char_choices.get(x));
first_choice = blob_choice_it.data();
if (first_choice->unichar_id() == slash ||
first_choice->unichar_id() == dash) {
if (x > first_index) {
if (segment_debug)
cprintf ("Hyphenated word found\n");
permute_subword(char_choices, rating_limit, first_index,
x - 1, ¤t_word);
if (current_word.rating() > rating_limit)
break;
}
// Append hyphen/slash separator to current_word.
current_word.append_unichar_id_space_allocated(
first_choice->unichar_id(), 1,
first_choice->rating(), first_choice->certainty());
first_index = x + 1; // update first_index
}
}
if (first_index > 0 && first_index < x &&
current_word.rating() <= rating_limit) {
permute_subword(char_choices, rating_limit, first_index,
x - 1, ¤t_word);
best_choice = new WERD_CHOICE(current_word);
best_choice->set_permuter(COMPOUND_PERM);
}
return (best_choice);
}
/**********************************************************************
* permute_subword
*
* Permute a part of a compound word this subword is bounded by hyphens
* and the start and end of the word. Call the standard word permute
* function on a set of choices covering only part of the original
* word. When it is done reclaim the memory that was used in the
* excercise.
**********************************************************************/
void Dict::permute_subword(const BLOB_CHOICE_LIST_VECTOR &char_choices,
float rating_limit,
int start,
int end,
WERD_CHOICE *current_word) {
int x;
BLOB_CHOICE_LIST_VECTOR subchoices;
WERD_CHOICE *best_choice = NULL;
WERD_CHOICE raw_choice;
raw_choice.make_bad();
DisableChoiceAccum();
for (x = start; x <= end; x++) {
if (char_choices.get(x) != NULL) {
subchoices += char_choices.get(x);
}
}
if (!subchoices.empty()) {
bool old_segment_dawg_debug = segment_dawg_debug;
if (segment_debug) segment_dawg_debug.set_value(true);
best_choice = permute_all(subchoices, rating_limit, &raw_choice);
if (segment_debug) {
segment_dawg_debug.set_value(old_segment_dawg_debug);
}
if (best_choice && best_choice->length() > 0) {
*current_word += *best_choice;
} else {
current_word->set_rating(MAX_FLOAT32);
}
} else {
current_word->set_rating(MAX_FLOAT32);
}
if (best_choice)
delete best_choice;
if (segment_debug && current_word->rating() < MAX_FLOAT32) {
cprintf ("Subword permuted = %s, %5.2f, %5.2f\n\n",
current_word->debug_string(getUnicharset()).string(),
current_word->rating(), current_word->certainty());
}
EnableChoiceAccum();
}
/**********************************************************************
* permute_top_choice
*
* Return the top choice for each character as the choice for the word.
* In addition a choice is created for the best lower and upper case
* non-words. In each character position the best lower (or upper) case
* character is substituted for the best overall character.
**********************************************************************/
WERD_CHOICE *Dict::permute_top_choice(
const BLOB_CHOICE_LIST_VECTOR &char_choices,
float* rating_limit,
WERD_CHOICE *raw_choice,
BOOL8 *any_alpha) {
BLOB_CHOICE *first_choice;
const char *first_char; //first choice
const char *second_char; //second choice
const char *third_char; //third choice
char prev_char[UNICHAR_LEN + 1]; //prev in word
const char *next_char = ""; //next in word
const char *next_next_char = ""; //after next next in word
WERD_CHOICE word(MAX_PERM_LENGTH);
word.set_permuter(TOP_CHOICE_PERM);
WERD_CHOICE capital_word(MAX_PERM_LENGTH);
capital_word.set_permuter(UPPER_CASE_PERM);
WERD_CHOICE lower_word(MAX_PERM_LENGTH);
lower_word.set_permuter(LOWER_CASE_PERM);
int x;
BOOL8 char_alpha;
float first_rating = 0;
float adjust_factor;
float certainties[MAX_PERM_LENGTH + 1];
float lower_certainties[MAX_PERM_LENGTH + 1];
float upper_certainties[MAX_PERM_LENGTH + 1];
BLOB_CHOICE_IT blob_choice_it;
UNICHAR_ID temp_id;
UNICHAR_ID unichar_id;
UNICHAR_ID space = getUnicharset().unichar_to_id(" ");
register const char* ch;
register inT8 lower_done;
register inT8 upper_done;
prev_char[0] = '\0';
if (any_alpha != NULL)
*any_alpha = FALSE;
if (char_choices.length() > MAX_PERM_LENGTH) {
return (NULL);
}
for (x = 0; x < char_choices.length(); ++x) {
if (x + 1 < char_choices.length()) {
unichar_id = get_top_choice_uid(char_choices.get(x+1));
next_char = unichar_id != INVALID_UNICHAR_ID ?
getUnicharset().id_to_unichar(unichar_id) : "";
} else {
next_char = "";
}
if (x + 2 < char_choices.length()) {
unichar_id = get_top_choice_uid(char_choices.get(x+2));
next_next_char = unichar_id != INVALID_UNICHAR_ID ?
getUnicharset().id_to_unichar(unichar_id) : "";
} else {
next_next_char = "";
}
blob_choice_it.set_to_list(char_choices.get(x));
ASSERT_HOST(!blob_choice_it.empty());
first_choice = NULL;
for (blob_choice_it.mark_cycle_pt(); !blob_choice_it.cycled_list();
blob_choice_it.forward()) { // find the best non-fragment char choice
temp_id = blob_choice_it.data()->unichar_id();
if (!(getUnicharset().get_fragment(temp_id))) {
first_choice = blob_choice_it.data();
break;
} else if (char_choices.length() > 1) {
word.set_fragment_mark(true);
capital_word.set_fragment_mark(true);
lower_word.set_fragment_mark(true);
}
}
if (first_choice == NULL) {
cprintf("Permuter found only fragments for"
" character at position %d; word=%s\n",
x, word.debug_string(getUnicharset()).string());
}
ASSERT_HOST(first_choice != NULL);
unichar_id = first_choice->unichar_id() != INVALID_UNICHAR_ID ?
first_choice->unichar_id() : space;
first_char = getUnicharset().id_to_unichar(unichar_id);
first_rating = first_choice->rating();
word.append_unichar_id_space_allocated(
unichar_id, 1, first_choice->rating(), first_choice->certainty());
capital_word.append_unichar_id_space_allocated(
unichar_id, 1, first_choice->rating(), first_choice->certainty());
lower_word.append_unichar_id_space_allocated(
unichar_id, 1, first_choice->rating(), first_choice->certainty());
certainties[x] = first_choice->certainty();
lower_certainties[x] = first_choice->certainty();
upper_certainties[x] = first_choice->certainty();
lower_done = FALSE;
upper_done = FALSE;
char_alpha = FALSE;
second_char = "";
third_char = "";
for (; !blob_choice_it.cycled_list(); blob_choice_it.forward()) {
unichar_id = blob_choice_it.data()->unichar_id();
if (getUnicharset().eq(unichar_id, "l") && !blob_choice_it.at_last() &&
blob_choice_it.data_relative(1)->rating() == first_rating) {
temp_id = blob_choice_it.data_relative(1)->unichar_id();
if (getUnicharset().eq(temp_id, "1") ||
getUnicharset().eq(temp_id, "I")) {
second_char = getUnicharset().id_to_unichar(temp_id);
blob_choice_it.forward();
if (!blob_choice_it.at_last() &&
blob_choice_it.data_relative(1)->rating() == first_rating) {
temp_id = blob_choice_it.data_relative(1)->unichar_id();
if (getUnicharset().eq(temp_id, "1") ||
getUnicharset().eq(temp_id, "I")) {
third_char = getUnicharset().id_to_unichar(temp_id);
blob_choice_it.forward();
}
}
ch = choose_il1 (first_char, second_char, third_char,
prev_char, next_char, next_next_char);
unichar_id = (ch != NULL && *ch != '\0') ?
getUnicharset().unichar_to_id(ch) : INVALID_UNICHAR_ID;
if (strcmp(ch, "l") != 0 &&
getUnicharset().eq(word.unichar_id(x), "l")) {
word.set_unichar_id(unichar_id, x);
lower_word.set_unichar_id(unichar_id, x);
capital_word.set_unichar_id(unichar_id, x);
}
}
}
if (unichar_id != INVALID_UNICHAR_ID) {
/* Find lower case */
if (!lower_done &&
(getUnicharset().get_islower(unichar_id) ||
(getUnicharset().get_isupper(unichar_id) && x == 0))) {
lower_word.set_unichar_id(unichar_id, x);
lower_word.set_rating(lower_word.rating() -
first_choice->rating() + blob_choice_it.data()->rating());
if (blob_choice_it.data()->certainty() < lower_word.certainty()) {
lower_word.set_certainty(blob_choice_it.data()->certainty());
}
lower_certainties[x] = blob_choice_it.data()->certainty();
lower_done = TRUE;
}
/* Find upper case */
if (!upper_done && getUnicharset().get_isupper(unichar_id)) {
capital_word.set_unichar_id(unichar_id, x);
capital_word.set_rating(capital_word.rating() -
first_choice->rating() + blob_choice_it.data()->rating());
if (blob_choice_it.data()->certainty() < capital_word.certainty()) {
capital_word.set_certainty(blob_choice_it.data()->certainty());
}
upper_certainties[x] = blob_choice_it.data()->certainty();
upper_done = TRUE;
}
if (!char_alpha) {
const CHAR_FRAGMENT *fragment =
getUnicharset().get_fragment(unichar_id);
temp_id = !fragment ? unichar_id :
getUnicharset().unichar_to_id(fragment->get_unichar());
if (getUnicharset().get_isalpha(temp_id)) {
char_alpha = TRUE;
}
}
if (lower_done && upper_done)
break;
}
}
if (char_alpha && any_alpha != NULL)
*any_alpha = TRUE;
if (word.rating() > bestrate_pruning_factor * *rating_limit) {
if (permute_debug)
tprintf("\n***** Aborting high-cost word: %g > limit %g \n",
word.rating(), bestrate_pruning_factor * *rating_limit);
return (NULL);
}
*prev_char = '\0';
temp_id = word.unichar_id(word.length()-1);
if (temp_id != INVALID_UNICHAR_ID) {
strcpy(prev_char, getUnicharset().id_to_unichar(temp_id));
}
}
if (word.rating() < raw_choice->rating()) {
*raw_choice = word;
LogNewChoice(*raw_choice, 1.0, certainties, true);
}
if (ngram_permuter_activated)
return NULL;
float rating = word.rating();
adjust_non_word(&word, &adjust_factor);
LogNewChoice(word, adjust_factor, certainties, false);
float lower_rating = lower_word.rating();
adjust_non_word(&lower_word, &adjust_factor);
LogNewChoice(lower_word, adjust_factor, lower_certainties, false);
float upper_rating = capital_word.rating();
adjust_non_word(&capital_word, &adjust_factor);
LogNewChoice(capital_word, adjust_factor, upper_certainties, false);
WERD_CHOICE *best_choice = &word;
*rating_limit = rating;
if (lower_word.rating() < best_choice->rating()) {
best_choice = &lower_word;
*rating_limit = lower_rating;
}
if (capital_word.rating() < best_choice->rating()) {
best_choice = &capital_word;
*rating_limit = upper_rating;
}
return new WERD_CHOICE(*best_choice);
}
/**********************************************************************
* choose_il1
*
* Choose between the candidate il1 chars.
**********************************************************************/
const char* Dict::choose_il1(const char *first_char, //first choice
const char *second_char, //second choice
const char *third_char, //third choice
const char *prev_char, //prev in word
const char *next_char, //next in word
const char *next_next_char) { //after next next in word
inT32 type1; //1/I/l type of first choice
inT32 type2; //1/I/l type of second choice
inT32 type3; //1/I/l type of third choice
int first_char_length = strlen(first_char);
int prev_char_length = strlen(prev_char);
int next_char_length = strlen(next_char);
int next_next_char_length = strlen(next_next_char);
if (*first_char == 'l' && *second_char != '\0') {
if (*second_char == 'I'
&& (((prev_char_length != 0 &&
getUnicharset().get_isupper (prev_char, prev_char_length)) &&
(next_char_length == 0 ||
!getUnicharset().get_islower (next_char, next_char_length)) &&
(next_char_length == 0 ||
!getUnicharset().get_isdigit (next_char, next_char_length))) ||
((next_char_length != 0 &&
getUnicharset().get_isupper (next_char, next_char_length)) &&
(prev_char_length == 0 ||
!getUnicharset().get_islower (prev_char, prev_char_length)) &&
(prev_char_length == 0 ||
!getUnicharset().get_isdigit (prev_char, prev_char_length)))))
first_char = second_char; //override
else if (*second_char == '1' || *third_char == '1') {
if ((next_char_length != 0 &&
getUnicharset().get_isdigit (next_char, next_char_length)) ||
(prev_char_length != 0 &&
getUnicharset().get_isdigit (prev_char, prev_char_length))
|| (*next_char == 'l' &&
(next_next_char_length != 0 &&
getUnicharset().get_isdigit (next_next_char,
next_next_char_length)))) {
first_char = "1";
first_char_length = 1;
}
else if ((prev_char_length == 0 ||
!getUnicharset().get_islower (prev_char, prev_char_length)) &&
((next_char_length == 0 ||
!getUnicharset().get_islower (next_char, next_char_length)) ||
(*next_char == 's' &&
*next_next_char == 't'))) {
if (((*prev_char != '\'' && *prev_char != '`') || *next_char != '\0')
&& ((*next_char != '\'' && *next_char != '`')
|| *prev_char != '\0')) {
first_char = "1";
first_char_length = 1;
}
}
}
if (*first_char == 'l' && *next_char != '\0' &&
(prev_char_length == 0 ||
!getUnicharset().get_isalpha (prev_char, prev_char_length))) {
type1 = 2;
if (*second_char == '1')
type2 = 0;
else if (*second_char == 'I')
type2 = 1;
else if (*second_char == 'l')
type2 = 2;
else
type2 = type1;
if (*third_char == '1')
type3 = 0;
else if (*third_char == 'I')
type3 = 1;
else if (*third_char == 'l')
type3 = 2;
else
type3 = type1;
#if 0
if (bigram_counts[*next_char][type2] >
bigram_counts[*next_char][type1]) {
first_char = second_char;
type1 = type2;
}
if (bigram_counts[*next_char][type3] >
bigram_counts[*next_char][type1]) {
first_char = third_char;
}
#endif
}
}
return first_char;
}
//
// Check all the DAWGs to see if this word is in any of them.
//
int Dict::valid_word(const WERD_CHOICE &word, bool numbers_ok) {
const WERD_CHOICE *word_ptr = &word;
WERD_CHOICE temp_word;
if (hyphenated()) {
copy_hyphen_info(&temp_word);
temp_word += word;
word_ptr = &temp_word;
}
if (word_ptr->length() == 0) return NO_PERM;
// Allocate vectors for holding current and updated
// active_dawgs and constraints and initialize them.
DawgInfoVector *active_dawgs = new DawgInfoVector[2];
DawgInfoVector *constraints = new DawgInfoVector[2];
init_active_dawgs(&(active_dawgs[0]));
init_constraints(&(constraints[0]));
DawgArgs dawg_args(&(active_dawgs[0]), &(constraints[0]),
&(active_dawgs[1]), &(constraints[1]), 0.0);
int last_index = word_ptr->length() - 1;
// Call leter_is_okay for each letter in the word.
for (int i = hyphen_base_size(); i <= last_index; ++i) {
if (!((this->*letter_is_okay_)(&dawg_args, i, word_ptr,
i == last_index))) break;
// Swap active_dawgs, constraints with the corresponding updated vector.
if (dawg_args.updated_active_dawgs == &(active_dawgs[1])) {
dawg_args.updated_active_dawgs = &(active_dawgs[0]);
dawg_args.updated_constraints = &(constraints[0]);
++(dawg_args.active_dawgs);
++(dawg_args.constraints);
} else {
++(dawg_args.updated_active_dawgs);
++(dawg_args.updated_constraints);
dawg_args.active_dawgs = &(active_dawgs[0]);
dawg_args.constraints = &(constraints[0]);
}
}
delete[] active_dawgs;
delete[] constraints;
if (dawg_args.permuter == SYSTEM_DAWG_PERM ||
dawg_args.permuter == DOC_DAWG_PERM ||
dawg_args.permuter == USER_DAWG_PERM ||
(numbers_ok && dawg_args.permuter == NUMBER_PERM)){
return dawg_args.permuter;
} else {
return NO_PERM;
}
}
//
// Return true if the word contains a valid punctuation pattern.
//
// Note: Since the domains of punctuation symbols and symblos
// used in numbers are not disjoint, a valid number might contain
// an invalid punctuation pattern (e.g. .99).
//
bool Dict::valid_punctuation(const WERD_CHOICE &word) {
if (word.length() == 0) return NO_PERM;
int i;
WERD_CHOICE new_word;
int last_index = word.length() - 1;
int new_len = 0;
for (i = 0; i <= last_index; ++i) {
UNICHAR_ID unichar_id = (word.unichar_id(i));
if (getUnicharset().get_ispunctuation(unichar_id)) {
new_word.append_unichar_id(unichar_id, 1, 0.0, 0.0);
} else if (!getUnicharset().get_isalpha(unichar_id) &&
!getUnicharset().get_isdigit(unichar_id)) {
return false; // neither punc, nor alpha, nor digit
} else if ((new_len = new_word.length()) == 0 ||
new_word.unichar_id(new_len-1) != Dawg::kPatternUnicharID) {
new_word.append_unichar_id(Dawg::kPatternUnicharID, 1, 0.0, 0.0);
}
}
for (i = 0; i < dawgs_.size(); ++i) {
if (dawgs_[i]->type() == DAWG_TYPE_PUNCTUATION &&
dawgs_[i]->word_in_dawg(new_word)) return true;
}
return false;
}
/**********************************************************************
* fragment_state
*
* Given the current char choice and information about previously seen
* fragments, determines whether adjacent character fragments are
* present and whether they can be concatenated.
*
* The given prev_char_frag_info contains:
* -- fragment: if not NULL contains information about immediately
* preceeding fragmented character choice
* -- num_fragments: number of fragments that have been used so far
* to construct a character
* -- certainty: certainty of the current choice or minimum
* certainty of all fragments concatenated so far
* -- rating: rating of the current choice or sum of fragment
* ratings concatenated so far
*
* The output char_frag_info is filled in as follows:
* -- character: is set to be NULL if the choice is a non-matching
* or non-ending fragment piece; is set to unichar of the given choice
* if it represents a regular character or a matching ending fragment
* -- fragment,num_fragments,certainty,rating are set as described above
*
* Returns false if a non-matching fragment is discovered, true otherwise.
**********************************************************************/
bool Dict::fragment_state_okay(UNICHAR_ID curr_unichar_id,
float curr_rating, float curr_certainty,
const CHAR_FRAGMENT_INFO *prev_char_frag_info,
const char *debug, int word_ending,
CHAR_FRAGMENT_INFO *char_frag_info) {
const CHAR_FRAGMENT *this_fragment =
getUnicharset().get_fragment(curr_unichar_id);
const CHAR_FRAGMENT *prev_fragment =
prev_char_frag_info != NULL ? prev_char_frag_info->fragment : NULL;
// Print debug info for fragments.
if (debug && (prev_fragment || this_fragment)) {
cprintf("%s check fragments: choice=%s word_ending=%d\n", debug,
getUnicharset().debug_str(curr_unichar_id).string(),
word_ending);
if (prev_fragment) {
cprintf("prev_fragment %s\n", prev_fragment->to_string().string());
}
if (this_fragment) {
cprintf("this_fragment %s\n", this_fragment->to_string().string());
}
}
char_frag_info->unichar_id = curr_unichar_id;
char_frag_info->fragment = this_fragment;
char_frag_info->rating = curr_rating;
char_frag_info->certainty = curr_certainty;
char_frag_info->num_fragments = 1;
if (prev_fragment && !this_fragment) {
if (debug) tprintf("Skip choice with incomplete fragment\n");
return false;
}
if (this_fragment) {
// We are dealing with a fragment.
char_frag_info->unichar_id = INVALID_UNICHAR_ID;
if (prev_fragment) {
if (!this_fragment->is_continuation_of(prev_fragment)) {
if (debug) tprintf("Non-matching fragment piece\n");
return false;
}
if (this_fragment->is_ending()) {
char_frag_info->unichar_id =
getUnicharset().unichar_to_id(this_fragment->get_unichar());
char_frag_info->fragment = NULL;
if (debug) {
tprintf("Built character %s from fragments\n",
getUnicharset().debug_str(
char_frag_info->unichar_id).string());
}
} else {
if (debug) tprintf("Record fragment continuation\n");
char_frag_info->fragment = this_fragment;
}
// Update certainty and rating.
char_frag_info->rating =
prev_char_frag_info->rating + curr_rating;
char_frag_info->num_fragments = prev_char_frag_info->num_fragments + 1;
char_frag_info->certainty =
MIN(curr_certainty, prev_char_frag_info->certainty);
} else {
if (this_fragment->is_beginning()) {
if (debug) cprintf("Record fragment beginning\n");
} else {
if (debug) {
tprintf("Non-starting fragment piece with no prev_fragment\n");
}
return false;
}
}
}
if (word_ending && char_frag_info->fragment) {
if (debug) tprintf("Word can not end with a fragment\n");
return false;
}
return true;
}
/**********************************************************************
* top_fragments_permute_and_select
*
* Creates a copy of character choices list that contain only fragments
* and the best non-fragmented character choice.
* Permutes character in this shortened list, builds characters from
* fragments if possible and returns a better choice if found.
**********************************************************************/
WERD_CHOICE *Dict::top_fragments_permute_and_select(
const BLOB_CHOICE_LIST_VECTOR &char_choices,
float rating_limit) {
if (char_choices.length() <= 1 ||
char_choices.length() > MAX_PERM_LENGTH) {
return NULL;
}
// See it would be possible to benefit from permuting fragments.
int x;
float min_rating = 0.0;
BLOB_CHOICE_IT blob_choice_it;
for (x = 0; x < char_choices.length(); ++x) {
blob_choice_it.set_to_list(char_choices.get(x));
if (blob_choice_it.data()) {
min_rating += blob_choice_it.data()->rating();
}
if (min_rating >= rating_limit) {
return NULL;
}
}
if (fragments_debug > 1) {
tprintf("A choice with fragment beats top choice\n");
tprintf("Running fragment permuter...\n");
}
// Construct a modified choices list that contains (for each position):
// the best choice, all fragments and at least one choice for
// a non-fragmented character.
BLOB_CHOICE_LIST_VECTOR frag_char_choices(char_choices.length());
for (x = 0; x < char_choices.length(); ++x) {
bool need_nonfrag_char = true;
BLOB_CHOICE_LIST *frag_choices = new BLOB_CHOICE_LIST();
BLOB_CHOICE_IT frag_choices_it;
frag_choices_it.set_to_list(frag_choices);
blob_choice_it.set_to_list(char_choices.get(x));
for (blob_choice_it.mark_cycle_pt(); !blob_choice_it.cycled_list();
blob_choice_it.forward()) {
if (getUnicharset().get_fragment(blob_choice_it.data()->unichar_id())) {
frag_choices_it.add_after_then_move(
new BLOB_CHOICE(*(blob_choice_it.data())));
} else if (need_nonfrag_char) {
frag_choices_it.add_after_then_move(
new BLOB_CHOICE(*(blob_choice_it.data())));
need_nonfrag_char = false;
}
}
frag_char_choices += frag_choices;
}
WERD_CHOICE *best_choice = new WERD_CHOICE();
best_choice->make_bad();
WERD_CHOICE word(MAX_PERM_LENGTH);
word.set_permuter(TOP_CHOICE_PERM);
float certainties[MAX_PERM_LENGTH];
this->go_deeper_fxn_ = &tesseract::Dict::go_deeper_top_fragments_fxn;
permute_choices((fragments_debug > 1) ? "fragments_debug" : NULL,
frag_char_choices, 0, NULL, &word, certainties,
&rating_limit, best_choice, NULL);
frag_char_choices.delete_data_pointers();
return best_choice;
}
/**********************************************************************
* permute_choices
*
* Call append_choices() for each BLOB_CHOICE in BLOB_CHOICE_LIST
* with the given char_choice_index in char_choices.
**********************************************************************/
void Dict::permute_choices(
const char *debug,
const BLOB_CHOICE_LIST_VECTOR &char_choices,
int char_choice_index,
const CHAR_FRAGMENT_INFO *prev_char_frag_info,
WERD_CHOICE *word,
float certainties[],
float *limit,
WERD_CHOICE *best_choice,
void *more_args) {
if (debug) {
tprintf("%s permute_choices: char_choice_index=%d"
" limit=%4.2f rating=%4.2f, certainty=%4.2f word=%s\n",
debug, char_choice_index, *limit, word->rating(),
word->certainty(), word->debug_string(getUnicharset()).string());
}
if (char_choice_index < char_choices.length()) {
BLOB_CHOICE_IT blob_choice_it;
blob_choice_it.set_to_list(char_choices.get(char_choice_index));
for (blob_choice_it.mark_cycle_pt(); !blob_choice_it.cycled_list();
blob_choice_it.forward()) {
append_choices(debug, char_choices, *(blob_choice_it.data()),
char_choice_index, prev_char_frag_info, word,
certainties, limit, best_choice, more_args);
}
}
}
/**********************************************************************
* append_choices
*
* Check to see whether or not the next choice is worth appending to
* the word being generated. If so then keep going deeper into the word.
*
* This function assumes that Dict::go_deeper_fxn_ is set.
**********************************************************************/
void Dict::append_choices(
const char *debug,
const BLOB_CHOICE_LIST_VECTOR &char_choices,
const BLOB_CHOICE &blob_choice,
int char_choice_index,
const CHAR_FRAGMENT_INFO *prev_char_frag_info,
WERD_CHOICE *word,
float certainties[],
float *limit,
WERD_CHOICE *best_choice,
void *more_args) {
int word_ending =
(char_choice_index == char_choices.length() - 1) ? true : false;
// Deal with fragments.
CHAR_FRAGMENT_INFO char_frag_info;
if (!fragment_state_okay(blob_choice.unichar_id(), blob_choice.rating(),
blob_choice.certainty(), prev_char_frag_info, debug,
word_ending, &char_frag_info)) {
return; // blob_choice must be an invalid fragment
}
// Search the next letter if this character is a fragment.
if (char_frag_info.unichar_id == INVALID_UNICHAR_ID) {
permute_choices(debug, char_choices, char_choice_index + 1,
&char_frag_info, word, certainties, limit,
best_choice, more_args);
return;
}
// Add the next unichar.
float old_rating = word->rating();
float old_certainty = word->certainty();
uinT8 old_permuter = word->permuter();
certainties[word->length()] = char_frag_info.certainty;
word->append_unichar_id_space_allocated(
char_frag_info.unichar_id, char_frag_info.num_fragments,
char_frag_info.rating, char_frag_info.certainty);
// Explore the next unichar.
(this->*go_deeper_fxn_)(debug, char_choices, char_choice_index,
&char_frag_info, word_ending, word, certainties,
limit, best_choice, more_args);
// Remove the unichar we added to explore other choices in it's place.
word->remove_last_unichar_id();
word->set_rating(old_rating);
word->set_certainty(old_certainty);
word->set_permuter(old_permuter);
}
/**********************************************************************
* go_deeper_top_fragments_fxn
*
* If the choice being composed so far could be better
* than best_choice keep exploring choices.
**********************************************************************/
void Dict::go_deeper_top_fragments_fxn(
const char *debug, const BLOB_CHOICE_LIST_VECTOR &char_choices,
int char_choice_index,
const CHAR_FRAGMENT_INFO *prev_char_frag_info,
bool word_ending, WERD_CHOICE *word, float certainties[],
float *limit, WERD_CHOICE *best_choice, void *more_args) {
if (word->rating() < *limit) {
if (word_ending) {
if (fragments_debug > 1) {
tprintf("fragments_debug new choice = %s\n",
word->debug_string(getUnicharset()).string());
}
*limit = word->rating();
float adjust_factor;
adjust_non_word(word, &adjust_factor);
LogNewChoice(*word, adjust_factor, certainties, false);
if (word->rating() < best_choice->rating()) {
*best_choice = *word;
}
} else { // search the next letter
permute_choices(debug, char_choices, char_choice_index + 1,
prev_char_frag_info, word, certainties, limit,
best_choice, more_args);
}
} else {
if (fragments_debug > 1) {
tprintf("fragments_debug pruned word (%s, rating=%4.2f, limit=%4.2f)\n",
word->debug_string(getUnicharset()).string(),
word->rating(), *limit);
}
}
}
} // namespace tesseract