// Graded ("fractal") connectors: see PREREG.md. Reuses the planted grammar, window-pair gate and Eisner
// parser of ../across-cluster/ac.c unchanged.
//
// fractal <seed> [--tiers 3000,10000,30000] [--heldout N] [--rule backoff|bestg]
// --rule picks the combined scorer that tiers GRADED and GRADED-R (run 1: backoff; run 2: bestg).
// Output rows:
// P <seed> <tier> <scorer> <F1> <P> <R> level-1 link F1 on held-out
// R <seed> <tier> <arm> <budget> <recall> <listlen> level-2 type recall at budget (budget -1 = all)
#define main ac_main
#include "../across-cluster/ac.c"
#undef main
#define NLEV 4 // W, G, S1, S2
#define LMAX 6
// ---------------------------------------------------------------- hierarchy (level2/l2.c merge_class)
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; }
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;
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;
}
// Level symbols for every token: level 0 = word, 1 = class, 2/3 = coarser. `cls` gives the level-1 class
// of a token (gold: the token's class; random: Rmap of its word); levels 2-3 merge it like S1/S2.
static void level_symbols (const corpus_t *C, const int *rmap, int lev, int *out) {
for (int t = 0; t < C->ntok; t++) {
if (lev == 0) { out[t] = C->w[t]; continue; }
int c = rmap ? rmap[C->w[t]] : C->c[t];
out[t] = lev == 1 ? c : merge_class(c, lev - 1); // lev 2 = S1, lev 3 = S2
}
}
// ---------------------------------------------------------------- per-level scores
typedef struct { int A[NLEV]; double *S[NLEV], *G[NLEV]; int *ho[NLEV]; } hier_t;
// G statistic of a pair (the significance gated_pmi tests), 0 if the pair fails the gate.
static double gate_g (const pairs_t *P, int a, int b) {
if (gated_pmi(P, a, b) <= NEG) return 0;
double n = P->M[(size_t) a * P->A + b], ra = P->R[a], cb = P->Cm[b], N = P->N;
double o[4] = { n, ra - n, cb - n, N - ra - cb + n };
double e[4] = { ra * cb / N, ra * (N - cb) / N, (N - ra) * cb / N, (N - ra) * (N - cb) / N };
double g = 0;
for (int k = 0; k < 4; k++) if (o[k] > 0) g += o[k] * log(o[k] / e[k]);
return 2 * g;
}
static corpus_t with_symbols (const corpus_t *C, int *sym) { corpus_t S = *C; S.c = sym; return S; }
static void build_hier (hier_t *H, const corpus_t *tr, const corpus_t *ho, const int *rmap) {
int *st = malloc(sizeof(int) * tr->ntok);
for (int l = 0; l < NLEV; l++) {
H->A[l] = l == 0 ? V : NCLS;
level_symbols(tr, rmap, l, st);
corpus_t ts = with_symbols(tr, st);
arm_t a = { "lev", H->A[l], NULL, 1 };
pairs_t P = count_pairs(&a, &ts);
long ev, acc;
H->S[l] = hard_scores(&P, &ev, &acc);
H->G[l] = calloc((size_t) H->A[l] * H->A[l], sizeof(double));
for (int a2 = 0; a2 < H->A[l]; a2++) for (int b2 = 0; b2 < H->A[l]; b2++)
if (H->S[l][(size_t) a2 * H->A[l] + b2] > NEG) H->G[l][(size_t) a2 * H->A[l] + b2] = gate_g(&P, a2, b2);
free_pairs(&P);
H->ho[l] = malloc(sizeof(int) * ho->ntok);
level_symbols(ho, rmap, l, H->ho[l]);
}
free(st);
}
static void free_hier (hier_t *H) { for (int l = 0; l < NLEV; l++) { free(H->S[l]); free(H->G[l]); free(H->ho[l]); } }
// Edge scorers. ctx = { hier, symbols-per-level for the corpus being parsed, mode }.
typedef struct { hier_t *H; int *sym[NLEV]; int mode; } edge_ctx_t; // mode 0..3 = single level, 4 = backoff, 5 = best-G
static double edge_level (const corpus_t *C, int o, int i, int j, void *vctx, int window) {
(void) C; (void) window;
edge_ctx_t *e = vctx;
if (e->mode < NLEV) {
int l = e->mode;
return e->H->S[l][(size_t) e->sym[l][o + i] * e->H->A[l] + e->sym[l][o + j]];
}
if (e->mode == NLEV) {
for (int l = 0; l < NLEV; l++) { // backoff: the finest level that passes the gate
double s = e->H->S[l][(size_t) e->sym[l][o + i] * e->H->A[l] + e->sym[l][o + j]];
if (s > NEG) return s;
}
return NEG;
}
double best = NEG, bg = 0; // best-G: the passing level with the largest G statistic (PREREG-2)
for (int l = 0; l < NLEV; l++) {
size_t k = (size_t) e->sym[l][o + i] * e->H->A[l] + e->sym[l][o + j];
if (e->H->S[l][k] > NEG && e->H->G[l][k] > bg) { bg = e->H->G[l][k]; best = e->H->S[l][k]; }
}
return best;
}
// Parse every sentence; head[t] = in-sentence offset of head, or -1 (as level2 parse_all).
static void parse_heads (const corpus_t *C, edge_ctx_t *e, int *head) {
int hd[MAXN + 1];
for (int s = 0; s < C->ns; s++) {
int o = C->off[s], n = C->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] = edge_level(C, o, i, j, e, 1);
eisner(m, hd);
for (int d = 1; d < m; d++) head[o + d - 1] = hd[d] - 1;
}
}
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;
}
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;
}
static int structure (const int *head, int o, int n, int i, int j) { return complete(head, o, n, i, j) ? 2 : connected(head, o, i, j) ? 1 : 0; }
// ---------------------------------------------------------------- level-2 type table (G-class sequences)
#define NARM 3 // tiering sources: 0 = backoff (gold hierarchy), 1 = G-level parse, 2 = backoff (random hierarchy)
typedef struct { uint64_t key; double n, ncomp_g; int tier[NARM]; int used; } type_t;
static type_t *types;
static size_t tmask2;
static uint64_t type_key (const int *cls, int i, int len) {
uint64_t k = (uint64_t) len;
for (int q = 0; q < len; q++) k = k * 32 + (uint64_t) cls[i + q];
return k;
}
static type_t *type_get (uint64_t key, int create) {
size_t i = (size_t) (key * 0x9e3779b97f4a7c15ULL) & tmask2;
while (types[i].used) {
if (types[i].key == key) return &types[i];
i = (i + 1) & tmask2;
}
if (!create) return NULL;
memset(&types[i], 0, sizeof(type_t));
types[i].used = 1; types[i].key = key;
return &types[i];
}
static int gold_spans (const corpus_t *C, int s, int *gi, int *gj) {
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;
}
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] || hi[t] - lo[t] + 1 > LMAX) continue;
gi[k] = lo[t]; gj[k] = hi[t]; k++;
}
return k;
}
typedef struct { type_t *t; double k1, k2; } rank_t;
static int by_key (const void *a, const void *b) {
const rank_t *x = a, *y = b;
if (x->k1 != y->k1) return x->k1 > y->k1 ? -1 : 1;
if (x->k2 != y->k2) return x->k2 > y->k2 ? -1 : 1;
return (x->t->key > y->t->key) - (x->t->key < y->t->key);
}
static const long fbudgets[] = { 300, 1000, 3000, 10000, -1 };
#define NBUD 5
// ---------------------------------------------------------------- main
int main (int argc, char **argv) {
if (argc < 2) { fprintf(stderr, "usage: fractal <seed> [--tiers a,b] [--heldout N]\n"); return 1; }
int seed = atoi(argv[1]);
int tiers[16] = { 3000, 10000, 30000 }, ntier = 3, nho = 2000, rule = NLEV; // rule: NLEV backoff, NLEV + 1 best-G
for (int i = 2; i < argc; i++) {
if (!strcmp(argv[i], "--heldout") && i + 1 < argc) nho = atoi(argv[++i]);
else if (!strcmp(argv[i], "--rule") && i + 1 < argc) { i++; rule = !strcmp(argv[i], "bestg") ? NLEV + 1 : NLEV; }
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();
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);
// Random hierarchy: words relabelled into classes with the gold class sizes (as level2's R).
int *rmap = malloc(sizeof(int) * V), *perm = malloc(sizeof(int) * V);
rng_t rr = { 777ULL * seed + 1 };
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]];
tmask2 = (1 << 20) - 1;
types = malloc(sizeof(type_t) * (tmask2 + 1));
for (int ti = 0; ti < ntier; ti++) {
int tier = tiers[ti];
corpus_t tr = prefix(full, tier);
hier_t Hg, Hr;
build_hier(&Hg, &tr, &ho, NULL);
build_hier(&Hr, &tr, &ho, rmap);
// Part 1: held-out link F1 per scorer.
const char *pname[6] = { "W", "G", "S1", "S2", "BACKOFF", "BEST-G" };
for (int mode = 0; mode <= NLEV + 1; mode++) {
edge_ctx_t e = { &Hg, { Hg.ho[0], Hg.ho[1], Hg.ho[2], Hg.ho[3] }, mode };
link_t L = parse_eval(&ho, edge_level, &e, 1);
double p = L.pred ? (double) L.tp / L.pred : 0, r = L.gold ? (double) L.tp / L.gold : 0;
printf("P\t%d\t%d\t%s\t%.5f\t%.5f\t%.5f\n", seed, tier, pname[mode], p + r > 0 ? 2 * p * r / (p + r) : 0, p, r);
}
// Part 2: parse the training prefix three ways, collect G-class span types with their best structure.
int *sym[NLEV], *symr[NLEV];
for (int l = 0; l < NLEV; l++) {
sym[l] = malloc(sizeof(int) * tr.ntok); level_symbols(&tr, NULL, l, sym[l]);
symr[l] = malloc(sizeof(int) * tr.ntok); level_symbols(&tr, rmap, l, symr[l]);
}
int *hb = malloc(sizeof(int) * tr.ntok), *hgp = malloc(sizeof(int) * tr.ntok), *hrb = malloc(sizeof(int) * tr.ntok);
edge_ctx_t eb = { &Hg, { sym[0], sym[1], sym[2], sym[3] }, rule };
edge_ctx_t eg = { &Hg, { sym[0], sym[1], sym[2], sym[3] }, 1 };
edge_ctx_t er = { &Hr, { symr[0], symr[1], symr[2], symr[3] }, rule };
parse_heads(&tr, &eb, hb); parse_heads(&tr, &eg, hgp); parse_heads(&tr, &er, hrb);
memset(types, 0, sizeof(type_t) * (tmask2 + 1));
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++) {
int j = i + len - 1;
type_t *t = type_get(type_key(tr.c + o, i, len), 1);
t->n += 1;
int sb = structure(hb, o, n, i, j), sg = structure(hgp, o, n, i, j), sr = structure(hrb, o, n, i, j);
if (sb > t->tier[0]) t->tier[0] = sb;
if (sg > t->tier[1]) t->tier[1] = sg;
if (sr > t->tier[2]) t->tier[2] = sr;
if (sg == 2) t->ncomp_g += 1;
}
}
size_t nt = 0;
for (size_t k = 0; k <= tmask2; k++) if (types[k].used) nt++;
rank_t *rk = malloc(sizeof(rank_t) * nt);
// Held-out gold span types.
size_t ng = 0, capg = 4096;
uint64_t *gkeys = malloc(sizeof(uint64_t) * capg);
int gi[MAXN], gj[MAXN];
for (int s = 0; s < ho.ns; s++) {
int k = gold_spans(&ho, s, gi, gj), o = ho.off[s];
for (int q = 0; q < k; q++) {
if (ng == capg) { capg *= 2; gkeys = realloc(gkeys, sizeof(uint64_t) * capg); }
gkeys[ng++] = type_key(ho.c + o, gi[q], gj[q] - gi[q] + 1);
}
}
const char *aname[5] = { "C-G", "HARD", "GRADED", "GRADED-G", "GRADED-R" };
for (int arm = 0; arm < 5; arm++) {
size_t m = 0;
for (size_t k = 0; k <= tmask2; k++) {
type_t *t = &types[k];
if (!t->used) continue;
if (arm == 1 && t->tier[1] < 2) continue; // HARD deletes non-assemblies
double k1 = arm == 0 ? t->n : arm == 1 ? t->ncomp_g : arm == 2 ? t->tier[0] : arm == 3 ? t->tier[1] : t->tier[2];
double k2 = arm >= 2 ? t->n : 0;
rk[m++] = (rank_t) { t, k1, k2 };
}
qsort(rk, m, sizeof(rank_t), by_key);
for (int b = 0; b < NBUD; b++) {
long B = fbudgets[b] < 0 || (size_t) fbudgets[b] > m ? (long) m : fbudgets[b];
// mark the first B types of this list (used = 2), count held-out gold spans whose type is marked
for (size_t q = 0; q < m; q++) rk[q].t->used = q < (size_t) B ? 2 : 1;
long hit = 0;
for (size_t g = 0; g < ng; g++) { type_t *t = type_get(gkeys[g], 0); if (t && t->used == 2) hit++; }
for (size_t q = 0; q < m; q++) rk[q].t->used = 1;
printf("R\t%d\t%d\t%s\t%ld\t%.5f\t%zu\n", seed, tier, aname[arm], fbudgets[b], ng ? (double) hit / ng : 0, m);
if (fbudgets[b] < 0) break;
}
}
free(rk); free(gkeys); free(hb); free(hgp); free(hrb);
for (int l = 0; l < NLEV; l++) { free(sym[l]); free(symr[l]); }
free_hier(&Hg); free_hier(&Hr);
}
return 0;
}