tesseract  4.1.1
tesseract::Trie Class Reference

#include <trie.h>

Inheritance diagram for tesseract::Trie:
tesseract::Dawg

Public Types

enum  RTLReversePolicy { RRP_DO_NO_REVERSE, RRP_REVERSE_IF_HAS_RTL, RRP_FORCE_REVERSE }
 

Public Member Functions

 Trie (DawgType type, const STRING &lang, PermuterType perm, int unicharset_size, int debug_level)
 
 ~Trie () override
 
void clear ()
 
EDGE_REF edge_char_of (NODE_REF node_ref, UNICHAR_ID unichar_id, bool word_end) const override
 
void unichar_ids_of (NODE_REF node, NodeChildVector *vec, bool word_end) const override
 
NODE_REF next_node (EDGE_REF edge_ref) const override
 
bool end_of_word (EDGE_REF edge_ref) const override
 
UNICHAR_ID edge_letter (EDGE_REF edge_ref) const override
 
void KillEdge (EDGE_RECORD *edge_rec) const
 
bool DeadEdge (const EDGE_RECORD &edge_rec) const
 
void print_node (NODE_REF node, int max_num_edges) const override
 
SquishedDawgtrie_to_dawg ()
 
bool read_and_add_word_list (const char *filename, const UNICHARSET &unicharset, Trie::RTLReversePolicy reverse)
 
bool read_word_list (const char *filename, GenericVector< STRING > *words)
 
bool add_word_list (const GenericVector< STRING > &words, const UNICHARSET &unicharset, Trie::RTLReversePolicy reverse_policy)
 
bool read_pattern_list (const char *filename, const UNICHARSET &unicharset)
 
void initialize_patterns (UNICHARSET *unicharset)
 
void unichar_id_to_patterns (UNICHAR_ID unichar_id, const UNICHARSET &unicharset, GenericVector< UNICHAR_ID > *vec) const override
 
EDGE_REF pattern_loop_edge (EDGE_REF edge_ref, UNICHAR_ID unichar_id, bool word_end) const override
 
bool add_word_to_dawg (const WERD_CHOICE &word, const GenericVector< bool > *repetitions)
 
bool add_word_to_dawg (const WERD_CHOICE &word)
 
- Public Member Functions inherited from tesseract::Dawg
DawgType type () const
 
const STRINGlang () const
 
PermuterType permuter () const
 
virtual ~Dawg ()
 
bool word_in_dawg (const WERD_CHOICE &word) const
 Returns true if the given word is in the Dawg. More...
 
bool prefix_in_dawg (const WERD_CHOICE &prefix, bool requires_complete) const
 
int check_for_words (const char *filename, const UNICHARSET &unicharset, bool enable_wildcard) const
 
void iterate_words (const UNICHARSET &unicharset, TessCallback1< const WERD_CHOICE * > *cb) const
 
void iterate_words (const UNICHARSET &unicharset, TessCallback1< const char * > *cb) const
 

Static Public Member Functions

static const char * get_reverse_policy_name (RTLReversePolicy reverse_policy)
 

Static Public Attributes

static const int kSaneNumConcreteChars = 0
 
static const char kAlphaPatternUnicode [] = "\u2000"
 
static const char kDigitPatternUnicode [] = "\u2001"
 
static const char kAlphanumPatternUnicode [] = "\u2002"
 
static const char kPuncPatternUnicode [] = "\u2003"
 
static const char kLowerPatternUnicode [] = "\u2004"
 
static const char kUpperPatternUnicode [] = "\u2005"
 
- Static Public Attributes inherited from tesseract::Dawg
static const int16_t kDawgMagicNumber = 42
 Magic number to determine endianness when reading the Dawg from file. More...
 
static const UNICHAR_ID kPatternUnicharID = 0
 

Protected Member Functions

EDGE_RECORDderef_edge_ref (EDGE_REF edge_ref) const
 
EDGE_REF make_edge_ref (NODE_REF node_index, EDGE_INDEX edge_index) const
 
void link_edge (EDGE_RECORD *edge, NODE_REF nxt, bool repeats, int direction, bool word_end, UNICHAR_ID unichar_id)
 
void print_edge_rec (const EDGE_RECORD &edge_rec) const
 
bool can_be_eliminated (const EDGE_RECORD &edge_rec)
 
void print_all (const char *msg, int max_num_edges)
 
bool edge_char_of (NODE_REF node_ref, NODE_REF next_node, int direction, bool word_end, UNICHAR_ID unichar_id, EDGE_RECORD **edge_ptr, EDGE_INDEX *edge_index) const
 
bool add_edge_linkage (NODE_REF node1, NODE_REF node2, bool repeats, int direction, bool word_end, UNICHAR_ID unichar_id)
 
bool add_new_edge (NODE_REF node1, NODE_REF node2, bool repeats, bool word_end, UNICHAR_ID unichar_id)
 
void add_word_ending (EDGE_RECORD *edge, NODE_REF the_next_node, bool repeats, UNICHAR_ID unichar_id)
 
NODE_REF new_dawg_node ()
 
void remove_edge_linkage (NODE_REF node1, NODE_REF node2, int direction, bool word_end, UNICHAR_ID unichar_id)
 
void remove_edge (NODE_REF node1, NODE_REF node2, bool word_end, UNICHAR_ID unichar_id)
 
bool eliminate_redundant_edges (NODE_REF node, const EDGE_RECORD &edge1, const EDGE_RECORD &edge2)
 
bool reduce_lettered_edges (EDGE_INDEX edge_index, UNICHAR_ID unichar_id, NODE_REF node, EDGE_VECTOR *backward_edges, NODE_MARKER reduced_nodes)
 
void sort_edges (EDGE_VECTOR *edges)
 
void reduce_node_input (NODE_REF node, NODE_MARKER reduced_nodes)
 
UNICHAR_ID character_class_to_pattern (char ch)
 
- Protected Member Functions inherited from tesseract::Dawg
 Dawg (DawgType type, const STRING &lang, PermuterType perm, int debug_level)
 
NODE_REF next_node_from_edge_rec (const EDGE_RECORD &edge_rec) const
 Returns the next node visited by following this edge. More...
 
bool marker_flag_from_edge_rec (const EDGE_RECORD &edge_rec) const
 Returns the marker flag of this edge. More...
 
int direction_from_edge_rec (const EDGE_RECORD &edge_rec) const
 Returns the direction flag of this edge. More...
 
bool end_of_word_from_edge_rec (const EDGE_RECORD &edge_rec) const
 Returns true if this edge marks the end of a word. More...
 
UNICHAR_ID unichar_id_from_edge_rec (const EDGE_RECORD &edge_rec) const
 Returns UNICHAR_ID recorded in this edge. More...
 
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. More...
 
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. More...
 
int given_greater_than_edge_rec (NODE_REF next_node, bool word_end, UNICHAR_ID unichar_id, const EDGE_RECORD &edge_rec) const
 
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
 
void init (int unicharset_size)
 
bool match_words (WERD_CHOICE *word, int32_t index, NODE_REF node, UNICHAR_ID wildcard) const
 
void iterate_words_rec (const WERD_CHOICE &word_so_far, NODE_REF to_explore, TessCallback1< const WERD_CHOICE * > *cb) const
 

Protected Attributes

TRIE_NODES nodes_
 
GenericVector< EDGE_INDEXroot_back_freelist_
 
uint64_t num_edges_
 
uint64_t deref_direction_mask_
 
uint64_t deref_node_index_mask_
 
UNICHAR_ID alpha_pattern_
 
UNICHAR_ID digit_pattern_
 
UNICHAR_ID alphanum_pattern_
 
UNICHAR_ID punc_pattern_
 
UNICHAR_ID lower_pattern_
 
UNICHAR_ID upper_pattern_
 
bool initialized_patterns_
 
