tesseract  4.1.1
tesseract::SquishedDawg Class Reference

#include <dawg.h>

Inheritance diagram for tesseract::SquishedDawg:
tesseract::Dawg

Public Member Functions

 SquishedDawg (DawgType type, const STRING &lang, PermuterType perm, int debug_level)
 
 SquishedDawg (const char *filename, DawgType type, const STRING &lang, PermuterType perm, int debug_level)
 
 SquishedDawg (EDGE_ARRAY edges, int num_edges, DawgType type, const STRING &lang, PermuterType perm, int unicharset_size, int debug_level)
 
 ~SquishedDawg () override
 
bool Load (TFile *fp)
 
int NumEdges ()
 
EDGE_REF edge_char_of (NODE_REF node, UNICHAR_ID unichar_id, bool word_end) const override
 Returns the edge that corresponds to the letter out of this node. More...
 
void unichar_ids_of (NODE_REF node, NodeChildVector *vec, bool word_end) const override
 
NODE_REF next_node (EDGE_REF edge) const override
 
bool end_of_word (EDGE_REF edge_ref) const override
 
UNICHAR_ID edge_letter (EDGE_REF edge_ref) const override
 Returns UNICHAR_ID stored in the edge indicated by the given EDGE_REF. More...
 
void print_node (NODE_REF node, int max_num_edges) const override
 
bool write_squished_dawg (TFile *file)
 Writes the squished/reduced Dawg to a file. More...
 
bool write_squished_dawg (const char *filename)
 
- 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
 
virtual void unichar_id_to_patterns (UNICHAR_ID unichar_id, const UNICHARSET &unicharset, GenericVector< UNICHAR_ID > *vec) const
 
virtual EDGE_REF pattern_loop_edge (EDGE_REF edge_ref, UNICHAR_ID unichar_id, bool word_end) const
 

Additional Inherited Members

- 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 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 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 that can operate on a compacted (squished) Dawg (read, search and write to file). This class is read-only in the sense that new words can not be added to an instance of SquishedDawg. The underlying representation of the nodes and edges in SquishedDawg is stored as a contiguous EDGE_ARRAY (read from file or given as an argument to the constructor).

Definition at line 407 of file dawg.h.

Constructor & Destructor Documentation

◆ SquishedDawg() [1/3]

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

Definition at line 409 of file dawg.h.

411  : Dawg(type, lang, perm, debug_level) {}

◆ SquishedDawg() [2/3]

tesseract::SquishedDawg::SquishedDawg ( const char *  filename,
DawgType  type,
const STRING lang,
PermuterType  perm,
int  debug_level 
)
inline

Definition at line 412 of file dawg.h.

414  : Dawg(type, lang, perm, debug_level) {
415  TFile file;
416  ASSERT_HOST(file.Open(filename, nullptr));
417  ASSERT_HOST(read_squished_dawg(&file));
418  num_forward_edges_in_node0 = num_forward_edges(0);
419  }

◆ SquishedDawg() [3/3]

tesseract::SquishedDawg::SquishedDawg ( EDGE_ARRAY  edges,
int  num_edges,
DawgType  type,
const STRING lang,
PermuterType  perm,
int  unicharset_size,
int  debug_level 
)
inline

Definition at line 420 of file dawg.h.

423  : Dawg(type, lang, perm, debug_level),
424  edges_(edges),
425  num_edges_(num_edges) {
426  init(unicharset_size);
427  num_forward_edges_in_node0 = num_forward_edges(0);
428  if (debug_level > 3) print_all("SquishedDawg:");
429  }

◆ ~SquishedDawg()

tesseract::SquishedDawg::~SquishedDawg ( )
override

Definition at line 193 of file dawg.cpp.

193 { delete[] edges_; }

Member Function Documentation

◆ edge_char_of()

EDGE_REF tesseract::SquishedDawg::edge_char_of ( NODE_REF  node,
UNICHAR_ID  unichar_id,
bool  word_end 
) const
overridevirtual

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

Implements tesseract::Dawg.

Definition at line 195 of file dawg.cpp.

