path: root/server/internal/detect/lags.go

package detect

import "math"

// minLagSeparation keeps the shortlist to one entry per shared segment.
//
// A real match spreads its energy over neighbouring lags, so without this a single
// advertisement fills every slot on the shortlist and the second one is never looked at.
const minLagSeparation = 64

type scoredLag struct {
	lag   int
	score float64
}

// BestLags shortlists the alignments at which a and b most strongly share audio.
//
// One cross-correlation over every lag, not a correlation per window position. That is the
// whole reason whole-episode scanning is possible: the sliding search it replaces cost a
// full-length correlation for each of 117 window positions -- 199 seconds for a 240-second
// clip, measured -- while this costs one FFT pair for the entire pair of recordings. A
// 70-minute episode decimated to 250Hz is three transforms of 2^22, about five seconds.
//
// A shortlist only. The scores here are unnormalised and favour loud or long overlaps, so they
// rank candidates and decide nothing: [MatchedRuns] establishes whether a lag means anything
// and how far the agreement actually extends.
//
// Lag is defined so that a[i] lines up with b[i-lag].
func BestLags(a, b []float64, keep int) []int {
	if len(a) == 0 || len(b) == 0 || keep < 1 {
		return nil
	}

	// Mean-centred, so two recordings that merely share a DC offset do not outscore two that
	// share actual audio.
	ca, cb := centred(a), centred(b)

	// Correlation is convolution with one input reversed.
	n := NextPowerOfTwo(len(ca) + len(cb))
	aRe := make([]float64, n)
	copy(aRe, ca)
	aIm := make([]float64, n)
	bRe := make([]float64, n)
	for i, v := range cb {
		bRe[len(cb)-1-i] = v
	}
	bIm := make([]float64, n)

	Transform(aRe, aIm, false)
	Transform(bRe, bIm, false)
	for i := 0; i < n; i++ {
		re := aRe[i]*bRe[i] - aIm[i]*bIm[i]
		im := aRe[i]*bIm[i] + aIm[i]*bRe[i]
		aRe[i], aIm[i] = re, im
	}
	Transform(aRe, aIm, true)

	// Index k of the convolution corresponds to lag k - (len(b) - 1).
	offset := len(cb) - 1
	best := make([]scoredLag, 0, keep)
	for k := 0; k < len(ca)+len(cb)-1; k++ {
		best = offer(best, scoredLag{lag: k - offset, score: math.Abs(aRe[k])}, keep)
	}

	// Strongest first, by insertion sort: the shortlist is a handful of entries.
	for i := 1; i < len(best); i++ {
		for j := i; j > 0 && best[j].score > best[j-1].score; j-- {
			best[j], best[j-1] = best[j-1], best[j]
		}
	}
	out := make([]int, 0, len(best))
	for _, s := range best {
		out = append(out, s.lag)
	}
	return out
}

// offer adds a candidate to the shortlist, keeping one entry per neighbourhood of lags and at
// most keep entries overall.
func offer(best []scoredLag, candidate scoredLag, keep int) []scoredLag {
	for i := range best {
		if abs(best[i].lag-candidate.lag) <= minLagSeparation {
			if candidate.score > best[i].score {
				best[i] = candidate
			}
			return best
		}
	}
	if len(best) < keep {
		return append(best, candidate)
	}
	weakest := 0
	for i := range best {
		if best[i].score < best[weakest].score {
			weakest = i
		}
	}
	if candidate.score > best[weakest].score {
		best[weakest] = candidate
	}
	return best
}

// Run is a stretch over which two recordings carry the same audio, in a's own sample positions.
type Run struct {
	StartA int
	EndA   int // exclusive
	// StartB is where the same audio begins in b.
	StartB int
	// Score is the weakest window correlation inside the run, so it describes the whole run
	// rather than its best moment.
	Score float64
}

// Length is the run's duration in samples.
func (r Run) Length() int { return r.EndA - r.StartA }

// RunOptions governs what counts as agreement.
type RunOptions struct {
	// WindowSamples is the granularity the comparison is made at.
	WindowSamples int
	// MinScore is the correlation a window must reach to count as the same audio.
	MinScore float64
	// MinRunSamples discards agreement too short to be a real inserted segment. Two
	// recordings will agree briefly by chance, and on silence they will agree completely.
	MinRunSamples int
}