- Protected Attributes inherited from tesseract::Dawg
STRING lang_
 
DawgType type_
 
PermuterType perm_
 Permuter code that should be used if the word is found in this Dawg. More...
 
uint64_t next_node_mask_
 
uint64_t flags_mask_
 
uint64_t letter_mask_
 
int unicharset_size_
 
int flag_start_bit_
 
int next_node_start_bit_
 
int debug_level_
 

Detailed Description

Concrete class for Trie data structure that allows to store a list of words (extends Dawg base class) as well as dynamically add new words. This class stores a vector of pointers to TRIE_NODE_RECORDs, each of which has a vector of forward and backward edges.

Definition at line 56 of file trie.h.

Member Enumeration Documentation

◆ RTLReversePolicy

Enumerator
RRP_DO_NO_REVERSE 
RRP_REVERSE_IF_HAS_RTL 
RRP_FORCE_REVERSE 

Definition at line 58 of file trie.h.

Constructor & Destructor Documentation

◆ Trie()

tesseract::Trie::Trie ( DawgType  type,
const STRING lang,
PermuterType  perm,
int  unicharset_size,
int  debug_level 
)
inline

Definition at line 83 of file trie.h.

85  : Dawg(type, lang, perm, debug_level) {
86  init(unicharset_size);
87  num_edges_ = 0;
89  new_dawg_node(); // need to allocate node 0
90  initialized_patterns_ = false;
91  }

◆ ~Trie()

tesseract::Trie::~Trie ( )
inlineoverride

Definition at line 92 of file trie.h.

Member Function Documentation

◆ add_edge_linkage()

bool tesseract::Trie::add_edge_linkage ( NODE_REF  node1,
NODE_REF  node2,
bool  repeats,
int  direction,
bool  word_end,
UNICHAR_ID  unichar_id 
)
protected

Definition at line 116 of file trie.cpp.

118  {
119  EDGE_VECTOR *vec = (direction == FORWARD_EDGE) ?
120  &(nodes_[node1]->forward_edges) : &(nodes_[node1]->backward_edges);
121  int search_index;
122  if (node1 == 0 && direction == FORWARD_EDGE) {
123  search_index = 0; // find the index to make the add sorted
124  while (search_index < vec->size() &&
125  given_greater_than_edge_rec(node2, word_end, unichar_id,
126  (*vec)[search_index]) == 1) {
127  search_index++;
128  }
129  } else {
130  search_index = vec->size(); // add is unsorted, so index does not matter
131  }
132  EDGE_RECORD edge_rec;
133  link_edge(&edge_rec, node2, marker_flag, direction, word_end, unichar_id);
134  if (node1 == 0 && direction == BACKWARD_EDGE &&
136  EDGE_INDEX edge_index = root_back_freelist_.pop_back();
137  (*vec)[edge_index] = edge_rec;
138  } else if (search_index < vec->size()) {
139  vec->insert(edge_rec, search_index);
140  } else {
141  vec->push_back(edge_rec);
142  }
143  if (debug_level_ > 1) {
144  tprintf("new edge in nodes_[" REFFORMAT "]: ", node1);
145  print_edge_rec(edge_rec);
146  tprintf("\n");
147  }
148  num_edges_++;
149  return true;
150 }

◆ add_new_edge()

bool tesseract::Trie::add_new_edge ( NODE_REF  node1,
NODE_REF  node2,
bool  repeats,
bool  word_end,
UNICHAR_ID  unichar_id 
)
inlineprotected

Definition at line 350 of file trie.h.

351  {
352  return (add_edge_linkage(node1, node2, repeats, FORWARD_EDGE,
353  word_end, unichar_id) &&
354  add_edge_linkage(node2, node1, repeats, BACKWARD_EDGE,
355  word_end, unichar_id));
356  }

◆ add_word_ending()

void tesseract::Trie::add_word_ending ( EDGE_RECORD edge,
NODE_REF  the_next_node,
bool  repeats,
UNICHAR_ID  unichar_id 
)
protected

Definition at line 152 of file trie.cpp.

155  {
156  EDGE_RECORD *back_edge_ptr;
157  EDGE_INDEX back_edge_index;
158  ASSERT_HOST(edge_char_of(the_next_node, NO_EDGE, BACKWARD_EDGE, false,
159  unichar_id, &back_edge_ptr, &back_edge_index));
160  if (marker_flag) {
161  *back_edge_ptr |= (MARKER_FLAG << flag_start_bit_);
162  *edge_ptr |= (MARKER_FLAG << flag_start_bit_);
163  }
164  // Mark both directions as end of word.
165  *back_edge_ptr |= (WERD_END_FLAG << flag_start_bit_);
166  *edge_ptr |= (WERD_END_FLAG << flag_start_bit_);
167 }

◆ add_word_list()

bool tesseract::Trie::add_word_list ( const GenericVector< STRING > &  words,
const UNICHARSET unicharset,
Trie::RTLReversePolicy  reverse_policy 
)

Definition at line 313 of file trie.cpp.

315  {
316  for (int i = 0; i < words.size(); ++i) {
317  WERD_CHOICE word(words[i].string(), unicharset);
318  if (word.length() == 0 || word.contains_unichar_id(INVALID_UNICHAR_ID))
319  continue;
320  if ((reverse_policy == RRP_REVERSE_IF_HAS_RTL &&
321  word.has_rtl_unichar_id()) ||
322  reverse_policy == RRP_FORCE_REVERSE) {
323  word.reverse_and_mirror_unichar_ids();
324  }
325  if (!word_in_dawg(word)) {
326  add_word_to_dawg(word);
327  if (!word_in_dawg(word)) {
328  tprintf("Error: word '%s' not in DAWG after adding it\n",
329  words[i].string());
330  return false;
331  }
332  }
333  }
334  return true;
335 }

◆ add_word_to_dawg() [1/2]

bool tesseract::Trie::add_word_to_dawg ( const WERD_CHOICE word)
inline

Definition at line 263 of file trie.h.

263  {
264  return add_word_to_dawg(word, nullptr);
265  }

◆ add_word_to_dawg() [2/2]

bool tesseract::Trie::add_word_to_dawg ( const WERD_CHOICE word,
const GenericVector< bool > *  repetitions 
)

Definition at line 169 of file trie.cpp.

