// Level-2 Test A: does layer 1, as a mating constraint, shrink the layer-2 search space while keeping the
// true phrases? See PREREG.md (amendment 1).
//
// Reuses the planted grammar, window-pair gate and Eisner parser of ../across-cluster/ac.c unchanged,
// by including it with its main() renamed.
//
// l2 <seed> [--tiers 3000,10000,30000] [--heldout N] [--mut-drop]
#define main ac_main
#include "../across-cluster/ac.c"
#undef main
#define LMAX 6
#define TABBITS 22
// ---------------------------------------------------------------- layer-1 sources (token -> class)
enum { SRC_G, SRC_P10, SRC_P30, SRC_P50, SRC_S1, SRC_S2, SRC_S3, SRC_L, SRC_R, NSRC };
static const char *src_name[NSRC] = { "G", "p10", "p30", "p50", "S1", "S2", "S3", "L", "R" };
static int is_noun (int c) { return c <= N_THING_PL; }
static int is_verb (int c) { return c >= V_I_SG && c <= V_SAY_PL; }
static int is_func (int c) { return (c >= DET_SG && c <= DET_ANY) || c == PRON_SG || c == PRON_PL || c == PREP_LOC || c == PREP_WITH || c == COMP; }
// Structured merges: each class maps to a representative.
static int merge_class (int c, int level) {
if (level >= 1) {
if (is_noun(c) || is_verb(c)) c -= (c - (is_noun(c) ? N_ANIM_SG : V_I_SG)) % 2; // sg/pl -> sg
if (c >= DET_SG && c <= DET_ANY) c = DET_SG;
if (c == PRON_PL) c = PRON_SG;
}
if (level >= 2) {
if (is_noun(c)) c = N_ANIM_SG;
if (is_verb(c)) c = V_I_SG;
}
if (level >= 3 && is_func(c)) c = DET_SG;
return c;
}
static uint64_t mix (uint64_t x) { rng_t r = { x }; return rnext(&r); }
// Fills sym[] (per token) for source x. Returns alphabet size.
static int layer1_symbols (int x, const corpus_t *C, int seed, const int *Lmap, const int *Rmap, int *sym) {
for (int t = 0; t < C->ntok; t++) {
int w = C->w[t], c = C->c[t], s = c;
switch (x) {
case SRC_P10: case SRC_P30: case SRC_P50: {
double p = x == SRC_P10 ? 0.1 : x == SRC_P30 ? 0.3 : 0.5;
uint64_t h = mix(((uint64_t) seed << 40) ^ ((uint64_t) w << 8) ^ (uint64_t) c ^ ((uint64_t) x << 56));
if ((h >> 11) * (1.0 / 9007199254740992.0) < p) s = (int) (mix(h) % NCLS);
break;
}
case SRC_S1: s = merge_class(c, 1); break;
case SRC_S2: s = merge_class(c, 2); break;
case SRC_S3: s = merge_class(c, 3); break;
case SRC_L: s = Lmap[w]; break;
case SRC_R: s = Rmap[w]; break;
}
sym[t] = s;
}
return NCLS; // every source uses ids < 30; unused ids are harmless
}
// ---------------------------------------------------------------- layer-1 parse
// Corpus view whose c[] holds the arm's symbols (so ac.c's gold_tok arm reads them).
static corpus_t with_symbols (const corpus_t *C, int *sym) { corpus_t S = *C; S.c = sym; return S; }
// Parses every sentence of S with gated scores Sc (A x A); head[t] = in-sentence offset of head, or -1.
static void parse_all (const corpus_t *S, const double *Sc, int A, int *head) {
int hd[MAXN + 1];
for (int s = 0; s < S->ns; s++) {
int o = S->off[s], n = S->off[s + 1] - o, m = n + 1;
for (int h = 0; h < m; h++) for (int d = 0; d < m; d++) sc[h][d] = NEG;
for (int d = 1; d < m; d++) sc[0][d] = 0;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n && j - i <= W; j++)
sc[i + 1][j + 1] = sc[j + 1][i + 1] = Sc[(size_t) S->c[o + i] * A + S->c[o + j]];
eisner(m, hd);
for (int d = 1; d < m; d++) head[o + d - 1] = hd[d] - 1;
if (getenv("L2_DIR_DEBUG")) {
static long arcs, lefthead, roots, root_first, root_last, gl, ga;
for (int d = 0; d < n; d++) {
int h = head[o + d];
if (h < 0) { roots++; root_first += d == 0; root_last += d == n - 1; } else { arcs++; lefthead += h < d; }
if (S->h[o + d] >= 0) { ga++; gl += S->h[o + d] < d; }
}
if (s == S->ns - 1) fprintf(stderr, "dir: arcs=%ld head-left=%.3f roots=%ld root-first=%.3f root-last=%.3f | gold head-left=%.3f\n",
arcs, (double) lefthead / arcs, roots, (double) root_first / roots, (double) root_last / roots, (double) gl / ga);
}
}
}
static void layer1_parse (const corpus_t *tr, const corpus_t *ho, int A, int *htr, int *hho) {
arm_t a = { "l1", A, NULL, 1 };
pairs_t P = count_pairs(&a, tr);
long ev, acc;
double *Sc = hard_scores(&P, &ev, &acc);
parse_all(tr, Sc, A, htr);
parse_all(ho, Sc, A, hho);
free(Sc); free_pairs(&P);
}
// Span [i, j] (sentence offsets, inclusive) is connected iff it holds len-1 parse edges.
static int connected (const int *head, int o, int i, int j) {
int e = 0;
for (int k = i; k <= j; k++) { int h = head[o + k]; if (h >= i && h <= j) e++; }
return e == j - i;
}
// Complete assembly: connected, and no token outside the span has its head inside it (one free connector).
static int complete (const int *head, int o, int n, int i, int j) {
if (!connected(head, o, i, j)) return 0;
for (int k = 0; k < n; k++) { if (k >= i && k <= j) continue; int h = head[o + k]; if (h >= i && h <= j) return 0; }
return 1;
}
// ---------------------------------------------------------------- Test A-U (PREREG-U.md): undirected parses
#define MAXL 24
typedef struct { int *lnk, *nl; } parse_t; // per token: in-sentence offsets of the tokens it is linked to
static parse_t parse_alloc (int ntok) { parse_t P = { malloc(sizeof(int) * ntok * MAXL), malloc(sizeof(int) * ntok) }; return P; }
static void parse_clear (parse_t *P, int o, int n) { for (int t = 0; t < n; t++) P->nl[o + t] = 0; }
static int linked (const parse_t *P, int o, int a, int b) { for (int k = 0; k < P->nl[o + a]; k++) if (P->lnk[(o + a) * MAXL + k] == b) return 1; return 0; }
static void add_link (parse_t *P, int o, int a, int b) {
if (a == b || linked(P, o, a, b) || P->nl[o + a] >= MAXL || P->nl[o + b] >= MAXL) return;
P->lnk[(o + a) * MAXL + P->nl[o + a]++] = b; P->lnk[(o + b) * MAXL + P->nl[o + b]++] = a;
}
static void links_from_heads (const corpus_t *C, const int *head, parse_t *P) {
for (int s = 0; s < C->ns; s++) {
int o = C->off[s], n = C->off[s + 1] - o;
parse_clear(P, o, n);
for (int t = 0; t < n; t++) if (head[o + t] >= 0) add_link(P, o, t, head[o + t]);
}
}
// Ungated ordered-pair MI over window counts; pairs never counted get -10.
static double *pair_mi (const pairs_t *P) {
double *M = malloc(sizeof(double) * P->A * P->A);
for (int a = 0; a < P->A; a++) for (int b = 0; b < P->A; b++) {
double n = P->M[(size_t) a * P->A + b];
M[(size_t) a * P->A + b] = n > 0 ? log2(n * P->N / (P->R[a] * P->Cm[b])) : -10;
}
return M;
}
// MST: projective spanning tree (Eisner, root edges -1e6 so one root child); MPG: + non-crossing MI > 0 links.
typedef struct { int i, j; double v; } cl_t;
static int cl_cmp (const void *a, const void *b) {
const cl_t *x = a, *y = b;
if (x->v != y->v) return x->v > y->v ? -1 : 1;
return x->i != y->i ? x->i - y->i : x->j - y->j;
}
static void parse_u (const corpus_t *S, const double *MI, int A, int mpg, parse_t *P) {
int hd[MAXN + 1];
static cl_t cand[MAXN * W];
for (int s = 0; s < S->ns; s++) {
int o = S->off[s], n = S->off[s + 1] - o, m = n + 1, nc = 0;
for (int h = 0; h < m; h++) for (int d = 0; d < m; d++) sc[h][d] = NEG;
for (int d = 1; d < m; d++) sc[0][d] = -1e6;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n && j - i <= W; j++)
sc[i + 1][j + 1] = sc[j + 1][i + 1] = MI[(size_t) S->c[o + i] * A + S->c[o + j]];
eisner(m, hd);
parse_clear(P, o, n);
for (int d = 1; d < m; d++) if (hd[d] > 0) add_link(P, o, d - 1, hd[d] - 1);
if (!mpg) continue;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n && j - i <= W; j++) {
double v = MI[(size_t) S->c[o + i] * A + S->c[o + j]];
if (v > 0 && !linked(P, o, i, j)) cand[nc++] = (cl_t) { i, j, v };
}
qsort(cand, nc, sizeof(cl_t), cl_cmp);
for (int c = 0; c < nc; c++) {
int i = cand[c].i, j = cand[c].j, ok = 1;
for (int a = 0; a < n && ok; a++) for (int k = 0; k < P->nl[o + a] && ok; k++) {
int b = P->lnk[(o + a) * MAXL + k];
if (a < b && ((a < i && i < b && b < j) || (i < a && a < j && j < b))) ok = 0;
}
if (ok) add_link(P, o, i, j);
}
}
}
// uconn: links inside [i, j] connect it. ucomp: uconn and at most one link leaves the span.
static int uconn (const parse_t *P, int o, int i, int j) {
int seen[MAXN] = { 0 }, stack[MAXN], sp = 0, cnt = 1;
seen[i] = 1; stack[sp++] = i;
while (sp) {
int a = stack[--sp];
for (int k = 0; k < P->nl[o + a]; k++) {
int b = P->lnk[(o + a) * MAXL + k];
if (b >= i && b <= j && !seen[b]) { seen[b] = 1; cnt++; stack[sp++] = b; }
}
}
return cnt == j - i + 1;
}
static int ucomp (const parse_t *P, int o, int i, int j) {
if (!uconn(P, o, i, j)) return 0;
int cross = 0;
for (int a = i; a <= j; a++) for (int k = 0; k < P->nl[o + a]; k++) { int b = P->lnk[(o + a) * MAXL + k]; cross += b < i || b > j; }
return cross <= 1;
}
// Undirected link precision / recall / F1 of P on C against the gold tree.
static void link_prf (const corpus_t *C, const parse_t *P, double *pr, double *rc, double *f1) {
long pred = 0, gold = 0, tp = 0;
for (int s = 0; s < C->ns; s++) {
int o = C->off[s], n = C->off[s + 1] - o;
for (int t = 0; t < n; t++) {
for (int k = 0; k < P->nl[o + t]; k++) pred += P->lnk[(o + t) * MAXL + k] > t;
int h = C->h[o + t];
if (h >= 0) { gold++; tp += linked(P, o, t, h); }
}
}
*pr = pred ? (double) tp / pred : 0; *rc = gold ? (double) tp / gold : 0;
*f1 = *pr + *rc > 0 ? 2 * *pr * *rc / (*pr + *rc) : 0;
}
// ---------------------------------------------------------------- re-parse loop (PREREG-reparse.md)
#define KR 30
#define ROUNDS 5
// Exchange algorithm over weighted ordered word pairs Wp (left a, right b); copied from
// ../jigsaw-transformer/jt.c exchange_weighted (K = KR).
static int *exchange_pairs (const double *Wp, const corpus_t *tr) {
double *freq = calloc(V, sizeof(double));
for (int t = 0; t < tr->ntok; t++) freq[tr->w[t]] += 1;
int *order = malloc(sizeof(int) * V);
for (int x = 0; x < V; x++) order[x] = x;
for (int i = 1; i < V; i++) { int x = order[i], j = i; while (j > 0 && freq[order[j - 1]] < freq[x]) { order[j] = order[j - 1]; j--; } order[j] = x; }
int *cls = malloc(sizeof(int) * V);
for (int i = 0; i < V; i++) cls[order[i]] = i % KR;
double *Nc = calloc((size_t) KR * KR, sizeof(double));
for (int a = 0; a < V; a++) for (int b = 0; b < V; b++) { double v = Wp[(size_t) a * V + b]; if (v > 0) Nc[cls[a] * KR + cls[b]] += v; }
double sv[64], pv[64];
for (int pass = 0; pass < 30; pass++) {
int moves = 0;
for (int i = 0; i < V; i++) {
int x = order[i];
if (freq[x] == 0) continue;
int a = cls[x];
double self = Wp[(size_t) x * V + x];
memset(sv, 0, sizeof sv); memset(pv, 0, sizeof pv);
for (int y = 0; y < V; y++) {
if (y == x) continue;
double r = Wp[(size_t) x * V + y], l = Wp[(size_t) y * V + x];
if (r > 0) sv[cls[y]] += r;
if (l > 0) pv[cls[y]] += l;
}
for (int c = 0; c < KR; c++) { Nc[a * KR + c] -= sv[c]; Nc[c * KR + a] -= pv[c]; }
Nc[a * KR + a] -= self;
int best = a; double bestF = -1e300;
for (int b = 0; b < KR; b++) {
for (int c = 0; c < KR; c++) { Nc[b * KR + c] += sv[c]; Nc[c * KR + b] += pv[c]; }
Nc[b * KR + b] += self;
double f = 0;
for (int r = 0; r < KR; r++) {
double row = 0, col = 0;
for (int c = 0; c < KR; c++) { double v = Nc[r * KR + c]; if (v > 0) f += v * log(v); row += Nc[r * KR + c]; col += Nc[c * KR + r]; }
if (row > 0) f -= row * log(row);
if (col > 0) f -= col * log(col);
}
if (f > bestF + 1e-9 || (b == a && f >= bestF - 1e-9)) { bestF = f; best = b; }
for (int c = 0; c < KR; c++) { Nc[b * KR + c] -= sv[c]; Nc[c * KR + b] -= pv[c]; }
Nc[b * KR + b] -= self;
}
for (int c = 0; c < KR; c++) { Nc[best * KR + c] += sv[c]; Nc[c * KR + best] += pv[c]; }
Nc[best * KR + best] += self;
if (best != a) { cls[x] = best; moves++; }
}
if (!moves) break;
}
free(freq); free(order); free(Nc);
return cls;
}
// Many-to-one accuracy of labels lab[] (< nlab) against gold token classes.
static double m1_acc (const corpus_t *C, const int *lab, int nlab) {
int *ct = calloc((size_t) nlab * NCLS, sizeof(int));
for (int t = 0; t < C->ntok; t++) ct[(size_t) lab[t] * NCLS + C->c[t]]++;
long ok = 0;
for (int l = 0; l < nlab; l++) { int b = 0; for (int g = 1; g < NCLS; g++) if (ct[(size_t) l * NCLS + g] > b) b = ct[(size_t) l * NCLS + g]; ok += b; }
free(ct);
return (double) ok / C->ntok;
}
// ---------------------------------------------------------------- Test DICT (PREREG-dict.md)
#define NCAND 31 // the MST + 30 perturbed MSTs
#define DBETA 10.0
#define NCODE 128 // connector code = side * 64 + class
typedef struct { size_t cap, n; uint64_t *key; double *cnt; } dtab_t;
typedef struct { dtab_t t; double nz[64], phi[64][NCODE], phin[64]; } dict_t;
static void dt_init (dtab_t *t, size_t cap) { t->cap = cap; t->n = 0; t->key = calloc(cap, sizeof(uint64_t)); t->cnt = calloc(cap, sizeof(double)); }
static double *dt_slot (dtab_t *t, uint64_t k, int create) {
if (create && 2 * (t->n + 1) > t->cap) {
dtab_t g; dt_init(&g, 2 * t->cap);
for (size_t i = 0; i < t->cap; i++) if (t->key[i]) { size_t j = t->key[i] & (g.cap - 1); while (g.key[j]) j = (j + 1) & (g.cap - 1); g.key[j] = t->key[i]; g.cnt[j] = t->cnt[i]; }
g.n = t->n; free(t->key); free(t->cnt); *t = g;
}
size_t i = k & (t->cap - 1);
while (t->key[i] && t->key[i] != k) i = (i + 1) & (t->cap - 1);
if (!t->key[i]) { if (!create) return NULL; t->key[i] = k; t->n++; }
return &t->cnt[i];
}
static void dict_init (dict_t *D) { dt_init(&D->t, 1 << 16); memset(D->nz, 0, sizeof D->nz); memset(D->phi, 0, sizeof D->phi); memset(D->phin, 0, sizeof D->phin); }
static void dict_free (dict_t *D) { free(D->t.key); free(D->t.cnt); }
// Sentence-local undirected parse: nl[t] links of token t, lk[t][k] their in-sentence offsets.
typedef struct { int nl[MAXN], lk[MAXN][MAXL]; } sparse_t;
// MST of one sentence over MI (root edges -1e6), with Gumbel noise of the given scale on every window edge.
static void parse_one (const corpus_t *S, int o, int n, const double *MI, int A, double scale, rng_t *r, sparse_t *T) {
int m = n + 1, hd[MAXN + 1];
for (int h = 0; h < m; h++) for (int d = 0; d < m; d++) sc[h][d] = NEG;
for (int d = 1; d < m; d++) sc[0][d] = -1e6;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n && j - i <= W; j++) {
double v = MI[(size_t) S->c[o + i] * A + S->c[o + j]];
if (scale > 0) { double u = runif(r); if (u <= 0) u = 1e-300; v += scale * -log(-log(u)); }
sc[i + 1][j + 1] = sc[j + 1][i + 1] = v;
}
eisner(m, hd);
for (int t = 0; t < n; t++) T->nl[t] = 0;
for (int d = 1; d < m; d++) if (hd[d] > 0) { int a = d - 1, b = hd[d] - 1; T->lk[a][T->nl[a]++] = b; T->lk[b][T->nl[b]++] = a; }
}
// Token t's disjunct: its links in position order as codes (side, class); returns the count.
static int disj (const corpus_t *S, int o, const sparse_t *T, int t, int *codes) {
int nb[MAXL], m = T->nl[t];
memcpy(nb, T->lk[t], sizeof(int) * m);
for (int x = 1; x < m; x++) { int v = nb[x], y = x; while (y > 0 && nb[y - 1] > v) { nb[y] = nb[y - 1]; y--; } nb[y] = v; }
for (int x = 0; x < m; x++) codes[x] = (nb[x] < t ? 0 : 64) + S->c[o + nb[x]];
return m;
}
static uint64_t disj_key (int z, const int *codes, int nc) {
uint64_t h = 1469598103934665603ULL ^ (uint64_t) z;
for (int k = 0; k < nc; k++) h = (h ^ (uint64_t) (codes[k] + 1)) * 1099511628211ULL;
h = (h ^ (uint64_t) nc) * 1099511628211ULL;
return mix(h) | 1;
}
static void dict_add (dict_t *D, const corpus_t *S, int o, int n, const sparse_t *T) {
int codes[MAXL];
for (int t = 0; t < n; t++) {
int z = S->c[o + t], nc = disj(S, o, T, t, codes);
*dt_slot(&D->t, disj_key(z, codes, nc), 1) += 1;
D->nz[z] += 1;
for (int k = 0; k < nc; k++) { D->phi[z][codes[k]] += 1; D->phin[z] += 1; }
}
}
static double dict_score (const dict_t *D, const corpus_t *S, int o, int n, const sparse_t *T) {
int codes[MAXL];
double tot = 0;
for (int t = 0; t < n; t++) {
int z = S->c[o + t], nc = disj(S, o, T, t, codes);
double lb = 0;
for (int k = 0; k < nc; k++) lb += log((D->phi[z][codes[k]] + 0.1) / (D->phin[z] + 0.1 * NCODE));
const double *c = dt_slot((dtab_t *) &D->t, disj_key(z, codes, nc), 0);
tot += log(((c ? *c : 0) + DBETA * exp(lb)) / (D->nz[z] + DBETA));
}
return tot;
}
static long gold_tp (const corpus_t *G, int o, int n, const sparse_t *T) {
long tp = 0;
for (int t = 0; t < n; t++) { int h = G->h[o + t]; if (h < 0) continue; for (int k = 0; k < T->nl[t]; k++) if (T->lk[t][k] == h) { tp++; break; } }
return tp;
}
// One source: dictionary 0 from the training MST, then 3 iterations of parse-with-dictionary + re-estimation.
static void run_dict (int seed, int tier, const char *name, const corpus_t *tr, const corpus_t *ho, const double *MI, int A) {
static sparse_t T, best;
dict_t D, Dn;
dict_init(&D);
long gold = 0, tp = 0, pred = 0;
for (int s = 0; s < tr->ns; s++) { int o = tr->off[s], n = tr->off[s + 1] - o; parse_one(tr, o, n, MI, A, 0, NULL, &T); dict_add(&D, tr, o, n, &T); }
for (int s = 0; s < ho->ns; s++) {
int o = ho->off[s], n = ho->off[s + 1] - o;
parse_one(ho, o, n, MI, A, 0, NULL, &T);
tp += gold_tp(ho, o, n, &T);
for (int t = 0; t < n; t++) { gold += ho->h[o + t] >= 0; pred += T.nl[t]; }
}
pred /= 2;
printf("DP\t%d\t%d\t%s\t0\t%.5f\t%.5f\n", seed, tier, name, 2.0 * tp / (pred + gold), 2.0 * tp / (pred + gold));
for (int it = 1; it <= 3; it++) {
rng_t r = { 1000003ULL * seed + 7919ULL * tier + 131ULL * it + (uint64_t) name[0] };
dict_init(&Dn);
for (int k = 0; k < 2; k++) {
const corpus_t *C = k ? ho : tr;
long ctp = 0, cor = 0, cpred = 0, cgold = 0;
for (int s = 0; s < C->ns; s++) {
int o = C->off[s], n = C->off[s + 1] - o;
double bs = -1e300; long otp = -1;
for (int c = 0; c < NCAND; c++) {
parse_one(C, o, n, MI, A, c ? 1.0 : 0, &r, &T);
double v = dict_score(&D, C, o, n, &T);
if (v > bs) { bs = v; best = T; }
if (k) { long g = gold_tp(C, o, n, &T); if (g > otp) otp = g; }
}
if (!k) dict_add(&Dn, C, o, n, &best);
else {
ctp += gold_tp(C, o, n, &best); cor += otp;
for (int t = 0; t < n; t++) { cgold += C->h[o + t] >= 0; cpred += best.nl[t]; }
}
}
if (k) { cpred /= 2; printf("DP\t%d\t%d\t%s\t%d\t%.5f\t%.5f\n", seed, tier, name, it, 2.0 * ctp / (cpred + cgold), 2.0 * cor / (cpred + cgold)); }
}
dict_free(&D); D = Dn;
}
dict_free(&D);
}
// ---------------------------------------------------------------- span-type table
typedef struct { uint16_t s[LMAX]; uint8_t len, used; uint32_t cnum, hard, first; float soft; } span_t; // hard/first/soft: Test A-soft
static span_t *tab;
static size_t tmask;
static uint32_t nfirst; // creation order (Test A-soft tie-break)
static uint64_t span_hash (const int *x, int len) {
uint64_t h = 1469598103934665603ULL ^ (uint64_t) len;
for (int k = 0; k < len; k++) h = (h ^ (uint64_t) x[k]) * 1099511628211ULL;
return mix(h);
}
static span_t *span_get (const int *x, int len, int create) {
size_t i = span_hash(x, len) & tmask;
for (;;) {
span_t *e = &tab[i];
if (!e->used) {
if (!create) return NULL;
e->used = 1; e->len = len; e->first = nfirst++;
for (int k = 0; k < len; k++) e->s[k] = x[k];
return e;
}
if (e->len == len) {
int k = 0;
while (k < len && e->s[k] == x[k]) k++;
if (k == len) return e;
}
i = (i + 1) & tmask;
}
}
// ---------------------------------------------------------------- brackets
typedef struct { int i, j; double s; } br_t;
static int br_cmp (const void *a, const void *b) {
const br_t *x = a, *y = b;
if (x->s != y->s) return x->s > y->s ? -1 : 1;
if (x->j - x->i != y->j - y->i) return (x->j - x->i) > (y->j - y->i) ? -1 : 1;
return x->i - y->i;
}
static int crosses (br_t a, br_t b) { return (a.i < b.i && b.i <= a.j && a.j < b.j) || (b.i < a.i && a.i <= b.j && b.j < a.j); }
// Greedy non-crossing selection, in place; returns the number kept.
static int select_brackets (br_t *c, int n) {
qsort(c, n, sizeof(br_t), br_cmp);
int k = 0;
for (int a = 0; a < n; a++) {
int ok = 1;
for (int b = 0; b < k && ok; b++) if (crosses(c[a], c[b]) || (c[a].i == c[b].i && c[a].j == c[b].j)) ok = 0;
if (ok) c[k++] = c[a];
}
return k;
}
// Gold layer 2: spans of NP / PP subtrees, length >= 2. Returns count; fills g.
static int gold_spans (const corpus_t *C, int s, br_t *g, int *n_le6) {
int o = C->off[s], n = C->off[s + 1] - o, lo[MAXN], hi[MAXN], k = 0;
for (int t = 0; t < n; t++) lo[t] = hi[t] = t;
for (int t = 0; t < n; t++) for (int h = C->h[o + t]; h >= 0; h = C->h[o + h]) {
if (t < lo[h]) lo[h] = t;
if (t > hi[h]) hi[h] = t;
}
*n_le6 = 0;
for (int t = 0; t < n; t++) {
int c = C->c[o + t];
if (!(is_noun(c) || c == PREP_LOC || c == PREP_WITH) || hi[t] == lo[t]) continue;
g[k].i = lo[t]; g[k].j = hi[t]; g[k].s = 0; k++;
if (hi[t] - lo[t] + 1 <= LMAX) (*n_le6)++;
}
return k;
}
// ---------------------------------------------------------------- one arm (Test A: the search space)
enum { RULE_ALL, RULE_CONN, RULE_COMP, RULE_UCONN, RULE_UCOMP };
static const parse_t *u_tr, *u_ho; // undirected parses for RULE_UCONN / RULE_UCOMP (set by the caller)
static int rule_ok (int rule, const int *head, int o, int n, int i, int j) {
if (rule == RULE_UCONN || rule == RULE_UCOMP) {
const parse_t *P = head == (const int *) u_tr ? u_tr : u_ho;
return rule == RULE_UCONN ? uconn(P, o, i, j) : ucomp(P, o, i, j);
}
return rule == RULE_ALL || (rule == RULE_CONN ? connected(head, o, i, j) : complete(head, o, n, i, j));
}
// tr/ho carry the arm's symbols in c[]; gold_ho carries gold classes + heads. htr/hho: layer-1 parse (unused for RULE_ALL).
static void run_arm (int seed, int tier, const char *name, int rule, const corpus_t *tr, const corpus_t *ho,
const corpus_t *gold_ho, const int *htr, const int *hho) {
memset(tab, 0, sizeof(span_t) * (tmask + 1));
int x[LMAX];
long bylen[LMAX + 1] = { 0 };
for (int s = 0; s < tr->ns; s++) {
int o = tr->off[s], n = tr->off[s + 1] - o;
for (int i = 0; i < n; i++) for (int len = 2; len <= LMAX && i + len <= n; len++) {
if (!rule_ok(rule, htr, o, n, i, i + len - 1)) continue;
for (int k = 0; k < len; k++) x[k] = tr->c[o + i + k];
span_t *e = span_get(x, len, 1);
if (!e->cnum++) bylen[len]++;
}
}
long types = 0;
for (int len = 2; len <= LMAX; len++) { types += bylen[len]; printf("X\t%d\t%d\t%s\t%d\t%ld\n", seed, tier, name, len, bylen[len]); }
long gold = 0, inst = 0, typed = 0, cand = 0, cand_gold = 0;
br_t gb[MAXN];
for (int s = 0; s < ho->ns; s++) {
int o = ho->off[s], n = ho->off[s + 1] - o, le6;
int ng = gold_spans(gold_ho, s, gb, &le6);
for (int i = 0; i < n; i++) for (int len = 2; len <= LMAX && i + len <= n; len++) {
int j = i + len - 1;
if (!rule_ok(rule, hho, o, n, i, j)) continue;
for (int k = 0; k < len; k++) x[k] = ho->c[o + i + k];
int seen = span_get(x, len, 0) != NULL, isg = 0;
for (int b = 0; b < ng; b++) if (gb[b].i == i && gb[b].j == j) isg = 1;
if (isg) { inst++; if (seen) typed++; }
if (seen) { cand++; if (isg) cand_gold++; }
}
for (int b = 0; b < ng; b++) if (gb[b].j - gb[b].i + 1 <= LMAX) gold++;
}
printf("A\t%d\t%d\t%s\t%ld\t%.5f\t%.5f\t%.5f\t%ld\t%ld\n", seed, tier, name, types,
gold ? (double) inst / gold : 0, gold ? (double) typed / gold : 0, cand ? (double) cand_gold / cand : 0, gold, cand);
}
// ---------------------------------------------------------------- Test A-soft (PREREG-soft.md)
#define KPARSE 6
static const int budgets_soft[3] = { 1000, 3000, 10000 };
static const span_t *rank_key_tab;
static int rank_method; // 0 CNT, 1 HARD, 2 SOFT
static int rank_cmp (const void *a, const void *b) {
const span_t *x = &rank_key_tab[*(const size_t *) a], *y = &rank_key_tab[*(const size_t *) b];
double kx = rank_method == 0 ? x->cnum : rank_method == 1 ? x->hard : x->soft;
double ky = rank_method == 0 ? y->cnum : rank_method == 1 ? y->hard : y->soft;
if (kx != ky) return kx > ky ? -1 : 1;
if (x->cnum != y->cnum) return x->cnum > y->cnum ? -1 : 1;
return x->first < y->first ? -1 : x->first > y->first;
}
// Fills ac.c's sc[][] for sentence o..o+n of S from gated scores Sc; Gumbel noise (scale) on gated edges.
static void fill_scores (const corpus_t *S, int o, int n, const double *Sc, int A, double scale, rng_t *r) {
int m = n + 1;
for (int h = 0; h < m; h++) for (int d = 0; d < m; d++) sc[h][d] = NEG;
for (int d = 1; d < m; d++) sc[0][d] = 0;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n && j - i <= W; j++) {
double v = Sc[(size_t) S->c[o + i] * A + S->c[o + j]];
if (v > NEG && scale > 0) { double u = runif(r); if (u <= 0) u = 1e-300; v += scale * -log(-log(u)); }
sc[i + 1][j + 1] = sc[j + 1][i + 1] = v;
}
}
static void run_soft (int seed, int tier, const char *src, const corpus_t *tr, const corpus_t *ho, const corpus_t *gold_ho,
const double *Sc, int A, double scale) {
memset(tab, 0, sizeof(span_t) * (tmask + 1));
nfirst = 0;
rng_t r = { 1000003ULL * seed + 7919ULL * tier + (uint64_t) src[0] };
int hd[MAXN + 1], hmax[MAXN], hp[KPARSE][MAXN], x[LMAX];
for (int s = 0; s < tr->ns; s++) {
int o = tr->off[s], n = tr->off[s + 1] - o, m = n + 1;
fill_scores(tr, o, n, Sc, A, 0, &r); eisner(m, hd);
for (int d = 1; d < m; d++) hmax[d - 1] = hd[d] - 1;
for (int k = 0; k < KPARSE; k++) { fill_scores(tr, o, n, Sc, A, scale, &r); eisner(m, hd); for (int d = 1; d < m; d++) hp[k][d - 1] = hd[d] - 1; }
for (int i = 0; i < n; i++) for (int len = 2; len <= LMAX && i + len <= n; len++) {
int j = i + len - 1, c = 0;
for (int k = 0; k < len; k++) x[k] = tr->c[o + i + k];
span_t *e = span_get(x, len, 1);
e->cnum++;
e->hard += complete(hmax, 0, n, i, j);
for (int k = 0; k < KPARSE; k++) c += complete(hp[k], 0, n, i, j);
e->soft += (float) c / KPARSE;
}
}
if (getenv("L2_SOFT_DEBUG")) for (size_t i = 0; i <= tmask; i++) if (tab[i].used && tab[i].cnum >= 3 && tab[i].soft / tab[i].cnum > 0.5) {
fprintf(stderr, "%s n=%u h=%u a=%.1f :", src, tab[i].cnum, tab[i].hard, tab[i].soft);
for (int k = 0; k < tab[i].len; k++) fprintf(stderr, " %d", tab[i].s[k]);
fprintf(stderr, "\n");
}
size_t nt = 0, *idx = malloc(sizeof(size_t) * nfirst);
for (size_t i = 0; i <= tmask; i++) if (tab[i].used) idx[nt++] = i;
uint32_t *rank[3];
rank_key_tab = tab;
for (int mth = 0; mth < 3; mth++) {
rank_method = mth;
qsort(idx, nt, sizeof(size_t), rank_cmp);
rank[mth] = malloc(sizeof(uint32_t) * (tmask + 1));
for (size_t k = 0; k < nt; k++) rank[mth][idx[k]] = (uint32_t) k;
}
long gold = 0, hit[3][3] = { { 0 } }, cand[3][3] = { { 0 } }, cgold[3][3] = { { 0 } };
long bpred[4] = { 0 }, btp[4] = { 0 }; // Test B (PREREG-B.md): CNT, HARD-R, SOFT-R, SOFT-RI
static br_t cb[4][MAXN * LMAX];
rng_t r2 = { 2000003ULL * seed + 7919ULL * tier + (uint64_t) src[0] };
br_t gb[MAXN];
for (int s = 0; s < ho->ns; s++) {
int o = ho->off[s], n = ho->off[s + 1] - o, le6, ng = gold_spans(gold_ho, s, gb, &le6), m = n + 1, nc[4] = { 0 };
for (int b = 0; b < ng; b++) if (gb[b].j - gb[b].i + 1 <= LMAX) gold++;
for (int k = 0; k < KPARSE; k++) { fill_scores(ho, o, n, Sc, A, scale, &r2); eisner(m, hd); for (int d = 1; d < m; d++) hp[k][d - 1] = hd[d] - 1; }
for (int i = 0; i < n; i++) for (int len = 2; len <= LMAX && i + len <= n; len++) {
int j = i + len - 1, c = 0;
for (int k = 0; k < len; k++) x[k] = ho->c[o + i + k];
span_t *e = span_get(x, len, 0);
if (!e || e->cnum < 3) continue;
for (int k = 0; k < KPARSE; k++) c += complete(hp[k], 0, n, i, j);
double rh = (double) e->hard / e->cnum, rs = e->soft / e->cnum, ii = (double) c / KPARSE;
cb[0][nc[0]++] = (br_t) { i, j, e->cnum };
if (rh > 0.5) cb[1][nc[1]++] = (br_t) { i, j, rh };
if (rs > 0.5) cb[2][nc[2]++] = (br_t) { i, j, rs };
if (rs > 0.5 && ii > 0.5) cb[3][nc[3]++] = (br_t) { i, j, rs * ii };
}
for (int arm = 0; arm < 4; arm++) {
int k = select_brackets(cb[arm], nc[arm]);
bpred[arm] += k;
for (int a = 0; a < k; a++) for (int b = 0; b < ng; b++)
if (gb[b].j - gb[b].i + 1 <= LMAX && cb[arm][a].i == gb[b].i && cb[arm][a].j == gb[b].j) { btp[arm]++; break; }
}
for (int i = 0; i < n; i++) for (int len = 2; len <= LMAX && i + len <= n; len++) {
int j = i + len - 1, isg = 0;
for (int k = 0; k < len; k++) x[k] = ho->c[o + i + k];
span_t *e = span_get(x, len, 0);
if (!e) continue;
for (int b = 0; b < ng; b++) if (gb[b].i == i && gb[b].j == j) isg = 1;
size_t slot = (size_t) (e - tab);
for (int mth = 0; mth < 3; mth++) for (int bi = 0; bi < 3; bi++) if (rank[mth][slot] < (uint32_t) budgets_soft[bi]) {
cand[mth][bi]++; if (isg) { cgold[mth][bi]++; hit[mth][bi]++; }
}
}
}
static const char *mname[3] = { "CNT", "HARD", "SOFT" };
for (int mth = 0; mth < 3; mth++) for (int bi = 0; bi < 3; bi++)
printf("R\t%d\t%d\t%s\t%s\t%d\t%.5f\t%.5f\t%zu\n", seed, tier, src, mname[mth], budgets_soft[bi],
gold ? (double) hit[mth][bi] / gold : 0, cand[mth][bi] ? (double) cgold[mth][bi] / cand[mth][bi] : 0, nt);
static const char *bname[4] = { "CNT", "HARD-R", "SOFT-R", "SOFT-RI" };
for (int arm = 0; arm < 4; arm++) {
double pr = bpred[arm] ? (double) btp[arm] / bpred[arm] : 0, rc = gold ? (double) btp[arm] / gold : 0;
printf("B\t%d\t%d\t%s\t%s\t%.5f\t%.5f\t%.5f\t%ld\n", seed, tier, src, bname[arm], pr, rc, pr + rc > 0 ? 2 * pr * rc / (pr + rc) : 0, bpred[arm]);
}
for (int mth = 0; mth < 3; mth++) free(rank[mth]);
free(idx);
}
// ---------------------------------------------------------------- main
int main (int argc, char **argv) {
if (argc < 2) { fprintf(stderr, "usage: l2 <seed> [--tiers a,b] [--heldout N] [--mut-drop] [--jt prefix] [--soft [--soft-scale s]] [--undirected] [--reparse] [--sections prefix] [--labels prefix [--labels-name n]] [--dict]\n"); return 1; }
int seed = atoi(argv[1]);
int tiers[16] = { 3000, 10000, 30000 }, ntier = 3, nho = 2000;
const char *jt_prefix = NULL;
int soft = 0, undirected = 0, reparse = 0, dict = 0; double soft_scale = 1.0;
const char *sect_prefix = NULL, *lab_prefix = NULL, *lab_name = "LV";
for (int i = 2; i < argc; i++) {
if (!strcmp(argv[i], "--mut-drop")) mut_drop = 1;
else if (!strcmp(argv[i], "--heldout") && i + 1 < argc) nho = atoi(argv[++i]);
else if (!strcmp(argv[i], "--jt") && i + 1 < argc) jt_prefix = argv[++i];
else if (!strcmp(argv[i], "--soft")) soft = 1;
else if (!strcmp(argv[i], "--undirected")) undirected = 1;
else if (!strcmp(argv[i], "--reparse")) reparse = 1;
else if (!strcmp(argv[i], "--dict")) dict = 1;
else if (!strcmp(argv[i], "--sections") && i + 1 < argc) sect_prefix = argv[++i];
else if (!strcmp(argv[i], "--labels") && i + 1 < argc) lab_prefix = argv[++i];
else if (!strcmp(argv[i], "--labels-name") && i + 1 < argc) lab_name = argv[++i];
else if (!strcmp(argv[i], "--soft-scale") && i + 1 < argc) soft_scale = atof(argv[++i]);
else if (!strcmp(argv[i], "--tiers") && i + 1 < argc) {
ntier = 0;
for (char *p = strtok(argv[++i], ","); p && ntier < 16; p = strtok(NULL, ",")) tiers[ntier++] = atoi(p);
}
}
setvbuf(stdout, NULL, _IOLBF, 0);
build_world();
tmask = ((size_t) 1 << TABBITS) - 1;
tab = malloc(sizeof(span_t) * (tmask + 1));
int maxt = 0;
for (int i = 0; i < ntier; i++) if (tiers[i] > maxt) maxt = tiers[i];
corpus_t full = gen_corpus(1000003ULL * seed + 1, maxt);
corpus_t ho = gen_corpus(1000003ULL * seed + 2, nho);
printf("#\tseed=%d\tV=%d\theldout_sents=%d\n", seed, V, ho.ns);
// C1: gold brackets fed through the selector give P = R = 1.
{
br_t gb[MAXN], cb[MAXN];
long g = 0, tp = 0, kept = 0;
for (int s = 0; s < ho.ns; s++) {
int le6, ng = gold_spans(&ho, s, gb, &le6);
for (int a = 0; a < ng; a++) { cb[a] = gb[a]; cb[a].s = mix(s * 131 + a) % 1000; }
int k = select_brackets(cb, ng);
g += ng; kept += k;
for (int a = 0; a < k; a++) for (int b = 0; b < ng; b++) if (cb[a].i == gb[b].i && cb[a].j == gb[b].j) { tp++; break; }
}
int ok = tp == g && kept == g;
printf("GUARD\tC1\t%s\ttp=%ld\tkept=%ld\tgold=%ld\n", ok ? "PASS" : "FAIL", tp, kept, g);
if (!ok) return 2;
}
// C5: with the TRUE tree as the "layer-1 parse", every gold span is connected and complete.
{
long g = 0, okc = 0, okp = 0;
br_t gb[MAXN];
for (int s = 0; s < ho.ns; s++) {
int o = ho.off[s], n = ho.off[s + 1] - o, le6, ng = gold_spans(&ho, s, gb, &le6);
for (int b = 0; b < ng; b++) { g++; okc += connected(ho.h, o, gb[b].i, gb[b].j); okp += complete(ho.h, o, n, gb[b].i, gb[b].j); }
}
int ok = okc == g && okp == g;
printf("GUARD\tC5\t%s\tgold=%ld\tconn=%ld\tcomp=%ld\n", ok ? "PASS" : "FAIL", g, okc, okp);
if (!ok) return 2;
}
// C5-U (PREREG-U.md): with the gold tree as an undirected parse, every gold span is uconn and ucomp.
parse_t Ptr = { 0 }, Pho = { 0 };
if (undirected) {
Ptr = parse_alloc(full.ntok); Pho = parse_alloc(ho.ntok);
links_from_heads(&ho, ho.h, &Pho);
long g = 0, okc = 0, okp = 0;
br_t gb[MAXN];
for (int s = 0; s < ho.ns; s++) {
int o = ho.off[s], le6, ng = gold_spans(&ho, s, gb, &le6);
for (int b = 0; b < ng; b++) { g++; okc += uconn(&Pho, o, gb[b].i, gb[b].j); okp += ucomp(&Pho, o, gb[b].i, gb[b].j); }
}
int ok = okc == g && okp == g;
printf("GUARD\tC5-U\t%s\tgold=%ld\tuconn=%ld\tucomp=%ld\n", ok ? "PASS" : "FAIL", g, okc, okp);
if (!ok) return 2;
}
int *str = malloc(sizeof(int) * full.ntok), *sho = malloc(sizeof(int) * ho.ntok);
int *htr = malloc(sizeof(int) * full.ntok), *hho = malloc(sizeof(int) * ho.ntok);
int *Rmap = malloc(sizeof(int) * V), *perm = malloc(sizeof(int) * V);
for (int ti = 0; ti < ntier; ti++) {
int tier = tiers[ti];
corpus_t tr = prefix(full, tier);
printf("#\ttier=%d\ttrain_toks=%d\n", tier, tr.ntok);
int passes;
int *Lmap = exchange(&tr, &passes);
rng_t rr = { 99991ULL * seed + tier };
for (int w = 0; w < V; w++) perm[w] = w;
for (int w = V - 1; w > 0; w--) { int j = rpick(&rr, w + 1), t = perm[w]; perm[w] = perm[j]; perm[j] = t; }
for (int w = 0; w < V; w++) Rmap[w] = primary[perm[w]];
// PREREG-dict.md: parse with the learned dictionary, sources G and RP1. Skips every other arm.
if (dict) {
if (!Ptr.lnk) { Ptr = parse_alloc(full.ntok); Pho = parse_alloc(ho.ntok); }
for (int xi = 0; xi < 2; xi++) {
if (xi == 0) { layer1_symbols(SRC_G, &tr, seed, Lmap, Rmap, str); layer1_symbols(SRC_G, &ho, seed, Lmap, Rmap, sho); }
else { // RP1: exchange over the word-MST links (PREREG-reparse round 1)
corpus_t trw = with_symbols(&tr, tr.w);
arm_t a = { "l1", V, NULL, 1 };
pairs_t P = count_pairs(&a, &trw);
double *MI = pair_mi(&P);
free_pairs(&P);
parse_u(&trw, MI, V, 0, &Ptr);
free(MI);
double *Wp = calloc((size_t) V * V, sizeof(double));
for (int s = 0; s < tr.ns; s++) {
int o = tr.off[s], n = tr.off[s + 1] - o;
for (int t = 0; t < n; t++) for (int k = 0; k < Ptr.nl[o + t]; k++) { int b = Ptr.lnk[(o + t) * MAXL + k]; if (b > t) Wp[(size_t) tr.w[o + t] * V + tr.w[o + b]] += 1; }
}
int *cls = exchange_pairs(Wp, &tr);
for (int t = 0; t < tr.ntok; t++) str[t] = cls[tr.w[t]];
for (int t = 0; t < ho.ntok; t++) sho[t] = cls[ho.w[t]];
free(cls); free(Wp);
}
corpus_t trs = with_symbols(&tr, str), hos = with_symbols(&ho, sho);
arm_t a = { "l1", NCLS, NULL, 1 };
pairs_t P = count_pairs(&a, &trs);
double *MI = pair_mi(&P);
free_pairs(&P);
run_dict(seed, tier, xi ? "RP1" : "G", &trs, &hos, MI, NCLS);
free(MI);
}
free(Lmap);
continue;
}
// PREREG-LV.md: external per-token labels (<prefix>-<tier>-{tr,ho}.lab, one int per token) as layer 1:
// MST over the labels, link F1, C-x and M-x-ucomp-MST. Skips every other arm.
if (lab_prefix) {
if (!Ptr.lnk) { Ptr = parse_alloc(full.ntok); Pho = parse_alloc(ho.ntok); }
u_tr = &Ptr; u_ho = &Pho;
int A = 0;
for (int k = 0; k < 2; k++) {
char path[512];
snprintf(path, sizeof path, "%s-%d-%s.lab", lab_prefix, tier, k ? "ho" : "tr");
FILE *f = fopen(path, "r");
if (!f) { perror(path); return 1; }
int *dst = k ? sho : str, nt = k ? ho.ntok : tr.ntok;
for (int t = 0; t < nt; t++) { if (fscanf(f, "%d", &dst[t]) != 1) { fprintf(stderr, "%s: short\n", path); return 1; } if (dst[t] + 1 > A) A = dst[t] + 1; }
fclose(f);
}
corpus_t trs = with_symbols(&tr, str), hos = with_symbols(&ho, sho);
arm_t a = { "l1", A, NULL, 1 };
pairs_t P = count_pairs(&a, &trs);
double *MI = pair_mi(&P), pr, rc, f1;
free_pairs(&P);
parse_u(&trs, MI, A, 0, &Ptr); parse_u(&hos, MI, A, 0, &Pho);
free(MI);
link_prf(&hos, &Pho, &pr, &rc, &f1);
printf("P\t%d\t%d\t%s\tMST\t%.5f\t%.5f\t%.5f\n", seed, tier, lab_name, pr, rc, f1);
char nm[48];
snprintf(nm, sizeof nm, "C-%s", lab_name);
run_arm(seed, tier, nm, RULE_ALL, &trs, &hos, &ho, NULL, NULL);
snprintf(nm, sizeof nm, "M-%s-ucomp-MST", lab_name);
run_arm(seed, tier, nm, RULE_UCOMP, &trs, &hos, &ho, (const int *) u_tr, (const int *) u_ho);
free(Lmap);
continue;
}
// F and MW: words
corpus_t trw = with_symbols(&tr, tr.w), how = with_symbols(&ho, ho.w);
run_arm(seed, tier, "F", RULE_ALL, &trw, &how, &ho, NULL, NULL);
layer1_parse(&trw, &how, V, htr, hho);
run_arm(seed, tier, "MW-conn", RULE_CONN, &trw, &how, &ho, htr, hho);
run_arm(seed, tier, "MW-comp", RULE_COMP, &trw, &how, &ho, htr, hho);
for (int x = 0; x < NSRC; x++) {
int A = layer1_symbols(x, &tr, seed, Lmap, Rmap, str);
layer1_symbols(x, &ho, seed, Lmap, Rmap, sho);
corpus_t trs = with_symbols(&tr, str), hos = with_symbols(&ho, sho);
char nm[24];
snprintf(nm, sizeof nm, "C-%s", src_name[x]);
run_arm(seed, tier, nm, RULE_ALL, &trs, &hos, &ho, NULL, NULL);
layer1_parse(&trs, &hos, A, htr, hho);
snprintf(nm, sizeof nm, "M-%s-conn", src_name[x]);
run_arm(seed, tier, nm, RULE_CONN, &trs, &hos, &ho, htr, hho);
snprintf(nm, sizeof nm, "M-%s-comp", src_name[x]);
run_arm(seed, tier, nm, RULE_COMP, &trs, &hos, &ho, htr, hho);
}
// PREREG-U.md: undirected FOREST / MST / MPG parses, undirected unit rules, link F1 (sources G, L, R).
if (undirected) {
static const int usrc[3] = { SRC_G, SRC_L, SRC_R };
static const char *pname[3] = { "FOREST", "MST", "MPG" };
u_tr = &Ptr; u_ho = &Pho;
for (int xi = 0; xi < 3; xi++) {
int x = usrc[xi];
int A = layer1_symbols(x, &tr, seed, Lmap, Rmap, str);
layer1_symbols(x, &ho, seed, Lmap, Rmap, sho);
corpus_t trs = with_symbols(&tr, str), hos = with_symbols(&ho, sho);
arm_t a = { "l1", A, NULL, 1 };
pairs_t P = count_pairs(&a, &trs);
double *MI = pair_mi(&P);
free_pairs(&P);
for (int pi = 0; pi < 3; pi++) {
if (pi == 0) { layer1_parse(&trs, &hos, A, htr, hho); links_from_heads(&trs, htr, &Ptr); links_from_heads(&hos, hho, &Pho); }
else { parse_u(&trs, MI, A, pi == 2, &Ptr); parse_u(&hos, MI, A, pi == 2, &Pho); }
double pr, rc, f1;
link_prf(&hos, &Pho, &pr, &rc, &f1);
// link_prf reads gold heads from hos.h, which is the held-out gold tree (with_symbols only replaces c[]).
printf("P\t%d\t%d\t%s\t%s\t%.5f\t%.5f\t%.5f\n", seed, tier, src_name[x], pname[pi], pr, rc, f1);
char nm[32];
snprintf(nm, sizeof nm, "M-%s-uconn-%s", src_name[x], pname[pi]);
run_arm(seed, tier, nm, RULE_UCONN, &trs, &hos, &ho, (const int *) u_tr, (const int *) u_ho);
snprintf(nm, sizeof nm, "M-%s-ucomp-%s", src_name[x], pname[pi]);
run_arm(seed, tier, nm, RULE_UCOMP, &trs, &hos, &ho, (const int *) u_tr, (const int *) u_ho);
}
free(MI);
}
}
// PREREG-reparse.md: round 0 parses words; round r clusters words over the round r-1 parse links, re-parses.
if (reparse) {
if (!Ptr.lnk) { Ptr = parse_alloc(full.ntok); Pho = parse_alloc(ho.ntok); }
u_tr = &Ptr; u_ho = &Pho;
int *cls = NULL;
double *Wp = malloc(sizeof(double) * V * V);
for (int r = 0; r <= ROUNDS; r++) {
int A = V;
if (r == 0) { memcpy(str, tr.w, sizeof(int) * tr.ntok); memcpy(sho, ho.w, sizeof(int) * ho.ntok); }
else {
memset(Wp, 0, sizeof(double) * V * V);
for (int s = 0; s < tr.ns; s++) {
int o = tr.off[s], n = tr.off[s + 1] - o;
for (int t = 0; t < n; t++) for (int k = 0; k < Ptr.nl[o + t]; k++) {
int b = Ptr.lnk[(o + t) * MAXL + k];
if (b > t) Wp[(size_t) tr.w[o + t] * V + tr.w[o + b]] += 1;
}
}
free(cls);
cls = exchange_pairs(Wp, &tr);
for (int t = 0; t < tr.ntok; t++) str[t] = cls[tr.w[t]];
for (int t = 0; t < ho.ntok; t++) sho[t] = cls[ho.w[t]];
A = KR;
}
corpus_t trs = with_symbols(&tr, str), hos = with_symbols(&ho, sho);
arm_t a = { "l1", A, NULL, 1 };
pairs_t P = count_pairs(&a, &trs);
double *MI = pair_mi(&P), pr, rc, f1;
free_pairs(&P);
parse_u(&trs, MI, A, 0, &Ptr); parse_u(&hos, MI, A, 0, &Pho);
free(MI);
link_prf(&hos, &Pho, &pr, &rc, &f1);
printf("RP\t%d\t%d\t%d\t%.5f\t%.5f\t%.5f\t%.5f\n", seed, tier, r, pr, rc, f1, m1_acc(&ho, sho, A));
char nm[32];
snprintf(nm, sizeof nm, "M-RP%d-ucomp", r);
run_arm(seed, tier, nm, RULE_UCOMP, &trs, &hos, &ho, (const int *) u_tr, (const int *) u_ho);
}
free(cls); free(Wp);
}
// Step 3 (#15): per-token Sections of the word-level MST (Linas: germ word + linked words, -/+ by position),
// written as <prefix>-<tier>-{tr,ho}.tsv lines: token index, germ, ConnectorSeq.
if (sect_prefix) {
if (!Ptr.lnk) { Ptr = parse_alloc(full.ntok); Pho = parse_alloc(ho.ntok); }
corpus_t trw = with_symbols(&tr, tr.w), how = with_symbols(&ho, ho.w);
arm_t a = { "l1", V, NULL, 1 };
pairs_t P = count_pairs(&a, &trw);
double *MI = pair_mi(&P);
free_pairs(&P);
parse_u(&trw, MI, V, 0, &Ptr); parse_u(&how, MI, V, 0, &Pho);
free(MI);
for (int k = 0; k < 2; k++) {
const corpus_t *C = k ? &how : &trw; const parse_t *Pp = k ? &Pho : &Ptr;
char path[512];
snprintf(path, sizeof path, "%s-%d-%s.tsv", sect_prefix, tier, k ? "ho" : "tr");
FILE *f = fopen(path, "w");
if (!f) { perror(path); return 1; }
for (int s = 0; s < C->ns; s++) {
int o = C->off[s], n = C->off[s + 1] - o;
for (int t = 0; t < n; t++) {
int nb[MAXL], m = 0;
for (int q = 0; q < Pp->nl[o + t]; q++) nb[m++] = Pp->lnk[(o + t) * MAXL + q];
for (int x = 1; x < m; x++) { int v = nb[x], y = x; while (y > 0 && nb[y - 1] > v) { nb[y] = nb[y - 1]; y--; } nb[y] = v; }
fprintf(f, "%d\tw%04d\t%d\t", o + t, C->w[o + t], (k ? &ho : &tr)->c[o + t]);
for (int x = 0; x < m; x++) fprintf(f, "(Connector (WordNode \"w%04d\") (SexNode \"%c\")) ", C->w[o + nb[x]], nb[x] < t ? '-' : '+');
fprintf(f, "\n");
}
}
fclose(f);
}
}
free(Lmap);
// PREREG-soft.md: rank span types by assembly-ness over KPARSE perturbed parses (sources G and L).
if (soft) for (int xi = 0; xi < 2; xi++) {
int x = xi ? SRC_L : SRC_G;
int *Lm = exchange(&tr, &passes);
int A = layer1_symbols(x, &tr, seed, Lm, Rmap, str);
layer1_symbols(x, &ho, seed, Lm, Rmap, sho);
corpus_t trs = with_symbols(&tr, str), hos = with_symbols(&ho, sho);
arm_t a = { "l1", A, NULL, 1 };
pairs_t P = count_pairs(&a, &trs);
long ev, acc;
double *Sc = hard_scores(&P, &ev, &acc);
run_soft(seed, tier, src_name[x], &trs, &hos, &ho, Sc, A, soft_scale);
free(Sc); free_pairs(&P); free(Lm);
}
// PREREG-JT.md: layer 1 from the jigsaw transformer (labels + its attention parse), from jt --dump.
if (jt_prefix) {
char path[512];
snprintf(path, sizeof path, "%s-%d.bin", jt_prefix, tier);
FILE *f = fopen(path, "rb");
if (!f) { fprintf(stderr, "cannot read %s\n", path); return 1; }
int *jtr = malloc(sizeof(int) * tr.ntok), *jho = malloc(sizeof(int) * ho.ntok), *atr = malloc(sizeof(int) * tr.ntok), *aho = malloc(sizeof(int) * ho.ntok), nt;
int ok = fread(&nt, sizeof(int), 1, f) == 1 && nt == tr.ntok && fread(jtr, sizeof(int), nt, f) == (size_t) nt && fread(atr, sizeof(int), nt, f) == (size_t) nt
&& fread(&nt, sizeof(int), 1, f) == 1 && nt == ho.ntok && fread(jho, sizeof(int), nt, f) == (size_t) nt && fread(aho, sizeof(int), nt, f) == (size_t) nt;
fclose(f);
if (!ok) { fprintf(stderr, "%s does not match this corpus\n", path); return 1; }
corpus_t trs = with_symbols(&tr, jtr), hos = with_symbols(&ho, jho);
run_arm(seed, tier, "C-JT", RULE_ALL, &trs, &hos, &ho, NULL, NULL);
layer1_parse(&trs, &hos, NCLS, htr, hho);
run_arm(seed, tier, "M-JT-conn", RULE_CONN, &trs, &hos, &ho, htr, hho);
run_arm(seed, tier, "M-JT-comp", RULE_COMP, &trs, &hos, &ho, htr, hho);
run_arm(seed, tier, "M-JTA-conn", RULE_CONN, &trs, &hos, &ho, atr, aho);
run_arm(seed, tier, "M-JTA-comp", RULE_COMP, &trs, &hos, &ho, atr, aho);
free(jtr); free(jho); free(atr); free(aho);
}
}
return 0;
}