Come potrebbe apparire un algoritmo che itera su tutte le combinazioni di due variabili per mirare a un certo numero di voci?

Consideriamo una serie di blocchi audio separati da pause e lasciamo che sia Li la lunghezza del frammento i , e Pi la pausa tra il pezzo i e il frammento i + 1 . Quindi abbiamo:

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

Se uniamo chunks ovunque Pi < P , otterremo da un minimo di 1 chunk (quando P > = max (Pi)) a un massimo di N (quando P < min (Pi)).

Se rifiutiamo blocchi di lunghezza inferiore a L, le pause si uniranno: scartando il blocco Cj, la pausa tra C j-1 e C j +1 diventa P j-1 + L j + P j , e quindi il numero di superchunchi per ogni dato P sarà aumentare.

Il numero di pezzi per ogni L data diminuirà monotonicamente con P crescente, da un massimo di C L = numero di pezzi più lungo di L.

Il risultato dovrebbe essere qualcosa del tipo:

Quindil'areadiinteressesaràditipoaformadiL(nonnecessariamenteuna"cella" larga o alta), e vista dall'alto, potrebbe apparire come questa:

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

Quindi, dato che una "esplorazione" dell'array sta per costare O (N), potresti iniziare con un valore adeguato di (L, P), ad es. (0,0) e "cammina" la matrice aumentando L fino a quando non si incontrano due punti, uno sopra, uno sotto (o uguale) alla soglia desiderata.

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

(Qui, 0 ... 9, A..F sono le iterazioni. Si noti che con iterazione 6 si controlla anche la cella "sopra" il 6, poiché 4 è "sopra" il 5, quindi costano il doppio) .

Il costo diminuisce da O (L'P ') (dove L' è la lunghezza massima che consideri, P 'è la pausa massima) a O (L' + P ').

Ma potrebbe esserci un clou importante, che succede se la pausa "intra-conversazione" è più lunga della pausa "inter-conversazione"?

Voglio dire, se l'intervallo tra le interviste è più lungo di qualsiasi intervallo all'interno delle interviste, allora tutto quanto sopra è ridondante: basta cercare le pause N più lunghe e quelle saranno le pause tra interviste.

Che cosa succede d'altra parte se c'è una pausa "interna" che è più lunga dello spazio tra le interviste? Quindi, l'algoritmo di cui sopra (in realtà, qualsiasi algoritmo basato sulla lunghezza che riesco a pensare, a meno che la lunghezza media di un'intervista sia nota e affidabile , e la pausa extra non sia troppo vicina all'inizio o alla fine dell'intervista) sceglierà la pausa come splitter di intervista, e qualsiasi cosa sia prima (o dopo) sarà assegnata al colloquio adiacente.

Per risolvere questo problema, penso che sia necessario eseguire un'ispezione più approfondita, magari classificando blocchi in base alla distribuzione di frequenza. Potresti ancora attribuire erroneamente il primo o l'ultimo frammento dell'intervistatore, se è lo stesso in due interviste adiacenti e non c'è uno "script" affidabile (ad esempio, le interviste sono sempre chiuse dall'intervistatore, ecc.):

<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.

Penso che questa sia una domanda interessante e non ho la soluzione. Tuttavia, abbiate pazienza, questo sarà molto lungo, e non una implementazione o anche una risposta (meriterò il downmodding in anticipo) ma una riformulazione della domanda con ulteriori osservazioni e osservazioni per tentare di condizionare il problema, che potrebbe portare sulla strada per trovare un'implementazione.

Nota: l'ho scritto prima che la spiegazione del problema reale fosse aggiunta nei commenti, quindi potrebbe essere eccessivamente generica, ma la pubblicheremo comunque.

Considera un elenco ordinato di blocchi di tempo non sovrapposti con un'ora di inizio e di fine (in cui l'ora di fine > ora di inizio).

Abbiamo un determinato filtro con parametri pause_threshold e minimal_length che, in ordine:

1. Unisce tutti i blocchi di tempo t0 e t1 dove t1.starttime - t0.endtime < pause_threshold. Questo può essere fatto in un passaggio, le unioni non influenzano la distanza tra i blocchi di tempo uniti.
2. scarta tutti i blocchi di tempo t0 dove t0.endtime - t0.starttime < minimal_length.
   Anche questo può essere fatto in un solo passaggio, ma suppongo che questo debba essere fatto dopo il passaggio di fusione, perché quello influisce decisamente sul numero di blocchi di tempo.

