degauss

/** Shannon entropy of a probability distribution (bits).
 *  H(X) = -Σ p(x) log₂ p(x)
 *  Returns 0 for empty or degenerate distributions. */
export function shannonEntropy(probs: number[]): number {
  let h = 0;
  for (const p of probs) {
    if (p > 0 && p <= 1) h -= p * Math.log(p) / LN2;
  }
  return h;
}

/** Self-information (surprisal) of a specific value.
 *  I(x) = -log₂ p(x)
 *  A name shared by 1 in 10,000: ~13.3 bits.
 *  A name shared by 1 in 10: ~3.3 bits. */
export function selfInfo(frequency: number): number {
  if (frequency <= 0 || frequency >= 1) return 0;
  return -Math.log(frequency) / LN2;
}

/** Compute the Fellegi-Sunter linkage weight for a single field. */
export function fieldWeight(
  field: QIField,
  agrees: boolean,
  uOverride?: number
): FieldComparison {
  const m = M_PROB[field] ?? M_PROB.other;
  const u = uOverride ?? estimateFrequency(field);

  let weight: number;
  if (agrees) {
    // w(agree) = log₂(m / u)
    // agreement on a rare field gives a high positive weight
    weight = Math.log2(m / Math.max(u, 1e-15));
  } else {
    // w(disagree) = log₂((1-m) / (1-u))
    weight = Math.log2((1 - m) / Math.max(1 - u, 1e-15));
  }

  return { field, agrees, weight, mProb: m, uProb: u };
}

/** Greedy removal ordering: sort by bits/difficulty.
 *
 *  If the exposure function is submodular (diminishing returns),
 *  greedy achieves (1-1/e) ≈ 63% of optimal.
 *  Submodularity is NOT proven here — the guarantee is aspirational.
 *  Krause & Golovin, "Submodular Function Maximization" (2014). */
export function greedyRemovalOrder(
  attributes: Array<{ bits: number; difficulty: number }>
): number[] {
  const indices = attributes.map((_, i) => i);
  indices.sort((a, b) => {
    const effA = attributes[a].bits / Math.max(attributes[a].difficulty, 0.01);
    const effB = attributes[b].bits / Math.max(attributes[b].difficulty, 0.01);
    return effB - effA;
  });
  return indices;
}