1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
package transcript
import (
"sort"
"strings"
"unicode"
)
/*
Finding the advertising by subtraction.
A publisher's transcript describes the ad-free master. Speech recognition over the mirrored file
describes the copy the phone will play. The copy is the master with advertising stitched into
it, so the text present in the served copy and absent from the master *is* the advertising, with
its own boundaries.
This is a measurement rather than a guess, which makes it different in kind from everything else
in this project. The audio scan infers advertising from what several episodes share and checks
itself against the declared-versus-served length gap; the phrase spotter infers it from ad copy
and checks itself against nothing. This one derives the answer from two independent descriptions
of the same recording.
It needs both halves, which is why a declined publisher transcript is kept rather than thrown
away. Declined means "this copy carries inserted advertising the master does not describe" --
precisely the episode this works on.
*/
// SignalDifference marks a candidate found by subtracting the master from the served copy,
// rather than by reading ad copy. Carried so one episode's candidates can come from either
// detector and still be told apart.
const SignalDifference = "difference"
const (
// anchorWords is how long a matching run must be to anchor the two texts together.
// Five: long enough that an ordinary phrase does not match in several places, short enough
// that it still fits between two recognition errors. Recognition is approximate -- whisper
// writes "Bombus" for "Bombas" -- so a window containing a mistake simply fails to anchor
// and its neighbours carry the alignment instead.
anchorWords = 5
// minInsertedWords is the shortest stretch worth calling an advertisement. A publisher who
// trims a sentence, or recognition that drops a clause, leaves a gap of a few words;
// skipping over one would clip the programme. Forty words is about fifteen seconds of
// speech, the same floor the phrase spotter uses and the same ad unit the length-gap rule
// uses.
minInsertedWords = 40
)
// token is one word of a transcript and where it was said.
type token struct {
word string
startMs int64
endMs int64
}
// Inserted reports the stretches of the served copy that the master does not contain.
//
// Returns nothing when either side is missing: there is nothing to subtract, which is a
// different answer from "no advertising" and the caller sees it as the absence of candidates
// either way. The episode record says which of the two it is.
func Inserted(master, served []Cue) []Candidate {
masterWords := tokenise(master)
servedWords := tokenise(served)
if len(masterWords) < anchorWords || len(servedWords) < anchorWords {
return nil
}
anchors := alignment(masterWords, servedWords)
// Walk the gaps between consecutive anchors, including the ones at each end. A gap where
// the served copy advanced a long way and the master did not is inserted content.
// An anchor names the start of a run of [anchorWords] matching words, so the content
// between two anchors begins after the first one's run ends, not after its first word.
// Getting this wrong puts the start of every break one anchor-length early, which on a real
// episode is a skip over the last sentence of the programme.
var found []Candidate
previous := anchor{master: -anchorWords, served: -anchorWords}
for _, next := range append(anchors, anchor{master: len(masterWords), served: len(servedWords)}) {
servedFrom := previous.served + anchorWords
masterFrom := previous.master + anchorWords
servedGap := next.served - servedFrom
masterGap := next.master - masterFrom
if servedGap-masterGap >= minInsertedWords && servedFrom < len(servedWords) {
from := servedWords[servedFrom]
to := servedWords[next.served-1]
found = append(found, Candidate{
StartMs: from.startMs,
EndMs: to.endMs,
Signals: []string{SignalDifference},
})
}
previous = next
}
// Every gap is then partitioned line by line against the master, which is what decides
// where within it the advertising actually is. See [Trimmed].
return trimmed(found, master, served)
}
// anchor ties a position in the master to the position in the served copy saying the same words.
type anchor struct{ master, served int }
/*
alignment finds where the two texts agree.
Anchored on runs of [anchorWords] words that occur exactly once in each text. Uniqueness is what
makes an anchor trustworthy: a phrase appearing twice in the master cannot say which occurrence
a served phrase matches, and a wrong anchor drags the alignment across a break. Inside an
advertisement there are no matching runs at all, which is what makes a pod show up as a gap.
The anchors are then reduced to the longest increasing run, because a handful will still be
spurious -- a stock phrase the publisher and an advertiser both used -- and those point
backwards.
*/
func alignment(masterWords, servedWords []token) []anchor {
masterRuns := uniqueRuns(masterWords)
servedRuns := uniqueRuns(servedWords)
var anchors []anchor
for run, servedAt := range servedRuns {
if masterAt, ok := masterRuns[run]; ok {
anchors = append(anchors, anchor{master: masterAt, served: servedAt})
}
}
sort.Slice(anchors, func(i, j int) bool { return anchors[i].served < anchors[j].served })
return longestIncreasing(anchors)
}
// uniqueRuns maps every run of [anchorWords] words that occurs exactly once to where it starts.
func uniqueRuns(words []token) map[string]int {
seen := make(map[string]int, len(words))
repeated := make(map[string]bool)
for i := 0; i+anchorWords <= len(words); i++ {
parts := make([]string, anchorWords)
for j := 0; j < anchorWords; j++ {
parts[j] = words[i+j].word
}
run := strings.Join(parts, " ")
if _, ok := seen[run]; ok {
repeated[run] = true
continue
}
seen[run] = i
}
for run := range repeated {
delete(seen, run)
}
return seen
}
// longestIncreasing keeps the longest run of anchors whose master positions increase, dropping
// the ones that would have the alignment going backwards.
func longestIncreasing(anchors []anchor) []anchor {
if len(anchors) == 0 {
return nil
}
// Patience sorting: tails[k] is the index of the anchor ending the best run of length k+1.
var tails []int
previous := make([]int, len(anchors))
for i, a := range anchors {
previous[i] = -1
at := sort.Search(len(tails), func(k int) bool {
return anchors[tails[k]].master >= a.master
})
if at > 0 {
previous[i] = tails[at-1]
}
if at == len(tails) {
tails = append(tails, i)
} else {
tails[at] = i
}
}
out := make([]anchor, 0, len(tails))
for i := tails[len(tails)-1]; i >= 0; i = previous[i] {
out = append(out, anchors[i])
}
for left, right := 0, len(out)-1; left < right; left, right = left+1, right-1 {
out[left], out[right] = out[right], out[left]
}
return out
}
// tokenise splits cues into comparable words, each carrying the time of the cue it came from.
//
// Case and punctuation are dropped because they are exactly what differs between a publisher's
// written transcript and a machine's reading of the same speech, and neither carries meaning
// for matching.
func tokenise(cues []Cue) []token {
var out []token
for _, cue := range cues {
for _, word := range strings.FieldsFunc(strings.ToLower(cue.Text), notWord) {
out = append(out, token{word: word, startMs: cue.StartMs, endMs: cue.EndMs})
}
}
return out
}
func notWord(r rune) bool { return !unicode.IsLetter(r) && !unicode.IsDigit(r) }
|
