Como um algoritmo poderia se iterar em todas as combinações de duas variáveis para apontar para um determinado número de entradas?

5

Para informações básicas, consulte "Alguns antecedentes" mais abaixo.

Eu tenho uma lista assim:

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

Isso funciona junto com um arquivo wave, agindo como uma lista de corte. Assim, as partes desejadas são 1-> 2, 4 > 6, 12- > 15, ...

Se a distância entre o tempo final em segundos do elemento anterior e o tempo de início em segundos do elemento atual estiver abaixo de um limiar de segundos (chamo de Pausendauer ) I mesclar os dois, ou seja, se o limite é de 3 segundos, então a lista será

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

Se a distância entre a Hora de Início-In-Segundos e a Hora de Fim-de-Segundo estiver abaixo de um limiar de segundos (eu chamo de Minimallänge ) descarto esta amostra, ou seja, se o limite é de 4 segundos, então a lista será

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

Como um algoritmo poderia se iterar (inteligentemente) através de todas as combinações de Minimallänge e Pausendauer para apontar um certo número de entradas? Exemplo:

O número de entradas deve ser 3. Dado o número 3 o algoritmo deve iterar (inteligentemente) através de todas as combinações de Minimallänge e Pausendauer para produzir algo como isto:

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

E isso deveria ser tudo. Você notou que eu não adicionei "..." a ele, pois a lista final é composta apenas por três entradas.

Alguns antecedentes : O arquivo wave contém várias entrevistas sendo gravadas continuamente com pausas entre elas. Um VAD me deu áreas onde presume que a voz seja. Como eu sei o número total de conversas (f. I. 3, geralmente mais, é por isso que isso faz sentido), meu objetivo é determiná-las automaticamente. A lista de corte é a saída bruta do meu VAD que quero transformar em uma lista de corte utilizável para o ffmpeg.

PS : Se você puder, compartilhe um algoritmo em c #.

    
por user1505034 07.03.2013 / 13:12
fonte

3 respostas

1

Vamos considerar uma série de trechos de áudio separados por pausas, e deixar Li ser o tamanho do trecho i i e o bloco i + 1 . Então nós temos:

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

Se unirmos pedaços onde Pi < P , obteremos de um mínimo de 1 pedaço (quando P > = max (Pi)) até um máximo de N (quando P < min (Pi)).

Se rejeitarmos pedaços de comprimento menores que L, as pausas serão mescladas: descartando-se o fragmento Cj, a pausa entre C j-1 e C j +1 torna-se P j-1 + L j + P j e, portanto, o número de superchunks para qualquer dado P aumentar.

O número de pedaços para qualquer dado L irá então diminuir monotonicamente com o aumento de P, de um máximo de C L = número de pedaços maiores que L.

O resultado deve ser algo assim:

Assim,aáreadeinteresseseráemformadeL(nãonecessariamenteuma"célula" larga ou alta) e, vista de cima, poderia ter a seguinte aparência:

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

Assim, dado que uma "exploração" do array vai custar O (N), você pode começar com um valor adequado de (L, P), por ex. (0,0) e "andar" a matriz aumentando L até encontrar dois pontos, um acima, um abaixo (ou igual) para o limite desejado.

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

(Aqui, 0 ... 9, A..F são as iterações. Note que na iteração 6 você também verifica a célula "acima" do 6, como 4 está "acima" do 5, então eles custam o dobro) .

O custo diminui de O (L'P ') (onde L' é o comprimento máximo que você considera, P 'é a pausa máxima) para O (L' + P ').

Mas um grande clinch poderia ser, o que acontece se a pausa "intra-conversação" for mais longa do que a pausa "inter-conversação"?

Quero dizer, se o intervalo entre entrevistas for maior do que qualquer intervalo dentro das entrevistas, então todas as alternativas acima são redundantes: apenas procure as N pausas mais longas, e essas serão as pausas entre entrevistas.

O que acontece, por outro lado, se houver uma pausa "interna" maior que o espaço entre as entrevistas? Então, o algoritmo acima (na verdade, qualquer algoritmo baseado em comprimento que eu possa imaginar, a menos que a duração média de uma entrevista seja conhecida e confiável , e a pausa extra não esteja muito próxima do início ou fim da entrevista) escolherá essa pausa como um separador de entrevista, e o que for antes (ou depois) será atribuído à entrevista adjacente.