197  {
198  EDGE_REF edge = node;
199  if (node == 0) { // binary search
200  EDGE_REF start = 0;
201  EDGE_REF end = num_forward_edges_in_node0 - 1;
202  int compare;
203  while (start <= end) {
204  edge = (start + end) >> 1; // (start + end) / 2
205  compare = given_greater_than_edge_rec(NO_EDGE, word_end,
206  unichar_id, edges_[edge]);
207  if (compare == 0) { // given == vec[k]
208  return edge;
209  } else if (compare == 1) { // given > vec[k]
210  start = edge + 1;
211  } else { // given < vec[k]
212  end = edge - 1;
213  }
214  }
215  } else { // linear search
216  if (edge != NO_EDGE && edge_occupied(edge)) {
217  do {
218  if ((unichar_id_from_edge_rec(edges_[edge]) == unichar_id) &&
219  (!word_end || end_of_word_from_edge_rec(edges_[edge])))
220  return (edge);
221  } while (!last_edge(edge++));
222  }
223  }
224  return (NO_EDGE); // not found
225 }

◆ edge_letter()

UNICHAR_ID tesseract::SquishedDawg::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 472 of file dawg.h.

472  {
473  return unichar_id_from_edge_rec((edges_[edge_ref]));
474  }

◆ end_of_word()

bool tesseract::SquishedDawg::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 467 of file dawg.h.

467  {
468  return end_of_word_from_edge_rec((edges_[edge_ref]));
469  }

◆ Load()

bool tesseract::SquishedDawg::Load ( TFile fp)
inline

Definition at line 433 of file dawg.h.

433  {
434  if (!read_squished_dawg(fp)) return false;
435  num_forward_edges_in_node0 = num_forward_edges(0);
436  return true;
437  }

◆ next_node()

NODE_REF tesseract::SquishedDawg::next_node ( EDGE_REF  edge) const
inlineoverridevirtual

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

Implements tesseract::Dawg.

Definition at line 461 of file dawg.h.

461  {
462  return next_node_from_edge_rec((edges_[edge]));
463  }

◆ NumEdges()

int tesseract::SquishedDawg::NumEdges ( )
inline

Definition at line 439 of file dawg.h.

439 { return num_edges_; }

◆ print_node()

void tesseract::SquishedDawg::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 240 of file dawg.cpp.

240  {
241  if (node == NO_EDGE) return; // nothing to print
242 
243  EDGE_REF edge = node;
244  const char *forward_string = "FORWARD";
245  const char *backward_string = " ";
246 
247  const char *last_string = "LAST";
248  const char *not_last_string = " ";
249 
250  const char *eow_string = "EOW";
251  const char *not_eow_string = " ";
252 
253  const char *direction;
254  const char *is_last;
255  const char *eow;
256 
257  UNICHAR_ID unichar_id;
258 
259  if (edge_occupied(edge)) {
260  do {
261  direction =
262  forward_edge(edge) ? forward_string : backward_string;
263  is_last = last_edge(edge) ? last_string : not_last_string;
264  eow = end_of_word(edge) ? eow_string : not_eow_string;
265 
266  unichar_id = edge_letter(edge);
267  tprintf(REFFORMAT " : next = " REFFORMAT ", unichar_id = %d, %s %s %s\n",
268  edge, next_node(edge), unichar_id,
269  direction, is_last, eow);
270 
271  if (edge - node > max_num_edges) return;
272  } while (!last_edge(edge++));
273 
274  if (edge < num_edges_ &&
275  edge_occupied(edge) && backward_edge(edge)) {
276  do {
277  direction =
278  forward_edge(edge) ? forward_string : backward_string;
279  is_last = last_edge(edge) ? last_string : not_last_string;
280  eow = end_of_word(edge) ? eow_string : not_eow_string;
281 
282  unichar_id = edge_letter(edge);
283  tprintf(REFFORMAT " : next = " REFFORMAT
284  ", unichar_id = %d, %s %s %s\n",
285  edge, next_node(edge), unichar_id,
286  direction, is_last, eow);
287 
288  if (edge - node > MAX_NODE_EDGES_DISPLAY) return;
289  } while (!last_edge(edge++));
290  }
291  }
292  else {
293  tprintf(REFFORMAT " : no edges in this node\n", node);
294  }
295  tprintf("\n");
296 }

◆ unichar_ids_of()

void tesseract::SquishedDawg::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 447 of file dawg.h.

448  {
449  EDGE_REF edge = node;
450  if (!edge_occupied(edge) || edge == NO_EDGE) return;
451  assert(forward_edge(edge)); // we don't expect any backward edges to
452  do { // be present when this function is called
453  if (!word_end || end_of_word_from_edge_rec(edges_[edge])) {
454  vec->push_back(NodeChild(unichar_id_from_edge_rec(edges_[edge]), edge));
455  }
456  } while (!last_edge(edge++));
457  }

◆ write_squished_dawg() [1/2]

