Método simples para detectar com segurança o código no texto?

142

O Gmail tem esse recurso onde ele irá avisá-lo se você tentar enviar um e-mail que ele pense que possa ter um anexo.

Como o GMail detectou a string see the attached no email, mas nenhum anexo real, ele me avisa com uma caixa de diálogo OK / Cancelar quando clico no botão Enviar.

Temos um problema relacionado no Stack Overflow. Ou seja, quando um usuário insere uma postagem como esta :

my problem is I need to change the database but I don't won't to create 
a new connection. example:

DataSet dsMasterInfo = new DataSet();
Database db = DatabaseFactory.CreateDatabase("ConnectionString");
DbCommand dbCommand = db.GetStoredProcCommand("uspGetMasterName");

Este usuário não formatou o código como código!

Ou seja, eles não foram recuados por 4 espaços por Markdown, ou usam o botão de código (ou o atalho de teclado ctrl + k ) que faz isso para eles .

Assim, nosso sistema está aceitando muitas edições em que as pessoas precisam entrar e formatar manualmente o código para pessoas que, de alguma forma, não conseguem descobrir isso. Isso leva a muita dor de barriga . Melhoramos a ajuda do editor várias vezes, mas, além de dirigir até a casa do usuário e pressionar os botões corretos no teclado para eles, não sabemos o que fazer a seguir.

É por isso que estamos considerando um aviso de estilo do GMail no Google:

Did you mean to post code?

You wrote stuff that we think looks like code, but you didn't format it as code by indenting 4 spaces, using the toolbar code button or the ctrl+k code formatting command.

No entanto, apresentar esse aviso exige que detectemos a presença do que achamos que é um código não formatado em uma pergunta . O que é uma maneira simples e semi-confiável de fazer isso?

  • Por Markdown , o código é sempre recuado por 4 espaços ou dentro de backticks, portanto, qualquer coisa formatada corretamente pode ser descartada do verifique imediatamente.
  • Este é apenas um aviso e só será aplicado a usuários de baixa reputação que fizerem as primeiras perguntas (ou fornecerem as primeiras respostas), portanto, alguns falsos positivos são aceitáveis, contanto que sejam sobre 5% ou menos.
  • As perguntas sobre o Stack Overflow podem estar em qualquer idioma, embora possamos realisticamente limitar nosso cheque para, digamos, os "dez grandes" idiomas. Pela página de tags que seria C #, Java, PHP, JavaScript, Objective-C, C, C ++, Python, Ruby.
  • Use o despejo de dados do Creative Stack Overflow para auditar sua possível solução (ou simplesmente escolha um algumas perguntas nas 10 principais tags no Stack Overflow) e veja como funciona.
  • O pseudocódigo é bom, mas usamos c # se você quiser ser mais amigável.
  • Quanto mais simples melhor (desde que funcione). BEIJO! Se a sua solução exige que tentemos compilar posts em 10 compiladores diferentes, ou um exército de pessoas para treinar manualmente um mecanismo de inferência bayesiano, isso não é exatamente o que tínhamos em mente.
por Jeff Atwood 23.05.2017 / 14:40
fonte

14 respostas

146

Uma solução adequada provavelmente seria um modelo de aprendizagem / estatística, mas aqui estão algumas ideias divertidas:

  1. Ponto e vírgula no final de uma linha . Só isso pegaria um monte de línguas.
  2. Parênteses diretamente após o texto sem espaço para separá-lo: myFunc()
  3. Um ponto ou uma seta entre duas palavras: foo.bar = ptr->val
  4. Presença de chaves, parênteses: while (true) { bar[i]; }
  5. Presença da sintaxe "comment" (/ *, //, etc): /* multi-line comment */
  6. Caracteres / operadores incomuns: +, *, &, &&, |, ||, <, >, ==, !=, >=, <=, >>, <<, ::, __
  7. Execute seu marcador de sintaxe no texto. Se acabar destacando alguma porcentagem alta, provavelmente é código.
  8. texto camelCase na postagem.
  9. parênteses, chaves e / ou colchetes aninhados.

Poder-se-ia acompanhar o número de vezes que cada um deles aparece, e estes poderiam ser usados como recursos em um algoritmo de aprendizado de máquina como perceptron , como o SpamAssassin faz.

    
por 28.06.2011 / 18:20
fonte
54

Eu ficaria curioso em saber quais são as métricas médias do inglês escrito de um lado e do código do outro lado.

  • comprimento dos parágrafos
  • comprimento das linhas
  • tamanho das palavras
  • caracteres usados
  • relação entre caracteres alfabéticos, numéricos e outros caracteres de símbolo
  • número de símbolos por palavra
  • etc.

Talvez só isso já possa discriminar entre o código e o resto. Pelo menos eu acredito que o código, independentemente da linguagem, mostre algumas métricas visivelmente diferentes em muitos casos.

A boa notícia é: você já tem muitos dados para criar suas estatísticas.

Ok, estou de volta com alguns dados para confirmar minhas suposições. : -)

