/* -*-C-*-
********************************************************************************
*
* File: dawg.h (Formerly dawg.h)
* Description: Definition of a class that represents Directed Accyclic Word
* Graph (DAWG), functions to build and manipulate the DAWG.
* Author: Mark Seaman, SW Productivity
* Created: Fri Oct 16 14:37:00 1987
* Modified: Wed Jun 19 16:50:24 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 DAWG_H
#define DAWG_H
/*----------------------------------------------------------------------
I n c l u d e s
----------------------------------------------------------------------*/
#include "elst.h"
#include "general.h"
#include "ratngs.h"
#include "varable.h"
/*----------------------------------------------------------------------
V a r i a b l e s
----------------------------------------------------------------------*/
extern INT_VAR_H(dawg_debug_level, 0, "Set to 1 for general debug info, to"
" 2 for more details, to 3 to see all the debug messages");
#ifdef __MSW32__
#define NO_EDGE (inT64) 0xffffffffffffffffi64
#else
#define NO_EDGE (inT64) 0xffffffffffffffffll
#endif
/*----------------------------------------------------------------------
T y p e s
----------------------------------------------------------------------*/
class UNICHARSET;
typedef uinT64 EDGE_RECORD;
typedef EDGE_RECORD *EDGE_ARRAY;
typedef inT64 EDGE_REF;
typedef inT64 NODE_REF;
typedef EDGE_REF *NODE_MAP;
namespace tesseract {
struct NodeChild {
UNICHAR_ID unichar_id;
EDGE_REF edge_ref;
NodeChild(UNICHAR_ID id, EDGE_REF ref): unichar_id(id), edge_ref(ref) {}
NodeChild(): unichar_id(INVALID_UNICHAR_ID), edge_ref(NO_EDGE) {}
};
typedef GenericVector<NodeChild> NodeChildVector;
typedef GenericVector<int> SuccessorList;
typedef GenericVector<SuccessorList *> SuccessorListsVector;
enum DawgType {
DAWG_TYPE_PUNCTUATION,
DAWG_TYPE_PREFIX,
DAWG_TYPE_ROOT,
DAWG_TYPE_WORD,
DAWG_TYPE_SUFFIX,
DAWG_TYPE_NUMBER,
DAWG_TYPE_COUNT // number of enum entries
};
/*----------------------------------------------------------------------
C o n s t a n t s
----------------------------------------------------------------------*/
#define FORWARD_EDGE (inT32) 0
#define BACKWARD_EDGE (inT32) 1
#define MAX_NODE_EDGES_DISPLAY (inT64) 100
#define LAST_FLAG (inT64) 1
#define DIRECTION_FLAG (inT64) 2
#define WERD_END_FLAG (inT64) 4
#define LETTER_START_BIT 0
#define NUM_FLAG_BITS 3
#define REFFORMAT "%lld"
// Set kBeginningDawgsType[i] to true if a Dawg of
// DawgType i can contain the beginning of a word.
static const bool kBeginningDawgsType[] = {1, 1, 0, 1, 0, 1 };
static const bool kDawgSuccessors[DAWG_TYPE_COUNT][DAWG_TYPE_COUNT] = {
{ 0, 1, 0, 1, 0, 0 }, // for DAWG_TYPE_PUNCTUATION
{ 0, 0, 1, 1, 0, 0 }, // for DAWG_TYPE_PREFIX
{ 0, 0, 0, 0, 1, 0 }, // for DAWG_TYPE_ROOT
{ 1, 0, 0, 0, 0, 0 }, // for DAWG_TYPE_WORD
{ 1, 0, 0, 0, 0, 0 }, // for DAWG_TYPE_SUFFIX
{ 0, 0, 0, 0, 0, 0 } // for DAWG_TYPE_NUMBER
};
static const char kWildcard[] = "*";
/*----------------------------------------------------------------------
C l a s s e s a n d S t r u c t s
----------------------------------------------------------------------*/
//
// 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).
//
class Dawg {
public:
// Magic number to determine endianness when reading the Dawg from file.
static const inT16 kDawgMagicNumber = 42;
// A special unichar id that indicates that any appropriate pattern
// (e.g.dicitonary word, 0-9 digit, etc) can be inserted instead
// Used for expressing patterns in punctuation and number Dawgs.
static const UNICHAR_ID kPatternUnicharID = 0;
inline DawgType type() const { return type_; }
inline const STRING &lang() const { return lang_; }
inline PermuterType permuter() const { return perm_; }
virtual ~Dawg() {};
// Returns true if the given word is in the Dawg.
bool word_in_dawg(const WERD_CHOICE &word) 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.
int check_for_words(const char *filename,
const UNICHARSET &unicharset,
bool enable_wildcard) const;
// Pure virtual function that should be implemented by the derived classes.
// Returns the edge that corresponds to the letter out of this node.
virtual EDGE_REF edge_char_of(NODE_REF node, UNICHAR_ID unichar_id,
bool word_end) const = 0;
// Fills the given NodeChildVector with all the unichar ids (and the
// corresponding EDGE_REFs) for which there is an edge out of this node.
virtual void unichar_ids_of(NODE_REF node, NodeChildVector *vec) const = 0;
// Returns the next node visited by following the edge
// indicated by the given EDGE_REF.
virtual NODE_REF next_node(EDGE_REF edge_ref) const = 0;
// Returns true if the edge indicated by the given EDGE_REF
// marks the end of a word.
virtual bool end_of_word(EDGE_REF edge_ref) const = 0;
// Returns UNICHAR_ID stored in the edge indicated by the given EDGE_REF.
virtual UNICHAR_ID edge_letter(EDGE_REF edge_ref) const = 0;
// Prints the contents of the node indicated by the given NODE_REF.
// At most max_num_edges will be printed.
virtual void print_node(NODE_REF node, int max_num_edges) const = 0;
protected:
Dawg() {}
// Returns the next node visited by following this edge.
inline NODE_REF next_node_from_edge_rec(const EDGE_RECORD &edge_rec) const {
return ((edge_rec & next_node_mask_) >> next_node_start_bit_);
}
// Returns the direction flag of this edge.
inline int direction_from_edge_rec(const EDGE_RECORD &edge_rec) const {
return ((edge_rec & (DIRECTION_FLAG << flag_start_bit_))) ?
BACKWARD_EDGE : FORWARD_EDGE;
}
// Returns true if this edge marks the end of a word.
inline bool end_of_word_from_edge_rec(const EDGE_RECORD &edge_rec) const {
return (edge_rec & (WERD_END_FLAG << flag_start_bit_)) != 0;
}
// Returns UNICHAR_ID recorded in this edge.
inline UNICHAR_ID unichar_id_from_edge_rec(
const EDGE_RECORD &edge_rec) const {
return ((edge_rec & letter_mask_) >> LETTER_START_BIT);
}
// Sets the next node link for this edge in the Dawg.
inline void set_next_node_in_edge_rec(
EDGE_RECORD *edge_rec, EDGE_REF value) {
*edge_rec &= (~next_node_mask_);
*edge_rec |= ((value << next_node_start_bit_) & next_node_mask_);
}
// Sets this edge record to be the last one in a sequence of edges.
inline void set_last_flag_in_edge_rec(EDGE_RECORD *edge_rec) {
*edge_rec |= (LAST_FLAG << flag_start_bit_);
}
// 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
inline int given_greater_than_edge_rec(NODE_REF next_node,
bool word_end,
UNICHAR_ID unichar_id,
const EDGE_RECORD &edge_rec) const {
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;
}
// 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).
inline 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 {
return ((unichar_id == other_unichar_id) &&
(next_node == NO_EDGE || next_node == other_next_node) &&
(!word_end || (word_end == other_word_end)));
}
// Sets type_, lang_, perm_, unicharset_size_.
// Initializes the values of various masks from unicharset_size_.
void init(DawgType type, const STRING &lang,
PermuterType perm, int unicharset_size);
// Matches all of the words that are represented by this string.
// If wilcard 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.
bool match_words(WERD_CHOICE *word, inT32 index,
NODE_REF node, UNICHAR_ID wildcard) const;
// Member Variables.
DawgType type_;
STRING lang_;
// Permuter code that should be used if the word is found in this Dawg.
PermuterType perm_;
// Variables to construct various edge masks. Formerly:
// #define NEXT_EDGE_MASK (inT64) 0xfffffff800000000i64
// #define FLAGS_MASK (inT64) 0x0000000700000000i64
// #define LETTER_MASK (inT64) 0x00000000ffffffffi64
int unicharset_size_;
int flag_start_bit_;
int next_node_start_bit_;
uinT64 next_node_mask_;
uinT64 flags_mask_;
uinT64 letter_mask_;
};
//
// DawgInfo struct and DawgInfoVector class are used for
// storing information about the current Dawg search state.
//
struct DawgInfo {
DawgInfo() : dawg_index(-1), ref(NO_EDGE) {}
DawgInfo(int i, EDGE_REF r) : dawg_index(i), ref(r) {}
bool operator==(const DawgInfo &other) {
return (this->dawg_index == other.dawg_index &&
this->ref == other.ref);
}
int dawg_index;
EDGE_REF ref;
};
class DawgInfoVector : public GenericVector<DawgInfo> {
public:
// Overload destructor, since clear() does not delete data_[] any more.
~DawgInfoVector() {
if (size_reserved_ > 0) {
delete[] data_;
size_used_ = 0;
size_reserved_ = 0;
}
}
// Overload clear() in order to avoid allocating/deallocating memory
// when clearing the vector and re-inserting entries into it later.
void clear() { size_used_ = 0; }
// Adds an entry for the given dawg_index with the given node to the vec.
// Returns false if the same entry already exists in the vector,
// true otherwise.
inline bool add_unique(const DawgInfo &new_info, const char *debug_msg) {
for (int i = 0; i < size_used_; ++i) {
if (data_[i] == new_info) return false;
}
push_back(new_info);
if (dawg_debug_level) {
tprintf("%s[%d, " REFFORMAT "]\n", debug_msg,
new_info.dawg_index, new_info.ref);
}
return true;
}
// Removes an entry that equals to the given DawgInfo.
// This function assumes that the entries in the vector are unique.
// Returns true if an entry was found and removed.
inline bool remove(const DawgInfo &info) {
for (int i = 0; i < size_used_; ++i) {
if (data_[i] == info) {
for (int j = i + 1; j < size_used_; ++j) {
data_[j-1] = data_[j];
}
size_used_--;
return true;
}
}
return false;
}
};
//
// Concrete class that can operate on a compacted (squished) Dawg (read,
// search and write to file). This class is read-only in the sense that
// new words can not be added to an instance of SquishedDawg.
// The underlying representation of the nodes and edges in SquishedDawg
// is stored as a contiguous EDGE_ARRAY (read from file or given as an
// argument to the constructor).
//
class SquishedDawg : public Dawg {
public:
SquishedDawg(FILE *file, DawgType type,
const STRING &lang, PermuterType perm) {
read_squished_dawg(file, type, lang, perm);
num_forward_edges_in_node0 = num_forward_edges(0);
}
SquishedDawg(const char* filename, DawgType type,
const STRING &lang, PermuterType perm) {
FILE *file = fopen(filename, "rb");
if (file == NULL) {
tprintf("Failed to open dawg file %s\n", filename);
exit(1);
}
read_squished_dawg(file, type, lang, perm);
num_forward_edges_in_node0 = num_forward_edges(0);
fclose(file);
}
SquishedDawg(EDGE_ARRAY edges, int num_edges, DawgType type,
const STRING &lang, PermuterType perm, int unicharset_size) :
edges_(edges), num_edges_(num_edges) {
init(type, lang, perm, unicharset_size);
num_forward_edges_in_node0 = num_forward_edges(0);
if (dawg_debug_level > 3) print_all("SquishedDawg:");
}
~SquishedDawg();
// Returns the edge that corresponds to the letter out of this node.
EDGE_REF edge_char_of(NODE_REF node, UNICHAR_ID unichar_id,
bool word_end) const;
// 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 {
EDGE_REF edge = node;
if (!edge_occupied(edge) || edge == NO_EDGE) return;
assert(forward_edge(edge)); // we don't expect any backward edges to
do { // be present when this funciton is called
vec->push_back(NodeChild(unichar_id_from_edge_rec(edges_[edge]), edge));
} while (!last_edge(edge++));
}
// Returns the next node visited by following the edge
// indicated by the given EDGE_REF.
NODE_REF next_node(EDGE_REF edge) const {
return next_node_from_edge_rec((edges_[edge]));
}
// 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 {
return end_of_word_from_edge_rec((edges_[edge_ref]));
}
// Returns UNICHAR_ID stored in the edge indicated by the given EDGE_REF.
UNICHAR_ID edge_letter(EDGE_REF edge_ref) const {
return unichar_id_from_edge_rec((edges_[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 the squished/reduced Dawg to a file.
void write_squished_dawg(const char *filename);
private:
// Sets the next node link for this edge.
inline void set_next_node(EDGE_REF edge_ref, EDGE_REF value) {
set_next_node_in_edge_rec(&(edges_[edge_ref]), value);
}
// Sets the edge to be empty.
inline void set_empty_edge(EDGE_REF edge_ref) {
(edges_[edge_ref] = next_node_mask_);
}
// Goes through all the edges and clears each one out.
inline void clear_all_edges() {
for (int edge = 0; edge < num_edges_; edge++) set_empty_edge(edge);
}
// Clears the last flag of this edge.
inline void clear_last_flag(EDGE_REF edge_ref) {
(edges_[edge_ref] &= ~(LAST_FLAG << flag_start_bit_));
}
// Returns true if this edge is in the forward direction.
inline bool forward_edge(EDGE_REF edge_ref) const {
return (edge_occupied(edge_ref) &&
(FORWARD_EDGE == direction_from_edge_rec(edges_[edge_ref])));
}
// Returns true if this edge is in the backward direction.
inline bool backward_edge(EDGE_REF edge_ref) const {
return (edge_occupied(edge_ref) &&
(BACKWARD_EDGE == direction_from_edge_rec(edges_[edge_ref])));
}
// Returns true if the edge spot in this location is occupied.
inline bool edge_occupied(EDGE_REF edge_ref) const {
return (edges_[edge_ref] != next_node_mask_);
}
// Returns true if this edge is the last edge in a sequence.
inline bool last_edge(EDGE_REF edge_ref) const {
return (edges_[edge_ref] & (LAST_FLAG << flag_start_bit_)) != 0;
}
// Counts and returns the number of forward edges in this node.
inT32 num_forward_edges(NODE_REF node) const;
// Reads SquishedDawg from a file.
void read_squished_dawg(FILE *file, DawgType type,
const STRING &lang, PermuterType perm);
// Prints the contents of an edge indicated by the given EDGE_REF.
void print_edge(EDGE_REF edge) const;
// Prints the contents of the SquishedDawg.
void print_all(const char* msg) {
tprintf("\n__________________________\n%s\n", msg);
for (int i = 0; i < num_edges_; ++i) print_edge(i);
tprintf("__________________________\n");
}
// Constructs a mapping from the memory node indices to disk node indices.
NODE_MAP build_node_map(inT32 *num_nodes) const;
// Member variables.
EDGE_ARRAY edges_;
int num_edges_;
int num_forward_edges_in_node0;
};
} // namespace tesseract
#endif