Teoretisk drøfting av opplevelsen av å lede lærernes profesjonsfelleskap

Os algoritmos para detec¸c˜ao de similaridade baseados em caracteres tˆem como objetivo tratar problemas principalmente de erros de ortografia ou de digita¸c˜ao dos dados. A seguir s˜ao apresentados os principais algoritmos que abordam esses casos encontrados na literatura.

Edit Distance

O algoritmo edit distance definido no trabalho de Zhan (ZHAN et. al., 2008) ´e o termo computacional utilizado para a t´ecnica cuja implementa¸c˜ao corresponde `a distˆancia de Levenshtein, que utiliza uma cadeia de caracteres para medir a quantidade de diferen¸cas entre duas sequˆencias. A distˆancia Levenshtein entre duas palavras ´e definida como o n´umero m´ınimo de edi¸c˜oes necess´arias para transformar uma palavra em outra, com as opera¸c˜oes de inser¸c˜ao, remo¸c˜ao ou substitui¸c˜ao de um ´unico caractere.

Essa t´ecnica ´e bastante popular dentre as ferramentas, pesquisas e trabalhos referen- tes `a detec¸c˜ao de semelhan¸ca entre palavras. Os autores do trabalho (ZHAN et. al., 2008) propuseram uma ferramenta para detec¸c˜ao de pl´agio entre documentos - quest˜oes de preocupa¸c˜ao crescente na comunidade acadˆemica - para detec¸c˜ao de uma variedade de pequenas altera¸c˜oes que incluem inser¸c˜ao, dele¸c˜ao ou substitui¸c˜ao de palavras. Tais mudan¸cas simples, no entanto, requerem compara¸c˜oes de cadeias excessivas e o algoritmo edit distance mostrou-se interessante para essa varredura.

Smith Waterman Distance

O algoritmo denominado Smith Waterman Distance ´e uma melhoria da t´ecnica do algoritmo edit distance. Basicamente a ideia proposta consiste em ignorar prefixos e sufixos a fim de que a distˆancia entre as palavras seja menor e ent˜ao, serem detectadas como semelhantes (ELMAGARMID; IPEIROTIS; VERYLIOS, 2007).

2.4 Algoritmos e T´ecnicas de Detec¸c˜ao de Similaridade ou Duplica¸c˜ao de Dados 17

O algoritmo cujo nome ´e Affice Gap Distance (ELMAGARMID; IPEIROTIS; VERY- LIOS, 2007) foi desenvolvido com o objetivo de melhorar a t´ecnica utilizada pelo algoritmo edit distance, que apresenta resultados n˜ao satisfat´orios para casos em que palavras cor- respondentes foram abreviadas ou truncadas, por exemplo, Luis I. Lula da Silva e Luis In´acio Lula da Silva. A fim de resolver esse problema, a t´ecnica Affine Gap Distance introduz duas opera¸c˜oes extras de edi¸c˜ao para que esses casos sejam tamb´em detectados como semelhantes (ELMAGARMID; IPEIROTIS; VERYLIOS, 2007).

Jaro Distance Metric

Similar ao algoritmo edit distance, o algoritmo que recebe o nome de Jaro Distance calcula a semelhan¸ca geral entre duas palavras. No entanto, quando um subconjunto de caracteres n˜ao compartilha um prefixo comum com a da outra palavra, a distˆancia ´e diminu´ıda (INFORMATICA CORPORATIONS, 2008).

Q-Gram Distance

O algoritmo Q-Gram Distance apresentado no trabalho de Petrovic (PETROVIC; BAKKE, 2008) consiste na t´ecnica que decomp˜oe cada palavra em subcadeia de caracteres em que cada subcadeia corresponde ao conjunto de subcadeias da palavra decomposta e q ´e a quantidade de letras de cada conjunto formado. Por exemplo, a palavra MESTRADO com q=3 teria os seguintes q-grams: MES, EST, STR, TRA, RAD e ADO. Diversas t´ecnicas tˆem sido desenvolvidas para comparar duas palavras com base em seus q-grams. Um exemplo simples seria contar o n´umero de q-grams que duas palavras tˆem em comum, e uma quantidade alta de q-grams em comum significaria uma forte correspondˆencia entre elas.

Tecnicamente, os algoritmos q-gram n˜ao s˜ao estritamente fon´eticos, ou seja, n˜ao ope- ram com base na compara¸c˜ao das caracter´ısticas fon´eticas das palavras. Em vez disso, as t´ecnicas que envolvem q-grams s˜ao utilizadas para calcular a distˆancia entre duas palavras. Como as palavras foneticamente semelhantes muitas vezes tˆem grafias semelhantes, esta t´ecnica pode fornecer resultados favor´aveis, principalmente na compara¸c˜ao de palavras

2.4 Algoritmos e T´ecnicas de Detec¸c˜ao de Similaridade ou Duplica¸c˜ao de Dados 18

com erros ortogr´aficos, mesmo que sejam foneticamente distintas.

Estudos recentes, como do autor Petrovic mostram que utilizar a t´ecnica q-gram para detec¸c˜ao de semelhan¸ca entre palavras ´e muito mais eficaz do que outros algoritmos com prop´ositos semelhantes, como o edit distance. No experimento realizado, ´e constatado que o algoritmo detecta com maior precis˜ao os casos de semelhan¸ca entre palavras.

Distˆancia de Hamming

O algoritmo Distˆancia de Hamming discutido no trabalho de Liu e demais autores (LIU; SHE; TORNG, 2011) corresponde ao n´umero de posi¸c˜oes nas quais dois conjuntos de mesmo tamanho diferem entre si. Vista de outra maneira, corresponde ao menor n´umero de substitui¸c˜oes necess´arias para transformar um conjunto de caracteres em outro.

Os autores propuseram tamb´em uma melhora no algoritmo e criaram o algoritmo Dis- tˆancia de Hamming Dinˆamica, denotado algoritmo HEngined, que apresentou a utiliza¸c˜ao de 5 vezes menos espa¸co para realiza¸c˜ao das consultas a serem processadas e melhoria de 16% no tempo de execu¸c˜ao que o original.

Coeficiente de Jaccard

Tamb´em conhecido como o Coeficiente de Semelhan¸ca Jaccard, originalmente deno- minado de Coeficiente de Communaut´e por Paul Jaccard, o Coeficiente de Jaccard ´e um m´etodo estat´ıstico utilizado para comparar a semelhan¸ca e diversidade de conjuntos de amostras e pode ser definido como o tamanho da intersec¸c˜ao dividido pelo tamanho da uni˜ao dos conjuntos de uma amostra (JACCARD, 1901).

Os autores Wang e Ying-Hua (WANG; YING-HUA, 2009) propuseram um algoritmo baseado no Coeficiente de Jaccard em que pesos s˜ao definidos aos atributos do texto. A f´ormula ´e proposta de tal maneira que cada atributo ´e multiplicado pelo peso, que ´e calculado por meio do processo AHP (Analytic Hierarchy Process). Com os atributos ponderados, ´e calculada a semelhan¸ca entre as entidades. Os resultados da experiˆencia mostraram que a modifica¸c˜ao proposta atinge maior precis˜ao e efic´acia na detec¸c˜ao de

2.4 Algoritmos e T´ecnicas de Detec¸c˜ao de Similaridade ou Duplica¸c˜ao de Dados 19

semelhan¸ca entre conjuntos de palavras.

2.4.2

Algoritmos e T´ecnicas de detec¸c˜ao de Similaridade Base-