Eu fiz um teste rápido e sujo em seu próprio post e em o primeiro post que encontrei no StackOverflow , com uma ferramenta bastante avançada: wc .

Aqui está o que eu tive depois de executar wc na parte de texto e na parte de código desses dois exemplos:

Primeiro, vamos analisar a parte em inglês :

  • A parte em inglês do seu post (2635 caracteres, 468 palavras, 32 linhas)
    • 5 caracteres / palavra, 82 caracteres / linha, 14 palavras / linha
  • A parte inglesa do outro post (1499 caracteres, 237 palavras, 12 linhas)
    • 6 chars / word, 124 caracteres / linha, 19 palavras / linha

Bem parecido, você não acha?

Agora vamos dar uma olhada na parte do código !

  • A parte do código do seu post (174 caracteres, 13 palavras, 3 linhas)
    • 13 chars / word, 58 caracteres / linha, 4 palavras / linha
  • A parte do código do outro post (4181 caracteres, 287 palavras, 151 linhas)
    • 14 caracteres / palavra, 27 caracteres / linha, 2 palavras / linha

Veja como essas métricas não são tão diferentes, mas, o que é mais importante, como elas diferem das métricas de inglês? E isso é apenas usando uma ferramenta limitada. Agora estou certo de que você pode obter algo realmente preciso medindo mais métricas (estou pensando em particular nas estatísticas de caracteres).

Eu posso usar cookies?

    
por 23.05.2017 / 14:40
fonte
23

Normalmente, cadeias de Markov são usadas para gerar texto, mas também podem ser usadas para prever a similaridade de texto (por CE Shannon 1950 ) para um modelo treinado. Eu recomendo várias cadeias de Markov.

Para cada idioma predominante, treine uma cadeia de Markov em uma amostra grande e representativa de código no idioma. Em seguida, para uma postagem do Stack Overflow para a qual você deseja detectar o código, faça o seguinte para cada uma das cadeias:

  • Percorra as linhas no post.
    • Declarar duas variáveis: ACTUAL = 1.0 e HIGHEST = 1.0
    • Faz um loop por cada caractere na linha.
      • Para cada caractere, encontre a probabilidade na cadeia de Markov de que o caractere atual é o seguinte dos caracteres N anteriores. Defina ACTUAL = ACTUAL * PROB 1 . Se o caractere atual não estiver presente na cadeia, use um valor minúsculo para PROB 1 , como 0,000001.
      • Agora, encontre o caractere mais provável (ou seja, a maior probabilidade) para seguir os N caracteres anteriores. Defina HIGHEST = HIGHEST * PROB 2 .
      • Obviamente, PROB 2 > = PROB 1

Para cada linha, você deve ter um valor ACTUAL e HIGHEST. Divida ACTUAL por MAIS ALTO. Isso lhe dará a pontuação de aptidão para saber se uma determinada linha é o código-fonte. Isso associaria um número a cada uma das linhas no exemplo que você forneceu:

my problem is I need to change the database but I don't won't to create // 0.0032
a new connection. example: // 0.0023

DataSet dsMasterInfo = new DataSet(); // 0.04
Database db = DatabaseFactory.CreateDatabase("ConnectionString");   // 0.05
DbCommand dbCommand = db.GetStoredProcCommand("uspGetMasterName");  // 0.04

Por fim, você precisará selecionar um limite para determinar quando há código na postagem. Isso pode ser simplesmente um número selecionado pela observação que produz alto desempenho. Também pode levar em conta o número de linhas com uma pontuação alta.