170  {
171  if (word.length() <= 0) return false; // can't add empty words
172  if (repetitions != nullptr) ASSERT_HOST(repetitions->size() == word.length());
173  // Make sure the word does not contain invalid unchar ids.
174  for (int i = 0; i < word.length(); ++i) {
175  if (word.unichar_id(i) < 0 ||
176  word.unichar_id(i) >= unicharset_size_) return false;
177  }
178 
179  EDGE_RECORD *edge_ptr;
180  NODE_REF last_node = 0;
181  NODE_REF the_next_node;
182  bool marker_flag = false;
183  EDGE_INDEX edge_index;
184  int i;
185  int32_t still_finding_chars = true;
186  int32_t word_end = false;
187  bool add_failed = false;
188  bool found;
189 
190  if (debug_level_ > 1) word.print("\nAdding word: ");
191 
192  UNICHAR_ID unichar_id;
193  for (i = 0; i < word.length() - 1; ++i) {
194  unichar_id = word.unichar_id(i);
195  marker_flag = (repetitions != nullptr) ? (*repetitions)[i] : false;
196  if (debug_level_ > 1) tprintf("Adding letter %d\n", unichar_id);
197  if (still_finding_chars) {
198  found = edge_char_of(last_node, NO_EDGE, FORWARD_EDGE, word_end,
199  unichar_id, &edge_ptr, &edge_index);
200  if (found && debug_level_ > 1) {
201  tprintf("exploring edge " REFFORMAT " in node " REFFORMAT "\n",
202  edge_index, last_node);
203  }
204  if (!found) {
205  still_finding_chars = false;
206  } else if (next_node_from_edge_rec(*edge_ptr) == 0) {
207  // We hit the end of an existing word, but the new word is longer.
208  // In this case we have to disconnect the existing word from the
209  // backwards root node, mark the current position as end-of-word
210  // and add new nodes for the increased length. Disconnecting the
211  // existing word from the backwards root node requires a linear
212  // search, so it is much faster to add the longest words first,
213  // to avoid having to come here.
214  word_end = true;
215  still_finding_chars = false;
216  remove_edge(last_node, 0, word_end, unichar_id);
217  } else {
218  // We have to add a new branch here for the new word.
219  if (marker_flag) set_marker_flag_in_edge_rec(edge_ptr);
220  last_node = next_node_from_edge_rec(*edge_ptr);
221  }
222  }
223  if (!still_finding_chars) {
224  the_next_node = new_dawg_node();
225  if (debug_level_ > 1)
226  tprintf("adding node " REFFORMAT "\n", the_next_node);
227  if (the_next_node == 0) {
228  add_failed = true;
229  break;
230  }
231  if (!add_new_edge(last_node, the_next_node,
232  marker_flag, word_end, unichar_id)) {
233  add_failed = true;
234  break;
235  }
236  word_end = false;
237  last_node = the_next_node;
238  }
239  }
240  the_next_node = 0;
241  unichar_id = word.unichar_id(i);
242  marker_flag = (repetitions != nullptr) ? (*repetitions)[i] : false;
243  if (debug_level_ > 1) tprintf("Adding letter %d\n", unichar_id);
244  if (still_finding_chars &&
245  edge_char_of(last_node, NO_EDGE, FORWARD_EDGE, false,
246  unichar_id, &edge_ptr, &edge_index)) {
247  // An extension of this word already exists in the trie, so we
248  // only have to add the ending flags in both directions.
249  add_word_ending(edge_ptr, next_node_from_edge_rec(*edge_ptr),
250  marker_flag, unichar_id);
251  } else {
252  // Add a link to node 0. All leaves connect to node 0 so the back links can
253  // be used in reduction to a dawg. This root backward node has one edge
254  // entry for every word, (except prefixes of longer words) so it is huge.
255  if (!add_failed &&
256  !add_new_edge(last_node, the_next_node, marker_flag, true, unichar_id))
257  add_failed = true;
258  }
259  if (add_failed) {
260  tprintf("Re-initializing document dictionary...\n");
261  clear();
262  return false;
263  } else {
264  return true;
265  }
266 }

◆ can_be_eliminated()

bool tesseract::Trie::can_be_eliminated ( const EDGE_RECORD edge_rec)
inlineprotected

Definition at line 320 of file trie.h.

320  {
321  NODE_REF node_ref = next_node_from_edge_rec(edge_rec);
322  return (node_ref != NO_EDGE &&
323  nodes_[static_cast<int>(node_ref)]->forward_edges.size() == 1);
324  }

◆ character_class_to_pattern()

UNICHAR_ID tesseract::Trie::character_class_to_pattern ( char  ch)
protected

Definition at line 376 of file trie.cpp.

376  {
377  if (ch == 'c') {
378  return alpha_pattern_;
379  } else if (ch == 'd') {
380  return digit_pattern_;
381  } else if (ch == 'n') {
382  return alphanum_pattern_;
383  } else if (ch == 'p') {
384  return punc_pattern_;
385  } else if (ch == 'a') {
386  return lower_pattern_;
387  } else if (ch == 'A') {
388  return upper_pattern_;
389  } else {
390  return INVALID_UNICHAR_ID;
391  }
392 }

◆ clear()

void tesseract::Trie::clear ( )

Definition at line 57 of file trie.cpp.

57  {
59  nodes_.clear();
61  num_edges_ = 0;
62  new_dawg_node(); // Need to allocate node 0.
63 }

◆ DeadEdge()

bool tesseract::Trie::DeadEdge ( const EDGE_RECORD edge_rec) const
inline

Definition at line 152 of file trie.h.

152  {
153  return unichar_id_from_edge_rec(edge_rec) == unicharset_size_;
154  }

◆ deref_edge_ref()

EDGE_RECORD* tesseract::Trie::deref_edge_ref ( EDGE_REF  edge_ref) const
inlineprotected

Definition at line 285 of file trie.h.

285  {
286  int edge_index = static_cast<int>(
287  (edge_ref & letter_mask_) >> LETTER_START_BIT);
288  int node_index = static_cast<int>(
289  (edge_ref & deref_node_index_mask_) >> flag_start_bit_);
290  TRIE_NODE_RECORD *node_rec = nodes_[node_index];
291  return &(node_rec->forward_edges[edge_index]);
292  }

◆ edge_char_of() [1/2]

bool tesseract::Trie::edge_char_of ( NODE_REF  node_ref,
NODE_REF  next_node,
int  direction,
bool  word_end,
UNICHAR_ID  unichar_id,
EDGE_RECORD **  edge_ptr,
EDGE_INDEX edge_index 
) const
protected

Definition at line 65 of file trie.cpp.

67  {
68  if (debug_level_ == 3) {
69  tprintf("edge_char_of() given node_ref " REFFORMAT " next_node " REFFORMAT
70  " direction %d word_end %d unichar_id %d, exploring node:\n",
71  node_ref, next_node, direction, word_end, unichar_id);
72  if (node_ref != NO_EDGE) {
73  print_node(node_ref, nodes_[node_ref]->forward_edges.size());
74  }
75  }
76  if (node_ref == NO_EDGE) return false;
77  assert(node_ref < nodes_.size());
78  EDGE_VECTOR &vec = (direction == FORWARD_EDGE) ?
79  nodes_[node_ref]->forward_edges : nodes_[node_ref]->backward_edges;
80  int vec_size = vec.size();
81  if (node_ref == 0 && direction == FORWARD_EDGE) { // binary search
82  EDGE_INDEX start = 0;
83  EDGE_INDEX end = vec_size - 1;
84  EDGE_INDEX k;
85  int compare;
86  while (start <= end) {
87  k = (start + end) >> 1; // (start + end) / 2
88  compare = given_greater_than_edge_rec(next_node, word_end,
89  unichar_id, vec[k]);
90  if (compare == 0) { // given == vec[k]
91  *edge_ptr = &(vec[k]);
92  *edge_index = k;
93  return true;
94  } else if (compare == 1) { // given > vec[k]
95  start = k + 1;
96  } else { // given < vec[k]
97  end = k - 1;
98  }
99  }
100  } else { // linear search
101  for (int i = 0; i < vec_size; ++i) {
102  EDGE_RECORD &edge_rec = vec[i];
103  if (edge_rec_match(next_node, word_end, unichar_id,
104  next_node_from_edge_rec(edge_rec),
105  end_of_word_from_edge_rec(edge_rec),
106  unichar_id_from_edge_rec(edge_rec))) {
107  *edge_ptr = &(edge_rec);
108  *edge_index = i;
109  return true;
110  }
111  }
112  }
113  return false; // not found
114 }

◆ edge_char_of() [2/2]

EDGE_REF tesseract::Trie::edge_char_of ( NODE_REF  node_ref,
UNICHAR_ID  unichar_id,
bool  word_end 
) const
inlineoverridevirtual

Returns the edge that corresponds to the letter out of this node.

Implements tesseract::Dawg.

Definition at line 98 of file trie.h.

99  {
100  EDGE_RECORD *edge_ptr;
101  EDGE_INDEX edge_index;
102  if (!edge_char_of(node_ref, NO_EDGE, FORWARD_EDGE, word_end, unichar_id,
103  &edge_ptr, &edge_index)) return NO_EDGE;
104  return make_edge_ref(node_ref, edge_index);
105  }

◆ edge_letter()

