tesseract  v4.0.0-17-g361f3264
Open Source OCR Engine
trie.h
1 /* -*-C-*-
2  ********************************************************************************
3  *
4  * File: trie.h (Formerly trie.h)
5  * Description: Functions to build a trie data structure.
6  * Author: Mark Seaman, SW Productivity
7  * Created: Fri Oct 16 14:37:00 1987
8  * Modified: Fri Jul 26 11:26:34 1991 (Mark Seaman) marks@hpgrlt
9  * Language: C
10  * Package: N/A
11  * Status: Reusable Software Component
12  *
13  * (c) Copyright 1987, Hewlett-Packard Company.
14  ** Licensed under the Apache License, Version 2.0 (the "License");
15  ** you may not use this file except in compliance with the License.
16  ** You may obtain a copy of the License at
17  ** http://www.apache.org/licenses/LICENSE-2.0
18  ** Unless required by applicable law or agreed to in writing, software
19  ** distributed under the License is distributed on an "AS IS" BASIS,
20  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21  ** See the License for the specific language governing permissions and
22  ** limitations under the License.
23  *
24  *********************************************************************************/
25 #ifndef TRIE_H
26 #define TRIE_H
27 
28 #include "dawg.h"
29 #include "genericvector.h"
30 
31 class UNICHARSET;
32 
33 // Note: if we consider either NODE_REF or EDGE_INDEX to ever exceed
34 // max int32, we will need to change GenericVector to use int64 for size
35 // and address indices. This does not seem to be needed immediately,
36 // since currently the largest number of edges limit used by tesseract
37 // (kMaxNumEdges in wordlist2dawg.cpp) is far less than max int32.
38 // There are also int casts below to satisfy the WIN32 compiler that would
39 // need to be changed.
40 // It might be cleanest to change the types of most of the Trie/Dawg related
41 // typedefs to int and restrict the casts to extracting these values from
42 // the 64 bit EDGE_RECORD.
43 using EDGE_INDEX = int64_t ; // index of an edge in a given node
44 using NODE_MARKER = bool *;
46 
50 };
52 
53 namespace tesseract {
54 
61 class Trie : public Dawg {
62  public:
67  };
68 
69  // Minimum number of concrete characters at the beginning of user patterns.
70  static const int kSaneNumConcreteChars = 0;
71  // Various unicode whitespace characters are used to denote unichar patterns,
72  // (character classifier would never produce these whitespace characters as a
73  // valid classification).
74  static const char kAlphaPatternUnicode[];
75  static const char kDigitPatternUnicode[];
76  static const char kAlphanumPatternUnicode[];
77  static const char kPuncPatternUnicode[];
78  static const char kLowerPatternUnicode[];
79  static const char kUpperPatternUnicode[];
80 
81  static const char *get_reverse_policy_name(
82  RTLReversePolicy reverse_policy);
83 
84  // max_num_edges argument allows limiting the amount of memory this
85  // Trie can consume (if a new word insert would cause the Trie to
86  // contain more edges than max_num_edges, all the edges are cleared
87  // so that new inserts can proceed).
88  Trie(DawgType type, const STRING &lang, PermuterType perm,
89  int unicharset_size, int debug_level)
90  : Dawg(type, lang, perm, debug_level) {
91  init(unicharset_size);
92  num_edges_ = 0;
93  deref_node_index_mask_ = ~letter_mask_;
94  new_dawg_node(); // need to allocate node 0
95  initialized_patterns_ = false;
96  }
97  virtual ~Trie() { nodes_.delete_data_pointers(); }
98 
99  // Reset the Trie to empty.
100  void clear();
101 
103  EDGE_REF edge_char_of(NODE_REF node_ref, UNICHAR_ID unichar_id,
104  bool word_end) const {
105  EDGE_RECORD *edge_ptr;
106  EDGE_INDEX edge_index;
107  if (!edge_char_of(node_ref, NO_EDGE, FORWARD_EDGE, word_end, unichar_id,
108  &edge_ptr, &edge_index)) return NO_EDGE;
109  return make_edge_ref(node_ref, edge_index);
110  }
111 
116  void unichar_ids_of(NODE_REF node, NodeChildVector *vec,
117  bool word_end) const {
118  const EDGE_VECTOR &forward_edges =
119  nodes_[static_cast<int>(node)]->forward_edges;
120  for (int i = 0; i < forward_edges.size(); ++i) {
121  if (!word_end || end_of_word_from_edge_rec(forward_edges[i])) {
122  vec->push_back(NodeChild(unichar_id_from_edge_rec(forward_edges[i]),
123  make_edge_ref(node, i)));
124  }
125  }
126  }
127 
132  NODE_REF next_node(EDGE_REF edge_ref) const {
133  if (edge_ref == NO_EDGE || num_edges_ == 0) return NO_EDGE;
134  return next_node_from_edge_rec(*deref_edge_ref(edge_ref));
135  }
136 
141  bool end_of_word(EDGE_REF edge_ref) const {
142  if (edge_ref == NO_EDGE || num_edges_ == 0) return false;
143  return end_of_word_from_edge_rec(*deref_edge_ref(edge_ref));
144  }
145 
147  UNICHAR_ID edge_letter(EDGE_REF edge_ref) const {
148  if (edge_ref == NO_EDGE || num_edges_ == 0) return INVALID_UNICHAR_ID;
149  return unichar_id_from_edge_rec(*deref_edge_ref(edge_ref));
150  }
151  // Sets the UNICHAR_ID in the given edge_rec to unicharset_size_, marking
152  // the edge dead.
153  void KillEdge(EDGE_RECORD* edge_rec) const {
154  *edge_rec &= ~letter_mask_;
155  *edge_rec |= (unicharset_size_ << LETTER_START_BIT);
156  }
157  bool DeadEdge(const EDGE_RECORD& edge_rec) const {
158  return unichar_id_from_edge_rec(edge_rec) == unicharset_size_;
159  }
160 
161  // Prints the contents of the node indicated by the given NODE_REF.
162  // At most max_num_edges will be printed.
163  void print_node(NODE_REF node, int max_num_edges) const;
164 
165  // Writes edges from nodes_ to an EDGE_ARRAY and creates a SquishedDawg.
166  // Eliminates redundant edges and returns the pointer to the SquishedDawg.
167  // Note: the caller is responsible for deallocating memory associated
168  // with the returned SquishedDawg pointer.
169  SquishedDawg *trie_to_dawg();
170 
171  // Reads a list of words from the given file and adds into the Trie.
172  // Calls WERD_CHOICE::reverse_unichar_ids_if_rtl() according to the reverse
173  // policy and information in the unicharset.
174  // Returns false on error.
175  bool read_and_add_word_list(const char *filename,
176  const UNICHARSET &unicharset,
177  Trie::RTLReversePolicy reverse);
178 
179  // Reads a list of words from the given file.
180  // Returns false on error.
181  bool read_word_list(const char *filename,
182  GenericVector<STRING>* words);
183  // Adds a list of words previously read using read_word_list to the trie
184  // using the given unicharset and reverse_policy to convert to unichar-ids.
185  // Returns false on error.
186  bool add_word_list(const GenericVector<STRING> &words,
187  const UNICHARSET &unicharset,
188  Trie::RTLReversePolicy reverse_policy);
189 
190  // Inserts the list of patterns from the given file into the Trie.
191  // The pattern list file should contain one pattern per line in UTF-8 format.
192  //
193  // Each pattern can contain any non-whitespace characters, however only the
194  // patterns that contain characters from the unicharset of the corresponding
195  // language will be useful.
196  // The only meta character is '\'. To be used in a pattern as an ordinary
197  // string it should be escaped with '\' (e.g. string "C:\Documents" should
198  // be written in the patterns file as "C:\\Documents").
199  // This function supports a very limited regular expression syntax. One can
200  // express a character, a certain character class and a number of times the
201  // entity should be repeated in the pattern.
202  //
203  // To denote a character class use one of:
204  // \c - unichar for which UNICHARSET::get_isalpha() is true (character)
205  // \d - unichar for which UNICHARSET::get_isdigit() is true
206  // \n - unichar for which UNICHARSET::get_isdigit() and
207  // UNICHARSET::isalpha() are true
208  // \p - unichar for which UNICHARSET::get_ispunct() is true
209  // \a - unichar for which UNICHARSET::get_islower() is true
210  // \A - unichar for which UNICHARSET::get_isupper() is true
211  //
212  // \* could be specified after each character or pattern to indicate that
213  // the character/pattern can be repeated any number of times before the next
214  // character/pattern occurs.
215  //
216  // Examples:
217  // 1-8\d\d-GOOG-411 will be expanded to strings:
218  // 1-800-GOOG-411, 1-801-GOOG-411, ... 1-899-GOOG-411.
219  //
220  // http://www.\n\*.com will be expanded to strings like:
221  // http://www.a.com http://www.a123.com ... http://www.ABCDefgHIJKLMNop.com
222  //
223  // Note: In choosing which patterns to include please be aware of the fact
224  // providing very generic patterns will make tesseract run slower.
225  // For example \n\* at the beginning of the pattern will make Tesseract
226  // consider all the combinations of proposed character choices for each
227  // of the segmentations, which will be unacceptably slow.
228  // Because of potential problems with speed that could be difficult to
229  // identify, each user pattern has to have at least kSaneNumConcreteChars
230  // concrete characters from the unicharset at the beginning.
231  bool read_pattern_list(const char *filename, const UNICHARSET &unicharset);
232 
233  // Initializes the values of *_pattern_ unichar ids.
234  // This function should be called before calling read_pattern_list().
235  void initialize_patterns(UNICHARSET *unicharset);
236 
237  // Fills in the given unichar id vector with the unichar ids that represent
238  // the patterns of the character classes of the given unichar_id.
239  void unichar_id_to_patterns(UNICHAR_ID unichar_id,
240  const UNICHARSET &unicharset,
241  GenericVector<UNICHAR_ID> *vec) const;
242 
243  // Returns the given EDGE_REF if the EDGE_RECORD that it points to has
244  // a self loop and the given unichar_id matches the unichar_id stored in the
245  // EDGE_RECORD, returns NO_EDGE otherwise.
246  virtual EDGE_REF pattern_loop_edge(EDGE_REF edge_ref,
247  UNICHAR_ID unichar_id,
248  bool word_end) const {
249  if (edge_ref == NO_EDGE) return NO_EDGE;
250  EDGE_RECORD *edge_rec = deref_edge_ref(edge_ref);
251  return (marker_flag_from_edge_rec(*edge_rec) &&
252  unichar_id == unichar_id_from_edge_rec(*edge_rec) &&
253  word_end == end_of_word_from_edge_rec(*edge_rec)) ?
254  edge_ref : NO_EDGE;
255  }
256 
257  // Adds a word to the Trie (creates the necessary nodes and edges).
258  //
259  // If repetitions vector is not nullptr, each entry in the vector indicates
260  // whether the unichar id with the corresponding index in the word is allowed
261  // to repeat an unlimited number of times. For each entry that is true, MARKER
262  // flag of the corresponding edge created for this unichar id is set to true).
263  //
264  // Return true if add succeeded, false otherwise (e.g. when a word contained
265  // an invalid unichar id or the trie was getting too large and was cleared).
266  bool add_word_to_dawg(const WERD_CHOICE &word,
267  const GenericVector<bool> *repetitions);
268  bool add_word_to_dawg(const WERD_CHOICE &word) {
269  return add_word_to_dawg(word, nullptr);
270  }
271 
272  protected:
273  // The structure of an EDGE_REF for Trie edges is as follows:
274  // [LETTER_START_BIT, flag_start_bit_):
275  // edge index in *_edges in a TRIE_NODE_RECORD
276  // [flag_start_bit, 30th bit]: node index in nodes (TRIE_NODES vector)
277  //
278  // With this arrangement there are enough bits to represent edge indices
279  // (each node can have at most unicharset_size_ forward edges and
280  // the position of flag_start_bit is set to be log2(unicharset_size_)).
281  // It is also possible to accommodate a maximum number of nodes that is at
282  // least as large as that of the SquishedDawg representation (in SquishedDawg
283  // each EDGE_RECORD has 32-(flag_start_bit+NUM_FLAG_BITS) bits to represent
284  // the next node index).
285  //
286 
287  // Returns the pointer to EDGE_RECORD after decoding the location
288  // of the edge from the information in the given EDGE_REF.
289  // This function assumes that EDGE_REF holds valid node/edge indices.
290  inline EDGE_RECORD *deref_edge_ref(EDGE_REF edge_ref) const {
291  int edge_index = static_cast<int>(
292  (edge_ref & letter_mask_) >> LETTER_START_BIT);
293  int node_index = static_cast<int>(
294  (edge_ref & deref_node_index_mask_) >> flag_start_bit_);
295  TRIE_NODE_RECORD *node_rec = nodes_[node_index];
296  return &(node_rec->forward_edges[edge_index]);
297  }
299  inline EDGE_REF make_edge_ref(NODE_REF node_index,
300  EDGE_INDEX edge_index) const {
301  return ((node_index << flag_start_bit_) |
302  (edge_index << LETTER_START_BIT));
303  }
305  inline void link_edge(EDGE_RECORD *edge, NODE_REF nxt, bool repeats,
306  int direction, bool word_end, UNICHAR_ID unichar_id) {
307  EDGE_RECORD flags = 0;
308  if (repeats) flags |= MARKER_FLAG;
309  if (word_end) flags |= WERD_END_FLAG;
310  if (direction == BACKWARD_EDGE) flags |= DIRECTION_FLAG;
311  *edge = ((nxt << next_node_start_bit_) |
312  (static_cast<EDGE_RECORD>(flags) << flag_start_bit_) |
313  (static_cast<EDGE_RECORD>(unichar_id) << LETTER_START_BIT));
314  }
316  inline void print_edge_rec(const EDGE_RECORD &edge_rec) const {
317  tprintf("|" REFFORMAT "|%s%s%s|%d|", next_node_from_edge_rec(edge_rec),
318  marker_flag_from_edge_rec(edge_rec) ? "R," : "",
319  (direction_from_edge_rec(edge_rec) == FORWARD_EDGE) ? "F" : "B",
320  end_of_word_from_edge_rec(edge_rec) ? ",E" : "",
321  unichar_id_from_edge_rec(edge_rec));
322  }
323  // Returns true if the next node in recorded the given EDGE_RECORD
324  // has exactly one forward edge.
325  inline bool can_be_eliminated(const EDGE_RECORD &edge_rec) {
326  NODE_REF node_ref = next_node_from_edge_rec(edge_rec);
327  return (node_ref != NO_EDGE &&
328  nodes_[static_cast<int>(node_ref)]->forward_edges.size() == 1);
329  }
330 
331  // Prints the contents of the Trie.
332  // At most max_num_edges will be printed for each node.
333  void print_all(const char* msg, int max_num_edges) {
334  tprintf("\n__________________________\n%s\n", msg);
335  for (int i = 0; i < nodes_.size(); ++i) print_node(i, max_num_edges);
336  tprintf("__________________________\n");
337  }
338 
339  // Finds the edge with the given direction, word_end and unichar_id
340  // in the node indicated by node_ref. Fills in the pointer to the
341  // EDGE_RECORD and the index of the edge with the the values
342  // corresponding to the edge found. Returns true if an edge was found.
343  bool edge_char_of(NODE_REF node_ref, NODE_REF next_node,
344  int direction, bool word_end, UNICHAR_ID unichar_id,
345  EDGE_RECORD **edge_ptr, EDGE_INDEX *edge_index) const;
346 
347  // Adds an single edge linkage between node1 and node2 in the direction
348  // indicated by direction argument.
349  bool add_edge_linkage(NODE_REF node1, NODE_REF node2, bool repeats,
350  int direction, bool word_end,
351  UNICHAR_ID unichar_id);
352 
353  // Adds forward edge linkage from node1 to node2 and the corresponding
354  // backward edge linkage in the other direction.
355  bool add_new_edge(NODE_REF node1, NODE_REF node2,
356  bool repeats, bool word_end, UNICHAR_ID unichar_id) {
357  return (add_edge_linkage(node1, node2, repeats, FORWARD_EDGE,
358  word_end, unichar_id) &&
359  add_edge_linkage(node2, node1, repeats, BACKWARD_EDGE,
360  word_end, unichar_id));
361  }
362 
363  // Sets the word ending flags in an already existing edge pair.
364  // Returns true on success.
365  void add_word_ending(EDGE_RECORD *edge,
366  NODE_REF the_next_node,
367  bool repeats,
368  UNICHAR_ID unichar_id);
369 
370  // Allocates space for a new node in the Trie.
371  NODE_REF new_dawg_node();
372 
373  // Removes a single edge linkage to between node1 and node2 in the
374  // direction indicated by direction argument.
375  void remove_edge_linkage(NODE_REF node1, NODE_REF node2, int direction,
376  bool word_end, UNICHAR_ID unichar_id);
377 
378  // Removes forward edge linkage from node1 to node2 and the corresponding
379  // backward edge linkage in the other direction.
380  void remove_edge(NODE_REF node1, NODE_REF node2,
381  bool word_end, UNICHAR_ID unichar_id) {
382  remove_edge_linkage(node1, node2, FORWARD_EDGE, word_end, unichar_id);
383  remove_edge_linkage(node2, node1, BACKWARD_EDGE, word_end, unichar_id);
384  }
385 
386  // Compares edge1 and edge2 in the given node to see if they point to two
387  // next nodes that could be collapsed. If they do, performs the reduction
388  // and returns true.
389  bool eliminate_redundant_edges(NODE_REF node, const EDGE_RECORD &edge1,
390  const EDGE_RECORD &edge2);
391 
392  // Assuming that edge_index indicates the first edge in a group of edges
393  // in this node with a particular letter value, looks through these edges
394  // to see if any of them can be collapsed. If so does it. Returns to the
395  // caller when all edges with this letter have been reduced.
396  // Returns true if further reduction is possible with this same letter.
397  bool reduce_lettered_edges(EDGE_INDEX edge_index,
398  UNICHAR_ID unichar_id,
399  NODE_REF node,
401  NODE_MARKER reduced_nodes);
402 
409  void sort_edges(EDGE_VECTOR *edges);
410 
412  void reduce_node_input(NODE_REF node, NODE_MARKER reduced_nodes);
413 
414  // Returns the pattern unichar id for the given character class code.
415  UNICHAR_ID character_class_to_pattern(char ch);
416 
417  // Member variables
418  TRIE_NODES nodes_; // vector of nodes in the Trie
419  uint64_t num_edges_; // sum of all edges (forward and backward)
420  uint64_t deref_direction_mask_; // mask for EDGE_REF to extract direction
421  uint64_t deref_node_index_mask_; // mask for EDGE_REF to extract node index
422  // Freelist of edges in the root backwards node that were previously zeroed.
424  // Variables for translating character class codes denoted in user patterns
425  // file to the unichar ids used to represent them in a Trie.
427  UNICHAR_ID alpha_pattern_;
428  UNICHAR_ID digit_pattern_;
429  UNICHAR_ID alphanum_pattern_;
430  UNICHAR_ID punc_pattern_;
431  UNICHAR_ID lower_pattern_;
432  UNICHAR_ID upper_pattern_;
433 };
434 } // namespace tesseract
435 
436 #endif
bool can_be_eliminated(const EDGE_RECORD &edge_rec)
Definition: trie.h:325
EDGE_REF make_edge_ref(NODE_REF node_index, EDGE_INDEX edge_index) const
Definition: trie.h:299
void KillEdge(EDGE_RECORD *edge_rec) const
Definition: trie.h:153
DawgType
Definition: dawg.h:72
Definition: dawg.h:61
UNICHAR_ID edge_letter(EDGE_REF edge_ref) const
Definition: trie.h:147
void print_all(const char *msg, int max_num_edges)
Definition: trie.h:333
uint64_t num_edges_
Definition: trie.h:419
Trie(DawgType type, const STRING &lang, PermuterType perm, int unicharset_size, int debug_level)
Definition: trie.h:88
Definition: dawg.h:119
UNICHAR_ID alpha_pattern_
Definition: trie.h:427
EDGE_VECTOR backward_edges
Definition: trie.h:49
EDGE_REF edge_char_of(NODE_REF node_ref, UNICHAR_ID unichar_id, bool word_end) const
Definition: trie.h:103
int push_back(T object)
Definition: genericvector.h:799
Definition: unicharset.h:146
bool add_new_edge(NODE_REF node1, NODE_REF node2, bool repeats, bool word_end, UNICHAR_ID unichar_id)
Definition: trie.h:355
RTLReversePolicy
Definition: trie.h:63
Definition: baseapi.cpp:94
virtual ~Trie()
Definition: trie.h:97
UNICHAR_ID punc_pattern_
Definition: trie.h:430
bool initialized_patterns_
Definition: trie.h:426
uint64_t deref_direction_mask_
Definition: trie.h:420
bool DeadEdge(const EDGE_RECORD &edge_rec) const
Definition: trie.h:157
EDGE_RECORD * deref_edge_ref(EDGE_REF edge_ref) const
Definition: trie.h:290
Definition: ratngs.h:273
void print_edge_rec(const EDGE_RECORD &edge_rec) const
Definition: trie.h:316
uint64_t deref_node_index_mask_
Definition: trie.h:421
void link_edge(EDGE_RECORD *edge, NODE_REF nxt, bool repeats, int direction, bool word_end, UNICHAR_ID unichar_id)
Definition: trie.h:305
virtual EDGE_REF pattern_loop_edge(EDGE_REF edge_ref, UNICHAR_ID unichar_id, bool word_end) const
Definition: trie.h:246
bool end_of_word(EDGE_REF edge_ref) const
Definition: trie.h:141
UNICHAR_ID digit_pattern_
Definition: trie.h:428
UNICHAR_ID upper_pattern_
Definition: trie.h:432
Definition: trie.h:47
UNICHAR_ID alphanum_pattern_
Definition: trie.h:429
Definition: strngs.h:45
NODE_REF next_node(EDGE_REF edge_ref) const
Definition: trie.h:132
TRIE_NODES nodes_
Definition: trie.h:418
int size() const
Definition: genericvector.h:71
Definition: dawg.h:413
GenericVector< EDGE_INDEX > root_back_freelist_
Definition: trie.h:423
bool add_word_to_dawg(const WERD_CHOICE &word)
Definition: trie.h:268
EDGE_VECTOR forward_edges
Definition: trie.h:48
UNICHAR_ID lower_pattern_
Definition: trie.h:431
Definition: trie.h:61
void unichar_ids_of(NODE_REF node, NodeChildVector *vec, bool word_end) const
Definition: trie.h:116
void remove_edge(NODE_REF node1, NODE_REF node2, bool word_end, UNICHAR_ID unichar_id)
Definition: trie.h:380