La domanda effettiva è : escogita un algoritmo per quanto segue: Per una data lista di elementi di tempo L e conta c, determina threshold_threshold e minimum_length in modo tale che dopo i due passaggi l'elenco contenga esattamente c inserimenti.

Osservazioni:

1. Un limite superiore valido per pause_threshold è leggermente maggiore del tempo maggiore tra due blocchi di tempo adiacenti in L. È facile vedere: utilizzando questo valore per il passaggio 1 dell'algoritmo si uniscono tutti i blocchi risultanti in una sola voce, che è già eccessivo.
2. Il set totale di pause_threshold da provare è finito: è l'insieme di tutte le distanze uniche tra i blocchi di tempo in L.
3. Analogamente anche il parametro minimal_length è vincolato. Se la si sceglie come leggermente più grande della lunghezza del pezzo più lungo, tutti i blocchi verranno scartati, quindi si tratterà di un limite superiore per le lunghezze minime da provare. Un insieme limitato limitato di parti minime da provare è l'insieme di lunghezze del pezzo uniche in L più 0 (il valore "nessun scarto").

Ora sai che il problema è vincolato - puoi semplicemente provare tutte le possibili combinazioni dai due set e vedere se qualcuno di loro arriva ad una soluzione (cioè il numero di voci nella lista risultante dopo aver applicato il filtro è uguale a c ).

Questa analisi non rivela se una risposta è sempre possibile: è banalmente facile dimostrare che non è il caso in generale: basta considerare una lista di partenza L con meno di c voci.

Questa osservazione porta ad un altro angolo di attacco all'algoritmo: l'attacco induttivo.

1. Se L ha meno di c voci, non c'è soluzione possibile.
2. Se L ha delle voci c è già banalmente corretto, quindi non vuoi unire o eliminare. Una soluzione valida (ma non unica) è pause_threshold e minimum_length 0.
3. Se L ha n > le voci c, quindi le voci n-c dovranno essere eliminate attraverso la fusione o scartando. Unire e scartare hanno esattamente lo stesso effetto: riducono il numero di blocchi nella lista di 1. Quindi è necessario unire n-c, scarti n-c o n-c unisce + scarti. Qui è dove diventa complicato, perché potresti non avere lunghezze di pausa uniche tra chunk, né lunghezze univoche di blocchi (prima o dopo l'unione).

Il motivo per cui diventa complicato con lunghezze o pause non univoche è perché non si avrà una mappatura univoca dei valori soglia per il numero di elementi eliminati. Ad esempio, considera una lista di blocchi con lunghezze [1 3 3 5 7]. Scegli il valore minimo_length 2 ed elimini 1 valore. Scegli 4 ed elimina 3. Non c'è alcun valore che puoi scegliere per eliminare solo 2, quindi non puoi risolverlo con gli scarti da solo.

... Devo tagliarlo qui, ma spero che questo possa essere l'inizio di un lavoro costruttivo da parte della comunità su una domanda interessante!

Lascia che n sia il numero di voci nell'elenco iniziale.

Quindi, ci sono spazi vuoti n-1 tra le voci adiacenti. Pausendauer determina quali spazi sono chiusi e quali no, e quindi ci sono al massimo n-1 possibilità utili per Pausendauer (valori tra "utili" possibilità don " t modificare il set di spazi chiusi, quindi non è necessario testarli).

Dopo che il passaggio Pausendauer chiude un certo numero di spazi vuoti, Minimallänge scarta un certo numero di segmenti. Poiché abbiamo una destinazione specifica per i segmenti di output, Minimallänge deve essere impostato in modo tale da eliminare tutti tranne k dei segmenti. Pertanto, puoi trovare Minimallänge semplicemente cercando la lunghezza del segmento k ^th e impostando Minimallänge uguale a quello, meno uno.

Pertanto, abbiamo un algoritmo che verrà eseguito al massimo al tempo O (n ² log n): mette alla prova ciascuna delle possibilità Pausendauer e per ciascuna < em> Pausendauer ordinerà i segmenti per lunghezza e troverà il k ^th segmento più grande per impostare Minimallänge .

Osserva che questo significa che, per qualsiasi Pausendauer , c'è sempre un Minimallänge che produce il numero desiderato di output (ignorando i legami) . Pertanto, potresti voler eseguire uno slap su un vincolo aggiuntivo per ridurre al minimo i parametri, ad es. per trovare la soluzione (P, M) che riduce al minimo P + M , o qualcosa del genere.

L'algoritmo è:

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