/* The first three #define's are to repair mangling by BITNET mailers */
#define EOR ^
/* This should be Caret (hat, up arrow) -- C Ex-or */
#define MOD %
/* This should be Percent -- C Modulus */
#define NOT ~
/* This should be Tilde (twiddle) -- C unary Not */
#include "copyr.h"
/*****************************************************************************/
/* */
/* FILE : DAWG.C */
/* */
/* Convert an alphabetically-ordered dictionary file in text format */
/* (one word per line) into a Directed Acyclic Word Graph. The command */
/* syntax is */
/* */
/* DAWG <text file (inc .ext)> <output file (no ext)> */
/* */
/* The first 4 bytes of the output file form a 24-bit number containing */
/* the number of edges in the dawg. The rest of the file contains the */
/* dawg itself (see "The World's Fastest Scrabble Program" by Appel */
/* and Jacobson for a description of a dawg). */
/* */
/*****************************************************************************/
#include "grope.h"
#include <stdio.h>
#include <string.h>
#include "dawg2.h" /* main system constants */
#include "utils.c" /* utils.c pulls in header file for malloc/free & exit */
#define ABS(x) ((x) < 0 ? -(x) : (x))
#define HASH_TABLE_SIZE 240007
#define MAX_EDGES (HASH_TABLE_SIZE-1)
static FILE *fpin, *fpout; /* Input/output files */
static char current_word[(MAX_LINE+1)]; /* The last word read from fpin */
static int first_diff, save_first_diff;
/* The position of the first letter at which */
/* current_word differs from the previous */
/* word read */
static NODE PCCRAP *hash_table;
static int first_time = TRUE;
static int this_char = '?', lastch;
static NODE PCCRAP *dawg;
static int FILE_ENDED = FALSE; /* I'm having real problems getting
merged dawgs to work on the PC; this is yet another filthy hack. Sorry. */
static INDEX nwords, nnodes, total_edges;
#define EDGE_LIST(idx) \
edge_list[RANGECHECK(idx, MAX_CHARS)]
#define CURRENT_WORD(idx) \
current_word[RANGECHECK(idx, MAX_LINE+1)]
#define DAWG(idx) \
dawg[RANGECHECK(idx, MAX_EDGES)]
#define HASH_TABLE(idx) \
hash_table[RANGECHECK(idx, HASH_TABLE_SIZE)]
static INDEX build_node(int depth);
static INDEX add_node(NODE *edge_list, INDEX nedges);
static void read_next_word(VOID);
static INDEX compute_hashcode(NODE *edge_list, INDEX nedges);
static void report_size(VOID);
long words; /* dirty communication variable -- the multi-pass stuff
was hacked in at the last minute. */
int main(int argc, char **argv)
{
INDEX i;
char fname[128];
if (argc != 3) {
fprintf(stderr,
"usage: dawg dictfile.ext dawgfile\n");
exit(EXIT_ERROR);
}
if ((dawg = MALLOC(MAX_EDGES, sizeof(NODE PCCRAP *))) == NULL) {
fprintf(stderr, "Can\'t allocate dictionary memory\n");
exit(EXIT_ERROR);
}
for (i = 0; i < (INDEX)MAX_EDGES; i++) dawg[i] = 0L;
/**
* Allocate the hash table.
* Fill it with zeroes later just before use. Don't trust calloc etc.
* - not portable enough. Anyway, in the multi-pass version we don't
* want to continually free/claim...
**/
if ((hash_table =
MALLOC((HASH_TABLE_SIZE+1), sizeof(NODE))) == NULL) {
fprintf(stderr, "Can\'t allocate memory for hash table\n");
exit(EXIT_ERROR);
}
/**
* Open the input/output files
**/
fpin = fopen(argv[1], READ_TEXT);
if (fpin == NULL) {
fprintf(stderr, "Can\'t open text file \"%s\"\n", argv[1]);
/* Could print out error string but it's not portable... */
exit(EXIT_ERROR);
}
/**
* Read the first word from the dictionary
**/
first_time = TRUE;
nwords = 0;
current_word[0] = 0;
read_next_word();
lastch = *current_word;
/**
* Initialise the counters, taking account of the root node (which is
* a special case)
**/
nnodes = 1; total_edges = MAX_CHARS;
/**
* Build the dawg and report the outcome
**/
/* Now, in the dim & distant past, this code supported the concept
of a restricted character set - ie a..z & A..Z were packed into 6 bits;
this caused awful problems in the loop below, where we had to try to
keep the loop-control variable and the character code in synch; nowadays
chars are 8 bits or else, so I'm starting to tidy up the places
where these hacks were necessary... */
/* Explicitly initialise hash table to all zeros */
{INDEX a; for (a = 0; a <= HASH_TABLE_SIZE; a++) hash_table[a] = 0;}
words = 0;
(void) build_node(0);
/**
* Save the dawg to file
**/
sprintf(fname, "%s%cdwg", argv[2], EXT_CHAR);
fpout = fopen(fname, WRITE_BIN);
if (fpout == NULL) {
fprintf(stderr, "Can\'t open output file \"%s\"\n", fname);
exit(EXIT_ERROR);
}
*dawg = total_edges;
total_edges = sizeof(NODE) * (total_edges + 1); /* Convert to byte count */
{
long cnt;
if ((cnt = putwords(dawg, (long)total_edges, fpout)) != total_edges) {
fprintf(stderr, "%ld bytes written instead of %ld\n.", cnt, total_edges);
exit(EXIT_ERROR);
}
}
fclose(fpout);
/**
* Read the first word from the dictionary
**/
first_diff = save_first_diff;
first_time = FALSE;
nwords = 0;
/**
* Initialise the counters, taking account of the root node (which is
* a special case)
**/
nnodes = 1; total_edges = MAX_CHARS;
lastch = *current_word;
/**
* Build the dawg and report the outcome
**/
fclose(fpin);
fprintf(stderr, "Dawg generated\n");
exit(EXIT_OK);
}
/**
* BUILD_NODE
*
* Recursively build the next node and all its sub-nodes
**/
static INDEX build_node(int depth)
{
INDEX nedges = 0;
INDEX i;
NODE *edge_list;
edge_list = NULL;
if (CURRENT_WORD(depth) == 0) {
/**
* End of word reached. If the next word isn't a continuation of the
* current one, then we've reached the bottom of the recursion tree.
**/
read_next_word();
if (first_diff < depth) return(0);
}
edge_list = (NODE *)malloc(MAX_CHARS*sizeof(NODE));
/* Note this is a 'near' array */
if (edge_list == NULL) {
fprintf(stderr, "Stack full (depth %d)\n", depth);
exit(EXIT_ERROR);
}
for (i = 0; i < MAX_CHARS; i++) EDGE_LIST(i) = 0L;
/**
* Loop through all the sub-nodes until a word is read which can't
* be reached via this node
**/
do
{
/* Construct the edge. Letter.... */
EDGE_LIST(nedges) = (NODE) (((NODE)CURRENT_WORD(depth)))
<< (NODE)V_LETTER;
/* ....end-of-word flag.... */
if (CURRENT_WORD(depth+1L) == 0) EDGE_LIST(nedges) |= M_END_OF_WORD;
/* ....and node pointer. */
EDGE_LIST(nedges) |= build_node(depth+1); nedges++;
/* (don't ++ in a macro) */
} while (first_diff == depth);
if (first_diff > depth) {
fprintf(stderr, "Internal error -- first_diff = %d, depth = %d\n",
first_diff, depth);
exit(EXIT_ERROR);
}
EDGE_LIST(nedges-1) |= M_END_OF_NODE;
/* Flag the last edge in the node */
/**
* Add the node to the dawg
**/
if (depth) {
NODE result = add_node(edge_list, nedges);
free(edge_list);
return(result);
}
/**
* depth is zero, so the root node (as a special case) goes at the start
**/
edge_list[MAX_CHARS-1] |= M_END_OF_NODE; /* For backward searches */
for (i = 0; i < MAX_CHARS; i++)
{
dawg[i+1] = edge_list[i];
}
free(edge_list);
return(0);
}
/**
* ADD_NODE
*
* Add a node to the dawg if it isn't already there. A hash table is
* used to speed up the search for an identical node.
**/
static INDEX add_node(NODE *edge_list, INDEX nedges)
{
NODE hash_entry;
INDEX inc;
INDEX a, first_a;
INDEX i;
/**
* Look for an identical node. A quadratic probing algorithm is used
* to traverse the hash table.
**/
first_a = compute_hashcode(edge_list, nedges);
first_a = ABS(first_a) MOD HASH_TABLE_SIZE;
a = first_a;
inc = 9;
for (;;)
{
hash_entry = HASH_TABLE(a) & M_NODE_POINTER;
if (hash_entry == 0) break; /* Node not found, so add it to the dawg */
for (i = 0; i < nedges; i++)
if (DAWG((hash_entry+i) MOD HASH_TABLE_SIZE) != EDGE_LIST(i)) break;
/* On the 1.6M dictionary, this gave a rangecheck with < 0. Now fixed
I think - it was a problem with MOD giving unexpected results. */
if (i == nedges) {
return(hash_entry); /* Node found */
}
/**
* Node not found here. Look in the next spot
**/
a += inc;
inc += 8;
if (a >= HASH_TABLE_SIZE) a -= HASH_TABLE_SIZE;
if (inc >= HASH_TABLE_SIZE) inc -= HASH_TABLE_SIZE;
if (a == first_a) {
fprintf(stderr, "Hash table full\n");
exit(EXIT_ERROR);
}
}
/**
* Add the node to the dawg
**/
if (total_edges + nedges >= MAX_EDGES) {
fprintf(stderr,
"Error -- dictionary full - total edges = %ld\n", total_edges);
exit(EXIT_ERROR);
}
HASH_TABLE(a) |= total_edges + 1;
nnodes++;
for (i = 0; i < nedges; i++) {
DAWG((total_edges + 1 + i) MOD HASH_TABLE_SIZE) = EDGE_LIST(i);
}
total_edges += nedges;
return(total_edges - nedges + 1);
}
/**
* READ_NEXT_WORD
*
* Read the next word from the input file, setting first_diff accordingly
**/
static void read_next_word(void)
{
/* This stuff imposes the limitation of not allowing '\0' in a word;
not yet a problem but the dawg structure itself could probably cope
if the feature were wanted. (Maybe with a little teweaking) */
char linebuff[(MAX_LINE+1)];
int length;
for (;;)
{
int next = 0, c;
for (;;) {
c = fgetc(fpin);
if (FILE_ENDED || c == EOF || ferror(fpin) || feof(fpin)) {
/* for some reason, we always get a blank line at the end of files */
current_word[0] = 0;
first_diff = -1;
linebuff[next] = '\0';
FILE_ENDED = TRUE;
return;
}
c &= 255;
if (next == 0 && c == '\n') continue; /* skip blank lines... */
linebuff[next++] = c;
if (c == '\n') break;
}
linebuff[next] = '\0';
words++;
length = strlen(linebuff);
if (linebuff[length-1] == '\n') linebuff[length-1] = '\0';
if (linebuff[length] == '\n') linebuff[length] = '\0';
if (length < 2 || length > MAX_LINE-1)
{
fprintf(stderr, "\n%s - invalid length\n", linebuff);
continue; /* Previously exit()ed, but now ignore so that
test sites without my pddict can use /usr/dict/words */
}
break;
}
for (length = 0; current_word[length] == linebuff[length]; length++) {
/* Get common part of string to check order */
}
if (current_word[length] > linebuff[length]) {
fprintf(stderr, "Error -- %s (word out of sequence)\n", linebuff);
exit(EXIT_ERROR);
}
first_diff = length;
nwords++;
strcpy(current_word, linebuff);
if ((nwords > 1) && (!(nwords & 0x3FF))) report_size();
this_char = current_word[0]; /* for diagnostics... */
}
/**
* COMPUTE_HASHCODE
*
* Compute the hash code for a node
**/
static INDEX compute_hashcode(NODE *edge_list, INDEX nedges)
{
INDEX i;
INDEX res = 0L;
for (i = 0; i < nedges; i++)
res = ((res << 1) | (res >> 31)) EOR EDGE_LIST(i);
return(res);
}
/**
* REPORT_SIZE
*
* Report the current size etc
**/
static void report_size(void)
{
if (first_time)
{
fprintf(stderr, " Words Nodes Edges Bytes BPW\n");
fprintf(stderr, " ----- ----- ----- ----- ---\n");
first_time = FALSE;
}
if (*current_word) fprintf(stderr, "%c:", *current_word);
else fprintf(stderr, "Total:");
/* THE FOLLOWING IS RATHER GRATUITOUS USE OF FLOATING POINT - REMOVE
IT AND REPLACE WITH INTEGER ARITHMETIC * 100 */
/* (hey - I already did this in the copy I sent to Richard; so how
come its missing? Oh no, not again: I've got out of synch and
used an old copy, haven't I? :-( ) */
fprintf(stderr, " %7ld %7ld %7ld %7ld %5.2f\n",
nwords, nnodes, total_edges, sizeof(NODE PCCRAP *)*(total_edges+1),
(float)(sizeof(NODE PCCRAP *)*(total_edges+1))/(float)nwords);
}