UNICHAR_ID tesseract::Trie::edge_letter ( EDGE_REF  edge_ref) const
inlineoverridevirtual

Returns UNICHAR_ID stored in the edge indicated by the given EDGE_REF.

Implements tesseract::Dawg.

Definition at line 142 of file trie.h.

142  {
143  if (edge_ref == NO_EDGE || num_edges_ == 0) return INVALID_UNICHAR_ID;
144  return unichar_id_from_edge_rec(*deref_edge_ref(edge_ref));
145  }

◆ eliminate_redundant_edges()

bool tesseract::Trie::eliminate_redundant_edges ( NODE_REF  node,
const EDGE_RECORD edge1,
const EDGE_RECORD edge2 
)
protected

Definition at line 558 of file trie.cpp.

560  {
561  if (debug_level_ > 1) {
562  tprintf("\nCollapsing node %" PRIi64 ":\n", node);
564  tprintf("Candidate edges: ");
565  print_edge_rec(edge1);
566  tprintf(", ");
567  print_edge_rec(edge2);
568  tprintf("\n\n");
569  }
570  NODE_REF next_node1 = next_node_from_edge_rec(edge1);
571  NODE_REF next_node2 = next_node_from_edge_rec(edge2);
572  TRIE_NODE_RECORD *next_node2_ptr = nodes_[next_node2];
573  // Translate all edges going to/from next_node2 to go to/from next_node1.
574  EDGE_RECORD *edge_ptr = nullptr;
575  EDGE_INDEX edge_index;
576  int i;
577  // The backward link in node to next_node2 will be zeroed out by the caller.
578  // Copy all the backward links in next_node2 to node next_node1
579  for (i = 0; i < next_node2_ptr->backward_edges.size(); ++i) {
580  const EDGE_RECORD &bkw_edge = next_node2_ptr->backward_edges[i];
581  NODE_REF curr_next_node = next_node_from_edge_rec(bkw_edge);
582  UNICHAR_ID curr_unichar_id = unichar_id_from_edge_rec(bkw_edge);
583  int curr_word_end = end_of_word_from_edge_rec(bkw_edge);
584  bool marker_flag = marker_flag_from_edge_rec(bkw_edge);
585  add_edge_linkage(next_node1, curr_next_node, marker_flag, BACKWARD_EDGE,
586  curr_word_end, curr_unichar_id);
587  // Relocate the corresponding forward edge in curr_next_node
588  ASSERT_HOST(edge_char_of(curr_next_node, next_node2, FORWARD_EDGE,
589  curr_word_end, curr_unichar_id,
590  &edge_ptr, &edge_index));
591  set_next_node_in_edge_rec(edge_ptr, next_node1);
592  }
593  int next_node2_num_edges = (next_node2_ptr->forward_edges.size() +
594  next_node2_ptr->backward_edges.size());
595  if (debug_level_ > 1) {
596  tprintf("removed %d edges from node " REFFORMAT "\n",
597  next_node2_num_edges, next_node2);
598  }
599  next_node2_ptr->forward_edges.clear();
600  next_node2_ptr->backward_edges.clear();
601  num_edges_ -= next_node2_num_edges;
602  return true;
603 }

◆ end_of_word()

bool tesseract::Trie::end_of_word ( EDGE_REF  edge_ref) const
inlineoverridevirtual

Returns true if the edge indicated by the given EDGE_REF marks the end of a word.

Implements tesseract::Dawg.

Definition at line 136 of file trie.h.

136  {
137  if (edge_ref == NO_EDGE || num_edges_ == 0) return false;
138  return end_of_word_from_edge_rec(*deref_edge_ref(edge_ref));
139  }

◆ get_reverse_policy_name()

const char * tesseract::Trie::get_reverse_policy_name ( RTLReversePolicy  reverse_policy)
static

Definition at line 52 of file trie.cpp.

52  {
53  return RTLReversePolicyNames[reverse_policy];
54 }

◆ initialize_patterns()

void tesseract::Trie::initialize_patterns ( UNICHARSET unicharset)

Definition at line 337 of file trie.cpp.

◆ KillEdge()

void tesseract::Trie::KillEdge ( EDGE_RECORD edge_rec) const
inline

Definition at line 148 of file trie.h.

148  {
149  *edge_rec &= ~letter_mask_;
150  *edge_rec |= (unicharset_size_ << LETTER_START_BIT);
151  }

◆ link_edge()

void tesseract::Trie::link_edge ( EDGE_RECORD edge,
NODE_REF  nxt,
bool  repeats,
int  direction,
bool  word_end,
UNICHAR_ID  unichar_id 
)
inlineprotected

Sets up this edge record to the requested values.

Definition at line 300 of file trie.h.

301  {
302  EDGE_RECORD flags = 0;
303  if (repeats) flags |= MARKER_FLAG;
304  if (word_end) flags |= WERD_END_FLAG;
305  if (direction == BACKWARD_EDGE) flags |= DIRECTION_FLAG;
306  *edge = ((nxt << next_node_start_bit_) |
307  (static_cast<EDGE_RECORD>(flags) << flag_start_bit_) |
308  (static_cast<EDGE_RECORD>(unichar_id) << LETTER_START_BIT));
309  }

◆ make_edge_ref()

EDGE_REF tesseract::Trie::make_edge_ref ( NODE_REF  node_index,
EDGE_INDEX  edge_index 
) const
inlineprotected

Constructs EDGE_REF from the given node_index and edge_index.

Definition at line 294 of file trie.h.

295  {
296  return ((node_index << flag_start_bit_) |
297  (edge_index << LETTER_START_BIT));
298  }

◆ new_dawg_node()

NODE_REF tesseract::Trie::new_dawg_node ( )
protected

Definition at line 268 of file trie.cpp.

268  {
269  auto *node = new TRIE_NODE_RECORD();
270  nodes_.push_back(node);
271  return nodes_.length() - 1;
272 }

◆ next_node()

NODE_REF tesseract::Trie::next_node ( EDGE_REF  edge_ref) const
inlineoverridevirtual

Returns the next node visited by following the edge indicated by the given EDGE_REF.

Implements tesseract::Dawg.

Definition at line 127 of file trie.h.

127  {
128  if (edge_ref == NO_EDGE || num_edges_ == 0) return NO_EDGE;
129  return next_node_from_edge_rec(*deref_edge_ref(edge_ref));
130  }

◆ pattern_loop_edge()

EDGE_REF tesseract::Trie::pattern_loop_edge ( EDGE_REF  edge_ref,
UNICHAR_ID  unichar_id,
bool  word_end 
) const
inlineoverridevirtual

Returns the given EDGE_REF if the EDGE_RECORD that it points to has a self loop and the given unichar_id matches the unichar_id stored in the EDGE_RECORD, returns NO_EDGE otherwise.

Reimplemented from tesseract::Dawg.

Definition at line 241 of file trie.h.

243  {
244  if (edge_ref == NO_EDGE) return NO_EDGE;
245  EDGE_RECORD *edge_rec = deref_edge_ref(edge_ref);
246  return (marker_flag_from_edge_rec(*edge_rec) &&
247  unichar_id == unichar_id_from_edge_rec(*edge_rec) &&
248  word_end == end_of_word_from_edge_rec(*edge_rec)) ?
249  edge_ref : NO_EDGE;
250  }

◆ print_all()

void tesseract::Trie::print_all ( const char *  msg,
int  max_num_edges 
)
inlineprotected

Definition at line 328 of file trie.h.

328  {
329  tprintf("\n__________________________\n%s\n", msg);
330  for (int i = 0; i < nodes_.size(); ++i) print_node(i, max_num_edges);
331  tprintf("__________________________\n");
332  }

◆ print_edge_rec()

void tesseract::Trie::print_edge_rec ( const EDGE_RECORD edge_rec) const
inlineprotected