// DefaultRunOptions is sized for audio decimated to 250Hz: one-second windows, and nothing
// shorter than twelve seconds taken seriously.
//
// Advertising comes in units of roughly fifteen seconds, grouped into pods with real programme
// between them. Below twelve the "agreement" is the detector matching itself by chance, not an
// advertisement: a real 38-minute episode produced 37 breaks against the old 1000-sample (4s)
// floor, 14 of them landing at *exactly* 4.0 seconds -- noise pinned at the floor, not findings.
// Episodes the feed proves carry advertising (served measurably longer than declared) have a
// median of 3 breaks each, never more than 7. Twelve rather than fifteen so a real 15-second ad
// whose correlation lapses briefly at one end still survives; both floors were measured against
// the declared-versus-served length gap and twelve scored better.
func DefaultRunOptions() RunOptions {
	return RunOptions{WindowSamples: 250, MinScore: 0.75, MinRunSamples: 3000}
}

// MatchedRuns reports the stretches over which a and b carry the same audio at the given lag.
//
// Direct, window by window, with no transform: once the alignment is known the comparison is a
// Pearson correlation over short windows, which is cheap and gives the extent of the agreement
// rather than only its strength. The extent is the point -- an advertisement has to be skipped
// in full, so where it stops matters as much as that it is there.
//
// Silent windows are not counted as agreement. Two recordings agree perfectly on silence, and
// treating that as shared audio would join unrelated segments across the gaps between them.
func MatchedRuns(a, b []float64, lag int, opts RunOptions) []Run {
	if opts.WindowSamples <= 0 || len(a) == 0 || len(b) == 0 {
		return nil
	}

	var runs []Run
	runStart := -1
	runScore := 1.0

	for start := 0; start+opts.WindowSamples <= len(a); start += opts.WindowSamples {
		bStart := start - lag
		score, ok := windowAgreement(a, b, start, bStart, opts.WindowSamples)

		if ok && score >= opts.MinScore {
			if runStart < 0 {
				runStart, runScore = start, score
			} else if score < runScore {
				runScore = score
			}
			continue
		}
		runs = closeRun(runs, runStart, start, lag, runScore, opts)
		runStart, runScore = -1, 1.0
	}
	end := (len(a) / opts.WindowSamples) * opts.WindowSamples
	return closeRun(runs, runStart, end, lag, runScore, opts)
}

func closeRun(runs []Run, runStart, end, lag int, score float64, opts RunOptions) []Run {
	if runStart < 0 || end-runStart < opts.MinRunSamples {
		return runs
	}
	return append(runs, Run{StartA: runStart, EndA: end, StartB: runStart - lag, Score: score})
}

// windowAgreement is the Pearson correlation of one aligned window, and whether it carries
// enough signal to mean anything.
func windowAgreement(a, b []float64, aStart, bStart, win int) (float64, bool) {
	if aStart < 0 || bStart < 0 || aStart+win > len(a) || bStart+win > len(b) {
		return 0, false
	}

	var sumA, sumB float64
	for i := 0; i < win; i++ {
		sumA += a[aStart+i]
		sumB += b[bStart+i]
	}
	meanA, meanB := sumA/float64(win), sumB/float64(win)

	var cov, varA, varB float64
	for i := 0; i < win; i++ {
		da, db := a[aStart+i]-meanA, b[bStart+i]-meanB
		cov += da * db
		varA += da * da
		varB += db * db
	}
	// Near-silence in either window: perfectly correlated and meaningless.
	if varA < silenceFloor || varB < silenceFloor {
		return 0, false
	}
	return cov / math.Sqrt(varA*varB), true
}

// silenceFloor is the variance below which a window carries no signal worth comparing. Scaled
// for 16-bit-derived samples, where ordinary speech sits in the hundreds.
const silenceFloor = 1e-6

func centred(x []float64) []float64 {
	mean := 0.0
	for _, v := range x {
		mean += v
	}
	mean /= float64(len(x))
	out := make([]float64, len(x))
	for i, v := range x {
		out[i] = v - mean
	}
	return out
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}