💬 NLP

Proposal and study of statistical features for string similarity computation and classification

Este artigo propõe e valida características estatísticas independentes de linguagem, derivadas de matrizes de co-ocorrência e de comprimentos de sequência, para o cálculo de similaridade entre strings e classificação, demonstrando seu desempenho superior em relação às medidas mais avançadas existentes tanto em experimentos sintéticos quanto em tarefas reais de detecção de plágio.

Autores originais: E. O. Rodrigues, D. Casanova, M. Teixeira, V. Pegorini, F. Favarim, E. Clua, A. Conci, Panos Liatsis

Publicado 2026-05-15

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: E. O. Rodrigues, D. Casanova, M. Teixeira, V. Pegorini, F. Favarim, E. Clua, A. Conci, Panos Liatsis

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um detetive tentando descobrir se dois textos são, na verdade, a mesma história, apenas escrita de forma diferente, ou se são completamente desconexos. Talvez você esteja verificando se um aluno copiou um artigo da Wikipedia, ou se um documento digitalizado de um livro antigo corresponde ao texto digital.

Este artigo apresenta uma nova maneira para computadores resolverem esse mistério. Em vez de apenas contar quantas letras coincidem (como um verificador ortográfico simples), os autores sugerem examinar a "impressão digital" do texto usando ferramentas emprestadas do mundo do processamento de imagens.

Aqui está a explicação de sua abordagem, usando analogias simples:

1. A Maneira Antiga vs. A Maneira Nova

A Maneira Antiga (O Detetive da "Contagem de Palavras"):
Tradicionalmente, os computadores comparam strings de texto procurando a sequência mais longa de letras coincidentes (como encontrar a frase mais longa que coincide) ou contando quantas edições (adicionar, deletar ou trocar letras) são necessárias para transformar uma palavra em outra.

O Problema: Esses métodos são como tentar identificar uma pessoa olhando apenas sua altura. Se duas pessoas tiverem a mesma altura, mas nada mais em comum, você pode ficar confuso. Além disso, esses métodos frequentemente falham se o texto for embaralhado ou se o idioma for diferente.

A Maneira Nova (O Detetive da "Textura"):
Os autores propõem tratar o texto como uma imagem.

A Matriz de Co-ocorrência (COM): Imagine que você tem uma grade. Você olha para o texto e pergunta: "Com que frequência a letra 'A' aparece logo ao lado da letra 'B'?" Você mapeia isso em uma grade. É como olhar para uma foto pixelada e contar com que frequência um pixel vermelho fica ao lado de um pixel azul. Isso ajuda o computador a ver a estrutura e o padrão do texto, não apenas as letras individuais.
A Matriz de Comprimento de Execução (RLM): Isso é como olhar para um código de barras ou uma fileira de blocos coloridos. Se você tem um texto como "aaabbb", o computador vê uma "execução" de três 'a's e uma "execução" de três 'b's. Ele conta esses blocos. Se dois textos tiverem padrões de "blocos" semelhantes (mesmo que as letras dentro dos blocos sejam ligeiramente diferentes), o computador sabe que eles provavelmente estão relacionados.

2. Por Que Isso é Especial

Os autores enfatizam que essas ferramentas são agnósticas em relação ao idioma.

A Analogia: A maioria das ferramentas de similaridade é como um dicionário que só fala inglês. Se você tentar comparar uma frase em francês com uma em espanhol, o dicionário falha.
A Solução: Os métodos COM e RLM são como uma câmera. Uma câmera não se importa se o objeto é um gato, um cachorro ou um carro; ela apenas vê as formas e os padrões. Da mesma forma, esses novos recursos não se importam se o texto é inglês, português ou código de computador. Eles apenas observam a "textura" estatística dos caracteres.

3. Os Experimentos (O "Test Drive")

Os pesquisadores colocaram suas novas ferramentas de detetive à prova de duas maneiras:

Teste A: O Laboratório Sintético (O Texto "Falso")
Eles criaram um programa de computador para gerar strings aleatórias de texto e depois as "embaralharam" deliberadamente para simular diferentes níveis de plágio ou erro.

O Resultado: Quando o texto foi apenas levemente embaralhado, os métodos antigos (como contar letras coincidentes) funcionaram bem. Mas, à medida que o texto ficou mais embaralhado e aleatório, os métodos antigos falharam. Os novos métodos de Comprimento de Execução (RLM) e Co-ocorrência (COM) mantiveram a calma e identificaram as similaridades muito melhor.
A Metáfora: Se você rasgar uma página de um livro e embaralhar as palavras, um simples contador de letras se perde. Mas um detector de "textura" ainda consegue ver que o "grão" do papel é o mesmo.

