tesseract  5.0.0-alpha-619-ge9db
trie.cpp
Go to the documentation of this file.
1 /******************************************************************************
2  *
3  * File: trie.cpp (Formerly trie.c)
4  * Description: Functions to build a trie data structure.
5  * Author: Mark Seaman, OCR Technology
6  *
7  * (c) Copyright 1987, Hewlett-Packard Company.
8  ** Licensed under the Apache License, Version 2.0 (the "License");
9  ** you may not use this file except in compliance with the License.
10  ** You may obtain a copy of the License at
11  ** http://www.apache.org/licenses/LICENSE-2.0
12  ** Unless required by applicable law or agreed to in writing, software
13  ** distributed under the License is distributed on an "AS IS" BASIS,
14  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  ** See the License for the specific language governing permissions and
16  ** limitations under the License.
17  *
18  *****************************************************************************/
19 /*----------------------------------------------------------------------
20  I n c l u d e s
21 ----------------------------------------------------------------------*/
22 
23 #include "trie.h"
24 
25 #include "callcpp.h"
26 #include "dawg.h"
27 #include "dict.h"
29 #include <tesseract/helpers.h>
30 #include "kdpair.h"
31 
32 namespace tesseract {
33 
34 const char kDoNotReverse[] = "RRP_DO_NO_REVERSE";
35 const char kReverseIfHasRTL[] = "RRP_REVERSE_IF_HAS_RTL";
36 const char kForceReverse[] = "RRP_FORCE_REVERSE";
37 
38 const char * const RTLReversePolicyNames[] = {
42 };
43 
44 const char Trie::kAlphaPatternUnicode[] = "\u2000";
45 const char Trie::kDigitPatternUnicode[] = "\u2001";
46 const char Trie::kAlphanumPatternUnicode[] = "\u2002";
47 const char Trie::kPuncPatternUnicode[] = "\u2003";
48 const char Trie::kLowerPatternUnicode[] = "\u2004";
49 const char Trie::kUpperPatternUnicode[] = "\u2005";
50 
51 const char *Trie::get_reverse_policy_name(RTLReversePolicy reverse_policy) {
52  return RTLReversePolicyNames[reverse_policy];
53 }
54 
55 // Reset the Trie to empty.
56 void Trie::clear() {
58  nodes_.clear();
60  num_edges_ = 0;
61  new_dawg_node(); // Need to allocate node 0.
62 }
63 
64 bool Trie::edge_char_of(NODE_REF node_ref, NODE_REF next_node,
65  int direction, bool word_end, UNICHAR_ID unichar_id,
66  EDGE_RECORD **edge_ptr, EDGE_INDEX *edge_index) const {
67  if (debug_level_ == 3) {
68  tprintf("edge_char_of() given node_ref " REFFORMAT " next_node " REFFORMAT
69  " direction %d word_end %d unichar_id %d, exploring node:\n",
70  node_ref, next_node, direction, word_end, unichar_id);
71  if (node_ref != NO_EDGE) {
72  print_node(node_ref, nodes_[node_ref]->forward_edges.size());
73  }
74  }
75  if (node_ref == NO_EDGE) return false;
76  assert(node_ref < nodes_.size());
77  EDGE_VECTOR &vec = (direction == FORWARD_EDGE) ?
78  nodes_[node_ref]->forward_edges : nodes_[node_ref]->backward_edges;
79  int vec_size = vec.size();
80  if (node_ref == 0 && direction == FORWARD_EDGE) { // binary search
81  EDGE_INDEX start = 0;
82  EDGE_INDEX end = vec_size - 1;
83  EDGE_INDEX k;
84  int compare;
85  while (start <= end) {
86  k = (start + end) >> 1; // (start + end) / 2
87  compare = given_greater_than_edge_rec(next_node, word_end,
88  unichar_id, vec[k]);
89  if (compare == 0) { // given == vec[k]
90  *edge_ptr = &(vec[k]);
91  *edge_index = k;
92  return true;
93  } else if (compare == 1) { // given > vec[k]
94  start = k + 1;
95  } else { // given < vec[k]
96  end = k - 1;
97  }
98  }
99  } else { // linear search
100  for (int i = 0; i < vec_size; ++i) {
101  EDGE_RECORD &edge_rec = vec[i];
102  if (edge_rec_match(next_node, word_end, unichar_id,
103  next_node_from_edge_rec(edge_rec),
104  end_of_word_from_edge_rec(edge_rec),
105  unichar_id_from_edge_rec(edge_rec))) {
106  *edge_ptr = &(edge_rec);
107  *edge_index = i;
108  return true;
109  }
110  }
111  }
112  return false; // not found
113 }
114 
115 bool Trie::add_edge_linkage(NODE_REF node1, NODE_REF node2, bool marker_flag,
116  int direction, bool word_end,
117  UNICHAR_ID unichar_id) {
118  EDGE_VECTOR *vec = (direction == FORWARD_EDGE) ?
119  &(nodes_[node1]->forward_edges) : &(nodes_[node1]->backward_edges);
120  int search_index;
121  if (node1 == 0 && direction == FORWARD_EDGE) {
122  search_index = 0; // find the index to make the add sorted
123  while (search_index < vec->size() &&
124  given_greater_than_edge_rec(node2, word_end, unichar_id,
125  (*vec)[search_index]) == 1) {
126  search_index++;
127  }
128  } else {
129  search_index = vec->size(); // add is unsorted, so index does not matter
130  }
131  EDGE_RECORD edge_rec;
132  link_edge(&edge_rec, node2, marker_flag, direction, word_end, unichar_id);
133  if (node1 == 0 && direction == BACKWARD_EDGE &&
135  EDGE_INDEX edge_index = root_back_freelist_.pop_back();
136  (*vec)[edge_index] = edge_rec;
137  } else if (search_index < vec->size()) {
138  vec->insert(edge_rec, search_index);
139  } else {
140  vec->push_back(edge_rec);
141  }
142  if (debug_level_ > 1) {
143  tprintf("new edge in nodes_[" REFFORMAT "]: ", node1);
144  print_edge_rec(edge_rec);
145  tprintf("\n");
146  }
147  num_edges_++;
148  return true;
149 }
150 
151 void Trie::add_word_ending(EDGE_RECORD *edge_ptr,
152  NODE_REF the_next_node,
153  bool marker_flag,
154  UNICHAR_ID unichar_id) {
155  EDGE_RECORD *back_edge_ptr;
156  EDGE_INDEX back_edge_index;
157  ASSERT_HOST(edge_char_of(the_next_node, NO_EDGE, BACKWARD_EDGE, false,
158  unichar_id, &back_edge_ptr, &back_edge_index));
159  if (marker_flag) {
160  *back_edge_ptr |= (MARKER_FLAG << flag_start_bit_);
161  *edge_ptr |= (MARKER_FLAG << flag_start_bit_);
162  }
163  // Mark both directions as end of word.
164  *back_edge_ptr |= (WERD_END_FLAG << flag_start_bit_);
165  *edge_ptr |= (WERD_END_FLAG << flag_start_bit_);
166 }
167 
168 bool Trie::add_word_to_dawg(const WERD_CHOICE &word,
169  const GenericVector<bool> *repetitions) {
170  if (word.length() <= 0) return false; // can't add empty words
171  if (repetitions != nullptr) ASSERT_HOST(repetitions->size() == word.length());
172  // Make sure the word does not contain invalid unchar ids.
173  for (int i = 0; i < word.length(); ++i) {
174  if (word.unichar_id(i) < 0 ||
175  word.unichar_id(i) >= unicharset_size_) return false;
176  }
177 
178  EDGE_RECORD *edge_ptr;
179  NODE_REF last_node = 0;
180  NODE_REF the_next_node;
181  bool marker_flag = false;
182  EDGE_INDEX edge_index;
183  int i;
184  int32_t still_finding_chars = true;
185  int32_t word_end = false;
186  bool add_failed = false;
187  bool found;
188 
189  if (debug_level_ > 1) word.print("\nAdding word: ");
190 
191  UNICHAR_ID unichar_id;
192  for (i = 0; i < word.length() - 1; ++i) {
193  unichar_id = word.unichar_id(i);
194  marker_flag = (repetitions != nullptr) ? (*repetitions)[i] : false;
195  if (debug_level_ > 1) tprintf("Adding letter %d\n", unichar_id);
196  if (still_finding_chars) {
197  found = edge_char_of(last_node, NO_EDGE, FORWARD_EDGE, word_end,
198  unichar_id, &edge_ptr, &edge_index);
199  if (found && debug_level_ > 1) {
200  tprintf("exploring edge " REFFORMAT " in node " REFFORMAT "\n",
201  edge_index, last_node);
202  }
203  if (!found) {
204  still_finding_chars = false;
205  } else if (next_node_from_edge_rec(*edge_ptr) == 0) {
206  // We hit the end of an existing word, but the new word is longer.
207  // In this case we have to disconnect the existing word from the
208  // backwards root node, mark the current position as end-of-word
209  // and add new nodes for the increased length. Disconnecting the
210  // existing word from the backwards root node requires a linear
211  // search, so it is much faster to add the longest words first,
212  // to avoid having to come here.
213  word_end = true;
214  still_finding_chars = false;
215  remove_edge(last_node, 0, word_end, unichar_id);
216  } else {
217  // We have to add a new branch here for the new word.
218  if (marker_flag) set_marker_flag_in_edge_rec(edge_ptr);
219  last_node = next_node_from_edge_rec(*edge_ptr);
220  }
221  }
222  if (!still_finding_chars) {
223  the_next_node = new_dawg_node();
224  if (debug_level_ > 1)
225  tprintf("adding node " REFFORMAT "\n", the_next_node);
226  if (the_next_node == 0) {
227  add_failed = true;
228  break;
229  }
230  if (!add_new_edge(last_node, the_next_node,
231  marker_flag, word_end, unichar_id)) {
232  add_failed = true;
233  break;
234  }
235  word_end = false;
236  last_node = the_next_node;
237  }
238  }
239  the_next_node = 0;
240  unichar_id = word.unichar_id(i);
241  marker_flag = (repetitions != nullptr) ? (*repetitions)[i] : false;
242  if (debug_level_ > 1) tprintf("Adding letter %d\n", unichar_id);
243  if (still_finding_chars &&
244  edge_char_of(last_node, NO_EDGE, FORWARD_EDGE, false,
245  unichar_id, &edge_ptr, &edge_index)) {
246  // An extension of this word already exists in the trie, so we
247  // only have to add the ending flags in both directions.
248  add_word_ending(edge_ptr, next_node_from_edge_rec(*edge_ptr),
249  marker_flag, unichar_id);
250  } else {
251  // Add a link to node 0. All leaves connect to node 0 so the back links can
252  // be used in reduction to a dawg. This root backward node has one edge
253  // entry for every word, (except prefixes of longer words) so it is huge.
254  if (!add_failed &&
255  !add_new_edge(last_node, the_next_node, marker_flag, true, unichar_id))
256  add_failed = true;
257  }
258  if (add_failed) {
259  tprintf("Re-initializing document dictionary...\n");
260  clear();
261  return false;
262  } else {
263  return true;
264  }
265 }
266 
268  auto *node = new TRIE_NODE_RECORD();
269  nodes_.push_back(node);
270  return nodes_.size() - 1;
271 }
272 
273 // Sort function to sort words by decreasing order of length.
274 static int sort_strings_by_dec_length(const void* v1, const void* v2) {
275  const auto *s1 = static_cast<const STRING *>(v1);
276  const auto *s2 = static_cast<const STRING *>(v2);
277  return s2->length() - s1->length();
278 }
279 
280 bool Trie::read_and_add_word_list(const char *filename,
281  const UNICHARSET &unicharset,
282  Trie::RTLReversePolicy reverse_policy) {
283  GenericVector<STRING> word_list;
284  if (!read_word_list(filename, &word_list)) return false;
285  word_list.sort(sort_strings_by_dec_length);
286  return add_word_list(word_list, unicharset, reverse_policy);
287 }
288 
289 bool Trie::read_word_list(const char *filename,
290  GenericVector<STRING>* words) {
291  FILE *word_file;
292  char line_str[CHARS_PER_LINE];
293  int word_count = 0;
294 
295  word_file = fopen(filename, "rb");
296  if (word_file == nullptr) return false;
297 
298  while (fgets(line_str, sizeof(line_str), word_file) != nullptr) {
299  chomp_string(line_str); // remove newline
300  STRING word_str(line_str);
301  ++word_count;
302  if (debug_level_ && word_count % 10000 == 0)
303  tprintf("Read %d words so far\n", word_count);
304  words->push_back(word_str);
305  }
306  if (debug_level_)
307  tprintf("Read %d words total.\n", word_count);
308  fclose(word_file);
309  return true;
310 }
311 
313  const UNICHARSET &unicharset,
314  Trie::RTLReversePolicy reverse_policy) {
315  for (int i = 0; i < words.size(); ++i) {
316  WERD_CHOICE word(words[i].c_str(), unicharset);
317  if (word.length() == 0 || word.contains_unichar_id(INVALID_UNICHAR_ID))
318  continue;
319  if ((reverse_policy == RRP_REVERSE_IF_HAS_RTL &&
320  word.has_rtl_unichar_id()) ||
321  reverse_policy == RRP_FORCE_REVERSE) {
323  }
324  if (!word_in_dawg(word)) {
325  add_word_to_dawg(word);
326  if (!word_in_dawg(word)) {
327  tprintf("Error: word '%s' not in DAWG after adding it\n",
328  words[i].c_str());
329  return false;
330  }
331  }
332  }
333  return true;
334 }
335 
336 void Trie::initialize_patterns(UNICHARSET *unicharset) {
343  unicharset->unichar_insert(kPuncPatternUnicode);
349  initialized_patterns_ = true;
350  unicharset_size_ = unicharset->size();
351 }
352 
354  const UNICHARSET &unicharset,
355  GenericVector<UNICHAR_ID> *vec) const {
356  bool is_alpha = unicharset.get_isalpha(unichar_id);
357  if (is_alpha) {
360  if (unicharset.get_islower(unichar_id)) {
362  } else if (unicharset.get_isupper(unichar_id)) {
364  }
365  }
366  if (unicharset.get_isdigit(unichar_id)) {
368  if (!is_alpha) vec->push_back(alphanum_pattern_);
369  }
370  if (unicharset.get_ispunctuation(unichar_id)) {
371  vec->push_back(punc_pattern_);
372  }
373 }
374 
376  if (ch == 'c') {
377  return alpha_pattern_;
378  } else if (ch == 'd') {
379  return digit_pattern_;
380  } else if (ch == 'n') {
381  return alphanum_pattern_;
382  } else if (ch == 'p') {
383  return punc_pattern_;
384  } else if (ch == 'a') {
385  return lower_pattern_;
386  } else if (ch == 'A') {
387  return upper_pattern_;
388  } else {
389  return INVALID_UNICHAR_ID;
390  }
391 }
392 
393 bool Trie::read_pattern_list(const char *filename,
394  const UNICHARSET &unicharset) {
395  if (!initialized_patterns_) {
396  tprintf("please call initialize_patterns() before read_pattern_list()\n");
397  return false;
398  }
399 
400  FILE *pattern_file = fopen(filename, "rb");
401  if (pattern_file == nullptr) {
402  tprintf("Error opening pattern file %s\n", filename);
403  return false;
404  }
405 
406  int pattern_count = 0;
407  char string[CHARS_PER_LINE];
408  while (fgets(string, CHARS_PER_LINE, pattern_file) != nullptr) {
409  chomp_string(string); // remove newline
410  // Parse the pattern and construct a unichar id vector.
411  // Record the number of repetitions of each unichar in the parallel vector.
412  WERD_CHOICE word(&unicharset);
413  GenericVector<bool> repetitions_vec;
414  const char *str_ptr = string;
415  int step = unicharset.step(str_ptr);
416  bool failed = false;
417  while (step > 0) {
418  UNICHAR_ID curr_unichar_id = INVALID_UNICHAR_ID;
419  if (step == 1 && *str_ptr == '\\') {
420  ++str_ptr;
421  if (*str_ptr == '\\') { // regular '\' unichar that was escaped
422  curr_unichar_id = unicharset.unichar_to_id(str_ptr, step);
423  } else {
424  if (word.length() < kSaneNumConcreteChars) {
425  tprintf("Please provide at least %d concrete characters at the"
426  " beginning of the pattern\n", kSaneNumConcreteChars);
427  failed = true;
428  break;
429  }
430  // Parse character class from expression.
431  curr_unichar_id = character_class_to_pattern(*str_ptr);
432  }
433  } else {
434  curr_unichar_id = unicharset.unichar_to_id(str_ptr, step);
435  }
436  if (curr_unichar_id == INVALID_UNICHAR_ID) {
437  failed = true;
438  break; // failed to parse this pattern
439  }
440  word.append_unichar_id(curr_unichar_id, 1, 0.0, 0.0);
441  repetitions_vec.push_back(false);
442  str_ptr += step;
443  step = unicharset.step(str_ptr);
444  // Check if there is a repetition pattern specified after this unichar.
445  if (step == 1 && *str_ptr == '\\' && *(str_ptr+1) == '*') {
446  repetitions_vec[repetitions_vec.size()-1] = true;
447  str_ptr += 2;
448  step = unicharset.step(str_ptr);
449  }
450  }
451  if (failed) {
452  tprintf("Invalid user pattern %s\n", string);
453  continue;
454  }
455  // Insert the pattern into the trie.
456  if (debug_level_ > 2) {
457  tprintf("Inserting expanded user pattern %s\n",
458  word.debug_string().c_str());
459  }
460  if (!this->word_in_dawg(word)) {
461  this->add_word_to_dawg(word, &repetitions_vec);
462  if (!this->word_in_dawg(word)) {
463  tprintf("Error: failed to insert pattern '%s'\n", string);
464  }
465  }
466  ++pattern_count;
467  }
468  if (debug_level_) {
469  tprintf("Read %d valid patterns from %s\n", pattern_count, filename);
470  }
471  fclose(pattern_file);
472  return true;
473 }
474 
475 void Trie::remove_edge_linkage(NODE_REF node1, NODE_REF node2, int direction,
476  bool word_end, UNICHAR_ID unichar_id) {
477  EDGE_RECORD *edge_ptr = nullptr;
478  EDGE_INDEX edge_index = 0;
479  ASSERT_HOST(edge_char_of(node1, node2, direction, word_end,
480  unichar_id, &edge_ptr, &edge_index));
481  if (debug_level_ > 1) {
482  tprintf("removed edge in nodes_[" REFFORMAT "]: ", node1);
483  print_edge_rec(*edge_ptr);
484  tprintf("\n");
485  }
486  if (direction == FORWARD_EDGE) {
487  nodes_[node1]->forward_edges.remove(edge_index);
488  } else if (node1 == 0) {
489  KillEdge(&nodes_[node1]->backward_edges[edge_index]);
491  } else {
492  nodes_[node1]->backward_edges.remove(edge_index);
493  }
494  --num_edges_;
495 }
496 
497 // Some optimizations employed in add_word_to_dawg and trie_to_dawg:
498 // 1 Avoid insertion sorting or bubble sorting the tail root node
499 // (back links on node 0, a list of all the leaves.). The node is
500 // huge, and sorting it with n^2 time is terrible.
501 // 2 Avoid using GenericVector::remove on the tail root node.
502 // (a) During add of words to the trie, zero-out the unichars and
503 // keep a freelist of spaces to re-use.
504 // (b) During reduction, just zero-out the unichars of deleted back
505 // links, skipping zero entries while searching.
506 // 3 Avoid linear search of the tail root node. This has to be done when
507 // a suffix is added to an existing word. Adding words by decreasing
508 // length avoids this problem entirely. Words can still be added in
509 // any order, but it is faster to add the longest first.
510 SquishedDawg *Trie::trie_to_dawg() {
511  root_back_freelist_.clear(); // Will be invalided by trie_to_dawg.
512  if (debug_level_ > 2) {
513  print_all("Before reduction:", MAX_NODE_EDGES_DISPLAY);
514  }
515  auto reduced_nodes = new bool[nodes_.size()];
516  for (int i = 0; i < nodes_.size(); i++) reduced_nodes[i] = false;
517  this->reduce_node_input(0, reduced_nodes);
518  delete[] reduced_nodes;
519 
520  if (debug_level_ > 2) {
521  print_all("After reduction:", MAX_NODE_EDGES_DISPLAY);
522  }
523  // Build a translation map from node indices in nodes_ vector to
524  // their target indices in EDGE_ARRAY.
525  auto *node_ref_map = new NODE_REF[nodes_.size() + 1];
526  int i, j;
527  node_ref_map[0] = 0;
528  for (i = 0; i < nodes_.size(); ++i) {
529  node_ref_map[i+1] = node_ref_map[i] + nodes_[i]->forward_edges.size();
530  }
531  int num_forward_edges = node_ref_map[i];
532 
533  // Convert nodes_ vector into EDGE_ARRAY translating the next node references
534  // in edges using node_ref_map. Empty nodes and backward edges are dropped.
535  auto edge_array = new EDGE_RECORD[num_forward_edges];
536  EDGE_ARRAY edge_array_ptr = edge_array;
537  for (i = 0; i < nodes_.size(); ++i) {
538  TRIE_NODE_RECORD *node_ptr = nodes_[i];
539  int end = node_ptr->forward_edges.size();
540  for (j = 0; j < end; ++j) {
541  EDGE_RECORD &edge_rec = node_ptr->forward_edges[j];
542  NODE_REF node_ref = next_node_from_edge_rec(edge_rec);
543  ASSERT_HOST(node_ref < nodes_.size());
544  UNICHAR_ID unichar_id = unichar_id_from_edge_rec(edge_rec);
545  link_edge(edge_array_ptr, node_ref_map[node_ref], false, FORWARD_EDGE,
546  end_of_word_from_edge_rec(edge_rec), unichar_id);
547  if (j == end - 1) set_marker_flag_in_edge_rec(edge_array_ptr);
548  ++edge_array_ptr;
549  }
550  }
551  delete[] node_ref_map;
552 
553  return new SquishedDawg(edge_array, num_forward_edges, type_, lang_,
555 }
556 
558  const EDGE_RECORD &edge1,
559  const EDGE_RECORD &edge2) {
560  if (debug_level_ > 1) {
561  tprintf("\nCollapsing node %" PRIi64 ":\n", node);
563  tprintf("Candidate edges: ");
564  print_edge_rec(edge1);
565  tprintf(", ");
566  print_edge_rec(edge2);
567  tprintf("\n\n");
568  }
569  NODE_REF next_node1 = next_node_from_edge_rec(edge1);
570  NODE_REF next_node2 = next_node_from_edge_rec(edge2);
571  TRIE_NODE_RECORD *next_node2_ptr = nodes_[next_node2];
572  // Translate all edges going to/from next_node2 to go to/from next_node1.
573  EDGE_RECORD *edge_ptr = nullptr;
574  EDGE_INDEX edge_index;
575  int i;
576  // The backward link in node to next_node2 will be zeroed out by the caller.
577  // Copy all the backward links in next_node2 to node next_node1
578  for (i = 0; i < next_node2_ptr->backward_edges.size(); ++i) {
579  const EDGE_RECORD &bkw_edge = next_node2_ptr->backward_edges[i];
580  NODE_REF curr_next_node = next_node_from_edge_rec(bkw_edge);
581  UNICHAR_ID curr_unichar_id = unichar_id_from_edge_rec(bkw_edge);
582  int curr_word_end = end_of_word_from_edge_rec(bkw_edge);
583  bool marker_flag = marker_flag_from_edge_rec(bkw_edge);
584  add_edge_linkage(next_node1, curr_next_node, marker_flag, BACKWARD_EDGE,
585  curr_word_end, curr_unichar_id);
586  // Relocate the corresponding forward edge in curr_next_node
587  ASSERT_HOST(edge_char_of(curr_next_node, next_node2, FORWARD_EDGE,
588  curr_word_end, curr_unichar_id,
589  &edge_ptr, &edge_index));
590  set_next_node_in_edge_rec(edge_ptr, next_node1);
591  }
592  int next_node2_num_edges = (next_node2_ptr->forward_edges.size() +
593  next_node2_ptr->backward_edges.size());
594  if (debug_level_ > 1) {
595  tprintf("removed %d edges from node " REFFORMAT "\n",
596  next_node2_num_edges, next_node2);
597  }
598  next_node2_ptr->forward_edges.clear();
599  next_node2_ptr->backward_edges.clear();
600  num_edges_ -= next_node2_num_edges;
601  return true;
602 }
603 
605  UNICHAR_ID unichar_id,
606  NODE_REF node,
607  EDGE_VECTOR* backward_edges,
608  NODE_MARKER reduced_nodes) {
609  if (debug_level_ > 1)
610  tprintf("reduce_lettered_edges(edge=" REFFORMAT ")\n", edge_index);
611  // Compare each of the edge pairs with the given unichar_id.
612  bool did_something = false;
613  for (int i = edge_index; i < backward_edges->size() - 1; ++i) {
614  // Find the first edge that can be eliminated.
615  UNICHAR_ID curr_unichar_id = INVALID_UNICHAR_ID;
616  while (i < backward_edges->size()) {
617  if (!DeadEdge((*backward_edges)[i])) {
618  curr_unichar_id = unichar_id_from_edge_rec((*backward_edges)[i]);
619  if (curr_unichar_id != unichar_id) return did_something;
620  if (can_be_eliminated((*backward_edges)[i])) break;
621  }
622  ++i;
623  }
624  if (i == backward_edges->size()) break;
625  const EDGE_RECORD &edge_rec = (*backward_edges)[i];
626  // Compare it to the rest of the edges with the given unichar_id.
627  for (int j = i + 1; j < backward_edges->size(); ++j) {
628  const EDGE_RECORD &next_edge_rec = (*backward_edges)[j];
629  if (DeadEdge(next_edge_rec)) continue;
630  UNICHAR_ID next_id = unichar_id_from_edge_rec(next_edge_rec);
631  if (next_id != unichar_id) break;
632  if (end_of_word_from_edge_rec(next_edge_rec) ==
633  end_of_word_from_edge_rec(edge_rec) &&
634  can_be_eliminated(next_edge_rec) &&
635  eliminate_redundant_edges(node, edge_rec, next_edge_rec)) {
636  reduced_nodes[next_node_from_edge_rec(edge_rec)] = false;
637  did_something = true;
638  KillEdge(&(*backward_edges)[j]);
639  }
640  }
641  }
642  return did_something;
643 }
644 
645 void Trie::sort_edges(EDGE_VECTOR *edges) {
646  int num_edges = edges->size();
647  if (num_edges <= 1) return;
649  sort_vec.reserve(num_edges);
650  for (int i = 0; i < num_edges; ++i) {
651  sort_vec.push_back(KDPairInc<UNICHAR_ID, EDGE_RECORD>(
652  unichar_id_from_edge_rec((*edges)[i]), (*edges)[i]));
653  }
654  sort_vec.sort();
655  for (int i = 0; i < num_edges; ++i)
656  (*edges)[i] = sort_vec[i].data;
657 }
658 
660  NODE_MARKER reduced_nodes) {
661  EDGE_VECTOR &backward_edges = nodes_[node]->backward_edges;
662  sort_edges(&backward_edges);
663  if (debug_level_ > 1) {
664  tprintf("reduce_node_input(node=" REFFORMAT ")\n", node);
666  }
667 
668  EDGE_INDEX edge_index = 0;
669  while (edge_index < backward_edges.size()) {
670  if (DeadEdge(backward_edges[edge_index])) continue;
671  UNICHAR_ID unichar_id =
672  unichar_id_from_edge_rec(backward_edges[edge_index]);
673  while (reduce_lettered_edges(edge_index, unichar_id, node,
674  &backward_edges, reduced_nodes));
675  while (++edge_index < backward_edges.size()) {
676  UNICHAR_ID id = unichar_id_from_edge_rec(backward_edges[edge_index]);
677  if (!DeadEdge(backward_edges[edge_index]) && id != unichar_id) break;
678  }
679  }
680  reduced_nodes[node] = true; // mark as reduced
681 
682  if (debug_level_ > 1) {
683  tprintf("Node " REFFORMAT " after reduction:\n", node);
685  }
686 
687  for (int i = 0; i < backward_edges.size(); ++i) {
688  if (DeadEdge(backward_edges[i])) continue;
689  NODE_REF next_node = next_node_from_edge_rec(backward_edges[i]);
690  if (next_node != 0 && !reduced_nodes[next_node]) {
691  reduce_node_input(next_node, reduced_nodes);
692  }
693  }
694 }
695 
696 void Trie::print_node(NODE_REF node, int max_num_edges) const {
697  if (node == NO_EDGE) return; // nothing to print
698  TRIE_NODE_RECORD *node_ptr = nodes_[node];
699  int num_fwd = node_ptr->forward_edges.size();
700  int num_bkw = node_ptr->backward_edges.size();
701  EDGE_VECTOR *vec;
702  for (int dir = 0; dir < 2; ++dir) {
703  if (dir == 0) {
704  vec = &(node_ptr->forward_edges);
705  tprintf(REFFORMAT " (%d %d): ", node, num_fwd, num_bkw);
706  } else {
707  vec = &(node_ptr->backward_edges);
708  tprintf("\t");
709  }
710  int i;
711  for (i = 0; (dir == 0 ? i < num_fwd : i < num_bkw) &&
712  i < max_num_edges; ++i) {
713  if (DeadEdge((*vec)[i])) continue;
714  print_edge_rec((*vec)[i]);
715  tprintf(" ");
716  }
717  if (dir == 0 ? i < num_fwd : i < num_bkw) tprintf("...");
718  tprintf("\n");
719  }
720 }
721 
722 } // namespace tesseract
string
std::string string
Definition: equationdetect_test.cc:21
GenericVector::delete_data_pointers
void delete_data_pointers()
Definition: genericvector.h:872
GenericVector::remove
void remove(int index)
Definition: genericvector.h:765
TRIE_NODE_RECORD::forward_edges
EDGE_VECTOR forward_edges
Definition: trie.h:41
tesseract::Trie::edge_char_of
EDGE_REF edge_char_of(NODE_REF node_ref, UNICHAR_ID unichar_id, bool word_end) const override
Definition: trie.h:96
tesseract::Trie::remove_edge
void remove_edge(NODE_REF node1, NODE_REF node2, bool word_end, UNICHAR_ID unichar_id)
Definition: trie.h:373
tesseract::Trie::kLowerPatternUnicode
static const char kLowerPatternUnicode[]
Definition: trie.h:71
tesseract::Trie::upper_pattern_
UNICHAR_ID upper_pattern_
Definition: trie.h:424
UNICHARSET::get_islower
bool get_islower(UNICHAR_ID unichar_id) const
Definition: unicharset.h:488
tesseract::Trie::kDigitPatternUnicode
static const char kDigitPatternUnicode[]
Definition: trie.h:68
tesseract::Trie::character_class_to_pattern
UNICHAR_ID character_class_to_pattern(char ch)
Definition: trie.cpp:390
dict.h
tesseract::Trie::kAlphanumPatternUnicode
static const char kAlphanumPatternUnicode[]
Definition: trie.h:69
tesseract::kReverseIfHasRTL
const char kReverseIfHasRTL[]
Definition: trie.cpp:50
WERD_CHOICE::unichar_id
UNICHAR_ID unichar_id(int index) const
Definition: ratngs.h:303
tesseract::Dawg::flag_start_bit_
int flag_start_bit_
Definition: dawg.h:307
UNICHARSET::get_isdigit
bool get_isdigit(UNICHAR_ID unichar_id) const
Definition: unicharset.h:502
WERD_CHOICE
Definition: ratngs.h:261
UNICHARSET::get_isalpha
bool get_isalpha(UNICHAR_ID unichar_id) const
Definition: unicharset.h:481
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:87
tesseract::Trie::initialize_patterns
void initialize_patterns(UNICHARSET *unicharset)
Definition: trie.cpp:351
EDGE_INDEX
int64_t EDGE_INDEX
Definition: trie.h:36
GenericVector::insert
void insert(const T &t, int index)
Definition: genericvector.h:750
tesseract::Dawg::next_node_from_edge_rec
NODE_REF next_node_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns the next node visited by following this edge.
Definition: dawg.h:207
WERD_CHOICE::contains_unichar_id
bool contains_unichar_id(UNICHAR_ID unichar_id) const
Definition: ratngs.cpp:328
tesseract::Trie::read_pattern_list
bool read_pattern_list(const char *filename, const UNICHARSET &unicharset)
Definition: trie.cpp:408
tesseract::Dawg::end_of_word_from_edge_rec
bool end_of_word_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns true if this edge marks the end of a word.
Definition: dawg.h:220
tesseract::Dawg::set_next_node_in_edge_rec
void set_next_node_in_edge_rec(EDGE_RECORD *edge_rec, EDGE_REF value)
Sets the next node link for this edge in the Dawg.
Definition: dawg.h:229
STRING
Definition: strngs.h:45
EDGE_ARRAY
EDGE_RECORD * EDGE_ARRAY
Definition: dawg.h:48
tesseract::Trie::kPuncPatternUnicode
static const char kPuncPatternUnicode[]
Definition: trie.h:70
tesseract::Trie::kAlphaPatternUnicode
static const char kAlphaPatternUnicode[]
Definition: trie.h:67
tesseract::Trie::print_node
void print_node(NODE_REF node, int max_num_edges) const override
Definition: trie.cpp:711
tesseract::Trie::alphanum_pattern_
UNICHAR_ID alphanum_pattern_
Definition: trie.h:421
tesseract::Trie::next_node
NODE_REF next_node(EDGE_REF edge_ref) const override
Definition: trie.h:125
tesseract::Trie::add_word_ending
void add_word_ending(EDGE_RECORD *edge, NODE_REF the_next_node, bool repeats, UNICHAR_ID unichar_id)
Definition: trie.cpp:166
tesseract::kForceReverse
const char kForceReverse[]
Definition: trie.cpp:51
tesseract::Dawg::given_greater_than_edge_rec
int given_greater_than_edge_rec(NODE_REF next_node, bool word_end, UNICHAR_ID unichar_id, const EDGE_RECORD &edge_rec) const
Definition: dawg.h:245
UNICHARSET::step
int step(const char *str) const
Definition: unicharset.cpp:232
tesseract::Trie::add_new_edge
bool add_new_edge(NODE_REF node1, NODE_REF node2, bool repeats, bool word_end, UNICHAR_ID unichar_id)
Definition: trie.h:348
tesseract::Trie::reduce_node_input
void reduce_node_input(NODE_REF node, NODE_MARKER reduced_nodes)
Definition: trie.cpp:674
FORWARD_EDGE
#define FORWARD_EDGE
Definition: dawg.h:79
tesseract::Dawg::unichar_id_from_edge_rec
UNICHAR_ID unichar_id_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns UNICHAR_ID recorded in this edge.
Definition: dawg.h:224
tesseract::Trie::kSaneNumConcreteChars
static const int kSaneNumConcreteChars
Definition: trie.h:63
UNICHARSET::get_ispunctuation
bool get_ispunctuation(UNICHAR_ID unichar_id) const
Definition: unicharset.h:509
tesseract::Dawg::perm_
PermuterType perm_
Permuter code that should be used if the word is found in this Dawg.
Definition: dawg.h:298
tesseract::Trie::read_word_list
bool read_word_list(const char *filename, GenericVector< STRING > *words)
Definition: trie.cpp:304
WERD_CHOICE::reverse_and_mirror_unichar_ids
void reverse_and_mirror_unichar_ids()
Definition: ratngs.cpp:367
MAX_NODE_EDGES_DISPLAY
#define MAX_NODE_EDGES_DISPLAY
Definition: dawg.h:81
genericvector.h
GenericVector::push_back
int push_back(T object)
Definition: genericvector.h:799
tesseract::Trie::print_all
void print_all(const char *msg, int max_num_edges)
Definition: trie.h:326
tesseract::Dawg::edge_rec_match
bool edge_rec_match(NODE_REF next_node, bool word_end, UNICHAR_ID unichar_id, NODE_REF other_next_node, bool other_word_end, UNICHAR_ID other_unichar_id) const
Definition: dawg.h:266
tesseract::Trie::alpha_pattern_
UNICHAR_ID alpha_pattern_
Definition: trie.h:419
tesseract::Trie::initialized_patterns_
bool initialized_patterns_
Definition: trie.h:425
tesseract::Trie::punc_pattern_
UNICHAR_ID punc_pattern_
Definition: trie.h:422
STRING::c_str
const char * c_str() const
Definition: strngs.cpp:192
dawg.h
chomp_string
void chomp_string(char *str)
Definition: helpers.h:75
tesseract::Trie::clear
void clear()
Definition: trie.cpp:71
tesseract::Trie::digit_pattern_
UNICHAR_ID digit_pattern_
Definition: trie.h:420
tesseract::Trie::sort_edges
void sort_edges(EDGE_VECTOR *edges)
Definition: trie.cpp:660
tesseract::Trie::RRP_REVERSE_IF_HAS_RTL
Definition: trie.h:58
tesseract::Trie::link_edge
void link_edge(EDGE_RECORD *edge, NODE_REF nxt, bool repeats, int direction, bool word_end, UNICHAR_ID unichar_id)
Definition: trie.h:298
EDGE_RECORD
uint64_t EDGE_RECORD
Definition: dawg.h:47
UNICHARSET::unichar_to_id
UNICHAR_ID unichar_to_id(const char *const unichar_repr) const
Definition: unicharset.cpp:209
tesseract::Dawg::debug_level_
int debug_level_
Definition: dawg.h:310
tesseract::Dawg::marker_flag_from_edge_rec
bool marker_flag_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns the marker flag of this edge.
Definition: dawg.h:211
GenericVector::empty
bool empty() const
Definition: genericvector.h:86
tesseract::Trie::trie_to_dawg
SquishedDawg * trie_to_dawg()
Definition: trie.cpp:525
UNICHARSET
Definition: unicharset.h:145
tesseract::Trie::eliminate_redundant_edges
bool eliminate_redundant_edges(NODE_REF node, const EDGE_RECORD &edge1, const EDGE_RECORD &edge2)
Definition: trie.cpp:572
tesseract::Trie::add_word_to_dawg
bool add_word_to_dawg(const WERD_CHOICE &word, const GenericVector< bool > *repetitions)
Definition: trie.cpp:183
helpers.h
kdpair.h
tesseract::Trie::RTLReversePolicy
RTLReversePolicy
Definition: trie.h:56
tesseract
Definition: baseapi.h:65
WERD_CHOICE::debug_string
const STRING debug_string() const
Definition: ratngs.h:493
tesseract::kDoNotReverse
const char kDoNotReverse[]
Definition: trie.cpp:49
REFFORMAT
#define REFFORMAT
Definition: dawg.h:87
GenericVector::pop_back
T pop_back()
Definition: genericvector.h:734
callcpp.h
tesseract::Trie::KillEdge
void KillEdge(EDGE_RECORD *edge_rec) const
Definition: trie.h:146
tesseract::Dawg::word_in_dawg
bool word_in_dawg(const WERD_CHOICE &word) const
Returns true if the given word is in the Dawg.
Definition: dawg.cpp:78
UNICHAR_ID
int UNICHAR_ID
Definition: unichar.h:36
TRIE_NODE_RECORD
Definition: trie.h:40
GenericVector< EDGE_RECORD >
GenericVector::reserve
void reserve(int size)
Definition: genericvector.h:679
WERD_CHOICE::has_rtl_unichar_id
bool has_rtl_unichar_id() const
Definition: ratngs.cpp:433
tesseract::Trie::nodes_
TRIE_NODES nodes_
Definition: trie.h:411
tesseract::Trie::kUpperPatternUnicode
static const char kUpperPatternUnicode[]
Definition: trie.h:72
UNICHARSET::get_isupper
bool get_isupper(UNICHAR_ID unichar_id) const
Definition: unicharset.h:495
tesseract::Dawg::set_marker_flag_in_edge_rec
void set_marker_flag_in_edge_rec(EDGE_RECORD *edge_rec)
Sets this edge record to be the last one in a sequence of edges.
Definition: dawg.h:235
tesseract::Dawg::lang_
STRING lang_
Definition: dawg.h:295
WERD_CHOICE::print
void print() const
Definition: ratngs.h:568
WERD_CHOICE::length
int length() const
Definition: ratngs.h:291
tesseract::Trie::remove_edge_linkage
void remove_edge_linkage(NODE_REF node1, NODE_REF node2, int direction, bool word_end, UNICHAR_ID unichar_id)
Definition: trie.cpp:490
MARKER_FLAG
#define MARKER_FLAG
Definition: dawg.h:82
tesseract::Trie::get_reverse_policy_name
static const char * get_reverse_policy_name(RTLReversePolicy reverse_policy)
Definition: trie.cpp:66
tesseract::Trie::add_edge_linkage
bool add_edge_linkage(NODE_REF node1, NODE_REF node2, bool repeats, int direction, bool word_end, UNICHAR_ID unichar_id)
Definition: trie.cpp:130
GenericVector::clear
void clear()
Definition: genericvector.h:857
tesseract::Trie::root_back_freelist_
GenericVector< EDGE_INDEX > root_back_freelist_
Definition: trie.h:413
tesseract::Trie::add_word_list
bool add_word_list(const GenericVector< STRING > &words, const UNICHARSET &unicharset, Trie::RTLReversePolicy reverse_policy)
Definition: trie.cpp:327
tesseract::Trie::unichar_id_to_patterns
void unichar_id_to_patterns(UNICHAR_ID unichar_id, const UNICHARSET &unicharset, GenericVector< UNICHAR_ID > *vec) const override
Definition: trie.cpp:368
tesseract::RTLReversePolicyNames
const char *const RTLReversePolicyNames[]
Definition: trie.cpp:53
tprintf
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:34
tesseract::Trie::print_edge_rec
void print_edge_rec(const EDGE_RECORD &edge_rec) const
Definition: trie.h:309
NODE_MARKER
bool * NODE_MARKER
Definition: trie.h:37
WERD_END_FLAG
#define WERD_END_FLAG
Definition: dawg.h:84
tesseract::Trie::can_be_eliminated
bool can_be_eliminated(const EDGE_RECORD &edge_rec)
Definition: trie.h:318
tesseract::Trie::reduce_lettered_edges
bool reduce_lettered_edges(EDGE_INDEX edge_index, UNICHAR_ID unichar_id, NODE_REF node, EDGE_VECTOR *backward_edges, NODE_MARKER reduced_nodes)
Definition: trie.cpp:619
tesseract::Trie::RRP_FORCE_REVERSE
Definition: trie.h:59
tesseract::Dawg::unicharset_size_
int unicharset_size_
Definition: dawg.h:306
GenericVector::sort
void sort()
Definition: genericvector.h:1102
CHARS_PER_LINE
#define CHARS_PER_LINE
Definition: dict.h:38
BACKWARD_EDGE
#define BACKWARD_EDGE
Definition: dawg.h:80
TRIE_NODE_RECORD::backward_edges
EDGE_VECTOR backward_edges
Definition: trie.h:42
GenericVector::size
int size() const
Definition: genericvector.h:71
tesseract::Trie::num_edges_
uint64_t num_edges_
Definition: trie.h:414
tesseract::Dawg::type_
DawgType type_
Definition: dawg.h:296
tesseract::Trie::DeadEdge
bool DeadEdge(const EDGE_RECORD &edge_rec) const
Definition: trie.h:150
UNICHARSET::unichar_insert
void unichar_insert(const char *const unichar_repr, OldUncleanUnichars old_style)
Definition: unicharset.cpp:625
tesseract::Trie::lower_pattern_
UNICHAR_ID lower_pattern_
Definition: trie.h:423
tesseract::Trie::new_dawg_node
NODE_REF new_dawg_node()
Definition: trie.cpp:282
tesseract::Trie::read_and_add_word_list
bool read_and_add_word_list(const char *filename, const UNICHARSET &unicharset, Trie::RTLReversePolicy reverse)
Definition: trie.cpp:295
UNICHARSET::size
int size() const
Definition: unicharset.h:341
WERD_CHOICE::append_unichar_id
void append_unichar_id(UNICHAR_ID unichar_id, int blob_count, float rating, float certainty)
Definition: ratngs.cpp:470
NODE_REF
int64_t NODE_REF
Definition: dawg.h:50
trie.h