#include <dawg.h>

Inheritance diagram for tesseract::Dawg:

Public Member Functions
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

Static Public Attributes
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
	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
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

Abstract class (an interface) that declares methods needed by the various tesseract classes to operate on SquishedDawg and Trie objects.

This class initializes all the edge masks (since their usage by SquishedDawg and Trie is identical) and implements simple accessors for each of the fields encoded in an EDGE_RECORD. This class also implements word_in_dawg() and check_for_words() (since they use only the public methods of SquishedDawg and Trie classes that are inherited from the Dawg base class).

Definition at line 110 of file dawg.h.

Constructor & Destructor Documentation

◆ ~Dawg()

tesseract::Dawg::~Dawg ( )

virtualdefault

◆ Dawg()

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

inlineprotected

Definition at line 201 of file dawg.h.

      : lang_(lang),
        type_(type),
        perm_(perm),
        unicharset_size_(0),
        debug_level_(debug_level) {}

Member Function Documentation

◆ check_for_words()

int tesseract::Dawg::check_for_words	(	const char *	filename,
		const UNICHARSET &	unicharset,
		bool	enable_wildcard
	)		const

Checks the Dawg for the words that are listed in the requested file. Returns the number of words in the given file missing from the Dawg.

Definition at line 68 of file dawg.cpp.

                                                      {
  if (filename == nullptr) {
    return 0;
  }
 
  FILE *word_file;
  char string[CHARS_PER_LINE];
  int misses = 0;
  UNICHAR_ID wildcard = unicharset.unichar_to_id(kWildcard);
 
  word_file = fopen(filename, "r");
  if (word_file == nullptr) {
    tprintf("Error: Could not open file %s\n", filename);
    ASSERT_HOST(word_file);
  }
 
  while (fgets(string, CHARS_PER_LINE, word_file) != nullptr) {
    chomp_string(string); // remove newline
    WERD_CHOICE word(string, unicharset);
    if (word.length() > 0 && !word.contains_unichar_id(INVALID_UNICHAR_ID)) {
      if (!match_words(&word, 0, 0,
                       enable_wildcard ? wildcard : INVALID_UNICHAR_ID)) {
        tprintf("Missing word: %s\n", string);
        ++misses;
      }
    } else {
      tprintf("Failed to create a valid word from %s\n", string);
    }
  }
  fclose(word_file);
  // Make sure the user sees this with fprintf instead of tprintf.
  if (debug_level_) {
    tprintf("Number of lost words=%d\n", misses);
  }
  return misses;
}

◆ direction_from_edge_rec()

int tesseract::Dawg::direction_from_edge_rec ( const EDGE_RECORD & edge_rec ) const

inlineprotected

Returns the direction flag of this edge.

Definition at line 218 of file dawg.h.

                                                                        {
    return ((edge_rec & (DIRECTION_FLAG << flag_start_bit_))) ? BACKWARD_EDGE
                                                              : FORWARD_EDGE;
  }

◆ edge_char_of()

virtual EDGE_REF tesseract::Dawg::edge_char_of	(	NODE_REF	node,
		UNICHAR_ID	unichar_id,
		bool	word_end
	)		const

pure virtual

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

Implemented in tesseract::SquishedDawg, and tesseract::Trie.

◆ edge_letter()

virtual UNICHAR_ID tesseract::Dawg::edge_letter ( EDGE_REF edge_ref ) const

pure virtual

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

Implemented in tesseract::SquishedDawg, and tesseract::Trie.

◆ edge_rec_match()

bool tesseract::Dawg::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

inlineprotected

Returns true if all the values are equal (any value matches next_node if next_node == NO_EDGE, any value matches word_end if word_end is false).

Definition at line 275 of file dawg.h.

                                                                {
    return ((unichar_id == other_unichar_id) &&
            (next_node == NO_EDGE || next_node == other_next_node) &&
            (!word_end || (word_end == other_word_end)));
  }

◆ end_of_word()

virtual bool tesseract::Dawg::end_of_word ( EDGE_REF edge_ref ) const

pure virtual

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

Implemented in tesseract::SquishedDawg, and tesseract::Trie.

◆ end_of_word_from_edge_rec()

bool tesseract::Dawg::end_of_word_from_edge_rec ( const EDGE_RECORD & edge_rec ) const

inlineprotected

Returns true if this edge marks the end of a word.

Definition at line 223 of file dawg.h.

                                                                           {
    return (edge_rec & (WERD_END_FLAG << flag_start_bit_)) != 0;
  }