Para resolver esse problema, acho que você precisa fazer uma inspeção mais profunda, talvez classificando os fragmentos com base na distribuição de frequência. Você pode ainda atribuir erroneamente o primeiro ou último trecho do entrevistador, se é o mesmo em duas entrevistas adjacentes e não há um "roteiro" confiável (por exemplo, as entrevistas são sempre fechadas pelo entrevistador, 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.
    
por 24.05.2013 / 11:28
fonte
0

Acho que esta é uma questão interessante e não tenho a solução. No entanto, tenha paciência comigo, isso vai ser longo, e não uma implementação ou mesmo uma resposta (eu mereço a downmodding com antecedência), mas uma reformulação da pergunta com observações e observações adicionais para tentar condicionar o problema, o que pode levar você no caminho para encontrar uma implementação.

Observação: eu escrevi isso antes que a explicação do problema real fosse adicionada nos comentários, então isso pode ser genérico demais, mas eu ainda vou postá-lo.

Considere uma lista ordenada de trechos de tempo não sobrepostos com um horário de início e término (em que hora de término > hora de início).

Temos um determinado filtro com os parâmetros pause_threshold e minimal_length que, na ordem:

  1. Mescla todos os trechos de tempo t0 e t1, em que t1.starttime - t0.endtime < pause_threshold. Isso pode ser feito de uma só vez, as mesclagens não afetam a distância entre blocos de tempo mesclados.
  2. Descarta todos os blocos de tempo t0, em que t0.endtime - t0.starttime < minimum_length.
    Isso também pode ser feito em uma única passagem, mas estou assumindo aqui que isso deve ser feito depois da passagem de mesclagem, porque essa afeta definitivamente o período de tempo em pedaços.

A pergunta atual é : crie um algoritmo para o seguinte: Para uma determinada lista de tempo-pedaço finita L e contagem c, determine pause_threshold e minimal_length de tal forma que após as duas passagens a lista contenha exatamente c entradas.

Observações:

  1. Um limite superior válido para pause_threshold é ligeiramente maior que o maior tempo entre dois fragmentos de tempo adjacentes em L. Isso é fácil de ver: usar esse valor para o passo 1 do algoritmo mesclaria todos os fragmentos resultando em apenas uma entrada, que já é um exagero.
  2. O conjunto total de pause_thresholds a tentar é finito: é o conjunto de todas as distâncias únicas entre blocos de tempo em L.
  3. Da mesma forma, o parâmetro minimum_length também é ligado. Se você escolher um pouco maior que o comprimento do maior pedaço, todos os pedaços serão descartados, de modo que é um limite superior para o minimal_lengths para tentar. Um conjunto finito limitado de minimum_lengths para tentar é o conjunto de comprimentos de pedaços exclusivos em L mais 0 (o valor "sem descartes").

Agora você sabe que o problema está limitado - você pode simplesmente tentar todas as combinações possíveis dos dois conjuntos e ver se algum deles chega a uma solução (ou seja, o número de entradas na lista resultante após aplicar o filtro é igual a c ).

Esta análise não revela se uma resposta é sempre possível: é trivialmente fácil provar que não é o caso em geral: apenas considere uma lista inicial L com menos de c entradas.

Essa observação leva a outro ângulo de ataque ao algoritmo: o ataque indutivo.

  1. Se L tiver menos de c entradas, não há solução possível.
  2. Se L tiver entradas c, isso já é trivialmente correto, portanto você não deseja mesclar ou descartar. Uma solução válida (mas não exclusiva) é pause_threshold e minimum_length 0.
  3. Se L tiver n > Entradas c, então as entradas n-c terão que ser eliminadas através de fusão ou descarte. Uma mesclagem e descarte têm exatamente o mesmo efeito: eles reduzem o número de pedaços na lista em 1. Portanto, você precisa de fusões n-c, descarte n-c ou fusão n-c + descartes. É aí que se torna complicado, porque você pode não ter comprimentos de pausa exclusivos entre trechos nem comprimentos exclusivos de trechos (antes ou depois das mesclagens).

O motivo pelo qual fica complicado com comprimentos ou pausas não exclusivos é porque você não terá um mapeamento exclusivo de valores de limite para o número de itens eliminados. Por exemplo, considere uma lista de fragmentos com comprimentos [1 3 3 5 7]. Escolha o valor minimum_length 2 e você elimina 1 valor. Escolha 4 e você elimina 3. Não há nenhum valor que você possa escolher para eliminar apenas 2, então você não pode resolvê-lo apenas com descartes.

Vou ter que resumir aqui, mas espero que isso possa ser o começo de um trabalho comunitário construtivo em uma questão interessante!

    
por 07.03.2013 / 16:00
fonte
-1

Seja n o número de entradas na lista inicial.

Em seguida, há n-1 de intervalos entre entradas adjacentes. O Pausendauer determina quais lacunas estão fechadas e quais não estão, e então há no máximo n-1 possibilidades úteis para o Pausendauer (valores entre possibilidades "úteis" don ' t altere o conjunto de lacunas fechadas, para que elas não precisem ser testadas).

Após o passo Pausendauer fechar algumas lacunas, o Minimallänge descarta algum número de segmentos. Como temos um destino específico de segmentos de saída, o Minimallänge deve ser definido de modo a descartar todos, exceto k dos segmentos. Portanto, você pode encontrar Minimallänge simplesmente procurando pelo comprimento do maior segmento e definindo Minimallänge igual a esse, menos um. / p>

Portanto, temos um algoritmo que será executado no máximo em tempo O (n 2 log n): testa cada uma das possibilidades Pausendauer , e para cada < em> Pausendauer ele irá ordenar os segmentos por comprimento e encontrar o k th maior segmento para definir Minimallänge .

Observe que isso significa que, para qualquer Pausendauer , há sempre um Minimallänge que produz o número desejado de saídas (ignorando os empates) . Portanto, você pode querer aplicar uma restrição adicional para minimizar os parâmetros, por ex. para encontrar a solução (P, M) que minimiza P + M , ou algo assim.

O 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
    
por 07.03.2013 / 18:22
fonte

Tags