What could an algorithm look like that iterates through all combinations of two variables to aim at a certain number of entries?

For background information, see “Some background” further down.

I have a list that looks like this:

Start-Time-In-Seconds;End-Time-In-Seconds
1;2
4;6
12;15
...

This works together with a wave file by acting as a cutlist. So the desired parts are 1->2, 4->6, 12->15, …

If the distance between End-Time-In-Seconds of the previous element and Start-Time-In-Seconds of the current element is below a threshold of seconds(I call it Pausendauer) I merge those two, ie if the threshold is 3 seconds then the list will be

Start-Time-In-Seconds;End-Time-In-Seconds
1;6
12;15
...

If the distance between Start-Time-In-Seconds and End-Time-In-Seconds is below a threshold of seconds(I call it Minimallänge) I discard this sample, ie if the threshold is 4 seconds then the list will be

Start-Time-In-Seconds;End-Time-In-Seconds
1;6
...

What could an algorithm look like that iterates (intelligently) through all combinations of Minimallänge and Pausendauer to aim at a certain number of entries? Example:

The number of entries should be 3. Given the number 3 the algorithm should iterate (intelligently) through all combinations of Minimallänge and Pausendauer to output something like this:

Start-Time-In-Seconds;End-Time-In-Seconds
1;12
18;20
50;100

And that should be all. You notice I did not add “…” to it as the final list is to only consist of three entries.

Some background: The wave file contains several interviews being recorded continuously with pauses in between. A VAD gave me areas where it presumes voice to be. As I know the number of total conversations(f.i. 3, usually more which is why this makes sense) my goal is to determine them automatically. The cutlist is the raw output of my VAD which I want to turn into a usable cutlist for ffmpeg.

PS: If you can, share an algorithm in c#.

Let us consider a series of audio chunks separated by pauses, and let Li be the length of chunk i, and Pi the pause between chunk i and chunk i+1. So we have:

[ chunk 0, L0 = 15s ]..(P0 s of silence)..[ chunk 1, L1 = 7s ]...

If we merge chunks wherever Pi < P, we will get from a minimum of 1 chunk (when P >= max(Pi) ) to a maximum of N (when P < min(Pi)).

If we reject chunks of length less than L, the pauses will merge: by discarding chunk Cj, the pause between Cj-1 and Cj+1 becomes Pj-1+Lj+Pj, and therefore the number of superchunks for any given P will increase.

The number of chunks for any given L will then monotonically decrease with increasing P, from a maximum of CL = number of chunks longer than L.

The result should be something like this:

So the area of interest will be sort of L-shaped (not necessarily one “cell” wide or tall), and seen from above, it could look like this:

#
##
###
###
#######
  ########
    #########

So, given that one “exploration” of the array is going to cost O(N), you could start with a suitable value of (L,P), e.g. (0,0) and “walk” the array increasing L until you meet two points, one above, one below (or equal) to the desired threshold.

#         0
##        1
###       2
###       3
######A   4
  ####98765
    #######

(Here, 0…9,A..F are the iterations. Note that at iteration 6 you also check the cell “above” the 6, as 4 is “above” the 5, so they cost double).

The cost decreases from O(L’P’) (where L’ is the maximum length you consider, P’ is the maximum pause) to O(L’+P’).

But a major clinch could be, what happens if the “intra-conversation” pause is longer than the “inter-conversation” pause?

I mean, if the interval between interviews is longer than any interval within the interviews, then all of the above is redundant: just hunt for the N longer pauses, and those will be the pauses between interviews.

What happens on the other hand if there is one “internal” pause that is longer than the space between interviews? Then, the above algorithm (actually, any length-based algorithm I can think of, unless the average length of an interview is known and reliable, and the extra pause is not too near to the beginning or end of the interview) will choose that pause as an interview splitter, and whatever is before (or after) will be assigned to the adjacent interview.

To address this issue, I think that you need to do a deeper inspection, maybe classifying chunks based on frequency distribution. You might still misattribute the first or last interviewer’s chunk, if it is the same in two adjacent interviews and there’s no reliable “script” (e.g. the interviews are always closed by the interviewer, etc.).:

<male voice> And that's all.

[ 3 seconds ]

<female voice> Very well.. then, thank you, mr. Alpha.
[ 2 seconds ]
<female voice> Good morning, mr. Beta.
<male voice> Good morning.

I think this is an interesting question, and I don’t have the solution. However, bear with me, this is going to be long, and not an implementation or even an answer (I deserve the downmodding in advance) but a rephrasing of the question with additional remarks and observations to attempt to condition the problem, which may lead you on the path to finding an implementation.