Treinamento

Para treinar, obtenha uma amostra grande e representativa do código no idioma. Escreva um programa para fazer um loop sobre o texto do código e associe cada N-grama no arquivo (o intervalo para N deve ser parametrizado) com a frequência estatística do caractere subseqüente. Isso produzirá múltiplos estados possíveis de caracteres que seguem o bigrama, cada um associado a uma probabilidade. Por exemplo, o bigrama "()" poderia ter algumas probabilidades de caracteres a seguir:

"()" 0.5-> ";"
"()" 0.2-> "."
"()" 0.3-> "{"

O primeiro deve ser lido, por exemplo, como "A probabilidade de um ponto-e-vírgula seguir um parênteses vazio é 0,5".

Para treinamento, recomendo N-gramas de tamanho dois a cinco. Quando eu fiz algumas pesquisas sobre isso , descobrimos que N-gramas de tamanho dois a cinco funcionavam bem para o inglês. Como grande parte do código-fonte é do tipo inglês, sugiro começar com esse intervalo e, em seguida, ajustar para encontrar os valores ideais dos parâmetros conforme você encontrar o que funciona.

Uma ressalva: o modelo será afetado por identificadores, nomes de métodos, espaço em branco e etc. No entanto, você pode ajustar o treinamento para omitir certos recursos da amostra de treinamento. Por exemplo, você pode recolher todos os espaços em branco desnecessários. A presença de espaços em branco na entrada (a postagem do Stack Overflow) também pode ser ignorada. Você também pode ignorar o caso alfabético, que seria mais resiliente em face das convenções de nomenclatura de identificadores variáveis.

Durante a minha pesquisa , descobrimos que nossos métodos funcionavam bem para o espanhol e o inglês . Não vejo por que isso também não funcionaria bem para o código-fonte. O código fonte é ainda mais estruturado e previsível que a linguagem humana.

    
por 28.06.2011 / 13:28
fonte
13

Posso sugerir uma abordagem radicalmente diferente? Em SO, a única linguagem humana permitida é o inglês, então qualquer coisa que não seja em inglês tem 99,9% de chances de ser um trecho de código .