◆ given_greater_than_edge_rec()

int tesseract::Dawg::given_greater_than_edge_rec	(	NODE_REF	next_node,
		bool	word_end,
		UNICHAR_ID	unichar_id,
		const EDGE_RECORD &	edge_rec
	)		const

inlineprotected

Sequentially compares the given values of unichar ID, next node and word end marker with the values in the given EDGE_RECORD. Returns: 1 if at any step the given input value exceeds that of edge_rec (and all the values already checked are the same) 0 if edge_rec_match() returns true -1 otherwise

Definition at line 247 of file dawg.h.

                                                                            {
    UNICHAR_ID curr_unichar_id = unichar_id_from_edge_rec(edge_rec);
    NODE_REF curr_next_node = next_node_from_edge_rec(edge_rec);
    bool curr_word_end = end_of_word_from_edge_rec(edge_rec);
    if (edge_rec_match(next_node, word_end, unichar_id, curr_next_node,
                       curr_word_end, curr_unichar_id)) {
      return 0;
    }
    if (unichar_id > curr_unichar_id) {
      return 1;
    }
    if (unichar_id == curr_unichar_id) {
      if (next_node > curr_next_node) {
        return 1;
      }
      if (next_node == curr_next_node) {
        if (word_end > curr_word_end) {
          return 1;
        }
      }
    }
    return -1;
  }

◆ init()

void tesseract::Dawg::init ( int unicharset_size )

protected

Sets unicharset_size_. Initializes the values of various masks from unicharset_size_.

Definition at line 178 of file dawg.cpp.

                                   {
  ASSERT_HOST(unicharset_size > 0);
  unicharset_size_ = unicharset_size;
  // Set bit masks. We will use the value unicharset_size_ as a null char, so
  // the actual number of unichars is unicharset_size_ + 1.
  flag_start_bit_ = ceil(log(unicharset_size_ + 1.0) / log(2.0));
  next_node_start_bit_ = flag_start_bit_ + NUM_FLAG_BITS;
  letter_mask_ = ~(~0ull << flag_start_bit_);
  next_node_mask_ = ~0ull << (flag_start_bit_ + NUM_FLAG_BITS);
  flags_mask_ = ~(letter_mask_ | next_node_mask_);
}

◆ iterate_words() [1/2]

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

Definition at line 119 of file dawg.cpp.

                                                                          {
  using namespace std::placeholders; // for _1
  std::function<void(const WERD_CHOICE *)> shim(
      std::bind(CallWithUTF8, cb, _1));
  WERD_CHOICE word(&unicharset);
  iterate_words_rec(word, 0, shim);
}

◆ iterate_words() [2/2]

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

Definition at line 106 of file dawg.cpp.

                                                                          {
  WERD_CHOICE word(&unicharset);
  iterate_words_rec(word, 0, cb);
}

◆ iterate_words_rec()

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

protected

Definition at line 128 of file dawg.cpp.

                                                            {
  NodeChildVector children;
  this->unichar_ids_of(to_explore, &children, false);
  for (auto &i : children) {
    WERD_CHOICE next_word(word_so_far);
    next_word.append_unichar_id(i.unichar_id, 1, 0.0, 0.0);
    if (this->end_of_word(i.edge_ref)) {
      cb(&next_word);
    }
    NODE_REF next = next_node(i.edge_ref);
    if (next != 0) {
      iterate_words_rec(next_word, next, cb);
    }
  }
}

◆ lang()

const std::string & tesseract::Dawg::lang ( ) const

inline

Definition at line 122 of file dawg.h.

                                       {
    return lang_;
  }

◆ marker_flag_from_edge_rec()

bool tesseract::Dawg::marker_flag_from_edge_rec ( const EDGE_RECORD & edge_rec ) const

inlineprotected

Returns the marker flag of this edge.

Definition at line 214 of file dawg.h.

                                                                           {
    return (edge_rec & (MARKER_FLAG << flag_start_bit_)) != 0;
  }

◆ match_words()

bool tesseract::Dawg::match_words	(	WERD_CHOICE *	word,
		uint32_t	index,
		NODE_REF	node,
		UNICHAR_ID	wildcard
	)		const

protected

Matches all of the words that are represented by this string. If wildcard is set to something other than INVALID_UNICHAR_ID, the *'s in this string are interpreted as wildcards. WERD_CHOICE param is not passed by const so that wildcard searches can modify it and work without having to copy WERD_CHOICEs.