bool tesseract::SquishedDawg::write_squished_dawg ( const char *  filename)
inline

Opens the file with the given filename and writes the squished/reduced Dawg to the file.

Definition at line 485 of file dawg.h.

485  {
486  TFile file;
487  file.OpenWrite(nullptr);
488  if (!this->write_squished_dawg(&file)) {
489  tprintf("Error serializing %s\n", filename);
490  return false;
491  }
492  if (!file.CloseWrite(filename, nullptr)) {
493  tprintf("Error writing file %s\n", filename);
494  return false;
495  }
496  return true;
497  }

◆ write_squished_dawg() [2/2]

bool tesseract::SquishedDawg::write_squished_dawg ( TFile file)

Writes the squished/reduced Dawg to a file.

Definition at line 368 of file dawg.cpp.

368  {
369  EDGE_REF edge;
370  int32_t num_edges;
371  int32_t node_count = 0;
372  EDGE_REF old_index;
373  EDGE_RECORD temp_record;
374 
375  if (debug_level_) tprintf("write_squished_dawg\n");
376 
377  std::unique_ptr<EDGE_REF[]> node_map(build_node_map(&node_count));
378 
379  // Write the magic number to help detecting a change in endianness.
380  int16_t magic = kDawgMagicNumber;
381  if (!file->Serialize(&magic)) return false;
382  if (!file->Serialize(&unicharset_size_)) return false;
383 
384  // Count the number of edges in this Dawg.
385  num_edges = 0;
386  for (edge=0; edge < num_edges_; edge++)
387  if (forward_edge(edge))
388  num_edges++;
389 
390  // Write edge count to file.
391  if (!file->Serialize(&num_edges)) return false;
392 
393  if (debug_level_) {
394  tprintf("%d nodes in DAWG\n", node_count);
395  tprintf("%d edges in DAWG\n", num_edges);
396  }
397 
398  for (edge = 0; edge < num_edges_; edge++) {
399  if (forward_edge(edge)) { // write forward edges
400  do {
401  old_index = next_node_from_edge_rec(edges_[edge]);
402  set_next_node(edge, node_map[old_index]);
403  temp_record = edges_[edge];
404  if (!file->Serialize(&temp_record)) return false;
405  set_next_node(edge, old_index);
406  } while (!last_edge(edge++));
407 
408  if (edge >= num_edges_) break;
409  if (backward_edge(edge)) // skip back links
410  while (!last_edge(edge++));
411 
412  edge--;
413  }
414  }
415  return true;
416 }

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
tesseract::Dawg::unicharset_size_
int unicharset_size_
Definition: dawg.h:308
tesseract::Dawg::init
void init(int unicharset_size)
Definition: dawg.cpp:176
tesseract::SquishedDawg::end_of_word
bool end_of_word(EDGE_REF edge_ref) const override
Definition: dawg.h:467
MAX_NODE_EDGES_DISPLAY
#define MAX_NODE_EDGES_DISPLAY
Definition: dawg.h:83
EDGE_RECORD
uint64_t EDGE_RECORD
Definition: dawg.h:49
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
REFFORMAT
#define REFFORMAT
Definition: dawg.h:89
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
UNICHAR_ID
int UNICHAR_ID
Definition: unichar.h:34
tesseract::Dawg::lang
const STRING & lang() const
Definition: dawg.h:125
tprintf
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:35
tesseract::SquishedDawg::edge_letter
UNICHAR_ID edge_letter(EDGE_REF edge_ref) const override
Returns UNICHAR_ID stored in the edge indicated by the given EDGE_REF.
Definition: dawg.h:472
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:88
tesseract::Dawg::Dawg
Dawg(DawgType type, const STRING &lang, PermuterType perm, int debug_level)
Definition: dawg.h:201
tesseract::SquishedDawg::write_squished_dawg
bool write_squished_dawg(TFile *file)
Writes the squished/reduced Dawg to a file.
Definition: dawg.cpp:368
tesseract::Dawg::debug_level_
int debug_level_
Definition: dawg.h:312
tesseract::SquishedDawg::next_node
NODE_REF next_node(EDGE_REF edge) const override
Definition: dawg.h:461
tesseract::Dawg::type
DawgType type() const
Definition: dawg.h:124
tesseract::Dawg::kDawgMagicNumber
static const int16_t kDawgMagicNumber
Magic number to determine endianness when reading the Dawg from file.
Definition: dawg.h:118
EDGE_REF
int64_t EDGE_REF
Definition: dawg.h:51