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

package detect

// Clip is a decoded window of one episode's audio, and where that window sits in the episode.
type Clip struct {
	EpisodeID  string
	Samples    []float64
	SampleRate int
	StartMs    int64
}

// Occurrence is where a recurring segment was found in one episode's clip.
type Occurrence struct {
	EpisodeID string
	Position  int // samples into the clip
	Score     float64
}

// Recurring is a segment found in enough episodes to be trusted, and where it sits in each.
type Recurring struct {
	Reference   []float64
	Occurrences []Occurrence
}

// Tuning is what the search is allowed to cost, plus the score a match must clear.
//
// MinScore and the confirmation threshold are safety mechanisms, not performance knobs: the
// threshold is the only thing standing between "the show's intro" and "an ad that happened to
// be inserted into two episodes fetched minutes apart". Reachable for tests, not for operators.
type Tuning struct {
	// CoarseFactor shrinks both clips before ranking candidate positions. 1 searches at full
	// resolution, which is kept reachable so the fast path can be compared against it.
	CoarseFactor int
	// FineCandidates is how many ranked positions get verified at full resolution. Several,
	// for two reasons: decimation can reorder near-equal peaks, and one strongly-recurring
	// segment that is not the one wanted must not be able to crowd the shortlist.
	FineCandidates int
	// MinScore is the correlation a match must exceed to count as the same audio.
	MinScore float64
}

// DefaultTuning is the production configuration, matching the values validated on real shows.
func DefaultTuning() Tuning {
	return Tuning{CoarseFactor: 8, FineCandidates: 5, MinScore: 0.6}
}

// minCoarseWindow is the point below which a decimated window stops carrying enough signal to
// rank positions by, so the search runs at full resolution instead.
const minCoarseWindow = 512

// candidateStepDivisor makes the search step a quarter of the window.
//
// A step of a whole window would almost always straddle a real embedded segment rather than
// land on it: any embed position that is not a multiple of the window length gets split across
// two candidate windows, each only partly the real signal, and often too weak to clear
// MinScore.
const candidateStepDivisor = 4

// DetectRecurring finds a referenceLen-sample segment present in at least confirmThreshold of
// the clips, and reports where it sits in each clip that has it. Nil when nothing recurs widely
// enough to trust.
//
// This is the whole reason for doing detection on a server. On the phone only one episode's clip
// could be held at a time, so the same question had to be answered by a rolling state machine
// that carried a "pending" clip between runs, re-decoded it, accumulated a confirmation count
// over weeks, and lost everything whenever retention reclaimed the pending episode's file.
// Holding every clip at once replaces all of that with a single pass: the threshold is evaluated
// rather than accumulated.
//
// Costs one coarse window search plus FineCandidates*len(clips) full-resolution correlations --
// not a correlation per window per clip, which would be hundreds of times more work for the
// same answer.
func DetectRecurring(clips []Clip, referenceLen, confirmThreshold int, t Tuning) *Recurring {
	if len(clips) < confirmThreshold || confirmThreshold < 1 || referenceLen <= 0 {
		return nil
	}

	pivot := clips[0]
	win := referenceLen
	for _, c := range clips {
		if len(c.Samples) < win {
			return nil
		}
	}

	// Rank candidate positions in the pivot by how well they match the next clip. Cheap, and
	// only a shortlist -- which of them is real is decided below, against every clip.
	ranked := rankPositions(pivot.Samples, clips[1].Samples, win, t)

	var best *Recurring
	for _, position := range ranked {
		start := clampStart(position, len(pivot.Samples), win)
		reference := pivot.Samples[start : start+win]

		occurrences := locateInAll(reference, clips, t.MinScore)
		if len(occurrences) < confirmThreshold {
			continue
		}
		// Most support wins, not first found. A rotating ad shared by two episodes must lose to
		// an intro shared by all of them -- picking the first candidate over MinScore is how a
		// skip feature starts cutting advertising it happens to have seen twice and calling it
		// the theme tune.
		if best == nil || len(occurrences) > len(best.Occurrences) {
			best = &Recurring{
				Reference:   append([]float64(nil), reference...),
				Occurrences: occurrences,
			}
		}
	}
	return best
}

// rankPositions returns candidate window starts in a, best-matching first, in a's own
// resolution. No score threshold is applied: at a coarse resolution these scores are not the
// ones detection is allowed to decide on, so rejecting here would reject on a number the
// full-resolution pass is about to compute properly.
func rankPositions(a, b []float64, win int, t Tuning) []int {
	factor := coarseFactor(win, t.CoarseFactor)
	searchA, searchB, searchWin := a, b, win
	if factor > 1 {
		searchA, searchB, searchWin = Decimate(a, factor), Decimate(b, factor), win/factor
	}
	if searchWin <= 0 || searchWin > len(searchA) || searchWin > len(searchB) {
		return nil
	}

	step := searchWin / candidateStepDivisor
	if step < 1 {
		step = 1
	}
	target := PrepareTarget(searchB, searchWin)

	type scored struct {
		position int
		score    float64
	}
	var all []scored
	for start := 0; start+searchWin <= len(searchA); start += step {
		if m := BestMatchPrepared(searchA[start:start+searchWin], target); m != nil {
			all = append(all, scored{position: start * factor, score: m.Score})
		}
	}

	// Highest-scoring first, but one entry per distinct region of a.
	//
	// Without the spacing rule the shortlist fills with overlapping slices of whichever
	// segment scores best, and any other recurring segment never gets looked at. That is not
	// hypothetical: a rotating ad present in two episodes produced three near-identical
	// candidates covering itself, so the intro shared by all four was never evaluated and the
	// detector confirmed the ad. Candidates have to describe different audio, not the same
	// audio three times.
	keep := t.FineCandidates
	if keep < 1 {
		keep = 1
	}
	out := make([]int, 0, keep)
	used := make([]bool, len(all))
	for len(out) < keep {
		bestIdx := -1
		for i, s := range all {
			if used[i] {
				continue
			}
			if bestIdx < 0 || s.score > all[bestIdx].score {
				bestIdx = i
			}
		}
		if bestIdx < 0 {
			break
		}
		used[bestIdx] = true

		position := all[bestIdx].position
		if !separated(out, position, win) {
			continue
		}
		out = append(out, position)
	}
	return out
}

// separated reports whether position describes a different stretch of audio than everything
// already shortlisted.
func separated(chosen []int, position, spacing int) bool {
	for _, c := range chosen {
		d := c - position
		if d < 0 {
			d = -d
		}
		if d < spacing {
			return false
		}
	}
	return true
}

// locateInAll finds reference in every clip at full resolution, keeping those that clear
// minScore. This is where detection actually happens: every number the coarse pass produced is
// discarded and the decision is made on native-resolution audio.
func locateInAll(reference []float64, clips []Clip, minScore float64) []Occurrence {
	var found []Occurrence
	for _, c := range clips {
		m := BestMatch(reference, c.Samples)
		if m == nil || m.Score < minScore {
			continue
		}
		found = append(found, Occurrence{EpisodeID: c.EpisodeID, Position: m.Position, Score: m.Score})
	}
	return found
}

func coarseFactor(win, requested int) int {
	if requested < 2 {
		return 1
	}
	if win/requested < minCoarseWindow {
		return 1
	}
	return requested
}

func clampStart(position, length, win int) int {
	if position < 0 {
		return 0
	}
	if position > length-win {
		return length - win
	}
	return position
}