#include <dawg.h>

Inheritance diagram for tesseract::SquishedDawg:

Public Member Functions
	SquishedDawg (DawgType type, const std::string &lang, PermuterType perm, int debug_level)

	SquishedDawg (const char *filename, DawgType type, const std::string &lang, PermuterType perm, int debug_level)

	SquishedDawg (EDGE_ARRAY edges, int num_edges, DawgType type, const std::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 std::string &	lang () 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, std::function< void(const WERD_CHOICE *)> cb) const

void	iterate_words (const UNICHARSET &unicharset, const std::function< void(const char *)> &cb) const

virtual EDGE_REF	edge_char_of (NODE_REF node, UNICHAR_ID unichar_id, bool word_end) const =0
	Returns the edge that corresponds to the letter out of this node. More...

virtual void	unichar_ids_of (NODE_REF node, NodeChildVector *vec, bool word_end) const =0

virtual NODE_REF	next_node (EDGE_REF edge_ref) const =0

virtual bool	end_of_word (EDGE_REF edge_ref) const =0

virtual UNICHAR_ID	edge_letter (EDGE_REF edge_ref) const =0
	Returns UNICHAR_ID stored in the edge indicated by the given EDGE_REF. More...

virtual void	print_node (NODE_REF node, int max_num_edges) const =0

virtual void	unichar_id_to_patterns (UNICHAR_ID unichar_id, const UNICHARSET &unicharset, std::vector< 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 std::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, uint32_t index, NODE_REF node, UNICHAR_ID wildcard) const

void	iterate_words_rec (const WERD_CHOICE &word_so_far, NODE_REF to_explore, const std::function< void(const WERD_CHOICE *)> &cb) const

Protected Attributes inherited from tesseract::Dawg
std::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_ = 0

uint64_t	flags_mask_ = 0

uint64_t	letter_mask_ = 0

int	unicharset_size_

int	flag_start_bit_ = 0

int	next_node_start_bit_ = 0

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 cannot 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 408 of file dawg.h.

Constructor & Destructor Documentation

◆ SquishedDawg() [1/3]

tesseract::SquishedDawg::SquishedDawg	(	DawgType	type,
		const std::string &	lang,
		PermuterType	perm,
		int	debug_level
	)

inline

Definition at line 410 of file dawg.h.

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

tesseract::Dawg::Dawg

Dawg(DawgType type, const std::string &lang, PermuterType perm, int debug_level)

Definition: dawg.h:201

tesseract::Dawg::lang

const std::string & lang() const

Definition: dawg.h:122

tesseract::Dawg::type

DawgType type() const

Definition: dawg.h:119

◆ SquishedDawg() [2/3]

tesseract::SquishedDawg::SquishedDawg	(	const char *	filename,
		DawgType	type,
		const std::string &	lang,
		PermuterType	perm,
		int	debug_level
	)

inline

Definition at line 413 of file dawg.h.

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

◆ SquishedDawg() [3/3]

tesseract::SquishedDawg::SquishedDawg	(	EDGE_ARRAY	edges,
		int	num_edges,
		DawgType	type,
		const std::string &	lang,
		PermuterType	perm,
		int	unicharset_size,
		int	debug_level
	)

inline

Definition at line 421 of file dawg.h.

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

◆ ~SquishedDawg()

tesseract::SquishedDawg::~SquishedDawg ( )

override

