71 static const int kSaneNumConcreteChars = 0;
75 static const char kAlphaPatternUnicode[];
76 static const char kDigitPatternUnicode[];
77 static const char kAlphanumPatternUnicode[];
78 static const char kPuncPatternUnicode[];
79 static const char kLowerPatternUnicode[];
80 static const char kUpperPatternUnicode[];
82 static const char *get_reverse_policy_name(
90 int unicharset_size,
int debug_level) {
91 init(type, lang, perm, unicharset_size, debug_level);
93 deref_node_index_mask_ = ~letter_mask_;
95 initialized_patterns_ =
false;
97 virtual ~Trie() { nodes_.delete_data_pointers(); }
104 bool word_end)
const {
107 if (!edge_char_of(node_ref, NO_EDGE,
FORWARD_EDGE, word_end, unichar_id,
108 &edge_ptr, &edge_index))
return NO_EDGE;
109 return make_edge_ref(node_ref, edge_index);
117 bool word_end)
const {
119 nodes_[
static_cast<int>(node)]->forward_edges;
120 for (
int i = 0; i < forward_edges.
size(); ++i) {
121 if (!word_end || end_of_word_from_edge_rec(forward_edges[i])) {
123 make_edge_ref(node, i)));
133 if (edge_ref == NO_EDGE || num_edges_ == 0)
return NO_EDGE;
134 return next_node_from_edge_rec(*deref_edge_ref(edge_ref));
142 if (edge_ref == NO_EDGE || num_edges_ == 0)
return false;
143 return end_of_word_from_edge_rec(*deref_edge_ref(edge_ref));
148 if (edge_ref == NO_EDGE || num_edges_ == 0)
return INVALID_UNICHAR_ID;
149 return unichar_id_from_edge_rec(*deref_edge_ref(edge_ref));
154 *edge_rec &= ~letter_mask_;
158 return unichar_id_from_edge_rec(edge_rec) == unicharset_size_;
163 void print_node(
NODE_REF node,
int max_num_edges)
const;
175 bool read_and_add_word_list(
const char *
filename,
182 bool read_word_list(
const char *filename,
233 bool read_pattern_list(
const char *filename,
const UNICHARSET &unicharset);
237 void initialize_patterns(
UNICHARSET *unicharset);
241 void unichar_id_to_patterns(
UNICHAR_ID unichar_id,
250 bool word_end)
const {
251 if (edge_ref == NO_EDGE)
return NO_EDGE;
253 return (marker_flag_from_edge_rec(*edge_rec) &&
254 unichar_id == unichar_id_from_edge_rec(*edge_rec) &&
255 word_end == end_of_word_from_edge_rec(*edge_rec)) ?
271 return add_word_to_dawg(word,
NULL);
293 int edge_index =
static_cast<int>(
295 int node_index =
static_cast<int>(
296 (edge_ref & deref_node_index_mask_) >> flag_start_bit_);
303 return ((node_index << flag_start_bit_) |
313 *edge = ((nxt << next_node_start_bit_) |
314 (static_cast<EDGE_RECORD>(flags) << flag_start_bit_) |
320 marker_flag_from_edge_rec(edge_rec) ?
"R," :
"",
321 (direction_from_edge_rec(edge_rec) ==
FORWARD_EDGE) ?
"F" :
"B",
322 end_of_word_from_edge_rec(edge_rec) ?
",E" :
"",
323 unichar_id_from_edge_rec(edge_rec));
328 NODE_REF node_ref = next_node_from_edge_rec(edge_rec);
329 return (node_ref != NO_EDGE &&
336 tprintf(
"\n__________________________\n%s\n", msg);
337 for (
int i = 0; i < nodes_.size(); ++i) print_node(i, max_num_edges);
338 tprintf(
"__________________________\n");
352 int direction,
bool word_end,
358 bool repeats,
bool word_end,
UNICHAR_ID unichar_id) {
359 return (add_edge_linkage(node1, node2, repeats,
FORWARD_EDGE,
360 word_end, unichar_id) &&
362 word_end, unichar_id));
384 remove_edge_linkage(node1, node2,
FORWARD_EDGE, word_end, unichar_id);
385 remove_edge_linkage(node2, node1,
BACKWARD_EDGE, word_end, unichar_id);
399 bool reduce_lettered_edges(
EDGE_INDEX edge_index,
417 UNICHAR_ID character_class_to_pattern(
char ch);
uinT64 deref_node_index_mask_
EDGE_VECTOR forward_edges
virtual EDGE_REF pattern_loop_edge(EDGE_REF edge_ref, UNICHAR_ID unichar_id, bool word_end) const
bool DeadEdge(const EDGE_RECORD &edge_rec) const
EDGE_REF edge_char_of(NODE_REF node_ref, UNICHAR_ID unichar_id, bool word_end) const
GenericVector< TRIE_NODE_RECORD * > TRIE_NODES
void link_edge(EDGE_RECORD *edge, NODE_REF nxt, bool repeats, int direction, bool word_end, UNICHAR_ID unichar_id)
GenericVector< EDGE_RECORD > EDGE_VECTOR
void print_all(const char *msg, int max_num_edges)
void remove_edge(NODE_REF node1, NODE_REF node2, bool word_end, UNICHAR_ID unichar_id)
UNICHAR_ID alpha_pattern_
void print_edge_rec(const EDGE_RECORD &edge_rec) const
bool add_new_edge(NODE_REF node1, NODE_REF node2, bool repeats, bool word_end, UNICHAR_ID unichar_id)
void unichar_ids_of(NODE_REF node, NodeChildVector *vec, bool word_end) const
EDGE_VECTOR backward_edges
bool initialized_patterns_
EDGE_RECORD * deref_edge_ref(EDGE_REF edge_ref) const
EDGE_REF make_edge_ref(NODE_REF node_index, EDGE_INDEX edge_index) const
UNICHAR_ID digit_pattern_
UNICHAR_ID upper_pattern_
unsigned long long int uinT64
bool end_of_word(EDGE_REF edge_ref) const
bool add_word_to_dawg(const WERD_CHOICE &word)
void KillEdge(EDGE_RECORD *edge_rec) const
bool can_be_eliminated(const EDGE_RECORD &edge_rec)
int direction(EDGEPT *point)
UNICHAR_ID lower_pattern_
Trie(DawgType type, const STRING &lang, PermuterType perm, int unicharset_size, int debug_level)
NODE_REF next_node(EDGE_REF edge_ref) const
GenericVector< EDGE_INDEX > root_back_freelist_
UNICHAR_ID alphanum_pattern_
UNICHAR_ID edge_letter(EDGE_REF edge_ref) const
uinT64 deref_direction_mask_