Definition at line 146 of file dawg.cpp.

                                                  {
  if (wildcard != INVALID_UNICHAR_ID && word->unichar_id(index) == wildcard) {
    bool any_matched = false;
    NodeChildVector vec;
    this->unichar_ids_of(node, &vec, false);
    for (auto &i : vec) {
      word->set_unichar_id(i.unichar_id, index);
      if (match_words(word, index, node, wildcard)) {
        any_matched = true;
      }
    }
    word->set_unichar_id(wildcard, index);
    return any_matched;
  } else {
    auto word_end = index == word->length() - 1;
    auto edge = edge_char_of(node, word->unichar_id(index), word_end);
    if (edge != NO_EDGE) { // normal edge in DAWG
      node = next_node(edge);
      if (word_end) {
        if (debug_level_ > 1) {
          word->print("match_words() found: ");
        }
        return true;
      } else if (node != 0) {
        return match_words(word, index + 1, node, wildcard);
      }
    }
  }
  return false;
}

◆ next_node()

virtual NODE_REF tesseract::Dawg::next_node ( EDGE_REF edge_ref ) const

pure virtual

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

Implemented in tesseract::SquishedDawg, and tesseract::Trie.

◆ next_node_from_edge_rec()

NODE_REF tesseract::Dawg::next_node_from_edge_rec ( const EDGE_RECORD & edge_rec ) const

inlineprotected

Returns the next node visited by following this edge.

Definition at line 210 of file dawg.h.

                                                                             {
    return ((edge_rec & next_node_mask_) >> next_node_start_bit_);
  }

◆ pattern_loop_edge()

virtual EDGE_REF tesseract::Dawg::pattern_loop_edge	(	EDGE_REF	edge_ref,
		UNICHAR_ID	unichar_id,
		bool	word_end
	)		const

inlinevirtual

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 in tesseract::Trie.

Definition at line 192 of file dawg.h.

                                                          {
    (void)edge_ref;
    (void)unichar_id;
    (void)word_end;
    return false;
  }

◆ permuter()

PermuterType tesseract::Dawg::permuter ( ) const

inline

Definition at line 125 of file dawg.h.

                                       {
    return perm_;
  }

◆ prefix_in_dawg()

bool tesseract::Dawg::prefix_in_dawg	(	const WERD_CHOICE &	prefix,
		bool	requires_complete
	)		const

Definition at line 41 of file dawg.cpp.

                                                        {
  if (word.empty()) {
    return !requires_complete;
  }
  NODE_REF node = 0;
  int end_index = word.length() - 1;
  for (int i = 0; i < end_index; i++) {
    EDGE_REF edge = edge_char_of(node, word.unichar_id(i), false);
    if (edge == NO_EDGE) {
      return false;
    }
    if ((node = next_node(edge)) == 0) {
      // This only happens if all words following this edge terminate --
      // there are no larger words.  See Trie::add_word_to_dawg()
      return false;
    }
  }
  // Now check the last character.
  return edge_char_of(node, word.unichar_id(end_index), requires_complete) !=
         NO_EDGE;
}

◆ print_node()

virtual void tesseract::Dawg::print_node	(	NODE_REF	node,
		int	max_num_edges
	)		const

pure virtual

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

Implemented in tesseract::SquishedDawg, and tesseract::Trie.

◆ set_marker_flag_in_edge_rec()

void tesseract::Dawg::set_marker_flag_in_edge_rec ( EDGE_RECORD * edge_rec )

inlineprotected

Sets this edge record to be the last one in a sequence of edges.

Definition at line 237 of file dawg.h.

                                                                 {
    *edge_rec |= (MARKER_FLAG << flag_start_bit_);
  }

◆ set_next_node_in_edge_rec()

void tesseract::Dawg::set_next_node_in_edge_rec	(	EDGE_RECORD *	edge_rec,
		EDGE_REF	value
	)

inlineprotected

Sets the next node link for this edge in the Dawg.

Definition at line 232 of file dawg.h.

                                                                               {
    *edge_rec &= (~next_node_mask_);
    *edge_rec |= ((value << next_node_start_bit_) & next_node_mask_);
  }

◆ type()

DawgType tesseract::Dawg::type ( ) const

inline

Definition at line 119 of file dawg.h.

                               {
    return type_;
  }

◆ unichar_id_from_edge_rec()

UNICHAR_ID tesseract::Dawg::unichar_id_from_edge_rec ( const EDGE_RECORD & edge_rec ) const

