Source code

// Groups articles from different outlets into events, then orders each event's
// coverage into a timeline.
//
// How grouping works, in plain terms: each headline (plus the start of its
// summary) becomes a set of meaningful words and names. Two stories belong to
// the same event when they share enough of those words and names and were
// published within two days of each other. Names count double, because "Senate"
// plus "Thune" plus "shutdown" is a stronger match than any common word.

const STOP = new Set(('a an and are as at be been but by for from has have he her his how i in into is it its of on or our over she so than that the their them they this to up was we were what when where which who why will with would you your after again all also any about against before being between both did does doing down during each few further here just more most new not now off once only other out own same says say said should some such then there these those through too under until very while again amid back can could may might must one two three first last year years week day today tuesday wednesday thursday friday saturday sunday monday news live update updates report reports video watch').split(' '));

// Words at the start of a headline are capitalized by style, not because they
// are names, so the first word is skipped when collecting names.
function namesIn(title) {
  const words = title.split(/\s+/);
  const names = new Set();
  for (let i = 1; i < words.length; i++) {
    const w = words[i].replace(/[^A-Za-z'\-]/g, '');
    if (/^[A-Z][a-zA-Z'\-]{2,}$/.test(w) && !STOP.has(w.toLowerCase())) names.add(stem(w.toLowerCase()));
  }
  return names;
}

function stem(w) {
  return w.replace(/'s$/, '').replace(/ies$/, 'y').replace(/(ss|x|sh|ch)es$/, '$1').replace(/(?<!s)s$/, '');
}

function wordsIn(text) {
  const set = new Set();
  for (const raw of text.toLowerCase().split(/[^a-z0-9'\-]+/)) {
    const w = raw.replace(/^['\-]+|['\-]+$/g, '');
    if (w.length >= 3 && !STOP.has(w) && !/^\d+$/.test(w)) set.add(stem(w));
  }
  return set;
}

function fingerprint(article) {
  const lead = (article.summary || '').split(/\s+/).slice(0, 30).join(' ');
  return { words: wordsIn(`${article.title} ${lead}`), names: namesIn(article.title) };
}

// Words that appear in a large share of political coverage. They still count,
// at half weight, but they do not count toward the two shared words.
const COMMON = new Set(['senate', 'house', 'bill', 'vote', 'voted', 'pass', 'passe', 'passed', 'congress', 'congressional', 'lawmaker', 'trump', 'biden', 'president', 'presidential', 'white', 'democrat', 'democratic', 'republican', 'gop', 'court', 'judge', 'state', 'federal', 'government', 'official', 'administration', 'election', 'campaign', 'law', 'plan', 'policy', 'american', 'america', 'nation', 'national', 'leader', 'party', 'sen', 'rep', 'gov', 'supreme', 'case', 'deal', 'order', 'executive', 'department', 'secretary', 'agency', 'public', 'million', 'billion', 'people', 'country', 'city', 'county']);

// Share of the smaller story's words that also appear in the other story.
// Using the smaller story keeps a long summary from diluting a strong match.
// At least two shared distinctive words are needed, so two short headlines that share
// one common word do not merge.
function similarity(a, b) {
  const weight = (k) => (COMMON.has(k) ? 0.5 : a.names.has(k) || b.names.has(k) ? 2 : 1);
  let shared = 0;
  let count = 0;
  for (const k of a.words) if (b.words.has(k)) { shared += weight(k); if (!COMMON.has(k)) count++; }
  if (count < 2) return 0;
  const size = (s) => [...s].reduce((n, k) => n + weight(k), 0);
  return shared / Math.min(size(a.words), size(b.words));
}

const WINDOW_MS = 48 * 3600 * 1000;

// articles: [{ title, link, summary, published, outletId }]
// returns events: [{ id, articles, outlets, firstAt, lastAt }]
function groupIntoEvents(articles, { threshold = 0.5 } = {}) {
  const dated = articles.filter((a) => a.published).sort((x, y) => x.published.localeCompare(y.published));
  const clusters = [];
  for (const art of dated) {
    const fp = fingerprint(art);
    const t = Date.parse(art.published);
    let best = null;
    let bestScore = 0;
    for (const c of clusters) {
      if (t - c.lastT > WINDOW_MS) continue;
      // Compare against each member and keep the strongest match, so a cluster
      // does not drift away from its own topic as it grows.
      for (const m of c.members) {
        const s = similarity(fp, m.fp);
        if (s > bestScore) { bestScore = s; best = c; }
      }
    }
    if (best && bestScore >= threshold) {
      best.members.push({ art, fp, link: bestScore });
      best.lastT = Math.max(best.lastT, t);
    } else {
      clusters.push({ members: [{ art, fp }], lastT: t });
    }
  }
  return clusters.map((c) => {
    const arts = c.members.map((m) => m.art);
    const outlets = [...new Set(arts.map((a) => a.outletId))];
    // Confidence: the weakest link that joined a report to the event (1 for a
    // single report). Low confidence marks events worth checking by hand.
    const links = c.members.slice(1).map((m) => m.link);
    const confidence = links.length ? Math.min(...links) : 1;
    return { id: eventId(arts[0]), articles: arts, outlets, firstAt: arts[0].published, lastAt: arts[arts.length - 1].published, confidence: Math.round(confidence * 100) / 100 };
  });
}

// A short, stable id taken from the first article, so an event keeps its link
// as long as its first article stays in the feed.
function eventId(first) {
  let h = 2166136261;
  const s = `${first.outletId}|${first.link}`;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 16777619); }
  return (h >>> 0).toString(36);
}

// Orders an event's coverage by publish time and works out who was first.
// Two reports less than a minute apart count as a tie.
function timeline(event) {
  const rows = [...event.articles].sort((a, b) => a.published.localeCompare(b.published));
  const t0 = Date.parse(rows[0].published);
  const firstOutlets = rows.filter((r) => Date.parse(r.published) - t0 < 60 * 1000).map((r) => r.outletId);
  const seen = new Set();
  return {
    first: [...new Set(firstOutlets)],
    rows: rows.map((r, i) => {
      const firstForOutlet = !seen.has(r.outletId);
      seen.add(r.outletId);
      return { ...r, order: i + 1, afterFirstMs: Date.parse(r.published) - t0, firstForOutlet };
    }),
  };
}

// Events that share names and words with this one but fell below the joining
// threshold within seven days: likely the same running story.
function relatedEvents(event, others, { min = 0.25, max = 0.5, days = 7 } = {}) {
  const fp = fingerprint(event.articles[0]);
  const t = Date.parse(event.firstAt);
  const out = [];
  for (const o of others) {
    if (o.id === event.id || Math.abs(Date.parse(o.firstAt) - t) > days * 86400000) continue;
    let best = 0;
    for (const a of o.articles.slice(0, 5)) best = Math.max(best, similarity(fp, fingerprint(a)));
    if (best >= min && best < max) out.push({ id: o.id, title: o.articles[0].title, score: best });
  }
  return out.sort((a, b) => b.score - a.score).slice(0, 5);
}

module.exports = { groupIntoEvents, timeline, similarity, fingerprint, wordsIn, namesIn, relatedEvents, WINDOW_MS };