Teste B: O Mundo Real (O Caso de "Plágio")
Eles testaram seu sistema em um conjunto de dados real de respostas de alunos comparadas a artigos da Wikipedia. O objetivo era detectar quatro níveis:

Cópia Quase Exata: Texto apenas colado.
Revisão Leve: Sinônimos trocados, gramática ajustada.
Revisão Pesada: Frases completamente reescritas.
Não Plágio: Escrito do zero.

O Resultado: Seu novo método alcançou 84,21% de precisão. Isso superou os melhores resultados anteriores no campo (que giravam em torno de 70%).
O Vencedor: Os recursos da Matriz de Comprimento de Execução (RLM) foram a estrela do show, provando que observar as "execuções" de caracteres é a maneira mais poderosa de detectar plágio, mesmo quando o texto foi pesadamente reescrito.

4. O Veredito

O artigo conclui que, embora os métodos tradicionais sejam adequados para textos muito semelhantes, eles lutam quando as coisas ficam confusas. Os novos recursos estatísticos (COM e RLM), emprestados da análise de imagens, são muito mais robustos. Eles conseguem lidar com textos mais longos e mudanças mais caóticas melhor do que qualquer outra coisa testada.

Em resumo: Os autores construíram um novo "scanner de textura" para texto. Em vez de apenas ler as palavras, ele analisa o padrão de como as letras ficam uma ao lado da outra e como se repetem. Isso permite que os computadores identifiquem textos copiados ou semelhantes com muito mais precisão, mesmo quando o texto foi pesadamente editado ou está em um idioma que o computador não "entende".

Resumo Técnico: Proposta e Estudo de Recursos Estatísticos para Cálculo e Classificação de Similaridade de Strings

Declaração do Problema
O artigo aborda o desafio de calcular a similaridade de strings para aplicações gerais, incluindo comparação de palavras, detecção de plágio de texto, inferência textual e reconhecimento óptico de caracteres (OCR). Embora os métodos existentes frequentemente dependam de informações semânticas (taxonomias, dicionários) ou distâncias de edição específicas, essas abordagens podem ser enviesadas linguisticamente ou computacionalmente intensivas. Os autores propõem um framework que utiliza medidas puramente estatísticas e baseadas em regras, garantindo que o método seja agnóstico à linguagem e aplicável a qualquer estrutura gramatical, sem exigir recursos linguísticos pré-treinados.

Metodologia
A contribuição central é a adaptação de recursos da computação visual — especificamente Matrizes de Coocorrência (COM) e Matrizes de Comprimento de Execução (RLM) — para análise de strings. Esses recursos são extraídos de pares de strings e alimentados em algoritmos de classificação supervisionada para determinar o grau de similaridade (por exemplo, se duas strings são idênticas ou se uma é uma versão modificada da outra).

Recursos Estatísticos Propostos:
- Informação Mútua Ponderada (WMI): Uma adaptação da Informação Mútua (MI) padrão que incorpora um fator de peso ( $m > 1$ ) e considera a ordenação dos caracteres. Inclui uma operação de deslocamento para contabilizar distâncias de deslocamento, distinguindo entre strings que são permutações uma da outra versus strings idênticas.
- Recursos de Matriz de Coocorrência (COM): Adaptadas do processamento de imagens, essas matrizes contam a coocorrência de caracteres idênticos em distâncias específicas entre duas strings. Recursos derivados incluem Probabilidade de Coocorrência (COP), Pontuação de Probabilidade (PS), Pontuação Total de Probabilidade (TPS) e Distribuição de Coocorrência (CODs).
- Recursos de Matriz de Comprimento de Execução (RLM): Baseadas em codificação de comprimento de execução, esses recursos contam as ocorrências de comprimentos de sequência específicos da primeira string ( $w_1$ ) dentro da segunda string ( $w_2$ ). Recursos derivados incluem Soma de Ocorrências (SO), SO Ponderada (WSO), Ocorrência Máxima (MO), Comprimento de Execução Máximo Ocorrido (MORL) e uma variante da Maior Subsequência Comum Consecutiva Mais Longa (RLMMCLCS).
Comparações com Linha de Base:
Os recursos propostos são comparados contra medidas estatísticas estabelecidas, incluindo:
- Maior Subsequência Comum (LCS) e LCS Normalizada.
- Maior Subsequência Comum Consecutiva Mais Longa (MCLCS).
- Informação Mútua Padrão (MI).
- Distâncias de edição: Hamming (modificada), Levenshtein e Damerau-Levenshtein.
- Coeficiente de Dice.
Configuração Experimental:
- Conjuntos de Dados Sintéticos: Dois conjuntos de experimentos foram conduzidos usando strings geradas.
  - Comparação de Palavras: Strings de até 14 caracteres com variados graus de aleatoriedade ( $R=0,5; 0,9$ ).
  - Comparação de Frases: Strings de até 200 caracteres com baixa ( $R=0$ ) e moderada ( $R=0,15$ ) aleatoriedade.
  - Os rótulos eram binários: "Igual" (versão modificada da primeira string) ou "Diferente" (gerada aleatoriamente).