inlineprotected

Returns UNICHAR_ID recorded in this edge.

Definition at line 227 of file dawg.h.

                                         {
    return ((edge_rec & letter_mask_) >> LETTER_START_BIT);
  }

◆ unichar_id_to_patterns()

virtual void tesseract::Dawg::unichar_id_to_patterns	(	UNICHAR_ID	unichar_id,
		const UNICHARSET &	unicharset,
		std::vector< UNICHAR_ID > *	vec
	)		const

inlinevirtual

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

Reimplemented in tesseract::Trie.

Definition at line 181 of file dawg.h.

                                                                        {
    (void)unichar_id;
    (void)unicharset;
    (void)vec;
  }

◆ unichar_ids_of()

virtual void tesseract::Dawg::unichar_ids_of	(	NODE_REF	node,
		NodeChildVector *	vec,
		bool	word_end
	)		const

pure virtual

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

Implemented in tesseract::SquishedDawg, and tesseract::Trie.

◆ word_in_dawg()

bool tesseract::Dawg::word_in_dawg ( const WERD_CHOICE & word ) const

Returns true if the given word is in the Dawg.

Definition at line 64 of file dawg.cpp.

                                                     {
  return prefix_in_dawg(word, true);
}

Member Data Documentation

◆ debug_level_

int tesseract::Dawg::debug_level_

protected

Definition at line 317 of file dawg.h.

◆ flag_start_bit_

int tesseract::Dawg::flag_start_bit_ = 0

protected

Definition at line 314 of file dawg.h.

◆ flags_mask_

uint64_t tesseract::Dawg::flags_mask_ = 0

protected

Definition at line 311 of file dawg.h.

◆ kDawgMagicNumber

const int16_t tesseract::Dawg::kDawgMagicNumber = 42

static

Magic number to determine endianness when reading the Dawg from file.

Definition at line 113 of file dawg.h.

◆ kPatternUnicharID

const UNICHAR_ID tesseract::Dawg::kPatternUnicharID = 0

static

A special unichar id that indicates that any appropriate pattern (e.g.dictionary word, 0-9 digit, etc) can be inserted instead Used for expressing patterns in punctuation and number Dawgs.

Definition at line 117 of file dawg.h.

◆ lang_

std::string tesseract::Dawg::lang_

protected

Definition at line 302 of file dawg.h.

◆ letter_mask_

uint64_t tesseract::Dawg::letter_mask_ = 0

protected

Definition at line 312 of file dawg.h.

◆ next_node_mask_

uint64_t tesseract::Dawg::next_node_mask_ = 0

protected

Definition at line 310 of file dawg.h.

◆ next_node_start_bit_

int tesseract::Dawg::next_node_start_bit_ = 0

protected

Definition at line 315 of file dawg.h.

◆ perm_

PermuterType tesseract::Dawg::perm_

protected

Permuter code that should be used if the word is found in this Dawg.

Definition at line 305 of file dawg.h.

◆ type_

DawgType tesseract::Dawg::type_

protected

Definition at line 303 of file dawg.h.

◆ unicharset_size_

int tesseract::Dawg::unicharset_size_

protected

Definition at line 313 of file dawg.h.

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

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ~Dawg()

◆ Dawg()

Member Function Documentation

◆ check_for_words()

◆ direction_from_edge_rec()

◆ edge_char_of()

◆ edge_letter()

◆ edge_rec_match()

◆ end_of_word()

◆ end_of_word_from_edge_rec()

◆ given_greater_than_edge_rec()

◆ init()

◆ iterate_words() [1/2]

◆ iterate_words() [2/2]

◆ iterate_words_rec()

◆ lang()

◆ marker_flag_from_edge_rec()

◆ match_words()

◆ next_node()

◆ next_node_from_edge_rec()

◆ pattern_loop_edge()

◆ permuter()

◆ prefix_in_dawg()

◆ print_node()

◆ set_marker_flag_in_edge_rec()

◆ set_next_node_in_edge_rec()

◆ type()

◆ unichar_id_from_edge_rec()

◆ unichar_id_to_patterns()

◆ unichar_ids_of()

◆ word_in_dawg()

Member Data Documentation

◆ debug_level_

◆ flag_start_bit_

◆ flags_mask_

◆ kDawgMagicNumber

◆ kPatternUnicharID

◆ lang_

◆ letter_mask_

◆ next_node_mask_

◆ next_node_start_bit_

◆ perm_

◆ type_

◆ unicharset_size_