Definition at line 194 of file dawg.cpp.

                            {
  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 198 of file dawg.cpp.

                                                         {
  EDGE_REF edge = node;
  if (node == 0) { // binary search
    EDGE_REF start = 0;
    EDGE_REF end = num_forward_edges_in_node0 - 1;
    int compare;
    while (start <= end) {
      edge = (start + end) >> 1; // (start + end) / 2
      compare = given_greater_than_edge_rec(NO_EDGE, word_end, unichar_id,
                                            edges_[edge]);
      if (compare == 0) { // given == vec[k]
        return edge;
      } else if (compare == 1) { // given > vec[k]
        start = edge + 1;
      } else { // given < vec[k]
        end = edge - 1;
      }
    }
  } else { // linear search
    if (edge != NO_EDGE && edge_occupied(edge)) {
      do {
        if ((unichar_id_from_edge_rec(edges_[edge]) == unichar_id) &&
            (!word_end || end_of_word_from_edge_rec(edges_[edge]))) {
          return (edge);
        }
      } while (!last_edge(edge++));
    }
  }
  return (NO_EDGE); // not found
}

◆ 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 481 of file dawg.h.

                                                           {
    return unichar_id_from_edge_rec((edges_[edge_ref]));
  }

◆ 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 476 of file dawg.h.

                                                     {
    return end_of_word_from_edge_rec((edges_[edge_ref]));
  }

◆ Load()

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

inline

Definition at line 436 of file dawg.h.

                       {
    if (!read_squished_dawg(fp)) {
      return false;
    }
    num_forward_edges_in_node0 = num_forward_edges(0);
    return true;
  }

◆ 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 470 of file dawg.h.

                                                   {
    return next_node_from_edge_rec((edges_[edge]));
  }

◆ NumEdges()

int tesseract::SquishedDawg::NumEdges ( )

inline

Definition at line 444 of file dawg.h.

                 {
    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 243 of file dawg.cpp.

                                                                    {
  if (node == NO_EDGE) {
    return; // nothing to print
  }
 
  EDGE_REF edge = node;
  const char *forward_string = "FORWARD";
  const char *backward_string = "       ";
 
  const char *last_string = "LAST";
  const char *not_last_string = "    ";
 
  const char *eow_string = "EOW";
  const char *not_eow_string = "   ";
 
  const char *direction;
  const char *is_last;
  const char *eow;
 
  UNICHAR_ID unichar_id;
 
  if (edge_occupied(edge)) {
    do {
      direction = forward_edge(edge) ? forward_string : backward_string;
      is_last = last_edge(edge) ? last_string : not_last_string;
      eow = end_of_word(edge) ? eow_string : not_eow_string;
 
      unichar_id = edge_letter(edge);
      tprintf(REFFORMAT " : next = " REFFORMAT ", unichar_id = %d, %s %s %s\n",
              edge, next_node(edge), unichar_id, direction, is_last, eow);
 
      if (edge - node > max_num_edges) {
        return;
      }
    } while (!last_edge(edge++));
 
    if (edge < num_edges_ && edge_occupied(edge) && backward_edge(edge)) {
      do {
        direction = forward_edge(edge) ? forward_string : backward_string;
        is_last = last_edge(edge) ? last_string : not_last_string;
        eow = end_of_word(edge) ? eow_string : not_eow_string;
 
        unichar_id = edge_letter(edge);
        tprintf(REFFORMAT " : next = " REFFORMAT
                          ", unichar_id = %d, %s %s %s\n",
                edge, next_node(edge), unichar_id, direction, is_last, eow);
 
        if (edge - node > MAX_NODE_EDGES_DISPLAY) {
          return;
        }
      } while (!last_edge(edge++));
    }
  } else {
    tprintf(REFFORMAT " : no edges in this node\n", node);
  }
  tprintf("\n");
}

◆ 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 454 of file dawg.h.

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

◆ 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 494 of file dawg.h.

                                                 {
    TFile file;
    file.OpenWrite(nullptr);
    if (!this->write_squished_dawg(&file)) {
      tprintf("Error serializing %s\n", filename);
      return false;
    }
    if (!file.CloseWrite(filename, nullptr)) {
      tprintf("Error writing file %s\n", filename);
      return false;
    }
    return true;
  }

◆ write_squished_dawg() [2/2]

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

Writes the squished/reduced Dawg to a file.

Definition at line 391 of file dawg.cpp.

                                                  {
  EDGE_REF edge;
  int32_t num_edges;
  int32_t node_count = 0;
  EDGE_REF old_index;
  EDGE_RECORD temp_record;
 
  if (debug_level_) {
    tprintf("write_squished_dawg\n");
  }
 
  std::unique_ptr<EDGE_REF[]> node_map(build_node_map(&node_count));
 
  // Write the magic number to help detecting a change in endianness.
  int16_t magic = kDawgMagicNumber;
  if (!file->Serialize(&magic)) {
    return false;
  }
  if (!file->Serialize(&unicharset_size_)) {
    return false;
  }
 
  // Count the number of edges in this Dawg.
  num_edges = 0;
  for (edge = 0; edge < num_edges_; edge++) {
    if (forward_edge(edge)) {
      num_edges++;
    }
  }
 
  // Write edge count to file.
  if (!file->Serialize(&num_edges)) {
    return false;
  }
 
  if (debug_level_) {
    tprintf("%d nodes in DAWG\n", node_count);
    tprintf("%d edges in DAWG\n", num_edges);
  }
 
  for (edge = 0; edge < num_edges_; edge++) {
    if (forward_edge(edge)) { // write forward edges
      do {
        old_index = next_node_from_edge_rec(edges_[edge]);
        set_next_node(edge, node_map[old_index]);
        temp_record = edges_[edge];
        if (!file->Serialize(&temp_record)) {
          return false;
        }
        set_next_node(edge, old_index);
      } while (!last_edge(edge++));
 
      if (edge >= num_edges_) {
        break;
      }
      if (backward_edge(edge)) { // skip back links
        while (!last_edge(edge++)) {
          ;
        }
      }
 
      edge--;
    }
  }
  return true;
}

The documentation for this class was generated from the following files:

/media/home/debian/src/github/tesseract-ocr/tesseract/src/dict/dawg.h
/media/home/debian/src/github/tesseract-ocr/tesseract/src/dict/dawg.cpp

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ SquishedDawg() [1/3]

◆ SquishedDawg() [2/3]

◆ SquishedDawg() [3/3]

◆ ~SquishedDawg()

Member Function Documentation

◆ edge_char_of()

◆ edge_letter()

◆ end_of_word()

◆ Load()

◆ next_node()

◆ NumEdges()

◆ print_node()

◆ unichar_ids_of()

◆ write_squished_dawg() [1/2]

◆ write_squished_dawg() [2/2]