Testes automatizados para algoritmo de diferenciação

5

Estamos projetando um algoritmo de diferenciação (baseado na Subsequência Comum Mais Longa) que compara um texto de origem e uma cópia modificada para extrair o novo conteúdo (ou seja, conteúdo que está apenas na cópia modificada). Atualmente estou compilando uma biblioteca de dados de casos de teste.

Precisamos ser capazes de executar testes automatizados que verificam os casos de teste, mas não queremos verificar a precisão estrita. Dada a natureza heurística do nosso algoritmo, precisamos que o nosso teste / falha seja confuso. Queremos especificar um limite de sobreposição entre o resultado desejado e o resultado real (ou seja, o conteúdo extraído).

Eu tenho alguns esboços em minha mente sobre como resolver isso, mas alguém já fez isso antes? Alguém tem orientação ou idéias sobre como fazer isso efetivamente?

    
por Matthew Rodatus 09.07.2012 / 16:59
fonte

2 respostas

1

Parece que você tem uma restrição rígida para produzir um conjunto correto de diferenças e uma meta para produzir um conjunto mínimo de diferenças.

Para verificar a restrição, você precisa mesclar as diferenças em uma das entradas e ver se obtém a outra entrada. Felizmente, isso já foi feito. Tudo o que você precisa fazer é mostrar as diferenças no formato esperado pelo patch GNU.

Para testar o segundo, você só precisa garantir que a saída não esteja ficando inaceitavelmente grande. Como você pode alterar o programa de modo que um conjunto de diferenças fique menor enquanto outro se torna maior, cabe a você definir uma medida de bondade e um limite de aceitabilidade.

    
por 09.07.2012 / 18:09
fonte
1

Como @kevin cline apontou, existem duas restrições diferentes. Eu chamarei estes a exatidão e as limitações da eficiência.

A verificação da restrição de precisão deve ser simples. Basicamente, tudo que você precisa fazer é testar se pode recriar os dados originais. Isso deve ser fácil, pois você pode usar ferramentas como o Patch, como o kevin sugere.

Mas a restrição de eficiência é mais complicada. Eu acho que definir um limite é uma má ideia. Suponha que você defina os limites com 10% de redução no desempenho atual dos algoritmos.

  1. O que acontece se a eficiência do algoritmo cair 1% como resultado de uma alteração? Seus testes não vão falar sobre isso.
  2. E se a eficiência do algoritmo aumentar em 1%, você perceberá?
  3. O que acontece se o algoritmo for melhorado em 20% e, em seguida, degradado em 10%, você ainda estará bem acima de seus limites iniciais, portanto, o teste não ajudará você.

O problema é que as restrições de eficiência não são uma preocupação de aprovação / reprovação. Tentar forçá-lo a um teste de aprovação / reprovação com um limite não é uma boa ideia.

Acho que você deveria tratar isso como um teste de desempenho. Para cada revisão, execute todos os testes e colete os dados de eficiência. Plote todos os dados em um gráfico mostrando a eficiência em mudança com diferentes revisões. Sempre que a eficiência de um teste diminuir, envie automaticamente um e-mail para alguém que possa decidir se é aceitável ou não.

    
por 09.07.2012 / 19:58
fonte