#include <trie.h>

Inheritance diagram for tesseract::Trie:

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

SquishedDawg *	trie_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 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, std::function< void(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_RECORD *	deref_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, std::function< void(const WERD_CHOICE *)> cb) const

Protected Attributes
TRIE_NODES	nodes_

GenericVector< EDGE_INDEX >	root_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_ = 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 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 54 of file trie.h.

Member Enumeration Documentation

◆ RTLReversePolicy

enum tesseract::Trie::RTLReversePolicy

Enumerator
RRP_DO_NO_REVERSE
RRP_REVERSE_IF_HAS_RTL
RRP_FORCE_REVERSE

Definition at line 56 of file trie.h.

        :
   enum RTLReversePolicy {
     RRP_DO_NO_REVERSE,
     RRP_REVERSE_IF_HAS_RTL,
     RRP_FORCE_REVERSE,

Constructor & Destructor Documentation

◆ Trie()

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

inline

Definition at line 81 of file trie.h.

       : Dawg(type, lang, perm, debug_level) {
     init(unicharset_size);
     num_edges_ = 0;
     deref_node_index_mask_ = ~letter_mask_;
     new_dawg_node();  // need to allocate node 0
     initialized_patterns_ = false;

◆ ~Trie()

tesseract::Trie::~Trie ( )

inlineoverride

Definition at line 90 of file trie.h.

91 { nodes_.delete_data_pointers(); }

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 130 of file trie.cpp.

                                     {
     EDGE_INDEX edge_index = root_back_freelist_.pop_back();
     (*vec)[edge_index] = edge_rec;
   } else if (search_index < vec->size()) {
     vec->insert(edge_rec, search_index);
   } else {
     vec->push_back(edge_rec);
   }
   if (debug_level_ > 1) {
     tprintf("new edge in nodes_[" REFFORMAT "]: ", node1);
     print_edge_rec(edge_rec);
     tprintf("\n");
   }
   num_edges_++;
   return true;
 }
  
 void Trie::add_word_ending(EDGE_RECORD *edge_ptr,
                            NODE_REF the_next_node,
                            bool marker_flag,
                            UNICHAR_ID unichar_id) {
   EDGE_RECORD *back_edge_ptr;
   EDGE_INDEX back_edge_index;
   ASSERT_HOST(edge_char_of(the_next_node, NO_EDGE, BACKWARD_EDGE, false,
                            unichar_id, &back_edge_ptr, &back_edge_index));
   if (marker_flag) {
     *back_edge_ptr |= (MARKER_FLAG << flag_start_bit_);
     *edge_ptr |= (MARKER_FLAG << flag_start_bit_);
   }
   // Mark both directions as end of word.
   *back_edge_ptr |= (WERD_END_FLAG << flag_start_bit_);

◆ 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 348 of file trie.h.

                                                                         {
     return (add_edge_linkage(node1, node2, repeats, FORWARD_EDGE,
                              word_end, unichar_id) &&
             add_edge_linkage(node2, node1, repeats, BACKWARD_EDGE,
                              word_end, unichar_id));

◆ 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 166 of file trie.cpp.

                                                                     {
   if (word.length() <= 0) return false;  // can't add empty words
   if (repetitions != nullptr) ASSERT_HOST(repetitions->size() == word.length());
   // Make sure the word does not contain invalid unchar ids.
   for (int i = 0; i < word.length(); ++i) {
     if (word.unichar_id(i) < 0 ||
         word.unichar_id(i) >= unicharset_size_) return false;
   }
  
   EDGE_RECORD *edge_ptr;
   NODE_REF last_node = 0;
   NODE_REF the_next_node;
   bool marker_flag = false;

◆ add_word_list()

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

Definition at line 327 of file trie.cpp.

                       : word '%s' not in DAWG after adding it\n",
                 words[i].c_str());
         return false;
       }
     }
   }
   return true;
 }
  
 void Trie::initialize_patterns(UNICHARSET *unicharset) {
   unicharset->unichar_insert(kAlphaPatternUnicode);
   alpha_pattern_ = unicharset->unichar_to_id(kAlphaPatternUnicode);
   unicharset->unichar_insert(kDigitPatternUnicode);
   digit_pattern_ = unicharset->unichar_to_id(kDigitPatternUnicode);
   unicharset->unichar_insert(kAlphanumPatternUnicode);
   alphanum_pattern_ = unicharset->unichar_to_id(kAlphanumPatternUnicode);
   unicharset->unichar_insert(kPuncPatternUnicode);
   punc_pattern_ = unicharset->unichar_to_id(kPuncPatternUnicode);
   unicharset->unichar_insert(kLowerPatternUnicode);
   lower_pattern_ = unicharset->unichar_to_id(kLowerPatternUnicode);
   unicharset->unichar_insert(kUpperPatternUnicode);
   upper_pattern_ = unicharset->unichar_to_id(kUpperPatternUnicode);
   initialized_patterns_ = true;

◆ add_word_to_dawg() [1/2]

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

inline

Definition at line 261 of file trie.h.

262 {

263 return add_word_to_dawg(word, nullptr);

◆ add_word_to_dawg() [2/2]

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

Definition at line 183 of file trie.cpp.

                                                  : ");
  
   UNICHAR_ID unichar_id;
   for (i = 0; i < word.length() - 1; ++i) {
     unichar_id = word.unichar_id(i);
     marker_flag = (repetitions != nullptr) ? (*repetitions)[i] : false;
     if (debug_level_ > 1) tprintf("Adding letter %d\n", unichar_id);
     if (still_finding_chars) {
       found = edge_char_of(last_node, NO_EDGE, FORWARD_EDGE, word_end,
                            unichar_id, &edge_ptr, &edge_index);
       if (found && debug_level_ > 1) {
         tprintf("exploring edge " REFFORMAT " in node " REFFORMAT "\n",
                 edge_index, last_node);
       }
       if (!found) {
         still_finding_chars = false;
       } else if (next_node_from_edge_rec(*edge_ptr) == 0) {
         // We hit the end of an existing word, but the new word is longer.
         // In this case we have to disconnect the existing word from the
         // backwards root node, mark the current position as end-of-word
         // and add new nodes for the increased length. Disconnecting the
         // existing word from the backwards root node requires a linear
         // search, so it is much faster to add the longest words first,
         // to avoid having to come here.
         word_end = true;
         still_finding_chars = false;
         remove_edge(last_node, 0, word_end, unichar_id);
       } else {
         // We have to add a new branch here for the new word.
         if (marker_flag) set_marker_flag_in_edge_rec(edge_ptr);
         last_node = next_node_from_edge_rec(*edge_ptr);
       }
     }
     if (!still_finding_chars) {
       the_next_node = new_dawg_node();
       if (debug_level_ > 1)
         tprintf("adding node " REFFORMAT "\n", the_next_node);
       if (the_next_node == 0) {
         add_failed = true;
         break;
       }
       if (!add_new_edge(last_node, the_next_node,
                         marker_flag, word_end, unichar_id)) {
         add_failed = true;
         break;
       }
       word_end = false;
       last_node = the_next_node;
     }
   }
   the_next_node = 0;
   unichar_id = word.unichar_id(i);
   marker_flag = (repetitions != nullptr) ? (*repetitions)[i] : false;
   if (debug_level_ > 1) tprintf("Adding letter %d\n", unichar_id);
   if (still_finding_chars &&
       edge_char_of(last_node, NO_EDGE, FORWARD_EDGE, false,
                    unichar_id, &edge_ptr, &edge_index)) {
     // An extension of this word already exists in the trie, so we
     // only have to add the ending flags in both directions.
     add_word_ending(edge_ptr, next_node_from_edge_rec(*edge_ptr),
                     marker_flag, unichar_id);
   } else {
     // Add a link to node 0. All leaves connect to node 0 so the back links can
     // be used in reduction to a dawg. This root backward node has one edge
     // entry for every word, (except prefixes of longer words) so it is huge.
     if (!add_failed &&
         !add_new_edge(last_node, the_next_node, marker_flag, true, unichar_id))
       add_failed = true;
   }
   if (add_failed) {
     tprintf("Re-initializing document dictionary...\n");
     clear();
     return false;
   } else {
     return true;
   }
 }
  
 NODE_REF Trie::new_dawg_node() {
   auto *node = new TRIE_NODE_RECORD();
   nodes_.push_back(node);
   return nodes_.size() - 1;
 }
  
 // Sort function to sort words by decreasing order of length.
 static int sort_strings_by_dec_length(const void* v1, const void* v2) {
   const auto *s1 = static_cast<const STRING *>(v1);
   const auto *s2 = static_cast<const STRING *>(v2);
   return s2->length() - s1->length();
 }
  
 bool Trie::read_and_add_word_list(const char *filename,

◆ can_be_eliminated()

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

inlineprotected

Definition at line 318 of file trie.h.

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

◆ character_class_to_pattern()

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

protected

Definition at line 390 of file trie.cpp.

                                                            {
   if (!initialized_patterns_) {
     tprintf("please call initialize_patterns() before read_pattern_list()\n");
     return false;
   }
  
   FILE *pattern_file = fopen(filename, "rb");
   if (pattern_file == nullptr) {
     tprintf("Error opening pattern file %s\n", filename);
     return false;
   }
  
   int pattern_count = 0;

◆ clear()

void tesseract::Trie::clear ( )

Definition at line 71 of file trie.cpp.

                              {
       print_node(node_ref, nodes_[node_ref]->forward_edges.size());
     }
   }
   if (node_ref == NO_EDGE) return false;
   assert(node_ref < nodes_.size());
   EDGE_VECTOR &vec = (direction == FORWARD_EDGE) ?

◆ DeadEdge()

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

inline

Definition at line 150 of file trie.h.

151 {

152 return unichar_id_from_edge_rec(edge_rec) == unicharset_size_;

◆ deref_edge_ref()

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

inlineprotected

Definition at line 283 of file trie.h.

                                                               {
     int edge_index = static_cast<int>(
       (edge_ref & letter_mask_) >> LETTER_START_BIT);
     int node_index = static_cast<int>(
       (edge_ref & deref_node_index_mask_) >> flag_start_bit_);
     TRIE_NODE_RECORD *node_rec = nodes_[node_index];
     return &(node_rec->forward_edges[edge_index]);

◆ 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 79 of file trie.cpp.

                                                   {  // binary search
     EDGE_INDEX start = 0;
     EDGE_INDEX end = vec_size - 1;
     EDGE_INDEX k;
     int compare;
     while (start <= end) {
       k = (start + end) >> 1;  // (start + end) / 2
       compare = given_greater_than_edge_rec(next_node, word_end,
                                             unichar_id, vec[k]);
       if (compare == 0) {  // given == vec[k]
         *edge_ptr = &(vec[k]);
         *edge_index = k;
         return true;
       } else if (compare == 1) {  // given > vec[k]
         start = k + 1;
       } else {  // given < vec[k]
         end = k - 1;
       }
     }
   } else {  // linear search
     for (int i = 0; i < vec_size; ++i) {
       EDGE_RECORD &edge_rec = vec[i];
       if (edge_rec_match(next_node, word_end, unichar_id,
                          next_node_from_edge_rec(edge_rec),
                          end_of_word_from_edge_rec(edge_rec),
                          unichar_id_from_edge_rec(edge_rec))) {
         *edge_ptr = &(edge_rec);
         *edge_index = i;
         return true;
       }
     }
   }
   return false;  // not found
 }
  
 bool Trie::add_edge_linkage(NODE_REF node1, NODE_REF node2, bool marker_flag,
                             int direction, bool word_end,
                             UNICHAR_ID unichar_id) {
   EDGE_VECTOR *vec = (direction == FORWARD_EDGE) ?
     &(nodes_[node1]->forward_edges) : &(nodes_[node1]->backward_edges);
   int search_index;
   if (node1 == 0 && direction == FORWARD_EDGE) {
     search_index = 0;  // find the index to make the add sorted
     while (search_index < vec->size() &&
            given_greater_than_edge_rec(node2, word_end, unichar_id,
                                        (*vec)[search_index]) == 1) {
       search_index++;
     }
   } else {

◆ 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 96 of file trie.h.

                                                       {
     EDGE_RECORD *edge_ptr;
     EDGE_INDEX edge_index;
     if (!edge_char_of(node_ref, NO_EDGE, FORWARD_EDGE, word_end, unichar_id,
                       &edge_ptr, &edge_index)) return NO_EDGE;
     return make_edge_ref(node_ref, edge_index);

◆ 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 140 of file trie.h.

                                                            {
     if (edge_ref == NO_EDGE || num_edges_ == 0) return INVALID_UNICHAR_ID;
     return unichar_id_from_edge_rec(*deref_edge_ref(edge_ref));

◆ eliminate_redundant_edges()

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

protected

Definition at line 572 of file trie.cpp.

                                                               {
     const EDGE_RECORD &bkw_edge = next_node2_ptr->backward_edges[i];
     NODE_REF curr_next_node = next_node_from_edge_rec(bkw_edge);
     UNICHAR_ID curr_unichar_id = unichar_id_from_edge_rec(bkw_edge);
     int curr_word_end = end_of_word_from_edge_rec(bkw_edge);
     bool marker_flag = marker_flag_from_edge_rec(bkw_edge);
     add_edge_linkage(next_node1, curr_next_node, marker_flag, BACKWARD_EDGE,
                      curr_word_end, curr_unichar_id);
     // Relocate the corresponding forward edge in curr_next_node
     ASSERT_HOST(edge_char_of(curr_next_node, next_node2, FORWARD_EDGE,
                              curr_word_end, curr_unichar_id,
                              &edge_ptr, &edge_index));
     set_next_node_in_edge_rec(edge_ptr, next_node1);
   }
   int next_node2_num_edges = (next_node2_ptr->forward_edges.size() +
                               next_node2_ptr->backward_edges.size());
   if (debug_level_ > 1) {
     tprintf("removed %d edges from node " REFFORMAT "\n",
             next_node2_num_edges, next_node2);
   }
   next_node2_ptr->forward_edges.clear();
   next_node2_ptr->backward_edges.clear();
   num_edges_ -= next_node2_num_edges;
   return true;
 }
  
 bool Trie::reduce_lettered_edges(EDGE_INDEX edge_index,
                                  UNICHAR_ID unichar_id,
                                  NODE_REF node,
                                  EDGE_VECTOR* backward_edges,
                                  NODE_MARKER reduced_nodes) {
   if (debug_level_ > 1)
     tprintf("reduce_lettered_edges(edge=" REFFORMAT ")\n", edge_index);
   // Compare each of the edge pairs with the given unichar_id.
   bool did_something = false;
   for (int i = edge_index; i < backward_edges->size() - 1; ++i) {
     // Find the first edge that can be eliminated.
     UNICHAR_ID curr_unichar_id = INVALID_UNICHAR_ID;
     while (i < backward_edges->size()) {
       if (!DeadEdge((*backward_edges)[i])) {

◆ 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 134 of file trie.h.

                                                      {
     if (edge_ref == NO_EDGE || num_edges_ == 0) return false;
     return end_of_word_from_edge_rec(*deref_edge_ref(edge_ref));

◆ get_reverse_policy_name()

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

static

Definition at line 66 of file trie.cpp.

                                                                               {
   if (debug_level_ == 3) {
     tprintf("edge_char_of() given node_ref " REFFORMAT " next_node " REFFORMAT

◆ initialize_patterns()

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

Definition at line 351 of file trie.cpp.

                                                                         {
   bool is_alpha = unicharset.get_isalpha(unichar_id);
   if (is_alpha) {
     vec->push_back(alpha_pattern_);
     vec->push_back(alphanum_pattern_);
     if (unicharset.get_islower(unichar_id)) {
       vec->push_back(lower_pattern_);
     } else if (unicharset.get_isupper(unichar_id)) {
       vec->push_back(upper_pattern_);
     }
   }
   if (unicharset.get_isdigit(unichar_id)) {

◆ KillEdge()

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

inline

Definition at line 146 of file trie.h.

                                              {
     *edge_rec &= ~letter_mask_;
     *edge_rec |= (unicharset_size_ << LETTER_START_BIT);

◆ 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 298 of file trie.h.

                                                                              {
     EDGE_RECORD flags = 0;
     if (repeats) flags |= MARKER_FLAG;
     if (word_end) flags |= WERD_END_FLAG;
     if (direction == BACKWARD_EDGE) flags |= DIRECTION_FLAG;
     *edge = ((nxt << next_node_start_bit_) |
              (static_cast<EDGE_RECORD>(flags) << flag_start_bit_) |
              (static_cast<EDGE_RECORD>(unichar_id) << LETTER_START_BIT));

◆ 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 292 of file trie.h.

                                                              {
     return ((node_index << flag_start_bit_) |
             (edge_index << LETTER_START_BIT));

◆ new_dawg_node()

NODE_REF tesseract::Trie::new_dawg_node ( )

protected

Definition at line 282 of file trie.cpp.

                                                                        {
   GenericVector<STRING> word_list;
   if (!read_word_list(filename, &word_list)) return false;
   word_list.sort(sort_strings_by_dec_length);
   return add_word_list(word_list, unicharset, reverse_policy);

◆ 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 125 of file trie.h.

                                                        {
     if (edge_ref == NO_EDGE || num_edges_ == 0) return NO_EDGE;
     return next_node_from_edge_rec(*deref_edge_ref(edge_ref));

◆ 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 239 of file trie.h.

                                                                    {
     if (edge_ref == NO_EDGE) return NO_EDGE;
     EDGE_RECORD *edge_rec = deref_edge_ref(edge_ref);
     return (marker_flag_from_edge_rec(*edge_rec) &&
             unichar_id == unichar_id_from_edge_rec(*edge_rec) &&
             word_end == end_of_word_from_edge_rec(*edge_rec)) ?
             edge_ref : NO_EDGE;

◆ print_all()

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

inlineprotected

Definition at line 326 of file trie.h.

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

◆ print_edge_rec()

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

inlineprotected

Prints the given EDGE_RECORD.

Definition at line 309 of file trie.h.

                                                                 {
     tprintf("|" REFFORMAT "|%s%s%s|%d|", next_node_from_edge_rec(edge_rec),
             marker_flag_from_edge_rec(edge_rec) ? "R," : "",
             (direction_from_edge_rec(edge_rec) == FORWARD_EDGE) ? "F" : "B",
             end_of_word_from_edge_rec(edge_rec) ? ",E" : "",
             unichar_id_from_edge_rec(edge_rec));

◆ 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 711 of file trie.cpp.

                                         : i < num_bkw) &&
          i < max_num_edges; ++i) {
       if (DeadEdge((*vec)[i])) continue;
       print_edge_rec((*vec)[i]);
       tprintf(" ");
     }
     if (dir == 0 ? i < num_fwd : i < num_bkw) tprintf("...");
     tprintf("\n");
   }
 }
  
 }  // namespace tesseract

◆ 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 295 of file trie.cpp.

                                                                   {
     chomp_string(line_str);  // remove newline
     STRING word_str(line_str);
     ++word_count;
     if (debug_level_ && word_count % 10000 == 0)

◆ read_pattern_list()

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

Definition at line 408 of file trie.cpp.

                                                                  {
     chomp_string(string);  // remove newline
     // Parse the pattern and construct a unichar id vector.
     // Record the number of repetitions of each unichar in the parallel vector.
     WERD_CHOICE word(&unicharset);
     GenericVector<bool> repetitions_vec;
     const char *str_ptr = string;
     int step = unicharset.step(str_ptr);
     bool failed = false;
     while (step > 0) {
       UNICHAR_ID curr_unichar_id = INVALID_UNICHAR_ID;
       if (step == 1 && *str_ptr == '\\') {
         ++str_ptr;
         if (*str_ptr == '\\') {  // regular '\' unichar that was escaped
           curr_unichar_id = unicharset.unichar_to_id(str_ptr, step);
         } else {
           if (word.length() < kSaneNumConcreteChars) {
             tprintf("Please provide at least %d concrete characters at the"
                     " beginning of the pattern\n", kSaneNumConcreteChars);
             failed = true;
             break;
           }
           // Parse character class from expression.
           curr_unichar_id = character_class_to_pattern(*str_ptr);
         }
       } else {
         curr_unichar_id = unicharset.unichar_to_id(str_ptr, step);
       }
       if (curr_unichar_id ==  INVALID_UNICHAR_ID) {
         failed = true;
         break;  // failed to parse this pattern
       }
       word.append_unichar_id(curr_unichar_id, 1, 0.0, 0.0);
       repetitions_vec.push_back(false);
       str_ptr += step;
       step = unicharset.step(str_ptr);
       // Check if there is a repetition pattern specified after this unichar.
       if (step == 1 && *str_ptr == '\\' && *(str_ptr+1) == '*') {
         repetitions_vec[repetitions_vec.size()-1] = true;
         str_ptr += 2;
         step = unicharset.step(str_ptr);
       }
     }
     if (failed) {
       tprintf("Invalid user pattern %s\n", string);
       continue;
     }
     // Insert the pattern into the trie.
     if (debug_level_ > 2) {
       tprintf("Inserting expanded user pattern %s\n",
               word.debug_string().c_str());
     }
     if (!this->word_in_dawg(word)) {
       this->add_word_to_dawg(word, &repetitions_vec);
       if (!this->word_in_dawg(word)) {
         tprintf("Error: failed to insert pattern '%s'\n", string);
       }
     }
     ++pattern_count;
   }
   if (debug_level_) {
     tprintf("Read %d valid patterns from %s\n", pattern_count, filename);
   }
   fclose(pattern_file);
   return true;
 }
  
 void Trie::remove_edge_linkage(NODE_REF node1, NODE_REF node2, int direction,
                                bool word_end, UNICHAR_ID unichar_id) {
   EDGE_RECORD *edge_ptr = nullptr;
   EDGE_INDEX edge_index = 0;
   ASSERT_HOST(edge_char_of(node1, node2, direction, word_end,
                            unichar_id, &edge_ptr, &edge_index));
   if (debug_level_ > 1) {
     tprintf("removed edge in nodes_[" REFFORMAT "]: ", node1);
     print_edge_rec(*edge_ptr);
     tprintf("\n");
   }
   if (direction == FORWARD_EDGE) {
     nodes_[node1]->forward_edges.remove(edge_index);
   } else if (node1 == 0) {

◆ read_word_list()

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

Definition at line 304 of file trie.cpp.

                                                               {
   for (int i = 0; i < words.size(); ++i) {
     WERD_CHOICE word(words[i].c_str(), unicharset);
     if (word.length() == 0 || word.contains_unichar_id(INVALID_UNICHAR_ID))
       continue;
     if ((reverse_policy == RRP_REVERSE_IF_HAS_RTL &&
          word.has_rtl_unichar_id()) ||
         reverse_policy == RRP_FORCE_REVERSE) {
       word.reverse_and_mirror_unichar_ids();
     }
     if (!word_in_dawg(word)) {
       add_word_to_dawg(word);

◆ 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 619 of file trie.cpp.

                                                          {
       const EDGE_RECORD &next_edge_rec = (*backward_edges)[j];
       if (DeadEdge(next_edge_rec)) continue;
       UNICHAR_ID next_id = unichar_id_from_edge_rec(next_edge_rec);
       if (next_id != unichar_id) break;
       if (end_of_word_from_edge_rec(next_edge_rec) ==
           end_of_word_from_edge_rec(edge_rec) &&
           can_be_eliminated(next_edge_rec) &&
           eliminate_redundant_edges(node, edge_rec, next_edge_rec)) {
         reduced_nodes[next_node_from_edge_rec(edge_rec)] = false;
         did_something = true;
         KillEdge(&(*backward_edges)[j]);
       }
     }
   }
   return did_something;
 }
  
 void Trie::sort_edges(EDGE_VECTOR *edges) {
   int num_edges = edges->size();
   if (num_edges <= 1) return;
   GenericVector<KDPairInc<UNICHAR_ID, EDGE_RECORD> > sort_vec;
   sort_vec.reserve(num_edges);
   for (int i = 0; i < num_edges; ++i) {
     sort_vec.push_back(KDPairInc<UNICHAR_ID, EDGE_RECORD>(
         unichar_id_from_edge_rec((*edges)[i]), (*edges)[i]));
   }
   sort_vec.sort();
   for (int i = 0; i < num_edges; ++i)
     (*edges)[i] = sort_vec[i].data;
 }
  

◆ 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 674 of file trie.cpp.

                                                  {
       UNICHAR_ID id = unichar_id_from_edge_rec(backward_edges[edge_index]);
       if (!DeadEdge(backward_edges[edge_index]) && id != unichar_id) break;
     }
   }
   reduced_nodes[node] = true;  // mark as reduced
  
   if (debug_level_ > 1) {
     tprintf("Node " REFFORMAT " after reduction:\n", node);
     print_node(node, MAX_NODE_EDGES_DISPLAY);
   }
  
   for (int i = 0; i < backward_edges.size(); ++i) {
     if (DeadEdge(backward_edges[i])) continue;
     NODE_REF next_node = next_node_from_edge_rec(backward_edges[i]);
     if (next_node != 0 && !reduced_nodes[next_node]) {
       reduce_node_input(next_node, reduced_nodes);
     }
   }
 }
  
 void Trie::print_node(NODE_REF node, int max_num_edges) const {
   if (node == NO_EDGE) return;  // nothing to print
   TRIE_NODE_RECORD *node_ptr = nodes_[node];
   int num_fwd = node_ptr->forward_edges.size();
   int num_bkw = node_ptr->backward_edges.size();
   EDGE_VECTOR *vec;
   for (int dir = 0; dir < 2; ++dir) {
     if (dir == 0) {
       vec = &(node_ptr->forward_edges);
       tprintf(REFFORMAT " (%d %d): ", node, num_fwd, num_bkw);
     } else {
       vec = &(node_ptr->backward_edges);
       tprintf("\t");
     }

◆ remove_edge()

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

inlineprotected

Definition at line 373 of file trie.h.

                                                          {
     remove_edge_linkage(node1, node2, FORWARD_EDGE, word_end, unichar_id);
     remove_edge_linkage(node2, node1, BACKWARD_EDGE, word_end, unichar_id);

◆ 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 490 of file trie.cpp.

          {
     nodes_[node1]->backward_edges.remove(edge_index);
   }
   --num_edges_;
 }
  
 // Some optimizations employed in add_word_to_dawg and trie_to_dawg:
 // 1 Avoid insertion sorting or bubble sorting the tail root node
 //   (back links on node 0, a list of all the leaves.). The node is
 //   huge, and sorting it with n^2 time is terrible.
 // 2 Avoid using GenericVector::remove on the tail root node.
 //   (a) During add of words to the trie, zero-out the unichars and
 //       keep a freelist of spaces to re-use.
 //   (b) During reduction, just zero-out the unichars of deleted back
 //       links, skipping zero entries while searching.
 // 3 Avoid linear search of the tail root node. This has to be done when
 //   a suffix is added to an existing word. Adding words by decreasing
 //   length avoids this problem entirely. Words can still be added in
 //   any order, but it is faster to add the longest first.
 SquishedDawg *Trie::trie_to_dawg() {

◆ 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 660 of file trie.cpp.

                                                         {
   EDGE_VECTOR &backward_edges = nodes_[node]->backward_edges;
   sort_edges(&backward_edges);
   if (debug_level_ > 1) {
     tprintf("reduce_node_input(node=" REFFORMAT ")\n", node);
     print_node(node, MAX_NODE_EDGES_DISPLAY);
   }
  
   EDGE_INDEX edge_index = 0;
   while (edge_index < backward_edges.size()) {
     if (DeadEdge(backward_edges[edge_index])) continue;
     UNICHAR_ID unichar_id =
       unichar_id_from_edge_rec(backward_edges[edge_index]);

◆ trie_to_dawg()

SquishedDawg * tesseract::Trie::trie_to_dawg ( )

Definition at line 525 of file trie.cpp.

                                       {
     node_ref_map[i+1] = node_ref_map[i] + nodes_[i]->forward_edges.size();
   }
   int num_forward_edges = node_ref_map[i];
  
   // Convert nodes_ vector into EDGE_ARRAY translating the next node references
   // in edges using node_ref_map. Empty nodes and backward edges are dropped.
   auto edge_array = new EDGE_RECORD[num_forward_edges];
   EDGE_ARRAY edge_array_ptr = edge_array;
   for (i = 0; i < nodes_.size(); ++i) {
     TRIE_NODE_RECORD *node_ptr = nodes_[i];
     int end = node_ptr->forward_edges.size();
     for (j = 0; j < end; ++j) {
       EDGE_RECORD &edge_rec = node_ptr->forward_edges[j];
       NODE_REF node_ref = next_node_from_edge_rec(edge_rec);
       ASSERT_HOST(node_ref < nodes_.size());
       UNICHAR_ID unichar_id = unichar_id_from_edge_rec(edge_rec);
       link_edge(edge_array_ptr, node_ref_map[node_ref], false, FORWARD_EDGE,
                 end_of_word_from_edge_rec(edge_rec), unichar_id);
       if (j == end - 1) set_marker_flag_in_edge_rec(edge_array_ptr);
       ++edge_array_ptr;
     }
   }
   delete[] node_ref_map;
  
   return new SquishedDawg(edge_array, num_forward_edges, type_, lang_,
                           perm_, unicharset_size_, debug_level_);
 }
  
 bool Trie::eliminate_redundant_edges(NODE_REF node,
                                      const EDGE_RECORD &edge1,
                                      const EDGE_RECORD &edge2) {
   if (debug_level_ > 1) {
     tprintf("\nCollapsing node %" PRIi64 ":\n", node);
     print_node(node, MAX_NODE_EDGES_DISPLAY);
     tprintf("Candidate edges: ");
     print_edge_rec(edge1);
     tprintf(", ");
     print_edge_rec(edge2);
     tprintf("\n\n");
   }
   NODE_REF next_node1 = next_node_from_edge_rec(edge1);
   NODE_REF next_node2 = next_node_from_edge_rec(edge2);

◆ 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 368 of file trie.cpp.

                                                 {
     vec->push_back(punc_pattern_);
   }
 }
  
 UNICHAR_ID Trie::character_class_to_pattern(char ch) {
   if (ch == 'c') {
     return alpha_pattern_;
   } else if (ch == 'd') {
     return digit_pattern_;
   } else if (ch == 'n') {
     return alphanum_pattern_;
   } else if (ch == 'p') {
     return punc_pattern_;
   } else if (ch == 'a') {
     return lower_pattern_;
   } else if (ch == 'A') {
     return upper_pattern_;
   } else {

◆ 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 109 of file trie.h.

                                                     {
     const EDGE_VECTOR &forward_edges =
       nodes_[static_cast<int>(node)]->forward_edges;
     for (int i = 0; i < forward_edges.size(); ++i) {
       if (!word_end || end_of_word_from_edge_rec(forward_edges[i])) {
         vec->push_back(NodeChild(unichar_id_from_edge_rec(forward_edges[i]),
                                  make_edge_ref(node, i)));
       }
     }

Definition at line 413 of file trie.h.

◆ upper_pattern_

UNICHAR_ID tesseract::Trie::upper_pattern_

protected

Definition at line 424 of file trie.h.

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

/tesseract/src/dict/trie.h
/tesseract/src/dict/trie.cpp

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Enumeration Documentation

◆ RTLReversePolicy

Constructor & Destructor Documentation

◆ Trie()

◆ ~Trie()

Member Function Documentation

◆ add_edge_linkage()

◆ add_new_edge()

◆ add_word_ending()

◆ add_word_list()

◆ add_word_to_dawg() [1/2]

◆ add_word_to_dawg() [2/2]

◆ can_be_eliminated()

◆ character_class_to_pattern()

◆ clear()

◆ DeadEdge()

◆ deref_edge_ref()

◆ edge_char_of() [1/2]

◆ edge_char_of() [2/2]

◆ edge_letter()

◆ eliminate_redundant_edges()

◆ end_of_word()

◆ get_reverse_policy_name()

◆ initialize_patterns()

◆ KillEdge()

◆ link_edge()

◆ make_edge_ref()

◆ new_dawg_node()

◆ next_node()

◆ pattern_loop_edge()

◆ print_all()

◆ print_edge_rec()

◆ print_node()

◆ read_and_add_word_list()

◆ read_pattern_list()

◆ read_word_list()

◆ reduce_lettered_edges()

◆ reduce_node_input()

◆ remove_edge()

◆ remove_edge_linkage()

◆ sort_edges()

◆ trie_to_dawg()

◆ unichar_id_to_patterns()

◆ unichar_ids_of()

Member Data Documentation

◆ alpha_pattern_

◆ alphanum_pattern_

◆ deref_direction_mask_

◆ deref_node_index_mask_

◆ digit_pattern_

◆ initialized_patterns_

◆ kAlphanumPatternUnicode

◆ kAlphaPatternUnicode

◆ kDigitPatternUnicode

◆ kLowerPatternUnicode

◆ kPuncPatternUnicode

◆ kSaneNumConcreteChars

◆ kUpperPatternUnicode

◆ lower_pattern_

◆ nodes_

◆ num_edges_

◆ punc_pattern_

◆ root_back_freelist_

◆ upper_pattern_