Remark: I wrote this before the explanation of the actual problem was added in the comments, so this may be overly generic, but I’ll still post it.

Consider an ordered list of non-overlapping time chunks with a start and end time (where end time > start time).

We have a given filter with parameters pause_threshold and minimal_length that, in order:

Merges all time chunks t0 and t1 where t1.starttime – t0.endtime < pause_threshold.
This can be done in one pass, the merges do not affect the distance between merged time chunks.
Discards all time chunks t0 where t0.endtime – t0.starttime < minimal_length.
This also can be done in one pass, but I am assuming here that this must be done after the merge pass, because that one definitely affects the length of time chunks.

The actual question is: devise an algorithm for the following: For a given finite time-chunk list L and count c, determine pause_threshold and minimal_length such that after the two passes the list contains exactly c entries.

Observations:

A valid upper bound for pause_threshold is slightly larger than the largest time between two adjacent time chunks in L. This is easy to see: using this value for pass 1 of the algorithm would merge all the chunks resulting in only one entry, which is already overkill.
The total set of pause_thresholds to try is finite: it is the set of all unique distances between time chunks in L.
Similarly the minimal_length parameter is also bound. If you choose it as slightly larger than the length of the longest chunk, all chunks will be discarded, so that is an upper bound for the minimal_lengths to try. A bounded finite set of minimal_lengths to try is the set of unique chunk lengths in L plus 0 (the “no discards” value).

Now you know the problem is bound – you can simply try all possible combinations from the two sets and see if any of them arrive at a solution (i.e. the number of entries in the resulting list after applying the filter is equal to c).

This analysis does not reveal if an answer is always possible: it’s trivially easy to prove that it’s not the case in general: just consider a starting list L with fewer than c entries.

That observation leads to another angle of attack on the algorithm: the inductive attack.

If L has less than c entries, there is no solution possible.
If L has c entries it’s already trivially correct so you want no merges or discards. A valid (but not unique) solution is pause_threshold and minimal_length 0.
If L has n > c entries, then n-c entries will have to be eliminated either through merging or discarding. A merge and discard have exactly the same effect: they reduce the number of chunks in the list by 1. Therefore you need n-c merges, n-c discards, or n-c merges + discards. This is where it becomes tricky, because you may not have unique pause lengths between chunks, nor unique lengths of chunks (before or after merges).

The reason it gets tricky with non-unique lengths or pauses is because you won’t have a unique mapping of threshold values to the number of items eliminated. For example consider a chunk list with lengths [1 3 3 5 7]. Pick minimal_length value 2 and you eliminate 1 value. Pick 4 and you eliminate 3. There is no value you can pick to eliminate just 2, so you cannot solve it with discards alone.

…
I’m going to have to cut it short here, but I hope this can be the start of constructive community work on an interesting question!

Let n be the number of entries in the initial list.

Then, there are n-1 gaps between adjacent entries. The Pausendauer determines which gaps are closed and which ones are not, and so there are at most n-1 useful possibilities for the Pausendauer (values between “useful” possibilities don’t change the set of closed gaps, so they need not be tested).

After the Pausendauer step closes some number of gaps, the Minimallänge discards some number of segments. Because we have a specific target of output segments, Minimallänge must be set such that it discards all but k of the segments. Therefore, you can find Minimallänge simply by looking for the length of the k^th largest segment and setting Minimallänge equal to that, minus one.

Therefore, we have an algorithm that will run in at most O(n² log n) time: it tests each of the Pausendauer possibilities, and for each Pausendauer it will sort the segments by length and find the k^th largest segment to set Minimallänge.

Observe that this means that, for any Pausendauer, there is always a Minimallänge that produces the desired number of outputs (ignoring ties). Therefore, you may want to slap on an additional constraint to minimize the parameters, e.g. to find the solution (P, M) that minimizes P + M, or something like that.

The algorithm is:

Let A = input array of segments
Let gaps = []
for i in 1..n-1
    gaps[i] = A[i+1].start - A[i].end
end

sort gaps

for P in gaps
    Let A' = segment array after merging with Pausendauer = P
    sort A' by segment length (.end - .start), decreasing order
    Let M = A'[k].start - A'[k].end - 1
    # P, M is now a possible solution.
end

Filed under: softwareengineering - @ 17:05

Thẻ: algorithms, c++

Thiết kế website giá rẻ

Danh mục

What could an algorithm look like that iterates through all combinations of two variables to aim at a certain number of entries?