Então, minha solução seria: usar um dos muitos verificadores de inglês lá fora (apenas certifique-se de que eles também sinalizam - além de erros de ortografia - erros de sintaxe como pontos duplos ou símbolos não relacionados a idioma como # ou ~ ). Em seguida, qualquer linha / parágrafo que gera uma grande quantidade de erros e avisos deve acionar o "este código?" pergunta.

Essa abordagem também pode ser adaptada para os sites do StackExchange usando outros idiomas além do inglês, é claro.

Apenas meu 2 ¢ ...

    
por 28.06.2011 / 21:09
fonte
11

Eu provavelmente vou conseguir alguns votos para baixo, mas acho que você está se aproximando disso do ângulo errado.

Esta linha me pegou:

people have to go in and manually format code for people that are somehow unable to figure this out

IMO, esse ponto de vista é meio arrogante. Eu acho muito isso no design de software, onde programadores e designers ficam irritados com usuários que não conseguem descobrir como usar o software corretamente, quando o problema não é o usuário, mas o software em si - ou a interface do usuário, pelo menos. p>

A causa deste problema não é o usuário, mas o fato de que não é óbvio para eles que eles podem fazer isso.

Que tal uma mudança na interface do usuário para tornar isso mais óbvio? Certamente isso será:

  1. mais óbvio para os novos usuários exatamente o que eles precisam fazer
  2. mais fácil para você criar, em vez de escrever algoritmos complexos para detectar lógica de código de vários idiomas

Exemplo:

    
por 28.06.2011 / 13:37
fonte
11

O pseudo-código seria um desafio real, porque toda a linguagem de programação depende de caracteres especiais como '[]', ';', '()' etc. Basta contar a ocorrência desses caracteres especiais. Assim como você detectaria um arquivo binário (mais de 5% de uma amostra contém o valor de byte 0).

    
por 08.02.2012 / 06:53
fonte
4

Eu acho que você pode precisar direcionar isso apenas para idiomas específicos, em geral este problema é provavelmente intratável, pois você pode obter idiomas que são bastante semelhantes ao Inglês (por exemplo, informar7 . mas, felizmente, os mais usados podem ser abordados com bastante facilidade.

Meu primeiro corte seria procurar a sequência "; \ n", que lhe proporcionaria uma boa correspondência para C, C ++, Java, C # e qualquer outra linguagem que usasse sintaxe semelhante e fosse realmente simples. Também é menos provável que seja usado em inglês do que um; sem uma nova linha

    
por 28.06.2011 / 10:19
fonte
4

Alguém mencionou olhar as tags e depois procurar a sintaxe para isso, mas isso foi cancelado porque isso é destinado a novos usuários.

Uma possível solução melhor seria procurar nomes de idiomas no corpo da pergunta e, em seguida, aplicar a mesma estratégia. Se eu mencionar "Javascript", "Java" ou "C #", as chances são de que é a questão, e o código na pergunta provavelmente estará nessa linguagem.

    
por 28.06.2011 / 11:43
fonte
1

Primeiro, execute-o através da verificação ortográfica, ele encontrará muito poucas palavras inglesas adequadas, no entanto, deve haver muitas palavras que o corretor ortográfico sugerirá para dividir.

Depois, há caracteres de pontuação / especiais que não são típicos do inglês simples, típicos de código:

  • something(); simplesmente não pode ser simples em inglês;
  • $something em que something não é todos numéricos;
  • -> entre palavras sem espaços;
  • . entre palavras sem espaço;

É claro que para que ele funcione bem, você pode querer ter um classificador Bayesiano baseado nessas características.

    
por 28.06.2011 / 10:26
fonte
1

existem vários conjuntos de idiomas que compartilham uma sintaxe semelhante. a maioria das linguagens foi influenciada por algumas linguagens, então as linguagens [AMPL, AWK, csh, C ++, C--, C #, Objective-C, BitC, D, Go, Java, JavaScript, Limbo, LPC, Perl, PHP, Pike, Processing [foram todos influenciados por C, então se você detectar C você provavelmente irá detectar todos esses idiomas. então você só precisa escrever um padrão simples para detectar esses conjuntos de idiomas.

Eu também dividiria o texto em blocos porque a maioria dos códigos seria dividida por duas novas linhas ou similares dos outros blocos de texto na postagem.

isso pode ser feito facilmente com javascript (uma amostra incompleta supersimples para a família c):

var txt = "my problem is I need to change the database but I don't won't to create a new connection. example:\n\nDataSet dsMasterInfo = new DataSet();Database db = DatabaseFactory.CreateDatabase(&quot;ConnectionString&quot;);DbCommand dbCommand = db.GetStoredProcCommand(&quot;uspGetMasterName&quot;);";
var blocks = txt.split(/\n\n/gi); console.dir(blocks);
var i = blocks.length;
var cReg = /if\s*\(.+?\)|.*(?:int|char|string|short|long).*?=.+|while\s*\(.+?\)/gi;

while ( i-- ){
   var current = blocks[i];
   if ( cReg.test( current ) ){
      console.log("found code in block[" +  i + "]");
   }
}
    
por 28.06.2011 / 11:13
fonte
0

Basta contar palavras / caracteres de pontuação para cada linha. Inglês tenderá a ter 4 ou mais, código menor que 2.

O parágrafo acima tem 18 palavras e 4 caracteres de pontuação, por exemplo. Este parágrafo tem 19 palavras e 4 pontuação, portanto dentro das expectativas.

É claro que isso precisaria ser testado em relação a perguntas de novatos em inglês, e pode ser que, nesses casos, as estatísticas sejam distorcidas.

Espero que [espaço não em branco] [espaço em branco ou nova linha] seja muito raro em código, mas comum em inglês, portanto, isso pode ser contado como palavras, e não como pontuação.

Acho que o maior problema será o código embutido, em que alguém faz uma pergunta como:

If I say for (i=0; i>100; i++) {} what does that mean?

Isso é código e inglês, e deve ser marcado com back-ticks:

If I say for (i=0; i>100; i++) {} what does that mean?

    
por 28.06.2011 / 12:36
fonte
0

Acho que você deve primeiro fazer uma distinção entre o código (suficientemente) formatado que precisa ser designado como tal e o código (muito) mal formatado, que precisa de formatação manual de qualquer maneira.

O código formatado tem linhas de interrupção e recuo. Ou seja: se uma linha é precedida por uma única linha de interrupção, você tem um bom candidato. Se tiver espaços em branco no topo disso, você tem um candidato muito bom.

O texto normal usa duas linhas de quebra ou dois espaços e uma linha de quebra para formatação, portanto, há um critério claro para distinção.

No código LISP você não encontrará ponto e vírgula, no código Ruby você pode não encontrar parênteses, no pseudo código você pode não encontrar muita coisa. Mas em qualquer linguagem (não-esotérica) você encontrará código decente para ser formatado com breaklines e recuo. Não há nada tão universal quanto isso. Porque o código final é escrito para ser lido por humanos.

Então, primeiro, pesquise por linhas de código em potencial. Além disso, linhas de código geralmente vêm em grupos. Se você tiver um, há uma boa chance de que o acima ou abaixo seja uma linha de código também.

Depois de selecionar possíveis linhas de código, você pode verificá-las em relação a critérios quantificáveis e escolher um limite :

  • frequência de caracteres não verbais
  • frequência de identificadores: palavras muito curtas ou palavras muito longas com CamelCase ou under_score style
  • repetição de palavras incomuns

Além disso, agora que há programadores e cs, o escopo do stackoverflow é claramente reduzido. Pode-se considerar denotar todas as tags de idioma como idiomas. E, ao postar, você seria solicitado a escolher pelo menos uma tag de idioma, escolher a tag language-agnostic ou explicitamente omiti-la.

No primeiro caso, você sabe quais idiomas procurar, no segundo caso, você pode querer procurar por pseudo-código e, no último caso, provavelmente não haverá código, porque é uma questão relacionada a alguma tecnologia ou estrutura ou tal.

    
por 28.06.2011 / 12:43
fonte
0

Você pode criar um analisador para cada idioma que você deseja detectar (as definições de idioma para ANTLR geralmente são fáceis de encontrar) e, em seguida, executar cada linha da pergunta por meio de cada analisador. Se alguma linha for analisada corretamente, você provavelmente terá código.

O problema com isso é que algumas frases em inglês (linguagem natural) podem ser analisadas como código, então você pode querer incluir algumas das outras idéias também, ou você pode limitar os resultados positivos somente se mais de uma ou duas linhas consecutivas analisar corretamente com o mesmo analisador de idioma.

O outro problema em potencial é que isso provavelmente não vai pegar o pseudocódigo, mas isso pode ser OK.

    
por 28.06.2011 / 13:52
fonte
0

O que pode ser mais duradouro e exigir o menor ajuste manual a longo prazo, pois outras linguagens (que parecem um pouco diferentes das linguagens de programação mais usadas atualmente) se tornam mais populares e as linguagens usadas atualmente se tornam menos populares, é fazer algo como o Google Tradutor (consulte o parágrafo intitulado "Como funciona?"), de procurar por certas coisas como ab e a (), etc.

Em outras palavras, em vez de pensar manualmente em padrões encontrados no código para procurar, o computador pode descobrir sozinho . Isso pode ser feito tendo

  1. muitos códigos em muitas linguagens de programação diferentes

    • Sugestão: obtenha automaticamente amostras de código de repositórios de código-fonte baseados na Web, como o Google Code ou o Github, ou mesmo de itens do Stackoverflow já marcados como código

    • Observação: pode ser uma boa ideia analisar comentários de código

  2. muitos textos em inglês tirados de artigos na web

    • embora não seja de artigos sobre programação (senão eles podem ter código neles e misturar o sistema :-))

e tendo algum tipo de algoritmo automaticamente encontra padrões no código que não estão no inglês, e vice-versa, e usando esses padrões para detectar o que é código e o que não é código executando o código algoritmo em posts.

(No entanto, não tenho certeza de como esse algoritmo funcionaria. Outras respostas à pergunta atual podem ter informações úteis sobre isso.)

Em seguida, o sistema pode varrer novamente o código de vez em quando para explicar as alterações na forma como o código analisa esse ponto no tempo.

    
por 28.06.2011 / 23:49
fonte