Prints the given EDGE_RECORD.

Definition at line 311 of file trie.h.

311  {
312  tprintf("|" REFFORMAT "|%s%s%s|%d|", next_node_from_edge_rec(edge_rec),
313  marker_flag_from_edge_rec(edge_rec) ? "R," : "",
314  (direction_from_edge_rec(edge_rec) == FORWARD_EDGE) ? "F" : "B",
315  end_of_word_from_edge_rec(edge_rec) ? ",E" : "",
316  unichar_id_from_edge_rec(edge_rec));
317  }

◆ print_node()

void tesseract::Trie::print_node ( NODE_REF  node,
int  max_num_edges 
) const
overridevirtual

Prints the contents of the node indicated by the given NODE_REF. At most max_num_edges will be printed.

Implements tesseract::Dawg.

Definition at line 697 of file trie.cpp.

697  {
698  if (node == NO_EDGE) return; // nothing to print
699  TRIE_NODE_RECORD *node_ptr = nodes_[node];
700  int num_fwd = node_ptr->forward_edges.size();
701  int num_bkw = node_ptr->backward_edges.size();
702  EDGE_VECTOR *vec;
703  for (int dir = 0; dir < 2; ++dir) {
704  if (dir == 0) {
705  vec = &(node_ptr->forward_edges);
706  tprintf(REFFORMAT " (%d %d): ", node, num_fwd, num_bkw);
707  } else {
708  vec = &(node_ptr->backward_edges);
709  tprintf("\t");
710  }
711  int i;
712  for (i = 0; (dir == 0 ? i < num_fwd : i < num_bkw) &&
713  i < max_num_edges; ++i) {
714  if (DeadEdge((*vec)[i])) continue;
715  print_edge_rec((*vec)[i]);
716  tprintf(" ");
717  }
718  if (dir == 0 ? i < num_fwd : i < num_bkw) tprintf("...");
719  tprintf("\n");
720  }
721 }

◆ read_and_add_word_list()

bool tesseract::Trie::read_and_add_word_list ( const char *  filename,
const UNICHARSET unicharset,
Trie::RTLReversePolicy  reverse 
)

Definition at line 281 of file trie.cpp.

283  {
284  GenericVector<STRING> word_list;
285  if (!read_word_list(filename, &word_list)) return false;
286  word_list.sort(sort_strings_by_dec_length);
287  return add_word_list(word_list, unicharset, reverse_policy);
288 }

◆ read_pattern_list()

bool tesseract::Trie::read_pattern_list ( const char *  filename,
const UNICHARSET unicharset 
)

Definition at line 394 of file trie.cpp.

395  {
396  if (!initialized_patterns_) {
397  tprintf("please call initialize_patterns() before read_pattern_list()\n");
398  return false;
399  }
400 
401  FILE *pattern_file = fopen(filename, "rb");
402  if (pattern_file == nullptr) {
403  tprintf("Error opening pattern file %s\n", filename);
404  return false;
405  }
406 
407  int pattern_count = 0;
408  char string[CHARS_PER_LINE];
409  while (fgets(string, CHARS_PER_LINE, pattern_file) != nullptr) {
410  chomp_string(string); // remove newline
411  // Parse the pattern and construct a unichar id vector.
412  // Record the number of repetitions of each unichar in the parallel vector.
413  WERD_CHOICE word(&unicharset);
414  GenericVector<bool> repetitions_vec;
415  const char *str_ptr = string;
416  int step = unicharset.step(str_ptr);
417  bool failed = false;
418  while (step > 0) {
419  UNICHAR_ID curr_unichar_id = INVALID_UNICHAR_ID;
420  if (step == 1 && *str_ptr == '\\') {
421  ++str_ptr;
422  if (*str_ptr == '\\') { // regular '\' unichar that was escaped
423  curr_unichar_id = unicharset.unichar_to_id(str_ptr, step);
424  } else {
425  if (word.length() < kSaneNumConcreteChars) {
426  tprintf("Please provide at least %d concrete characters at the"
427  " beginning of the pattern\n", kSaneNumConcreteChars);
428  failed = true;
429  break;
430  }
431  // Parse character class from expression.
432  curr_unichar_id = character_class_to_pattern(*str_ptr);
433  }
434  } else {
435  curr_unichar_id = unicharset.unichar_to_id(str_ptr, step);
436  }
437  if (curr_unichar_id == INVALID_UNICHAR_ID) {
438  failed = true;
439  break; // failed to parse this pattern
440  }
441  word.append_unichar_id(curr_unichar_id, 1, 0.0, 0.0);
442  repetitions_vec.push_back(false);
443  str_ptr += step;
444  step = unicharset.step(str_ptr);
445  // Check if there is a repetition pattern specified after this unichar.
446  if (step == 1 && *str_ptr == '\\' && *(str_ptr+1) == '*') {
447  repetitions_vec[repetitions_vec.size()-1] = true;
448  str_ptr += 2;
449  step = unicharset.step(str_ptr);
450  }
451  }
452  if (failed) {
453  tprintf("Invalid user pattern %s\n", string);
454  continue;
455  }
456  // Insert the pattern into the trie.
457  if (debug_level_ > 2) {
458  tprintf("Inserting expanded user pattern %s\n",
459  word.debug_string().string());
460  }
461  if (!this->word_in_dawg(word)) {
462  this->add_word_to_dawg(word, &repetitions_vec);
463  if (!this->word_in_dawg(word)) {
464  tprintf("Error: failed to insert pattern '%s'\n", string);
465  }
466  }
467  ++pattern_count;
468  }
469  if (debug_level_) {
470  tprintf("Read %d valid patterns from %s\n", pattern_count, filename);
471  }
472  fclose(pattern_file);
473  return true;
474 }

◆ read_word_list()

bool tesseract::Trie::read_word_list ( const char *  filename,
GenericVector< STRING > *  words 
)

Definition at line 290 of file trie.cpp.

291  {
292  FILE *word_file;
293  char line_str[CHARS_PER_LINE];
294  int word_count = 0;
295 
296  word_file = fopen(filename, "rb");
297  if (word_file == nullptr) return false;
298 
299  while (fgets(line_str, sizeof(line_str), word_file) != nullptr) {
300  chomp_string(line_str); // remove newline
301  STRING word_str(line_str);
302  ++word_count;
303  if (debug_level_ && word_count % 10000 == 0)
304  tprintf("Read %d words so far\n", word_count);
305  words->push_back(word_str);
306  }
307  if (debug_level_)
308  tprintf("Read %d words total.\n", word_count);
309  fclose(word_file);
310  return true;
311 }

◆ reduce_lettered_edges()

bool tesseract::Trie::reduce_lettered_edges ( EDGE_INDEX  edge_index,
UNICHAR_ID  unichar_id,
NODE_REF  node,
EDGE_VECTOR backward_edges,
NODE_MARKER  reduced_nodes 
)
protected

Definition at line 605 of file trie.cpp.

