41 #define NO_EDGE (inT64) 0xffffffffffffffffi64 44 #define NO_EDGE (inT64) 0xffffffffffffffffll 64 NodeChild(): unichar_id(INVALID_UNICHAR_ID), edge_ref(NO_EDGE) {}
84 #define FORWARD_EDGE (inT32) 0 85 #define BACKWARD_EDGE (inT32) 1 86 #define MAX_NODE_EDGES_DISPLAY (inT64) 100 87 #define MARKER_FLAG (inT64) 1 88 #define DIRECTION_FLAG (inT64) 2 89 #define WERD_END_FLAG (inT64) 4 90 #define LETTER_START_BIT 0 91 #define NUM_FLAG_BITS 3 92 #define REFFORMAT "%lld" 101 static const char kWildcard[] =
"*";
121 static const inT16 kDawgMagicNumber = 42;
138 bool prefix_in_dawg(
const WERD_CHOICE &prefix,
bool requires_complete)
const;
142 int check_for_words(
const char *
filename,
144 bool enable_wildcard)
const;
148 void iterate_words(
const UNICHARSET &unicharset,
153 void iterate_words(
const UNICHARSET &unicharset,
160 bool word_end)
const = 0;
164 virtual void unichar_ids_of(
NODE_REF node, NodeChildVector *vec,
165 bool word_end)
const = 0;
173 virtual bool end_of_word(
EDGE_REF edge_ref)
const = 0;
180 virtual void print_node(
NODE_REF node,
int max_num_edges)
const = 0;
201 return ((edge_rec & next_node_mask_) >> next_node_start_bit_);
205 return (edge_rec & (
MARKER_FLAG << flag_start_bit_)) != 0;
224 *edge_rec &= (~next_node_mask_);
225 *edge_rec |= ((value << next_node_start_bit_) & next_node_mask_);
242 UNICHAR_ID curr_unichar_id = unichar_id_from_edge_rec(edge_rec);
243 NODE_REF curr_next_node = next_node_from_edge_rec(edge_rec);
244 bool curr_word_end = end_of_word_from_edge_rec(edge_rec);
245 if (edge_rec_match(next_node, word_end, unichar_id, curr_next_node,
246 curr_word_end, curr_unichar_id))
return 0;
247 if (unichar_id > curr_unichar_id)
return 1;
248 if (unichar_id == curr_unichar_id) {
249 if (next_node > curr_next_node)
return 1;
250 if (next_node == curr_next_node) {
251 if (word_end > curr_word_end)
return 1;
265 return ((unichar_id == other_unichar_id) &&
266 (next_node == NO_EDGE || next_node == other_next_node) &&
267 (!word_end || (word_end == other_word_end)));
273 PermuterType perm,
int unicharset_size,
int debug_level);
284 void iterate_words_rec(
const WERD_CHOICE &word_so_far,
344 : dawg_index(-1), dawg_ref(NO_EDGE), punc_ref(NO_EDGE),
345 back_to_punc(false) {}
349 : dawg_index(dawg_idx), dawg_ref(dawgref),
350 punc_index(punc_idx), punc_ref(puncref),
351 back_to_punc(backtopunc) {
373 if (size_reserved_ > 0) {
387 const char *debug_msg) {
388 for (
int i = 0; i < size_used_; ++i) {
389 if (data_[i] == new_pos)
return false;
413 read_squished_dawg(file, type, lang, perm, debug_level);
414 num_forward_edges_in_node0 = num_forward_edges(0);
418 FILE *file = fopen(filename,
"rb");
420 tprintf(
"Failed to open dawg file %s\n", filename);
423 read_squished_dawg(file, type, lang, perm, debug_level);
424 num_forward_edges_in_node0 = num_forward_edges(0);
429 int unicharset_size,
int debug_level) :
430 edges_(edges), num_edges_(num_edges) {
431 init(type, lang, perm, unicharset_size, debug_level);
432 num_forward_edges_in_node0 = num_forward_edges(0);
433 if (debug_level > 3) print_all(
"SquishedDawg:");
441 bool word_end)
const;
446 bool word_end)
const {
448 if (!edge_occupied(edge) || edge == NO_EDGE)
return;
449 assert(forward_edge(edge));
451 if (!word_end || end_of_word_from_edge_rec(edges_[edge])) {
454 }
while (!last_edge(edge++));
460 return next_node_from_edge_rec((edges_[edge]));
466 return end_of_word_from_edge_rec((edges_[edge_ref]));
471 return unichar_id_from_edge_rec((edges_[edge_ref]));
476 void print_node(
NODE_REF node,
int max_num_edges)
const;
479 void write_squished_dawg(FILE *file);
484 FILE *file = fopen(filename,
"wb");
486 tprintf(
"Error opening %s\n", filename);
489 this->write_squished_dawg(file);
496 set_next_node_in_edge_rec(&(edges_[edge_ref]), value);
499 inline void set_empty_edge(
EDGE_REF edge_ref) {
500 (edges_[
edge_ref] = next_node_mask_);
503 inline void clear_all_edges() {
504 for (
int edge = 0; edge < num_edges_; edge++) set_empty_edge(edge);
507 inline void clear_marker_flag(
EDGE_REF edge_ref) {
511 inline bool forward_edge(
EDGE_REF edge_ref)
const {
512 return (edge_occupied(edge_ref) &&
513 (
FORWARD_EDGE == direction_from_edge_rec(edges_[edge_ref])));
516 inline bool backward_edge(
EDGE_REF edge_ref)
const {
517 return (edge_occupied(edge_ref) &&
518 (
BACKWARD_EDGE == direction_from_edge_rec(edges_[edge_ref])));
521 inline bool edge_occupied(
EDGE_REF edge_ref)
const {
522 return (edges_[edge_ref] != next_node_mask_);
525 inline bool last_edge(
EDGE_REF edge_ref)
const {
526 return (edges_[edge_ref] & (
MARKER_FLAG << flag_start_bit_)) != 0;
537 void print_edge(
EDGE_REF edge)
const;
540 void print_all(
const char* msg) {
541 tprintf(
"\n__________________________\n%s\n", msg);
542 for (
int i = 0; i < num_edges_; ++i) print_edge(i);
543 tprintf(
"__________________________\n");
552 int num_forward_edges_in_node0;
557 #endif // DICT_DAWG_H_
NODE_REF next_node_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns the next node visited by following this edge.
SquishedDawg(FILE *file, DawgType type, const STRING &lang, PermuterType perm, int debug_level)
~DawgPositionVector()
Overload destructor, since clear() does not delete data_[] any more.
NODE_REF next_node(EDGE_REF edge) const
SquishedDawg(const char *filename, DawgType type, const STRING &lang, PermuterType perm, int debug_level)
bool marker_flag_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns the marker flag of this edge.
GenericVector< SuccessorList * > SuccessorListsVector
PermuterType permuter() const
void unichar_ids_of(NODE_REF node, NodeChildVector *vec, bool word_end) const
bool end_of_word(EDGE_REF edge_ref) const
DawgPosition(int dawg_idx, EDGE_REF dawgref, int punc_idx, EDGE_REF puncref, bool backtopunc)
bool add_unique(const DawgPosition &new_pos, bool debug, const char *debug_msg)
virtual EDGE_REF pattern_loop_edge(EDGE_REF edge_ref, UNICHAR_ID unichar_id, bool word_end) const
const STRING & lang() const
unsigned long long int uinT64
NodeChild(UNICHAR_ID id, EDGE_REF ref)
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.
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
SquishedDawg(EDGE_ARRAY edges, int num_edges, DawgType type, const STRING &lang, PermuterType perm, int unicharset_size, int debug_level)
UNICHAR_ID unichar_id_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns UNICHAR_ID recorded in this edge.
int direction_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns the direction flag of this edge.
virtual void unichar_id_to_patterns(UNICHAR_ID unichar_id, const UNICHARSET &unicharset, GenericVector< UNICHAR_ID > *vec) const
bool operator==(const DawgPosition &other)
GenericVector< NodeChild > NodeChildVector
GenericVector< int > SuccessorList
int given_greater_than_edge_rec(NODE_REF next_node, bool word_end, UNICHAR_ID unichar_id, const EDGE_RECORD &edge_rec) const
void write_squished_dawg(const char *filename)
UNICHAR_ID edge_letter(EDGE_REF edge_ref) const
Returns UNICHAR_ID stored in the edge indicated by the given EDGE_REF.
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.
bool end_of_word_from_edge_rec(const EDGE_RECORD &edge_rec) const
Returns true if this edge marks the end of a word.
PermuterType perm_
Permuter code that should be used if the word is found in this Dawg.