| /* -*-C-*- |
| ******************************************************************************** |
| * |
| * File: permdawg.c (Formerly permdawg.c) |
| * Description: Scale word choices by a dictionary |
| * Author: Mark Seaman, OCR Technology |
| * Created: Fri Oct 16 14:37:00 1987 |
| * Modified: Tue Jul 9 15:43:18 1991 (Mark Seaman) marks@hpgrlt |
| * Language: C |
| * Package: N/A |
| * Status: Reusable Software Component |
| * |
| * (c) Copyright 1987, 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 "permdawg.h" |
| #include "debug.h" |
| #include "hyphen.h" |
| #include "permute.h" |
| #include "tordvars.h" |
| #include "context.h" |
| #include "stopper.h" |
| #include "freelist.h" |
| #include "globals.h" |
| #include "tprintf.h" |
| #include "cutil.h" |
| #include "dawg.h" |
| #include "ndminx.h" |
| #include "varable.h" |
| #include "conversion.h" |
| |
| #include <ctype.h> |
| #include "dict.h" |
| #include "image.h" |
| |
| /*---------------------------------------------------------------------- |
| T y p e s |
| ----------------------------------------------------------------------*/ |
| #define FREQ_WERD 1.0 |
| #define GOOD_WERD 1.1 |
| #define OK_WERD 1.3125 |
| #define MAX_FREQ_EDGES 1500 |
| #define NO_RATING -1 |
| |
| /*---------------------------------------------------------------------- |
| V a r i a b l e s |
| ----------------------------------------------------------------------*/ |
| static EDGE_ARRAY frequent_words; |
| static float rating_margin; |
| static float rating_pad = 5.0; |
| |
| BOOL_VAR(segment_dawg_debug, 0, "Debug mode for word segmentation"); |
| |
| double_VAR(segment_penalty_dict_punc_bad, OK_WERD, |
| "Default score multiplier for word matches, which may have case or " |
| "punctuation issues (lower is better)."); |
| |
| double_VAR(segment_penalty_dict_punc_ok, GOOD_WERD, |
| "Score multiplier for word matches that have good case " |
| "(lower is better)."); |
| |
| double_VAR(segment_penalty_dict_frequent_word, FREQ_WERD, |
| "Score multiplier for word matches which have good case and are " |
| "frequent in the given language (lower is better)."); |
| |
| /*---------------------------------------------------------------------- |
| F u n c t i o n s |
| ----------------------------------------------------------------------*/ |
| /********************************************************************** |
| * adjust_word |
| * |
| * Assign an adjusted value to a string that is a word. The value |
| * that this word choice has is based on case and punctuation rules. |
| **********************************************************************/ |
| namespace tesseract { |
| void Dict::adjust_word(A_CHOICE *best_choice, float *certainty_array) { |
| char *this_word; |
| int punct_status; |
| float adjust_factor; |
| |
| if (segment_adjust_debug) |
| tprintf ("Word: %s %4.2f ", |
| class_string (best_choice), class_rating (best_choice)); |
| |
| this_word = class_string (best_choice); |
| punct_status = punctuation_ok (this_word, class_lengths (best_choice)); |
| |
| class_rating (best_choice) += RATING_PAD; |
| if (case_ok (this_word, class_lengths (best_choice)) |
| && punct_status != -1) { |
| if (punct_status < 1 && word_in_dawg (frequent_words, this_word)) { |
| class_rating (best_choice) *= segment_penalty_dict_frequent_word; |
| class_permuter (best_choice) = FREQ_DAWG_PERM; |
| adjust_factor = segment_penalty_dict_frequent_word; |
| if (segment_adjust_debug) |
| tprintf(", F, %4.2f ", (double)segment_penalty_dict_frequent_word); |
| } |
| else { |
| class_rating (best_choice) *= segment_penalty_dict_punc_ok; |
| adjust_factor = segment_penalty_dict_punc_ok; |
| if (segment_adjust_debug) |
| tprintf(", %4.2f ", (double)segment_penalty_dict_punc_ok); |
| } |
| } |
| else { |
| class_rating (best_choice) *= segment_penalty_dict_punc_bad; |
| adjust_factor = segment_penalty_dict_punc_bad; |
| if (segment_adjust_debug) { |
| if (!case_ok (this_word, class_lengths (best_choice))) |
| tprintf(", C"); |
| if (punctuation_ok (this_word, class_lengths (best_choice)) == -1) |
| tprintf(", P"); |
| tprintf(", %4.2f ", (double)segment_penalty_dict_punc_bad); |
| } |
| } |
| |
| class_rating (best_choice) -= RATING_PAD; |
| |
| LogNewWordChoice(best_choice, adjust_factor, |
| certainty_array, getUnicharset()); |
| |
| if (segment_adjust_debug) |
| tprintf(" --> %4.2f\n", class_rating (best_choice)); |
| } |
| |
| |
| /********************************************************************** |
| * append_next_choice |
| * |
| * Check to see whether or not the next choice is worth appending to |
| * the string being generated. If so then keep going deeper into the |
| * word. |
| **********************************************************************/ |
| void Dict::append_next_choice( /*previous option */ |
| EDGE_ARRAY dawg, |
| NODE_REF node, |
| char permuter, |
| char *word, |
| char unichar_lengths[], |
| int unichar_offsets[], |
| CHOICES_LIST choices, |
| int char_choice_index, |
| int word_index, |
| A_CHOICE *this_choice, |
| const char *prevchar, |
| float *limit, |
| float rating, |
| float certainty, |
| float *rating_array, |
| float *certainty_array, |
| int word_ending, |
| int last_word, |
| const CHAR_FRAGMENT_INFO *prev_char_frag_info, |
| char fragment_lengths[], |
| CHOICES *result) { |
| A_CHOICE *better_choice; |
| CHAR_FRAGMENT_INFO char_frag_info; |
| const char *ch = NULL; |
| |
| /* Deal with fragments */ |
| if (!fragment_state_okay( |
| getUnicharset().unichar_to_id(class_string(this_choice)), |
| class_rating(this_choice), class_certainty(this_choice), |
| prev_char_frag_info, |
| (segment_dawg_debug && (fragments_debug > 1)) ? "dawg_debug" : NULL, |
| word_ending, &char_frag_info)) { |
| return; // this_choice must be an invalid fragment |
| } |
| if (char_frag_info.unichar_id != INVALID_UNICHAR_ID) { |
| ch = getUnicharset().id_to_unichar(char_frag_info.unichar_id); |
| } |
| if (ch == NULL) { // this character is a fragment |
| JOIN_ON(*result, // so search the next letter |
| dawg_permute(dawg, node, permuter, choices, |
| char_choice_index + 1, word_index, |
| limit, word, unichar_lengths, unichar_offsets, |
| rating, certainty, rating_array, certainty_array, |
| last_word, &char_frag_info, fragment_lengths)); |
| return; |
| } |
| |
| /* Add new character */ |
| strcpy(word + unichar_offsets[word_index], ch); |
| |
| unichar_lengths[word_index] = strlen(ch); |
| unichar_lengths[word_index + 1] = 0; |
| fragment_lengths[word_index] = char_frag_info.num_fragments; |
| fragment_lengths[word_index + 1] = 0; |
| unichar_offsets[word_index + 1] = |
| unichar_offsets[word_index] + unichar_lengths[word_index]; |
| if (word[unichar_offsets[word_index]] == '\0') { |
| word[unichar_offsets[word_index]] = ' '; |
| word[unichar_offsets[word_index] + 1] = '\0'; |
| unichar_lengths[word_index] = 1; |
| unichar_lengths[word_index + 1] = 0; |
| fragment_lengths[word_index] = 1; |
| fragment_lengths[word_index + 1] = 0; |
| unichar_offsets[word_index + 1] = unichar_offsets[word_index] + |
| unichar_lengths[word_index]; |
| } |
| certainty_array[word_index] = char_frag_info.certainty; |
| rating += char_frag_info.rating; |
| certainty = MIN (char_frag_info.certainty, certainty); |
| |
| /* Prune bad subwords */ |
| if (rating_array[char_choice_index] == NO_RATING) { |
| rating_array[char_choice_index] = rating; |
| } else { |
| if (rating_array[word_index] * rating_margin + rating_pad < rating) { |
| if (segment_dawg_debug) { |
| tprintf("early pruned word rating=%4.2f, limit=%4.2f", rating, *limit); |
| print_word_string(word); |
| tprintf("\n"); |
| } |
| return; |
| } |
| } |
| |
| /* Deal with hyphens */ |
| if (word_ending && last_word && word[unichar_offsets[word_index]] == '-' && |
| word_index > 0) { |
| *limit = rating; |
| if (segment_dawg_debug) |
| tprintf("new hyphen choice = %s\n", word); |
| better_choice = new_choice (word, unichar_lengths, rating, certainty, |
| -1, NULL, permuter, false, fragment_lengths); |
| |
| adjust_word(better_choice, certainty_array); |
| push_on(*result, better_choice); |
| if (permuter == SYSTEM_DAWG_PERM) { |
| // Until dawg is a class, it is only safe to use set_hyphen_word |
| // on a single dawg type, as it saves permuter state to use on another |
| // word in hyphen_state, and this *must* apply to the same dawg. |
| set_hyphen_word(word, unichar_lengths, unichar_offsets, |
| rating, node, char_choice_index, fragment_lengths); |
| } |
| } |
| /* Look up char in DAWG */ |
| else { |
| int sub_offset = 0; |
| NODE_REF node_saved = node; |
| while (sub_offset < unichar_lengths[word_index] && |
| (this->*letter_is_okay_)(dawg, &node, |
| unichar_offsets[word_index] + sub_offset, |
| *prevchar, word, word_ending && |
| sub_offset == |
| unichar_lengths[word_index] - 1)) { |
| ++sub_offset; |
| } |
| if (sub_offset == unichar_lengths[word_index]) { |
| /* Add a new word choice */ |
| if (word_ending) { |
| if (segment_dawg_debug == 1) |
| tprintf("new choice = %s\n", word); |
| *limit = rating; |
| |
| better_choice = |
| new_choice (hyphen_tail (word), unichar_lengths + hyphen_base_size(), |
| rating, certainty, -1, NULL, permuter, false, |
| fragment_lengths + hyphen_base_size()); |
| adjust_word (better_choice, &certainty_array[hyphen_base_size()]); |
| push_on(*result, better_choice); |
| } |
| else { |
| /* Search the next letter */ |
| JOIN_ON (*result, |
| dawg_permute (dawg, node, permuter, choices, |
| char_choice_index + 1, word_index + 1, limit, |
| word, unichar_lengths, unichar_offsets, rating, |
| certainty, rating_array, certainty_array, |
| last_word, &char_frag_info, fragment_lengths)); |
| } |
| } else { |
| if (segment_dawg_debug == 1) { |
| tprintf("letter not OK at char %d, index %d + sub index %d/%d\n", |
| word_index, unichar_offsets[word_index], |
| sub_offset, unichar_lengths[word_index]); |
| tprintf("Word"); |
| print_word_string(word); |
| tprintf("\nRejected tail"); |
| print_word_string(word + unichar_offsets[word_index]); |
| tprintf("\n"); |
| } |
| if (node != 0) |
| node = node_saved; |
| } |
| } |
| } |
| |
| |
| /********************************************************************** |
| * dawg_permute |
| * |
| * Permute all the valid words that can be created with this starting |
| * point. The node (in the DAWG) and the word string define a base |
| * from which to start adding the remaining character choices. |
| **********************************************************************/ |
| CHOICES Dict::dawg_permute(EDGE_ARRAY dawg, |
| NODE_REF node, |
| char permuter, |
| CHOICES_LIST choices, |
| int char_choice_index, |
| int word_index, |
| float *limit, |
| char *word, |
| char unichar_lengths[], |
| int unichar_offsets[], |
| float rating, |
| float certainty, |
| float *rating_array, |
| float *certainty_array, |
| int last_word, |
| const CHAR_FRAGMENT_INFO *prev_char_frag_info, |
| char fragment_lengths[]) { |
| CHOICES result = NIL; |
| CHOICES c; |
| char *prevchar; |
| int word_ending = FALSE; |
| |
| if (segment_dawg_debug) { |
| tprintf("dawg_permute (node=" REFFORMAT ", char_choice_index=%d," |
| " word_index=%d, limit=%f, word=", |
| node, char_choice_index, word_index, *limit); |
| print_word_string(word); |
| tprintf(", rating=%4.2f, certainty=%4.2f)\n", rating, certainty); |
| } |
| |
| /* Check for EOW */ |
| if (1 + char_choice_index == array_count (choices) + hyphen_char_choice_size()) { |
| word_ending = TRUE; |
| } |
| |
| if (char_choice_index < array_count (choices) + hyphen_char_choice_size()) { |
| prevchar = NULL; |
| iterate_list (c, (CHOICES) array_index (choices, |
| char_choice_index - hyphen_char_choice_size())) { |
| append_next_choice (dawg, node, permuter, word, unichar_lengths, |
| unichar_offsets, choices, char_choice_index, |
| word_index, (A_CHOICE *) first_node (c), |
| prevchar != NULL ? prevchar : "", limit, |
| rating, certainty, rating_array, certainty_array, |
| word_ending, last_word, prev_char_frag_info, |
| fragment_lengths, &result); |
| prevchar = best_string (c); |
| } |
| } |
| |
| if (result && (segment_dawg_debug == 1)) |
| print_choices ("dawg_permute", result); |
| |
| return (result); |
| } |
| |
| /********************************************************************** |
| * dawg_permute_and_select |
| * |
| * Use a DAWG type data structure to enumerate all the valid strings |
| * in some gramar. Compare each of the choices against the best choice |
| * so far. Update the best choice if needed. |
| **********************************************************************/ |
| void Dict::dawg_permute_and_select(const char *string, |
| EDGE_ARRAY dawg, |
| char permuter, |
| CHOICES_LIST character_choices, |
| A_CHOICE *best_choice) { |
| CHOICES result = NIL; |
| char word[UNICHAR_LEN * MAX_WERD_LENGTH + 1]; |
| char unichar_lengths[MAX_WERD_LENGTH + 1]; |
| int unichar_offsets[MAX_WERD_LENGTH + 1]; |
| float certainty_array[MAX_WERD_LENGTH + 1]; |
| float rating_array[MAX_WERD_LENGTH + 1]; |
| char fragment_lengths[MAX_WERD_LENGTH + 1]; // num fragments from which |
| // each char was constructed |
| float rating; |
| int char_choice_index = 0; |
| int word_index = 0; |
| NODE_REF dawg_node = 0; |
| |
| /* Pruning margin ratio */ |
| rating_margin = segment_penalty_dict_punc_bad / segment_penalty_dict_punc_ok; |
| |
| word[0] = '\0'; |
| unichar_lengths[0] = 0; |
| fragment_lengths[0] = 0; |
| unichar_offsets[0] = 0; |
| rating = class_rating (best_choice); |
| |
| for (int i = 0; i < MAX_WERD_LENGTH + 1; ++i) { |
| rating_array[i] = NO_RATING; |
| } |
| |
| if (!is_last_word () && hyphen_string) { |
| strcpy(word, hyphen_string); |
| strcpy(unichar_lengths, hyphen_unichar_lengths); |
| strcpy(fragment_lengths, hyphen_fragment_lengths); |
| memcpy(unichar_offsets, hyphen_unichar_offsets, |
| (hyphen_base_size()) * sizeof (int)); |
| unichar_offsets[hyphen_base_size()] = |
| unichar_offsets[hyphen_base_size() - 1] + |
| unichar_lengths[hyphen_base_size() - 1]; |
| char_choice_index = hyphen_char_choice_size(); |
| word_index = strlen (hyphen_unichar_lengths); |
| if (permuter == SYSTEM_DAWG_PERM) |
| // Until dawg is a class, it is only safe to use set_hyphen_word |
| // on a single dawg type, as it saves permuter state to use on another |
| // word in hyphen_state, and this *must* apply to the same dawg. |
| dawg_node = hyphen_state; |
| } |
| |
| result = dawg_permute (dawg, dawg_node, permuter, character_choices, |
| char_choice_index, word_index, &rating, word, unichar_lengths, |
| unichar_offsets, 0.0, 0.0, rating_array, certainty_array, |
| is_last_word(), NULL, fragment_lengths); |
| |
| if (display_ratings && result) { |
| print_choices(string, result); |
| } |
| |
| while (result != NIL) { |
| if (best_rating (result) < class_rating (best_choice)) { |
| clone_choice (best_choice, (A_CHOICE *) first_node (result)); |
| } |
| free_choice (first_node (result)); |
| pop_off(result); |
| } |
| } |
| |
| |
| /********************************************************************** |
| * init_permdawg |
| * |
| * Initialize the variables needed by this file. |
| **********************************************************************/ |
| void Dict::init_permdawg() { |
| STRING name; |
| name = getImage()->getCCUtil()->language_data_path_prefix; |
| name += "freq-dawg"; |
| frequent_words = read_squished_dawg(name.string()); |
| } |
| |
| void Dict::end_permdawg() { |
| memfree(frequent_words); |
| frequent_words = NULL; |
| } |
| |
| |
| /********************************************************************** |
| * test_freq_words() |
| * |
| * Tests a word against the frequent word dawg |
| **********************************************************************/ |
| int Dict::test_freq_words(const char *word) { |
| return (word_in_dawg (frequent_words, word)); |
| } |
| } // namespace tesseract |