609  {
610  if (debug_level_ > 1)
611  tprintf("reduce_lettered_edges(edge=" REFFORMAT ")\n", edge_index);
612  // Compare each of the edge pairs with the given unichar_id.
613  bool did_something = false;
614  for (int i = edge_index; i < backward_edges->size() - 1; ++i) {
615  // Find the first edge that can be eliminated.
616  UNICHAR_ID curr_unichar_id = INVALID_UNICHAR_ID;
617  while (i < backward_edges->size()) {
618  if (!DeadEdge((*backward_edges)[i])) {
619  curr_unichar_id = unichar_id_from_edge_rec((*backward_edges)[i]);
620  if (curr_unichar_id != unichar_id) return did_something;
621  if (can_be_eliminated((*backward_edges)[i])) break;
622  }
623  ++i;
624  }
625  if (i == backward_edges->size()) break;
626  const EDGE_RECORD &edge_rec = (*backward_edges)[i];
627  // Compare it to the rest of the edges with the given unichar_id.
628  for (int j = i + 1; j < backward_edges->size(); ++j) {
629  const EDGE_RECORD &next_edge_rec = (*backward_edges)[j];
630  if (DeadEdge(next_edge_rec)) continue;
631  UNICHAR_ID next_id = unichar_id_from_edge_rec(next_edge_rec);
632  if (next_id != unichar_id) break;
633  if (end_of_word_from_edge_rec(next_edge_rec) ==
634  end_of_word_from_edge_rec(edge_rec) &&
635  can_be_eliminated(next_edge_rec) &&
636  eliminate_redundant_edges(node, edge_rec, next_edge_rec)) {
637  reduced_nodes[next_node_from_edge_rec(edge_rec)] = false;
638  did_something = true;
639  KillEdge(&(*backward_edges)[j]);
640  }
641  }
642  }
643  return did_something;
644 }

◆ reduce_node_input()

void tesseract::Trie::reduce_node_input ( NODE_REF  node,
NODE_MARKER  reduced_nodes 
)
protected

Eliminates any redundant edges from this node in the Trie.

Definition at line 660 of file trie.cpp.

661  {
662  EDGE_VECTOR &backward_edges = nodes_[node]->backward_edges;
663  sort_edges(&backward_edges);
664  if (debug_level_ > 1) {
665  tprintf("reduce_node_input(node=" REFFORMAT ")\n", node);
667  }
668 
669  EDGE_INDEX edge_index = 0;
670  while (edge_index < backward_edges.size()) {
671  if (DeadEdge(backward_edges[edge_index])) continue;
672  UNICHAR_ID unichar_id =
673  unichar_id_from_edge_rec(backward_edges[edge_index]);
674  while (reduce_lettered_edges(edge_index, unichar_id, node,
675  &backward_edges, reduced_nodes));
676  while (++edge_index < backward_edges.size()) {
677  UNICHAR_ID id = unichar_id_from_edge_rec(backward_edges[edge_index]);
678  if (!DeadEdge(backward_edges[edge_index]) && id != unichar_id) break;
679  }
680  }
681  reduced_nodes[node] = true; // mark as reduced
682 
683  if (debug_level_ > 1) {
684  tprintf("Node " REFFORMAT " after reduction:\n", node);
686  }
687 
688  for (int i = 0; i < backward_edges.size(); ++i) {
689  if (DeadEdge(backward_edges[i])) continue;
690  NODE_REF next_node = next_node_from_edge_rec(backward_edges[i]);
691  if (next_node != 0 && !reduced_nodes[next_node]) {
692  reduce_node_input(next_node, reduced_nodes);
693  }
694  }
695 }

◆ remove_edge()

void tesseract::Trie::remove_edge ( NODE_REF  node1,
NODE_REF  node2,
bool  word_end,
UNICHAR_ID  unichar_id 
)
inlineprotected

Definition at line 375 of file trie.h.

376  {
377  remove_edge_linkage(node1, node2, FORWARD_EDGE, word_end, unichar_id);
378  remove_edge_linkage(node2, node1, BACKWARD_EDGE, word_end, unichar_id);
379  }

◆ remove_edge_linkage()

void tesseract::Trie::remove_edge_linkage ( NODE_REF  node1,
NODE_REF  node2,
int  direction,
bool  word_end,
UNICHAR_ID  unichar_id 
)
protected

Definition at line 476 of file trie.cpp.

477  {
478  EDGE_RECORD *edge_ptr = nullptr;
479  EDGE_INDEX edge_index = 0;
480  ASSERT_HOST(edge_char_of(node1, node2, direction, word_end,
481  unichar_id, &edge_ptr, &edge_index));
482  if (debug_level_ > 1) {
483  tprintf("removed edge in nodes_[" REFFORMAT "]: ", node1);
484  print_edge_rec(*edge_ptr);
485  tprintf("\n");
486  }
487  if (direction == FORWARD_EDGE) {
488  nodes_[node1]->forward_edges.remove(edge_index);
489  } else if (node1 == 0) {
490  KillEdge(&nodes_[node1]->backward_edges[edge_index]);
491  root_back_freelist_.push_back(edge_index);
492  } else {
493  nodes_[node1]->backward_edges.remove(edge_index);
494  }
495  --num_edges_;
496 }

◆ sort_edges()

void tesseract::Trie::sort_edges ( EDGE_VECTOR edges)
protected

Order num_edges of consecutive EDGE_RECORDS in the given EDGE_VECTOR in increasing order of unichar ids. This function is normally called for all edges in a single node, and since number of edges in each node is usually quite small, selection sort is used.

Definition at line 646 of file trie.cpp.

646  {
647  int num_edges = edges->size();
648  if (num_edges <= 1) return;
650  sort_vec.reserve(num_edges);
651  for (int i = 0; i < num_edges; ++i) {
652  sort_vec.push_back(KDPairInc<UNICHAR_ID, EDGE_RECORD>(
653  unichar_id_from_edge_rec((*edges)[i]), (*edges)[i]));
654  }
655  sort_vec.sort();
656  for (int i = 0; i < num_edges; ++i)
657  (*edges)[i] = sort_vec[i].data;
658 }

◆ trie_to_dawg()

SquishedDawg * tesseract::Trie::trie_to_dawg ( )

Definition at line 511 of file trie.cpp.