- Conjunto de Dados do Mundo Real: O corpus de plágio da Wikipedia (Clough e Stevenson, 2011) foi utilizado para um problema de classificação multiclasse envolvendo quatro níveis: Cópia Próxima, Revisão Leve, Revisão Pesada e Não-plágio.
- Classificadores: Uma variedade de algoritmos foi testada, incluindo LMT (Árvores de Modelo Logístico), Random Forest, REP Tree, Perceptron Multicamadas, k-NN e Naive Bayes, utilizando o Weka.

Principais Resultados

Experimentos Sintéticos:
- Em 3 dos 4 cenários sintéticos, os recursos RLM e COM propostos superaram estatisticamente os recursos baseados em distância de última geração (Valor-p < 0,001).
- Os recursos COM apresentaram o melhor desempenho quando a aleatoriedade era baixa a moderada (por exemplo, $R=0,5$ para strings curtas), alcançando a maior acurácia individual (86,78% com LMT).
- Os recursos RLM demonstraram robustez superior em cenários de alta aleatoriedade e strings longas (por exemplo, $R=0,15$ para strings de 200 caracteres), superando significativamente os grupos de distância.
- A Informação Mútua Padrão (MI) e os recursos baseados em comprimento tiveram desempenho consistentemente inferior.
- O LMT foi o classificador mais preciso no geral, embora tenha exigido tempo de treinamento significativo. O k-NN foi o mais rápido para "gerar" um modelo (pois é preguiçoso), mas teve o tempo de classificação mais lento.
Detecção de Plágio:
- Usando o conjunto de dados da Wikipedia, a metodologia proposta alcançou uma acurácia de 84,21% usando um ensemble de classificador Voto.
- Este resultado superou trabalhos anteriores no mesmo conjunto de dados (Clough e Stevenson: 66,31% com base em sua matriz de confusão; Chong et al.: 70,52%).
- A classificação de recursos indicou que os recursos derivados de RLM (especificamente MORL e RLMMCLCS) foram os preditores mais valiosos para esta tarefa.

Significado e Alegações
O artigo afirma que adaptar matrizes de computação visual (COM e RLM) para similaridade de strings oferece uma alternativa robusta e independente de linguagem às distâncias de edição tradicionais e medidas semânticas.

Independência Linguística: Os recursos propostos dependem exclusivamente de padrões estatísticos, tornando-os aplicáveis a qualquer idioma sem a necessidade de dicionários ou taxonomias.
Robustez à Aleatoriedade: O estudo demonstra que, enquanto métodos baseados em distância funcionam bem para mudanças sutis, os recursos RLM são particularmente eficazes para textos mais longos e maiores graus de aleatoriedade, mimetizando cenários de plágio do mundo real.
Eficiência: Embora a extração de recursos para COM e RLM exija a construção de matrizes, a extração de múltiplos recursos de uma única matriz é computacionalmente eficiente.
Potencial Futuro: Os autores observam modestamente que o potencial completo de COM e RLM na similaridade de strings ainda não foi totalmente explorado, sugerindo que uma engenharia de recursos adicional baseada nessas matrizes é uma direção viável para trabalhos futuros.

O estudo conclui que, para tarefas envolvendo comparação de texto, inferência ou detecção de plágio envolvendo strings mais longas ou alta variabilidade, os recursos baseados em RLM fornecem uma vantagem estatisticamente significativa sobre as medidas estatísticas atuais de última geração.

1. A Maneira Antiga vs. A Maneira Nova

2. Por Que Isso é Especial

3. Os Experimentos (O "Test Drive")

4. O Veredito

Mais como este