// Port of Linas's pair counting (learn stage A) and pair MI (matrix batch-all-pair-mi, stage B).
//
// Input: recorded parses, one atom per line: <window>\t<parse>\t<atom>, as written by oracle/g0.scm
// (WordNode lines = the parse's words, EdgeLink lines = its ANY links). Counts are occurrences, which is
// what G0's tally guard proved Linas's pipe stores for stage A.
//
// Output: one line per (atom, key) in G0's dump format, for every value batch-all-pair-mi writes that is
// ported here. Sources:
// counts learn pipe-count (TruthValueKey index 2)
// Norm Key (l0 l1 l2 lq su), Left/Right Total Key, Supp Dimension Key matrix support.scm
// FrequencyKey (p, -log2 p, -p log2 p) matrix frequency.scm set-freq
// Mutual Info Key (mi, fmi), fmi = logli(x,*) + logli(*,y) - logli(x,y) matrix compute-mi.scm:187-202
// Entropy Key (h, h/p), wildcard MI (mi, mi/p), Total Entropy / Total MI matrix entropy.scm
// Not ported: Dimension Key and Left/Right Norm Key (the report object's centrality stats).
//
// pairmi <parses.tsv> > state.tsv
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// ---------------------------------------------------------------- vocabulary
typedef struct { char *name; double count; } word_t;
static word_t *words;
static int nwords, capwords;
static int *wtab;
static size_t wmask;
static uint64_t fnv (const char *s) {
uint64_t h = 1469598103934665603ULL;
while (*s) h = (h ^ (unsigned char) *s++) * 1099511628211ULL;
return h;
}
static void wtab_grow (void);
static int word_id (const char *name) {
size_t i = fnv(name) & wmask;
while (wtab[i] >= 0) {
if (!strcmp(words[wtab[i]].name, name)) return wtab[i];
i = (i + 1) & wmask;
}
if (nwords == capwords) { capwords *= 2; words = realloc(words, sizeof(word_t) * capwords); }
words[nwords].name = strdup(name);
words[nwords].count = 0;
wtab[i] = nwords++;
if ((size_t) nwords * 2 > wmask) wtab_grow();
return nwords - 1;
}
static void wtab_grow (void) {
wmask = wmask * 2 + 1;
free(wtab);
wtab = malloc(sizeof(int) * (wmask + 1));
for (size_t i = 0; i <= wmask; i++) wtab[i] = -1;
for (int w = 0; w < nwords; w++) {
size_t i = fnv(words[w].name) & wmask;
while (wtab[i] >= 0) i = (i + 1) & wmask;
wtab[i] = w;
}
}
// ---------------------------------------------------------------- pairs
typedef struct { int l, r; double n; } pair_t;
static pair_t *pairs;
static int npairs, cappairs;
static int *ptab;
static size_t pmask;
static uint64_t pair_hash (int l, int r) { return ((uint64_t) l * 0x9e3779b97f4a7c15ULL) ^ ((uint64_t) r * 0xbf58476d1ce4e5b9ULL); }
static void ptab_grow (void) {
pmask = pmask * 2 + 1;
free(ptab);
ptab = malloc(sizeof(int) * (pmask + 1));
for (size_t i = 0; i <= pmask; i++) ptab[i] = -1;
for (int k = 0; k < npairs; k++) {
size_t i = pair_hash(pairs[k].l, pairs[k].r) & pmask;
while (ptab[i] >= 0) i = (i + 1) & pmask;
ptab[i] = k;
}
}
static void pair_inc (int l, int r) {
size_t i = pair_hash(l, r) & pmask;
while (ptab[i] >= 0) {
pair_t *p = &pairs[ptab[i]];
if (p->l == l && p->r == r) { p->n += 1; return; }
i = (i + 1) & pmask;
}
if (npairs == cappairs) { cappairs *= 2; pairs = realloc(pairs, sizeof(pair_t) * cappairs); }
pairs[npairs] = (pair_t) { l, r, 1 };
ptab[i] = npairs++;
if ((size_t) npairs * 2 > pmask) ptab_grow();
}
// ---------------------------------------------------------------- input
// Copies the k-th quoted name (k = 0, 1) of an atom string into out. Returns 0 if absent.
static int quoted (const char *s, int k, char *out, size_t cap) {
for (int q = 0; q <= k; q++) {
s = strstr(s, "(WordNode \"");
if (!s) return 0;
s += 11;
if (q < k) continue;
const char *e = strstr(s, "\")");
if (!e || (size_t) (e - s) >= cap) return 0;
memcpy(out, s, e - s);
out[e - s] = 0;
}
return 1;
}
static void read_parses (const char *path) {
FILE *f = fopen(path, "r");
if (!f) { perror(path); exit(1); }
char line[4096], a[1024], b[1024];
long nline = 0;
while (fgets(line, sizeof line, f)) {
nline++;
char *atom = strchr(line, '\t');
if (atom) atom = strchr(atom + 1, '\t');
if (!atom) { fprintf(stderr, "%s:%ld: malformed\n", path, nline); exit(1); }
atom++;
if (!strncmp(atom, "(WordNode ", 10)) {
if (!quoted(atom, 0, a, sizeof a)) { fprintf(stderr, "%s:%ld: bad word\n", path, nline); exit(1); }
words[word_id(a)].count += 1;
} else if (!strncmp(atom, "(EdgeLink (BondNode \"ANY\") (ListLink (WordNode ", 47)) {
if (!quoted(atom, 0, a, sizeof a) || !quoted(atom, 1, b, sizeof b)) {
fprintf(stderr, "%s:%ld: bad edge\n", path, nline);
exit(1);
}
int l = word_id(a), r = word_id(b);
pair_inc(l, r);
} else {
fprintf(stderr, "%s:%ld: unexpected atom\n", path, nline);
exit(1);
}
}
fclose(f);
}
// ---------------------------------------------------------------- MI (batch-all-pair-mi)
typedef struct { double l0, l1, l2, lq, su; } norms_t;
static void norm_add (norms_t *m, double n) { m->l0 += 1; m->l1 += fabs(n); m->l2 += n * n; m->lq += sqrt(fabs(n)); m->su += n; }
static double nlog2 (double p) { return -1.4426950408889634 * log(p); } // frequency.scm set-freq
static void put (const char *atom, const char *key, int nv, const double *v) {
printf("%s\t(PredicateNode \"%s\")\t", atom, key);
for (int k = 0; k < nv; k++) printf(k ? " %.17g" : "%.17g", v[k]);
printf("\n");
}
static void freq3 (double p, double *v) {
double ln2 = nlog2(p);
v[0] = p; v[1] = ln2; v[2] = isfinite(ln2) ? p * ln2 : 0;
}
int main (int argc, char **argv) {
if (argc != 2) { fprintf(stderr, "usage: pairmi <parses.tsv>\n"); return 1; }
capwords = 1024; words = malloc(sizeof(word_t) * capwords);
wmask = 2047; wtab = malloc(sizeof(int) * (wmask + 1));
for (size_t i = 0; i <= wmask; i++) wtab[i] = -1;
cappairs = 4096; pairs = malloc(sizeof(pair_t) * cappairs);
pmask = 8191; ptab = malloc(sizeof(int) * (pmask + 1));
for (size_t i = 0; i <= pmask; i++) ptab[i] = -1;
read_parses(argv[1]);
char atom[4096];
double v[5];
for (int w = 0; w < nwords; w++) {
snprintf(atom, sizeof atom, "(WordNode \"%s\")", words[w].name);
v[0] = 0; v[1] = 0; v[2] = words[w].count;
put(atom, "*-TruthValueKey-*", 3, v);
}
// support.scm: marginals. right(x) = row x = N(x,*), stored on (x, right-word); left(y) on (left-word, y).
norms_t *right = calloc(nwords, sizeof(norms_t)), *left = calloc(nwords, sizeof(norms_t));
for (int k = 0; k < npairs; k++) { norm_add(&right[pairs[k].l], pairs[k].n); norm_add(&left[pairs[k].r], pairs[k].n); }
double tot_l0 = 0, tot_l1 = 0, tot_su = 0, tor_l0 = 0, tor_l1 = 0, tor_su = 0;
int nleft = 0, nright = 0;
for (int w = 0; w < nwords; w++) {
if (right[w].l0 > 0) { nleft++; tot_l0 += right[w].l0; tot_l1 += right[w].l1; tot_su += right[w].su; }
if (left[w].l0 > 0) { nright++; tor_l0 += left[w].l0; tor_l1 += left[w].l1; tor_su += left[w].su; }
}
const char *ww = "(EdgeLink (BondNode \"ANY\") (ListLink (AnyNode \"left-word\") (AnyNode \"right-word\")))";
v[0] = tot_l0; v[1] = tot_l1; v[2] = tot_su; put(ww, "*-Left Total Key-*", 3, v);
v[0] = tor_l0; v[1] = tor_l1; v[2] = tor_su; put(ww, "*-Right Total Key-*", 3, v);
v[0] = nleft; v[1] = nright; v[2] = npairs; put(ww, "*-Supp Dimension Key-*", 3, v);
// frequency.scm: tot = total-sum-left; marginal frequencies use the l1 count ('left-count / 'right-count).
double tot = tot_su;
double *rlogli = malloc(sizeof(double) * nwords), *llogli = malloc(sizeof(double) * nwords);
double *rfreq = malloc(sizeof(double) * nwords), *lfreq = malloc(sizeof(double) * nwords);
for (int w = 0; w < nwords; w++) {
rfreq[w] = right[w].l1 / tot; rlogli[w] = nlog2(rfreq[w]);
lfreq[w] = left[w].l1 / tot; llogli[w] = nlog2(lfreq[w]);
}
// compute-mi.scm: per pair. entropy.scm: per-marginal sums of pair entropy and pair mi.
double *rent = calloc(nwords, sizeof(double)), *lent = calloc(nwords, sizeof(double));
double *rmi = calloc(nwords, sizeof(double)), *lmi = calloc(nwords, sizeof(double));
for (int k = 0; k < npairs; k++) {
pair_t *p = &pairs[k];
snprintf(atom, sizeof atom, "(EdgeLink (BondNode \"ANY\") (ListLink (WordNode \"%s\") (WordNode \"%s\")))",
words[p->l].name, words[p->r].name);
v[0] = 0; v[1] = 0; v[2] = p->n;
put(atom, "*-TruthValueKey-*", 3, v);
double f[3];
freq3(p->n / tot, f);
put(atom, "*-FrequencyKey-*", 3, f);
double fmi = (rlogli[p->l] + llogli[p->r]) - f[1], mi = f[0] * fmi;
v[0] = mi; v[1] = fmi;
put(atom, "*-Mutual Info Key-*", 2, v);
rent[p->l] += f[2]; lent[p->r] += f[2];
if (isfinite(mi)) { rmi[p->l] += mi; lmi[p->r] += mi; }
}
double hl = 0, hr = 0, htot_l = 0, htot_r = 0, mitot_l = 0, mitot_r = 0;
for (int w = 0; w < nwords; w++) {
if (right[w].l0 > 0) {
snprintf(atom, sizeof atom, "(EdgeLink (BondNode \"ANY\") (ListLink (WordNode \"%s\") (AnyNode \"right-word\")))", words[w].name);
v[0] = right[w].l0; v[1] = right[w].l1; v[2] = sqrt(right[w].l2); v[3] = right[w].lq * right[w].lq; v[4] = right[w].su;
put(atom, "*-Norm Key-*", 5, v);
double f[3];
freq3(rfreq[w], f);
put(atom, "*-FrequencyKey-*", 3, f);
v[0] = rent[w]; v[1] = rent[w] / rfreq[w]; put(atom, "*-Entropy Key-*", 2, v);
v[0] = rmi[w]; v[1] = rmi[w] / rfreq[w]; put(atom, "*-Mutual Info Key-*", 2, v);
if (isfinite(rlogli[w])) hr += rfreq[w] * rlogli[w];
htot_r += rent[w]; mitot_r += rmi[w];
}
if (left[w].l0 > 0) {
snprintf(atom, sizeof atom, "(EdgeLink (BondNode \"ANY\") (ListLink (AnyNode \"left-word\") (WordNode \"%s\")))", words[w].name);
v[0] = left[w].l0; v[1] = left[w].l1; v[2] = sqrt(left[w].l2); v[3] = left[w].lq * left[w].lq; v[4] = left[w].su;
put(atom, "*-Norm Key-*", 5, v);
double f[3];
freq3(lfreq[w], f);
put(atom, "*-FrequencyKey-*", 3, f);
v[0] = lent[w]; v[1] = lent[w] / lfreq[w]; put(atom, "*-Entropy Key-*", 2, v);
v[0] = lmi[w]; v[1] = lmi[w] / lfreq[w]; put(atom, "*-Mutual Info Key-*", 2, v);
if (isfinite(llogli[w])) hl += lfreq[w] * llogli[w];
htot_l += lent[w]; mitot_l += lmi[w];
}
}
// entropy.scm: total entropy and MI are the left sums; the right sums must agree to 1e-8.
if (fabs(htot_l - htot_r) / htot_l > 1e-8 || fabs(mitot_l - mitot_r) / mitot_l > 1e-8) {
fprintf(stderr, "left/right totals disagree: H %g %g MI %g %g\n", htot_l, htot_r, mitot_l, mitot_r);
return 2;
}
v[0] = hl; v[1] = hr; v[2] = htot_l; put(ww, "*-Total Entropy Key-*", 3, v);
v[0] = mitot_l; put(ww, "*-Total MI Key-*", 1, v);
return 0;
}