Appendix: Program
with Michael D. Riley
The following code is the core of align. It is a C language program which inputs two text files, with one
token (word) per line. The text files contain a number of delimiter tokens. There are two types of delimiter
tokens: ¡®¡®hard¡¯¡¯ and ¡®¡®soft¡¯¡¯. The hard regions (e.g., paragraphs) may not be changed, and there must be
equal numbers of them in the two input files. The soft regions (e.g., sentences) may be deleted (1-0),
inserted (0-1), substituted (1-1), contracted (2-1), expanded (1-2), or merged (2-2) as necessary so that the
output ends up with the same number of soft regions. The program generates two output files. The two
output files contain an equal number of soft regions, each on a line. If the -v command line option is
included, each soft region is preceded by its probability score.
#include <fcntl.h>
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <values.h>
#include <sys/stat.h>
/*
usage:
align_regions -D ¡¯.PARA¡¯ -d ¡¯.End of Sentence¡¯ file1 file2
outputs two files: file1.al & file2.al
hard regions are delimited by the -D arg
soft regions are delimited by the -d arg
*/
#define dist(x,y) distances[(x) * ((ny) + 1) + (y)]
#define pathx(x,y) path_x[(x) * ((ny) + 1) + (y)]
#define pathy(x,y) path_y[(x) * ((ny) + 1) + (y)]
#define MAX_FILENAME 256
#define BIG_DISTANCE 2500
/* Dynamic Programming Optimization */
struct alignment {
int x1;
int y1;
int x2;
int y2;
int d;
};
char *hard_delimiter = NULL; /* -D arg */
char *soft_delimiter = NULL; /* -d arg */
int verbose = 0; /* -v arg */
/* utility functions */
char *readchars(), **readlines(), **substrings();
void err();
/*
seq_align by Mike Riley
x and y are sequences of objects, represented as non-zero ints, to be aligned.
dist_funct(x1, y1, x2, y2) is a distance function of 4 args:
dist_funct(x1, y1, 0, 0) gives cost of substitution of x1 by y1.
dist_funct(x1, 0, 0, 0) gives cost of deletion of x1.
dist_funct(0, y1, 0, 0) gives cost of insertion of y1.
dist_funct(x1, y1, x2, 0) gives cost of contraction of (x1,x2) to y1.
dist_funct(x1, y1, 0, y2) gives cost of expansion of x1 to (y1,y2).
dist_funct(x1, y1, x2, y2) gives cost to match (x1,x2) to (y1,y2).
align is the alignment, with (align[i].x1, align[i].x2) aligned
with (align[i].y1, align[i].y2). Zero in align[].x1 and align[].y1
correspond to insertion and deletion, respectively. Non-zero in
align[].x2 and align[].y2 correspond to contraction and expansion,
respectively. align[].d gives the distance for that pairing.