511  {
512  root_back_freelist_.clear(); // Will be invalided by trie_to_dawg.
513  if (debug_level_ > 2) {
514  print_all("Before reduction:", MAX_NODE_EDGES_DISPLAY);
515  }
516  auto reduced_nodes = new bool[nodes_.size()];
517  for (int i = 0; i < nodes_.size(); i++) reduced_nodes[i] = false;
518  this->reduce_node_input(0, reduced_nodes);
519  delete[] reduced_nodes;
520 
521  if (debug_level_ > 2) {
522  print_all("After reduction:", MAX_NODE_EDGES_DISPLAY);
523  }
524  // Build a translation map from node indices in nodes_ vector to
525  // their target indices in EDGE_ARRAY.
526  auto *node_ref_map = new NODE_REF[nodes_.size() + 1];
527  int i, j;
528  node_ref_map[0] = 0;
529  for (i = 0; i < nodes_.size(); ++i) {
530  node_ref_map[i+1] = node_ref_map[i] + nodes_[i]->forward_edges.size();
531  }
532  int num_forward_edges = node_ref_map[i];
533 
534  // Convert nodes_ vector into EDGE_ARRAY translating the next node references
535  // in edges using node_ref_map. Empty nodes and backward edges are dropped.
536  auto edge_array = new EDGE_RECORD[num_forward_edges];
537  EDGE_ARRAY edge_array_ptr = edge_array;
538  for (i = 0; i < nodes_.size(); ++i) {
539  TRIE_NODE_RECORD *node_ptr = nodes_[i];
540  int end = node_ptr->forward_edges.size();
541  for (j = 0; j < end; ++j) {
542  EDGE_RECORD &edge_rec = node_ptr->forward_edges[j];
543  NODE_REF node_ref = next_node_from_edge_rec(edge_rec);
544  ASSERT_HOST(node_ref < nodes_.size());
545  UNICHAR_ID unichar_id = unichar_id_from_edge_rec(edge_rec);
546  link_edge(edge_array_ptr, node_ref_map[node_ref], false, FORWARD_EDGE,
547  end_of_word_from_edge_rec(edge_rec), unichar_id);
548  if (j == end - 1) set_marker_flag_in_edge_rec(edge_array_ptr);
549  ++edge_array_ptr;
550  }
551  }
552  delete[] node_ref_map;
553 
554  return new SquishedDawg(edge_array, num_forward_edges, type_, lang_,
556 }

◆ unichar_id_to_patterns()

void tesseract::Trie::unichar_id_to_patterns ( UNICHAR_ID  unichar_id,
const UNICHARSET unicharset,
GenericVector< UNICHAR_ID > *  vec 
) const
overridevirtual

Fills vec with unichar ids that represent the character classes of the given unichar_id.

Reimplemented from tesseract::Dawg.

Definition at line 354 of file trie.cpp.

356  {
357  bool is_alpha = unicharset.get_isalpha(unichar_id);
358  if (is_alpha) {
361  if (unicharset.get_islower(unichar_id)) {
363  } else if (unicharset.get_isupper(unichar_id)) {
365  }
366  }
367  if (unicharset.get_isdigit(unichar_id)) {
369  if (!is_alpha) vec->push_back(alphanum_pattern_);
370  }
371  if (unicharset.get_ispunctuation(unichar_id)) {
372  vec->push_back(punc_pattern_);
373  }
374 }

◆ unichar_ids_of()

void tesseract::Trie::unichar_ids_of ( NODE_REF  node,
NodeChildVector vec,
bool  word_end 
) const
inlineoverridevirtual

Fills the given NodeChildVector with all the unichar ids (and the corresponding EDGE_REFs) for which there is an edge out of this node.

Implements tesseract::Dawg.

Definition at line 111 of file trie.h.

112  {
113  const EDGE_VECTOR &forward_edges =
114  nodes_[static_cast<int>(node)]->forward_edges;
115  for (int i = 0; i < forward_edges.size(); ++i) {
116  if (!word_end || end_of_word_from_edge_rec(forward_edges[i])) {
117  vec->push_back(NodeChild(unichar_id_from_edge_rec(forward_edges[i]),
118  make_edge_ref(node, i)));
119  }
120  }
121  }

Member Data Documentation

◆ alpha_pattern_

UNICHAR_ID tesseract::Trie::alpha_pattern_
protected

Definition at line 421 of file trie.h.

◆ alphanum_pattern_

UNICHAR_ID tesseract::Trie::alphanum_pattern_
protected

Definition at line 423 of file trie.h.

◆ deref_direction_mask_

uint64_t tesseract::Trie::deref_direction_mask_
protected

Definition at line 417 of file trie.h.

◆ deref_node_index_mask_

uint64_t tesseract::Trie::deref_node_index_mask_
protected

Definition at line 418 of file trie.h.

◆ digit_pattern_

UNICHAR_ID tesseract::Trie::digit_pattern_
protected

Definition at line 422 of file trie.h.

◆ initialized_patterns_

bool tesseract::Trie::initialized_patterns_
protected

Definition at line 427 of file trie.h.

◆ kAlphanumPatternUnicode

const char tesseract::Trie::kAlphanumPatternUnicode = "\u2002"
static

Definition at line 71 of file trie.h.

◆ kAlphaPatternUnicode

const char tesseract::Trie::kAlphaPatternUnicode = "\u2000"
static

Definition at line 69 of file trie.h.

◆ kDigitPatternUnicode

const char tesseract::Trie::kDigitPatternUnicode = "\u2001"
static

Definition at line 70 of file trie.h.

◆ kLowerPatternUnicode

const char tesseract::Trie::kLowerPatternUnicode = "\u2004"
static

Definition at line 73 of file trie.h.

◆ kPuncPatternUnicode

const char tesseract::Trie::kPuncPatternUnicode = "\u2003"
static

Definition at line 72 of file trie.h.

◆ kSaneNumConcreteChars

const int tesseract::Trie::kSaneNumConcreteChars = 0
static

Definition at line 65 of file trie.h.

◆ kUpperPatternUnicode

const char tesseract::Trie::kUpperPatternUnicode = "\u2005"
static

Definition at line 74 of file trie.h.

◆ lower_pattern_

UNICHAR_ID tesseract::Trie::lower_pattern_
protected

Definition at line 425 of file trie.h.

◆ nodes_

TRIE_NODES tesseract::Trie::nodes_
protected

Definition at line 413 of file trie.h.

◆ num_edges_

uint64_t tesseract::Trie::num_edges_
protected

Definition at line 416 of file trie.h.

◆ punc_pattern_

UNICHAR_ID tesseract::Trie::punc_pattern_
protected

Definition at line 424 of file trie.h.

◆ root_back_freelist_

GenericVector<EDGE_INDEX> tesseract::Trie::root_back_freelist_
protected

Definition at line 415 of file trie.h.

◆ upper_pattern_

UNICHAR_ID tesseract::Trie::upper_pattern_
protected

Definition at line 426 of file trie.h.


The documentation for this class was generated from the following files:
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:247
chomp_string
void chomp_string(char *str)
Definition: helpers.h:77
tesseract::Trie::kAlphanumPatternUnicode
static const char kAlphanumPatternUnicode[]
Definition: trie.h:71
UNICHARSET::size
int size() const
Definition: unicharset.h:341
tesseract::Dawg::letter_mask_
uint64_t letter_mask_
Definition: dawg.h:307
tesseract::Dawg::unicharset_size_
int unicharset_size_
Definition: dawg.h:308
TRIE_NODE_RECORD::forward_edges
EDGE_VECTOR forward_edges
Definition: trie.h:43
tesseract::Trie::next_node
NODE_REF next_node(EDGE_REF edge_ref) const override
Definition: trie.h:127
tesseract::Trie::kSaneNumConcreteChars
static const int kSaneNumConcreteChars
Definition: trie.h:65
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:300
UNICHARSET::step
int step(const char *str) const
Definition: unicharset.cpp:233
tesseract::Dawg::perm_
PermuterType perm_
Permuter code that should be used if the word is found in this Dawg.
Definition: dawg.h:300
GenericVector::sort
void sort()
Definition: genericvector.h:1146
tesseract::Trie::reduce_node_input
void reduce_node_input(NODE_REF node, NODE_MARKER reduced_nodes)
Definition: trie.cpp:660
tesseract::Trie::initialized_patterns_
bool initialized_patterns_
Definition: trie.h:427
tesseract::Trie::DeadEdge
bool DeadEdge(const EDGE_RECORD &edge_rec) const
Definition: trie.h:152
tesseract::Dawg::init
void init(int unicharset_size)
Definition: dawg.cpp:176
tesseract::Trie::print_edge_rec
void print_edge_rec(const EDGE_RECORD &edge_rec) const
Definition: trie.h:311
BACKWARD_EDGE
#define BACKWARD_EDGE
Definition: dawg.h:82
MAX_NODE_EDGES_DISPLAY
#define MAX_NODE_EDGES_DISPLAY
Definition: dawg.h:83
CHARS_PER_LINE
#define CHARS_PER_LINE
Definition: dict.h:38
EDGE_RECORD
uint64_t EDGE_RECORD
Definition: dawg.h:49
LETTER_START_BIT
#define LETTER_START_BIT
Definition: dawg.h:87
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:222
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:226
tesseract::Trie::alpha_pattern_
UNICHAR_ID alpha_pattern_
Definition: trie.h:421
UNICHARSET::get_isalpha
bool get_isalpha(UNICHAR_ID unichar_id) const
Definition: unicharset.h:491
tesseract::Trie::eliminate_redundant_edges
bool eliminate_redundant_edges(NODE_REF node, const EDGE_RECORD &edge1, const EDGE_RECORD &edge2)
Definition: trie.cpp:558
REFFORMAT
#define REFFORMAT
Definition: dawg.h:89
tesseract::Trie::punc_pattern_
UNICHAR_ID punc_pattern_
Definition: trie.h:424
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:65
GenericVector::remove
void remove(int index)
Definition: genericvector.h:803
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:268
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:350
tesseract::Trie::deref_node_index_mask_
uint64_t deref_node_index_mask_
Definition: trie.h:418
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:209
tesseract::Trie::lower_pattern_
UNICHAR_ID lower_pattern_
Definition: trie.h:425
UNICHARSET::get_isdigit
bool get_isdigit(UNICHAR_ID unichar_id) const
Definition: unicharset.h:512
GenericVector< EDGE_RECORD >
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:98
UNICHARSET::get_islower
bool get_islower(UNICHAR_ID unichar_id) const
Definition: unicharset.h:498
tesseract::Trie::read_word_list
bool read_word_list(const char *filename, GenericVector< STRING > *words)
Definition: trie.cpp:290
tesseract::Trie::KillEdge
void KillEdge(EDGE_RECORD *edge_rec) const
Definition: trie.h:148
tesseract::Dawg::lang_
STRING lang_
Definition: dawg.h:297
tesseract::Trie::make_edge_ref
EDGE_REF make_edge_ref(NODE_REF node_index, EDGE_INDEX edge_index) const
Definition: trie.h:294
tesseract::Trie::deref_edge_ref
EDGE_RECORD * deref_edge_ref(EDGE_REF edge_ref) const
Definition: trie.h:285
UNICHAR_ID
int UNICHAR_ID
Definition: unichar.h:34
tesseract::Dawg::lang
const STRING & lang() const
Definition: dawg.h:125
WERD_CHOICE::unichar_id
UNICHAR_ID unichar_id(int index) const
Definition: ratngs.h:305
tprintf
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:35
tesseract::Trie::upper_pattern_
UNICHAR_ID upper_pattern_
Definition: trie.h:426
GenericVector::clear
void clear()
Definition: genericvector.h:895
UNICHARSET::unichar_to_id
UNICHAR_ID unichar_to_id(const char *const unichar_repr) const
Definition: unicharset.cpp:210
tesseract::Trie::RRP_FORCE_REVERSE
@ RRP_FORCE_REVERSE
Definition: trie.h:61
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:88
GenericVector::insert
void insert(const T &t, int index)
Definition: genericvector.h:788
GenericVector::pop_back
T pop_back()
Definition: genericvector.h:772
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:237
TRIE_NODE_RECORD
Definition: trie.h:42
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:231
tesseract::Trie::print_all
void print_all(const char *msg, int max_num_edges)
Definition: trie.h:328
GenericVector::reserve
void reserve(int size)
Definition: genericvector.h:717
tesseract::Dawg::type_
DawgType type_
Definition: dawg.h:298
WERD_END_FLAG
#define WERD_END_FLAG
Definition: dawg.h:86
tesseract::Trie::print_node
void print_node(NODE_REF node, int max_num_edges) const override
Definition: trie.cpp:697
tesseract::Trie::new_dawg_node
NODE_REF new_dawg_node()
Definition: trie.cpp:268
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:152
tesseract::Trie::sort_edges
void sort_edges(EDGE_VECTOR *edges)
Definition: trie.cpp:646
UNICHARSET::unichar_insert
void unichar_insert(const char *const unichar_repr, OldUncleanUnichars old_style)
Definition: unicharset.cpp:626
NODE_REF
int64_t NODE_REF
Definition: dawg.h:52
MARKER_FLAG
#define MARKER_FLAG
Definition: dawg.h:84
GenericVector::length
int length() const
Definition: genericvector.h:86
tesseract::Trie::root_back_freelist_
GenericVector< EDGE_INDEX > root_back_freelist_
Definition: trie.h:415
DIRECTION_FLAG
#define DIRECTION_FLAG
Definition: dawg.h:85
tesseract::Dawg::flag_start_bit_
int flag_start_bit_
Definition: dawg.h:309
tesseract::Dawg::Dawg
Dawg(DawgType type, const STRING &lang, PermuterType perm, int debug_level)
Definition: dawg.h:201
FORWARD_EDGE
#define FORWARD_EDGE
Definition: dawg.h:81
tesseract::Trie::can_be_eliminated
bool can_be_eliminated(const EDGE_RECORD &edge_rec)
Definition: trie.h:320
tesseract::Dawg::next_node_start_bit_
int next_node_start_bit_
Definition: dawg.h:310
tesseract::Trie::add_word_list
bool add_word_list(const GenericVector< STRING > &words, const UNICHARSET &unicharset, Trie::RTLReversePolicy reverse_policy)
Definition: trie.cpp:313
tesseract::Trie::alphanum_pattern_
UNICHAR_ID alphanum_pattern_
Definition: trie.h:423
tesseract::Trie::num_edges_
uint64_t num_edges_
Definition: trie.h:416
tesseract::Trie::nodes_
TRIE_NODES nodes_
Definition: trie.h:413
GenericVector::size
int size() const
Definition: genericvector.h:72
tesseract::Trie::kAlphaPatternUnicode
static const char kAlphaPatternUnicode[]
Definition: trie.h:69
TRIE_NODE_RECORD::backward_edges
EDGE_VECTOR backward_edges
Definition: trie.h:44
EDGE_INDEX
int64_t EDGE_INDEX
Definition: trie.h:38
EDGE_ARRAY
EDGE_RECORD * EDGE_ARRAY
Definition: dawg.h:50
tesseract::Dawg::direction_from_edge_rec
int direction_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns the direction flag of this edge.
Definition: dawg.h:217
tesseract::Trie::kPuncPatternUnicode
static const char kPuncPatternUnicode[]
Definition: trie.h:72
tesseract::Trie::kDigitPatternUnicode
static const char kDigitPatternUnicode[]
Definition: trie.h:70
tesseract::RTLReversePolicyNames
const char *const RTLReversePolicyNames[]
Definition: trie.cpp:39
GenericVector::delete_data_pointers
void delete_data_pointers()
Definition: genericvector.h:912
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:476
tesseract::Trie::add_word_to_dawg
bool add_word_to_dawg(const WERD_CHOICE &word, const GenericVector< bool > *repetitions)
Definition: trie.cpp:169
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:116
WERD_CHOICE::length
int length() const
Definition: ratngs.h:293
UNICHARSET::get_ispunctuation
bool get_ispunctuation(UNICHAR_ID unichar_id) const
Definition: unicharset.h:519
tesseract::Trie::RRP_REVERSE_IF_HAS_RTL
@ RRP_REVERSE_IF_HAS_RTL
Definition: trie.h:60
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:605
tesseract::Dawg::debug_level_
int debug_level_
Definition: dawg.h:312
STRING
Definition: strngs.h:45
tesseract::Trie::digit_pattern_
UNICHAR_ID digit_pattern_
Definition: trie.h:422
tesseract::Trie::character_class_to_pattern
UNICHAR_ID character_class_to_pattern(char ch)
Definition: trie.cpp:376
UNICHARSET::get_isupper
bool get_isupper(UNICHAR_ID unichar_id) const
Definition: unicharset.h:505
WERD_CHOICE::print
void print() const
Definition: ratngs.h:570
tesseract::Trie::remove_edge
void remove_edge(NODE_REF node1, NODE_REF node2, bool word_end, UNICHAR_ID unichar_id)
Definition: trie.h:375
tesseract::Trie::kLowerPatternUnicode
static const char kLowerPatternUnicode[]
Definition: trie.h:73
GenericVector::empty
bool empty() const
Definition: genericvector.h:91
tesseract::Dawg::type
DawgType type() const
Definition: dawg.h:124
WERD_CHOICE
Definition: ratngs.h:263
tesseract::Trie::kUpperPatternUnicode
static const char kUpperPatternUnicode[]
Definition: trie.h:74
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:213
tesseract::Trie::RRP_DO_NO_REVERSE
@ RRP_DO_NO_REVERSE
Definition: trie.h:59
tesseract::Trie::clear
void clear()
Definition: trie.cpp:57
GenericVector::push_back
int push_back(T object)
Definition: genericvector.h:837