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