\documentclass[12pt]{article}
\usepackage{cite}
\usepackage{sbc-template}
\usepackage{graphicx,url}
\usepackage{subfigure}
\usepackage{amssymb,amsmath,amsthm}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage{float}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref}
\usepackage[table,xcdraw]{xcolor}
\renewcommand{\algorithmicforall}{\textbf{for each}}
\newcommand{\nameOfProgram}{Rorschach}
\sloppy
\title{\nameOfProgram: Uma Ferramenta para Detecção de Plágio}
\author{
Yuri Karan Benevides Tomas\inst{1}, Edna Ayako Hoshino (orientadora)\inst{1}
}
\address{
Faculdade de Computação -- Universidade Federal de Mato Grosso do Sul (UFMS) \\
Caixa Postal 549 -- 79.070-900 -- Campo Grande -- MS
\email{
iruynarak@gmail.com, eah@facom.ufms.br
}
}
\begin{document}
\maketitle
\begin{abstract}
Considering the growing impact of ideas nowadays, via quaternary sector, the plagiarism detection has become constant in texts, songs, as well as source codes. This work proposes the creation of the tool \nameOfProgram \ for plagiarism detection in simple texts with GNU GPL license. \nameOfProgram \ was designed to allow your extension for plagiarism detection in source codes. The tool was tested and results are presented in this paper.
\end{abstract}
\begin{resumo}
Considerando o crescente impacto das ideias atualmente, através do setor quaternário, a detecção de plágio tem se tornado constante em textos, músicas, assim como códigos-fonte. Este trabalho propõe a criação da ferramenta \nameOfProgram \ para detecção de plágio em textos simples com licença GNU GPL. \nameOfProgram \ foi projetado para permitir sua extensão para detecção de plágio em códigos-fonte. A ferramenta foi testada e os resultados são apresentados neste artigo.
\end{resumo}
\section{Introdução}
Plagiar é o ato de assumir a autoria ou utilizar como fonte uma obra intelectual pertencente a outra pessoa. Ideias possuem um valor cada vez maior na sociedade conforme o setor quaternário, setor econômico relacionado à informação, ganha importância. Por este motivo, há um interesse crescente na detecção de plágio em textos, músicas, vídeos e até mesmo em códigos-fonte.
Diversos artigos já foram publicados comparando o desempenho e os algoritmos utilizados pelas principais ferramentas de detecção de plágio existentes. Em \cite{hage2010comparison} o autor compara o desempenho de cada uma delas. Apesar de haver uma variação de resultados entre os testes realizados, aqueles com melhores resultados, de maneira geral, segundo o artigo foram o JPlag \cite{prechelt2002finding} e o Marble \cite{hage2007programmeerplagiaatdetectie}, seguidos pelo MOSS \cite{aiken2005moss}.
Em \cite{djuric2012source} são descritas e comparadas superficialmente as principais ferramentas e seus respectivos algoritmos. Também é proposto um novo algoritmo baseado nas ferramentas JPlag e MOSS. Em \cite{martinsEtAl}, o desempenho de diversas ferramentas são comparadas, além de uma breve descrição técnica de cada uma delas.
Através destas pesquisas é possível perceber que muitas ferramentas utilizam o algoritmo RKR-GST como base para sua implementação. Entre elas podemos citar o JPlag \cite{prechelt2002finding}, o CPD \cite{copeland2003detecting}, o Plaggie \cite{ahtiainen2006plaggie}, o Marble \cite{hage2007programmeerplagiaatdetectie} e o YAP3 \cite{wise1996yap3}.
Neste trabalho propôs-se a criação do programa \nameOfProgram, um detector de plágio em textos, base para um futuro detector de plágio em códigos-fonte, que utiliza o algoritmo \hyperref[sec:rkrgst]{RKR-GST} para encontrar a similaridade.
A ferramenta Plaggie \cite{ahtiainen2006plaggie} possui licença GNU GPL e detecta plágio em códigos-fonte escritos em Java 1.5, mas sua única documentação são os comentários existentes no código, o que prejudica a sua compreensão. Por este motivo, em \nameOfProgram \ é utilizada a versão 3 da licença GNU General Public License \cite{gnu} e a documentação foi criada através da ferramenta \cite{doxygen}, de licença GNU GPL e pelas informações presentes neste artigo. Esta escolha foi feita para facilitar o estudo ou modificação do código.
Este texto está dividido em mais três seções. Na Seção 2 são apresentados os principais algoritmos e os conceitos necessários para a compreensão do RKR-GST. A Seção 3 discute o projeto desenvolvido neste trabalho. Por fim, a Seção 4 apresenta uma conclusão, as contribuições do trabalho e os desafios enfrentados.
\section{Metodologia}
Nesta seção, são descritos conceitos teóricos importantes para a devida compreensão deste trabalho.
\subsection{Conceitos de Linguagens Formais}
A seguir serão apresentados alguns conceitos de linguagens formais, de acordo com \cite{Hopcroft+Ullman/79/Introduction}, que são importantes para a compreensão deste trabalho.
\subsubsection{Alfabeto}
Um \textit{alfabeto} é um conjunto finito e não vazio de elementos, que por sua vez são chamados de \textit{letras}. Utilizamos a letra grega $\Sigma$ (sigma maiúsculo) para representar um \textit{alfabeto} arbitrário. Alguns exemplos de alfabetos:
\begin{itemize}
\item $\Sigma = \{0, 1\}$, o alfabeto binário;
\item $\Sigma = \{0, 1, ..., 9\}$, o \textit{alfabeto} numérico;
\item $\Sigma = \{a, b, ..., z\}$, o \textit{alfabeto} das \textit{letras} minúsculas; e
\item O conjunto de caracteres que compõem o código ASCII.
\end{itemize}
\subsubsection{Palavra}
Uma \textit{palavra} \textit{w}, sobre um alfabeto $\Sigma$, é uma sequência finita de \textit{letras} de $\Sigma$. A $i$-ésima letra de \textit{w} é denotada por \textit{$w_i$}. O comprimento, ou tamanho, de \textit{w}, representado por $|\textit{w}|$ é a quantidade de \textit{letras} que a compõe.
\subsubsection{Subcadeia}
Uma \textit{subcadeia} de \textit{w} é uma \textit{palavra} \textit{x} cujas \textit{letras} pertencem a \textit{w} e estão em \textit{x} na mesma sequência que em \textit{w}. Por exemplo, a \textit{palavra} ``tarde'' é subcadeia da \textit{palavra} ``Boa tarde''. Isto é, \textit{x} é \textit{subcadeia} de \textit{y} se $\exists$ \textit{z} e \textit{w}, \textit{palavras}, tal que \textit{zxw} = \textit{y}.
\subsection{Função \textit{Hash}}
\textit{Função hash} é o nome dado a qualquer função que pode ser utilizada para mapear qualquer informação sem tamanho fixo para uma de tamanho fixo. O valor retornado pela função de \textit{hash} é chamado valor de \textit{hash}. Ela pode ser utilizada na criação de uma estrutura de dados compacta -- e consequentemente eficiente e econômica em relação ao consumo de memória -- evitando estouro de variável. Funções \textit{hash} também podem ser utilizadas em criptografia de dados.
Por exemplo, podemos criar uma função \textit{hash} para o mapeamento de números inteiros para o intervalo de inteiros $[0,99]$ através da função $f(x)= x\ \bmod\ 100 $. Assim o valor de \textit{hash} para o número 1039 seria 39.
\subsection{Janela}
\label{sec:janela}
Uma \textit{janela} é uma sequência de tamanho fixo de \textit{letras} em uma \textit{palavra}. Esta sequência pode se deslocar para a direita ou para a esquerda dentro da palavra. Quando ocorre um deslocamento à direita, o termo mais à esquerda da \textit{janela} anterior ao deslocamento passa a não pertencer mais à \textit{janela}. Além disto, o termo mais à direita da nova \textit{janela} passa a ser o elemento seguinte ao elemento mais à direita da \textit{janela} anterior. A figura 1 ilustra um exemplo de janela.
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.35]{janela.eps}
\end{center}
\caption{\small Exemplo de janela.}
\label{janelaFigure}
\end{figure}
\subsection{\textit{Rolling Hash}}
\label{sec:rollingHash}
O custo computacional para o cálculo do valor de \textit{hash} de uma \textit{janela} pode ser muito alto dependendo das operações matemáticas envolvidas na função de \textit{hash}. O \textit{Rolling Hash}(\cite{demaine2011-1}) é um algoritmo utilizado para encontrar o valor de \textit{hash} em \textit{janelas}, proposto a fim de diminuir o custo desse processamento. Para isto, ele aproveita o valor de \textit{hash} da posição atual da \textit{janela} para o cálculo do valor após um deslocamento à direita.
Após um deslocamento à direita, todas as \textit{letras} contidas na \textit{janela} serão as mesmas exceto pela inclusão de uma nova \textit{letra} à direita e a exclusão de outra à esquerda. Para obter vantagem desta característica é feita uma certa analogia da \textit{palavra} a um número. O valor de \textit{hash} da \textit{palavra} será o próprio número gerado pela analogia.
Cada \textit{palavra} é associada a um número em uma base numérica específica definida pelo tamanho do alfabeto. Cada \textit{letra} é associada a um algarismo deste \textit{alfabeto}. Assim, sendo \textit{w} uma palavra, \textit{hash(w)} = $ \sum\limits_{i = 1}^{|w|} w_i * base^{|w| - i}$.
Por exemplo, se $\Sigma = \{a, b\}$, como $|\Sigma| = 2$, então a base é 2. Podemos associar $a = 1$ e $b = 2$. Assim a \textit{palavra} ``aa'' possui valor de hash igual a 3, pois $1*2^1 + 1*2^0 = 3$. De forma análoga: ab = 4, ba = 5, bb = 6.
Para a construção do valor de \textit{hash} da \textit{janela} inicial o número é calculado integralmente, não havendo ganho de desempenho por causa da \textit{Rolling Hash}. O valor de \textit{hash} desta \textit{palavra} após a realização de um deslocamento pode ser calculado em tempo linear utilizando o valor de \textit{hash} antes deste deslocamento.
Cada algarismo do número encontrado pela função de \textit{hash}, considerando a base numérica adotada, refere-se a uma \textit{letra} da \textit{janela}. Para encontrar o valor de \textit{hash} após um deslocamento à direita, o algarismo mais à esquerda deixa de pertencer ao número referente ao valor de \textit{hash} da janela. Além disto, o algarismo referente à \textit{letra} mais à direita da nova \textit{janela} passa a fazer parte do valor de hash da janela atual.
Após um deslocamento à direita, a \textit{letra} mais à esquerda na janela deixa de pertencer a ela e a \textit{letra} à direita da \textit{janela}, passa a fazer parte dela. Assim, o número referente ao valor de \textit{hash} após o deslocamento à direita será o igual ao atual, exceto pela remoção de um algarismo à esquerda e o acréscimo de outra à direita. Matematicamente as seguintes operações são realizadas para a \textit{janela} inicial:
\begin{enumerate}
\item Zerar valor de hash:
\subitem $hashValue = 0$
\item Para cada \textit{letra} a ser adicionada:
\subitem Incrementar a posição de cada termo do número:
\subsubitem $hashValue = hashValue \times base$
\subitem Adicionar o novo termo na posição menos significativa do número
\subsubitem $hashValue = hashValue + newLetter$
\end{enumerate}
Para a \textit{janela} após um deslocamento à direita
\begin{enumerate}
\item Remover o termo mais significativo do número (oldLetter):
\subitem $hashValue = hashValue - base^{oldIndex-1} \times oldLetter$
\item Incrementar a posição de cada termo do número:
\subitem $hashValue = hashValue \times base$
\item Adicionar o novo termo (newLetter) na posição menos significativa do número
\subitem $hashValue = hashValue + newLetter$
\end{enumerate}
Cada uma dessas três operações feitas para encontrar o valor de \textit{hash} após um deslocamento é feita em O(1), fazendo com que o custo computacional para a descoberta dos valores de \textit{hash} seja linear.
Para encontrar o valor inicial de \textit{hash} para uma sequência de caracteres, por exemplo, o transformamos em um número. Se fizermos isto para caracteres acentuados a base deste número deverá ser 256 já que o ASCII extendido, o alfabeto em questão, possui 256 valores possíveis.
A Tabela \ref{table:ascIIExt} ilustra os valores das \textit{letras} que compõem a \textit{palavra}``so'' de acordo com a tabela ASCII .
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|}
\hline
Índice da posição & 3 & 2 & 1 \\ \hline
Código ASCII extendido & 115 & 111 & 109\\ \hline
Caractere & s & o & m \\ \hline
\end{tabular}
\caption{Valores correspondentes na tabela ASCII extendida.}
\label{table:ascIIExt}
\end{table}
Dessa forma, o valor de \textit{hash} para a \textit{palavra} ``som''=\\*
$115 \times 256^2 + 111 \times 256^1 + 109\times 256^0 = 7565165$
Caso a \textit{letra} à direita da \textit{janela} atual fosse ``a'' e deslocássemos a \textit{janela} nesta direção, as sequintes operações ocorreriam na próxima iteração:
\begin{enumerate}
\item Remover o termo mais significativo do número:
\subitem $28525 = 7565165 - 115 \times 256^2$
\item Incrementando a posição de cada termo do número:
\subitem $7302400 = 28525 \times 256$
\item Adicionar o novo termo na posição menos significativa do número
\subitem $7302497 = 7302400 + 97$
\end{enumerate}
O número resultante destas operações pode acabar estourando a quantidade de bits máxima determinada para o tipo usado para armazená-lo, principalmente quando o tamanho da janela é muito grande. Por este motivo, após cada operação, é feita uma operação de aritmética modular utilizando um número primo maior do que o tamanho do alfabeto utilizado. Assim, as operações matemáticas se tornariam:
\begin{enumerate}
\item Encontrar o valor do termo mais significativo:
\subitem aux = $ (oldLetter \times ( base^{oldIndex - 1} \bmod primeNumber) \bmod primeNumber$
\item Remover o termo mais significativo do número:
\subitem $hashValue = hashValue - aux$
\item Operação de resto para evitar overflow
\subitem $hashValue = hashValue \bmod primeNumber$
\item Incrementando a posição de cada termo do número:
\subitem $hashValue = hashValue * base$
\item Adicionar o novo termo na posição menos significativa do número
\subitem $hashValue = hashValue + newLetter$
\item Evitando overflow que a adição do termo poderia causar
\subitem $hashValue = hashValue \bmod primeNumber $
\end{enumerate}
\subsection{Busca de Padrão em Palavra}
A busca de padrão em \textit{palavra}, também nomeado como \textit{string-matching} ou \textit{string-searching} é o nome dado a uma classe de algoritmos. Neles procura-se por um padrão em um texto. Tanto o padrão quanto o texto são \textit{palavras} do mesmo alfabeto $\Sigma$. Neste artigo denominaremos o texto como \textit{text}, o padrão como \textit{pattern} e \textit{subText} uma \textit{subcadeia} de \text{text}. Assim, a busca de padrão procura um \textit{subText} de tamanho $|\textit{pattern}|$ que seja igual a \textit{pattern}.
\subsubsection{Algoritmo Trivial para String-matching}
A solução trivial é dada pelo algoritmo abaixo :
\begin{algorithm} [H]
\caption{Algorimo Trivial de String-Matching}\label{alg:naive-string-searching}
\begin{algorithmic}[1]
\State int i, j
\For{(i = 0; $i < textSize - patternSize$; i++)}
\For{(j = 0; $j < patternSize$ ; j++)}
\If{(! (text[i + j] == pattern[j])}
\State break
\EndIf
\EndFor
\If{(j == patternSize)}
\State return 1
\EndIf
\EndFor
\State return 0
\end{algorithmic}
\end{algorithm}
O algoritmo compara cada \textit{subcadeia} de \textit{text}, iniciada em uma posição i, ao \textit{pattern} buscado, \textit{letra} a \textit{letra}. Caso a comparação indique igualdade entre as duas, encontramos o padrão buscado. Caso \textit{subtext} difira de \textit{pattern}, incrementamos o \textit{i} e repetimos o processo.
Realizamos este laço até, no pior caso, $|\textit{text}| - |\textit{pattern}|$ vezes, sendo o valor inicial de \textit{i} igual ao índice do primero caracter do texto. Após este ponto não haverá caracteres suficientes para criar um \textit{subtext} de tamanho $|\textit{pattern}|$. Cada iteração do laço, no pior caso, realiza $|\textit{pattern}|$ comparações já que a diferença pode estar apenas na última \textit{letra}.
Dessa forma temos que a complexidade do algoritmo trivial é de $O((|\textit{text}| - |\textit{pattern}|)\times |\textit{pattern}|) = O(|\textit{text}| \times |\textit{pattern}|)$.
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.25]{string-matching.eps}
\end{center}
\caption{\small Buscando um padrão contendo cinco \textit{letras} em um texto. \textit{Subcadeias} do texto de cinco \textit{letras} são comparadas ao padrão.}
\label{stringMatchingFigure}
\end{figure}
\subsubsection{Algoritmo Karp-Rabin}
\label{sec:karpRabin}
Embora simples e custoso, o algoritmo trivial foi a base para a criação do algoritmo Karp-Rabin (\cite{karp1987efficient}). A diferença está na comparação feita entre \textit{pattern} e as \textit{subcadeias} de tamanho $|\textit{pattern}|$.
No algoritmo Karp-Rabin, ao invés de compararmos \textit{pattern} e uma \textit{subcadeia} de \textit{text} de tamanho \textit{$|pattern|$}, \textit{letra} a \textit{letra}, damos a cada um deles um valor calculado através de uma \textit{hash}. Através disto é possível realizar comparações em tempo linear já que estamos apenas comparando números. Se, de alguma forma, possuirmos os valores de \textit{hash}, o tempo passará a ser $O(|\textit{text}|-|\textit{pattern}|)$.
Uma vez que \textit{text} e \textit{pattern} não são fixos, seus valores de \textit{hash} não são previamente conhecidos. Ainda assim, podemos suprimir o custo de cálculo de uma \textit{hash}, tornando-o linear. O fato que possibilita isto é a similaridade entre uma \textit{subcadeia} e a formada após um deslocamento como explicado na \hyperref[sec:janela]{Seção 2.3} e na \hyperref[sec:rollingHash]{Seção 2.4}.
de iterações vizinhas. A \textit{subcadeia} da iteração \textit{i+1} é igual ao da iteração \textit{i} com a retirada do termo mais à esquerda e o acréscimo do termo mais à direita.
Dessa forma utilizamos o conceito de \textit{Rolling Hash} para nos aproveitar desta característica.
\subsection{Definições Necessárias para o Algoritmo \textit{RKR-GST}}
Para um melhor entendimento do \hyperref[sec:rkrgst]{Running-Karp-Rabin Greedy-String-Tilling}, ou simplesmente RKR-GST, algumas definições devem ser vistas.
\subsubsection{Casamento}
O \textit{casamento} ocorre quando uma \textit{subcadeia} é igual a outra de mesmo tamanho. Podemos utilizar a notação \text{casamento($p, t, l$)} para representar um \textit{casamento} entre \textit{subcadeia} de \textit{pattern} e outra \textit{text}, ambas de tamanho $l$, que iniciam na posição $p$ e $t$, de \textit{pattern} e \textit{text}, respectivamente.
\subsubsection{\textit{Tile}}
O \textit{tile} é um \textit{casamento} único e permanente entre uma \textit{subcadeia} de \textit{text} e outra de \textit{pattern}. Após a formação de um \textit{tile}, as \textit{letras} de ambas as \textit{subcadeias} são \textit{marcadas} para evitar a sobreposição de \textit{tiles}.
\subsubsection{Letra Marcada}
Uma \textit{letra} considerada \textit{marcada} é indisponível para novos \textit{casamentos}, ou seja, \textit{casamentos} não são permitidos se alguma das \textit{subcadeias} possui \textit{letra} marcada.
\subsubsection{Casamento Maximal}
Um \textit{casamento maximal} é um \textit{casamento} de uma \textit{subcadeia} de \textit{pattern} e outra de \textit{text} que não permite aumento do seu tamanho, ou seja, não permite aumento do tamanho das suas \textit{subcadeias}. O aumento do tamanho das \textit{subcadeias casadas} pode causa diferença entre elas, inclusão de \textit{letra marcada} em alguma delas ou encontro do fim de alguma das palavras.
\subsubsection{Tamanho Mínimo de Casamento}
\textit{Tamanho mínimo de casamento} é o tamanho mínimo permitido para um \textit{casamento maximal}. Qualquer \textit{casamento maximal} encontrado com valor inferior ao \textit{tamanho mínimo de casamento} definido é ignorado. A decisão do valor adotado possui uma grande influência na detecção de plágio e depende do contexto. Quando comparamos códigos-fonte, por exemplo, não é interessante encontrar palavras-chave da linguagem em questão durante a busca por plágio. Na linguagem C, por exemplo, pode-se escolher um \textit{tamanho mínimo de casamento} maior do que $|$``if''$|$, o que possibilita ignorar vários trechos que contém a palavra-chave ``if'', mas cujas condições são diferentes.
\subsubsection{O algoritmo \textit{Greedy-String-Tilling}}
\label{sec:gst}
Um \textit{tile} grande é um indício maior de similaridade do que um pequeno, por representar um trecho maior similar entre as \textit{palavras} comparadas. Por este motivo, é possível utilizar um algoritmo guloso, como o \textit{Greedy-String-Tilling} (\cite{karp1987efficient}), também chamado de GST, para encontrar \textit{tiles}, dando preferência aos maiores.
Fazendo \textit{P[i]} a \textit{letra} de índice \textit{i} na palavra \textit{palavra} \textit{P}, temos o seguinte pseudocódigo do algoritmo GST :
\begin{algorithm} [H]
\caption{Algorimo GST}
\label{alg:gst}
\begin{algorithmic}[1]
\State lengthTiled = 0 \;
\While { $ maxMatch != tamanhoMinimo $ }
\For{Cada letra não marcada de índice p de pattern}
\For{Cada letra não \textit{marcada} de índice t de text}
\State j = 0\;
\While{ pattern[p + j] = text[t + j] E text[t +j] não é marcada }
\State $ j := j+1 $
\EndWhile
\If{j = maxMatch}
\State Adicionar o casamento(p, t j) à lista de casamentos
\ElsIf{ $ j > maxMatch $ }
\State Começar nova lista de casamentos com casamento(p, t, j) e maxMatch = j
\EndIf
\EndFor
\EndFor
\For{ cada casamento(p, t, maxMatch) na lista de casamentos}
\If{as duas subcadeias do casamento não contenham letras marcadas}
\State Criar tile
\For{j de 0 a maxMatch-1}
\State Marcar text[t + j]
\State Marcar pattern[p + j]
\EndFor
\State lengthTiled := lengthTiled + maxMatch
\EndIf
\EndFor
\EndWhile
\Return lengthTiled
\end{algorithmic}
\end{algorithm}
Neste algoritmo tenta-se criar os maiores \textit{tiles} antes dos menores. Caso um \textit{casamento} maior que os já encontrados na iteração atual seja encontrado, os outros são descartados.
Podemos dividir o \hyperref[alg:gst]{algoritmo do GST} em duas partes. A primeira, que chamaremos de \textit{scanPattern}, é representada pelo laço da 4 à 11 e busca os maiores \textit{casamentos} possíveis. A segunda, que chamaremos de \textit{markArrays}, é representada pelo laço das linhas 12 à 18 e \textit{marca} as \textit{letras} dos \textit{tiles} formados.
\label{sec:gst2}
Como provado em \cite{wise1993string}, o pior caso para o GST possui complexidade $O(n^3)$. Algumas técnicas podem ser utilizadas para melhorar o desempenho dele. Entre elas estão:
\begin{itemize}
\item A estrutura de dados utilizada para armazenar as \textit{letras}, tanto de \textit{pattern} quanto de \textit{text}, deverá conter um ponteiro para a próxima \textit{letra} não \textit{marcada}. Dessa forma, a cada novo \textit{tile} criado, menor será o espaço de busca;
\item Se a distância do ponteiro atual até o próximo \textit{tile} for menor do que o valor atribuído ao \textit{tamanho mínimo de casamento}, ir para a primeira posição após o \textit{tile}, já que um \textit{casamento} menor que \textit{tamanho mínimo de casamento} deve ser ignorado;
\item Utilizar o algoritmo \hyperref[sec:karpRabin]{Karp-Rabin} para a criação de valores de \textit{hash} para todas as \textit{subcadeias} de \textit{pattern} e \textit{text} do tamanho da variável \textit{maxMatch}, que indica o tamanho do \textit{casamento} buscado na atual iteração.
\end{itemize}
\subsection{\textit{Algoritmo Running-Karp-Rabin Greedy String Tilling}}
\label{sec:rkrgst}
As otimizações do \hyperref[sec:gst]{GST} serviram de base para a criação do RKR-GST. O algoritmo chamado Running-Karp-Rabin foi criado e utilizado, em que invés de criarmos um valor de hash para \textit{pattern}, como no \hyperref[sec:karpRabin]{Karp-Rabin}, criamos uma para cada \textit{subcadeia}, formada por \textit{letras} não \textit{marcadas}, de tamanho \textit{s}.
Outra mudança significativa está na escolha do tamanho \textit{s} utilizado a cada iteração. Ao invés de ser decrementado até alcançar \textit{tamanho mínimo de casamento}, seu valor na próxima iteração é decidido através de uma estimativa. Esta estimativa será comentada posteriormente.
De forma simplificada podemos descrever o RKR-GST pelo algoritmo abaixo:
\begin{enumerate}
\item Criar valores de \textit{hash} para todas as \textit{subcadeias} de \textit{text} e de \textit{pattern}, contendo apenas letras não \textit{marcadas}, de tamanho \textit{s}. Para reduzir o custo de comparação, uma tabela de hash é criada para armazenar todas as \textit{subcadeias} de \textit{text} utilizando seus valores de \textit{hash} para o posicionamento na tabela;
\item Comparar os valores de hash de todas as \textit{subcadeia} de tamanho \textit{s} de ambas as \textit{palavras}. Caso sejam iguais há uma grande chance das \textit{subcadeia} serem iguais, ou seja, são candidatas a formarem um \textit{casamento}. Posteriormente comparamos as duas \textit{subcadeia}, \textit{letra} a \textit{letra} para verificar se o \textit{casamento} ocorre. Assim como no \hyperref[sec:gst]{GST}, comprovada a existência de um \textit{casamento}, tenta-se transformá-lo em um \textit{casamento maximal};
\item Repetir os passos 1 e 2 até que o tamanho buscado \textit{s} seja igual a \textit{tamanho mínimo de casamento}.
\end{enumerate}
Vale ressaltar que, no algoritmo original os \textit{casamentos maximais} de tamanhos diferentes são guardados em listas diferentes. Na implementação foi utilizada apenas uma lista ordenada pelo tamanho.
%%%---------------------------------------------------------------------------
Sendo \textit{s} o tamanho das \textit{subadeias} buscadas na iteração atual, o algoritmo que marca os \textit{tiles} é apresentado no Algoritmo 3:
\begin{algorithm} [H]
\caption{markArrays}
\label{markArrays}
\begin{algorithmic}[1]
\ForAll {Fila de \textit{casamentos}}
\While { Fila atual não é vazia }
\State Remova um \textit{casamento(p, t, l)} da fila
\If{\textit{Match} não possui \textit{letras} \textit{marcadas}}
\For{(i = 0 ; i $<$ l; i++)}
\State Marcar \textit{$pattern_{p+i}$}
\State Marcar \textit{$text_{t+i}$}
\EndFor
\State lengthOfTokensTiled = lengthOfTokensTiled + l
\ElsIf{Tamanho do trecho não \textit{marcado} do \textit{casamento} $>=$ s}
\State Guardar trecho não \textit{marcado} na lista adequada ao seu tamanho.
\EndIf
\EndWhile
\EndFor
\end{algorithmic}
\end{algorithm}
O Algoritmo 4 apresenta o pseudocódigo do \textit{scanPattern}.
%%%---------------------------------------------------------------------------
\begin{algorithm} [H]
\caption{scanPattern(s)}
\label{alg:scanPattern}
\begin{algorithmic}[1]
\ForAll {\textit{letra}, não \textit{marcada}, \textit{t} de \textit{text}}
\If{ Distância para o próximo \textit{tile} de \textit{text} for menor do que \textit{s}}
\State Ir para primeira \textit{letra} após o próximo \textit{tile}
\Else
\State Criar valor de \textit{hash} para a \textit{subcadeia} de \textit{text} que começa na posição \textit{t} e possui tamanho \textit{s}.
\EndIf
\EndFor
\ForAll {\textit{letra}, não \textit{marcada}, \textit{p} de \textit{pattern}}
\If{Distância para o próximo \textit{tile} de \textit{pattern} for menor do que \textit{s}}
\State{Ir para primeira \textit{letra} após o próximo \textit{tile}}
\Else
\State Criar valor de \textit{hash}, patternHash, utilizando o \hyperref[sec:karpRabin]{Karp-Rabin} para a \textit{subcadeia} que começa na posição \textit{p} de \textit{pattern} e possui \textit{s} letras.
\ForAll {Entrada da tabela de \textit{hash}, textHash, igual a patternHash}
\If{Todas as letras das \textit{subcadeia} representadas por patternHash e textHash forem iguais, ou seja, se o match for confirmado }
\State k = s
\While{pattern[p + k] = text[t + k] E pattern[p+k] não for \textit{marcado} E text[t + k] não for \textit{marcado}}
\State k++
\EndWhile
\If{$k > 2* s$}
\State return k(recomeçar o scanPattern com s = k)
\Else
\State registar novo maximalMatch guardado-o em uma fila.
\EndIf
\EndIf
\EndFor
\EndIf
\EndFor
\State return $|maximalMatch|$
\end{algorithmic}
\end{algorithm}
%%%---------------------------------------------------------------------------
O Algoritmo 5 representa o algoritmo RKR-GST. Ao contrário do algoritmo GST ele tenta alterar o tamanho do \textit{casamento} buscado em cada iteração através de uma estimativa estática. Isto é feito através de comparações entre o tamanho buscado, o tamanho encontrado e o tamanho mínimo para o \textit{casamento}.
\begin{algorithm} [H]
\label{alg:RKR-GST}
\begin{algorithmic}[1]
\caption{Running-Karp-Rabin Greedy String Tilling}
\State searchLength s = initialSearchLength
\While{true}
\State maxLength = scanPattern(s)
\If{$maxLength > 2 \times s$}
\State s = maxLength
\Else
\State markArrays(s)
\If{$s > 2 \times minimumMatchLength$}
\State $s = s / 2$
\ElsIf{$s > minimumMatchLength$}
\State s = minimumMatchLength
\Else
\State break\;
\EndIf
\EndIf
\EndWhile
\end{algorithmic}
\end{algorithm}
%%%---------------------------------------------------------------------------
\section{Abordagem}
\nameOfProgram \ foi escrito de forma a permitir a fácil adaptação para a detecção de plágio em código-fonte. Esta facilidade se deve ao uso de classes paramétricas cujo parâmetro do template é o tipo ou classe que representa a \textit{letra} utilizada. Dessa forma, para a detecção de plágio em textos este parâmetro do template será um caractere, enquanto para códigos-fonte será o token gerado após a análise léxica da linguagem de programação do código-fonte. Esta seção descreve as decisões do projeto e os resultados dos testes realizados para avaliar a ferramenta. A figura 3 ilustra as classes difinidas no projeto.
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.3]{doxygenDocumentation.png}
\end{center}
\caption{\small Exemplo de documentação gerada pelo Doxygen.}
\end{figure}
\subsection{Decisões de Projeto}
A seguir, são apresentadas as principais decisões de projeto tomadas para a implementação do \nameOfProgram.
\subsubsection{Classes Criadas}
Uma descrição de cada classe é apresentada a seguir:
\begin{itemize}
\item Reader: responsável pela leitura dos arquivos que contém \textit{text} e \textit{pattern} para o seu posterior tratamento. Para a detecção de plágio em textos, após construção de um objeto desta classe, o método filesToBox deve ser executado. Este método faz a leitura de \textit{text} e \textit{pattern} e agrupa as informações destes arquivos que serão úteis durante toda a execução do programa em um objeto da classe Box. Para a detecção de plágio em códigos-fonte será necessário implementar um método que faça a \textit{tokenização} do conteúdo dos arquivos antes de grupar esses dados em um objeto da classe Box;
\item Box: classe que agrupa informações sobre os dados de entrada previamente tratados pelo Reader. Esta classe possui um vetor de \textit{letras} de \textit{text}, um vetor de \textit{letras} de \textit{pattern} e duas variáveis inteiras que representam os tamanhos de cada vetor;
\item RandomNumber: classe que gera número aleatórios. Utilizada para a criação de números primos aleatórios;
\item RandomPrime: classe que gera números primos aleatórios utilizando os números aleatórios criados por um objeto da classe RandomNumber;
\item (*)Letter: classe parametrizada que representa uma \textit{letra}. Possui como atributos seu conteúdo, uma variável binária que representa se a letra está \textit{marcada} ou não e ponteiros para as próxima e prévia letras \textit{marcadas} dentro de uma estrutura externa que a \textit{letra} em questão se encaixa;
\item Match: representação de um \textit{casamento}, possuindo as três informações que a caracteriza: tamanho, posição inicial em \textit{pattern} e posição inicial em \textit{text}. Além disto, possui ponteiros para \textit{casamentos} anteriores e posteriores ao objeto em questão, o que é útil quando este faz parte de uma estrutura externa que o engloba;
\item (*)Substring: classe que representa uma \textit{subcadeia} da \textit{palavra} que será comparada a outra. Possui ponteiros para \textit{subcadeias} anteriores e posteriores, útil quando o objeto desta classe for parte de uma estrutura de dados maior;
\item Tile: classe que representa uma \textit{subcadeia} casada de forma definitiva. Possui apenas informações sobre suas posições inicial e final, além de ponteiros para \textit{tiles} anteriores e posteriores a este quando fizer parte de uma estrutura que o engloba;
\item ListOfMatches: em \cite{wise1993string}, foi criada uma lista diferente para \textit{casamentos} de tamanhos diferentes, dando preferência a listas com \textit{casamentos} maiores durante a criação de \textit{tiles}. Neste trabalho optou-se por utilizar apenas uma lista ordenada em ordem decrescente;
\item (*)ListOfSubstrings: lista de \textit{subcadeias};
\item ListOfTiles: uma lista contendo todos os \textit{tiles} criados;
\item (*)RollingHash: classe que gerencia as operações do algoritmo RollingHash. Para todo objeto desta classe os valores da base e o número primo utilizados devem ser os mesmos;
\item (*)HashTable: cria uma tabela de hash cujo número de entradas possíveis é igual ao número primo utilizado pela RollingHash;
\item (*)RKRGST: classe que implementa o algoritmo RKR-GST, possuindo três métodos: o \textit{markArrays}, o \textit{scanPattern} e o \textit{execute}. Este último é o que executa o RKR-GST através de chamadas dos dois métodos anteriores.
\end{itemize}
O símbolo (*) indica as classes que utilizam templates referentes ao tipo ou classe que representa a \textit{letra}.
\subsubsection{Outras Decisões de Projeto}
Para quantificar a taxa de similaridade à partir dos \textit{tiles} encontrados através do método \textit{execute} da classe RKR-GST utilizamos a fórmula proposta em \cite{djuric2012source}:
$similaridade (a, b)$ = $ (2 * numberOfTokensTiled) / (length(a) + length (b))$
A similaridade quantifica o proporção da porção semelhante entre as duas \textit{palavras} comparadas em relação ao tamanho total delas. Uma similaridade de 100\% significa que a porção semelhante em cada uma das \textit{palavras} é equivalemente a \textit{palavra} inteira.
O acréscimo de uma operação modular entre cada operação realizada, como foi explicado na [ \hyperref[sec:rollingHash]{Seção 2.4}, serve para evitar o estouro da variável, que armazena o valor da hash, gerada pelo conjunto de operações feitas para remover ou adicionar uma letra na RollingHash. Mesmo que não tenha sido alertado em \cite{wise1993string}, durante a implementação deste trabalho foi descoberto que uma só operação pode facilmente provocar o estouro de uma variável por causa da grandeza dos operandos. Para evitar que isto ocorra o valor da base, a princípio o tamanho do alfabeto utilizado, foi alterado de 256 para 2.
Após um deslocamento à direita da \textit{janela}, a \textit{letra} que deixa de pertencer a janela é a de algarismo mais significativo numericamente. Para a remoção do valor desta \textit{letra} no valor de hash utilizamos, entre outras operações matemáticas, a operação $base^{|s| -1}$(mais detalhes na \hyperref[sec:rollingHash]{Seção 2.4}). Mesmo que o valor da base tenha passado de 256 para 2, o valor desta expressão cresce exponencialmente e quando \textit{s} é muito grande, podendo ultrapassar o tamanho máximo possível para uma variável. Para contornar o problema limitamos o tamanho máximo das \textit{subcadeias} através de uma constante. Esta alteração não possui muita influência na taxa de similaridade, já que se analisarmos a fórmula utilizada não importa quantos \textit{tiles} sejam criados, mas o somatório dos seus tamanhos.
Se cada variável tivesse tamanho infinito, e dessa forma não fosse necessário a utilização de operações modulares, cada palavra possuiria um valor de hash único. O uso das operações modulares e de uma base muito menor do que a desejável criaram valores de hash iguais para algumas palavras diferentes, o que deixou código um pouco menos eficiente já que a linha 12 do \hyperref[alg:scanPattern]{algoritmo \textit{scanPattern}} será executada mais vezes sem que isto signifique a existência de mais \textit{casamentos}.
Os caracteres dos arquivos referentes a \textit{text} e \textit{pattern} foram lidos como caracteres sem sinal já que alguns deles possuem valor maior do que 127 fazendo com que necessitem utilizar o bit mais significativo do byte para a sua representação, tornando-os negativos.
\subsection{Testes Realizados}
Em \cite{djuric2012source} são descritas modificações utilizadas na criação de versões plagiadas de um código-fonte original. São elas:
\begin{itemize}
\item Modificações léxicas:
\begin{itemize}
\item Modificação do formato do código fonte;
\item Adição, remoção ou modificação de comentários;
\item Modificação da linguagem do código;
\item Modificação do formato de saída do programa;
\item Renomeação de identificadores;
\item Quebra ou junção de declarações de variáveis;
\item Adição, remoção ou modificação de modificadores; e
\item Modificação de valores de constantes.
\end{itemize}
\end{itemize}
\begin{itemize}
\item Modificações estruturais:
\begin{itemize}
\item Mudança de ordem de variáveis na sentença;
\item Mudança de ordem de sentenças dentro de um bloco de código;
\item Reordenação de blocos de código;
\item Adição de sentenças ou variáveis redundantes;
\item Modificação das estruturas de controle;
\item Mudança de tipos de dados e modificar estruturas de dados;
\item Refatoração de métodos;
\item Redundância em geral; e
\item Variáveis temporárias.
\end{itemize}
\end{itemize}
Muitas das alterações citadas poderiam ser detectadas somente através de uma prévia tokenização da entrada, sendo necessário para isto a implementação de análise léxica para o português, inglês ou outra linguagem escolhida. Isto tornaria a detecção mais precisa, mas o intuito deste trabalho é base para um futuro detector de plágio em códigos-fonte, não textos simples. Mesmo com essas restrições, duas modificações foram testadas: acréscimo de redundância; e reordenação de trecho.
Para a realização dos testes foi utilizado o conteúdo publicado no site \cite{slashDot}. As notícias publicadas neste site são sumários de notícias de outros sites que são enviados por leitores. Esses sumários são avaliados pelos editores antes de serem publicados ou descartados.
Foram utilizados seis sumários para os testes. Os seguintes arquivos foram criados para cada sumário:
\begin{itemize}
\item \texttt{resume.txt}: o sumário publicado no site Slash Dot;
\item \texttt{original.txt}: a notícia original;
\item \texttt{reordering.txt}: o sumário com trechos fora de ordem;
\item \texttt{redundancy.txt}: o sumário com acréscimo de trechos quaisquer; e
\item \texttt{redundancyAndReordering.txt}: o sumário incluso fora de ordem em um texto qualquer.
\end{itemize}
Os arquivos gerados foram agrupados de acordo com o sumário que o originou. Para cada grupo o respectivo arquivo \texttt{resume.txt} foi comparado aos outros arquivos gerados utilizando o valor 7 como \textit{tamanho mínimo de casamento} e o valor 10 como o tamanho de \textit{casamento} inicialmente buscado. Para cada comparação, o tempo gasto em milissegundos e a similaridade foram registrados. Abaixo os resultados encontrados:
% Please add the following required packages to your document preamble:
% \usepackage[table,xcdraw]{xcolor}
% If you use beamer only pass "xcolor=table" option, i.e. \documentclass[xcolor=table]{beamer}
% Please add the following required packages to your document preamble:
% \usepackage[table,xcdraw]{xcolor}
% If you use beamer only pass "xcolor=table" option, i.e. \documentclass[xcolor=table]{beamer}
\begin{table}[H]
\label{table:tests}
\begin{tabular}{llll}
Grupo & Comparação & Tempo & Similaridade \\
\rowcolor[HTML]{CBCEFB}
1 & resume X reordering & 25,79 & 94,2\% \\
\rowcolor[HTML]{CBCEFB}
1 & resume X redundancy & 30,29 & 60,6\% \\
\rowcolor[HTML]{CBCEFB}
1 & resume X redundancyAndReordering & 31,22 & 59,9\% \\
\rowcolor[HTML]{CBCEFB}
1 & resume X original & 33,34 & 30,5\% \\
2 & resume X reordering & 12,33 & 95,0\% \\
2 & resume X redundancy & 26,85 & 40,4\% \\
2 & resume X redundancyAndReordering & 54,15 & 40,2\% \\
2 & resume X original & 31,11 & 28,5\% \\
\rowcolor[HTML]{CBCEFB}
3 & resume X reordering & 12,46 & 94,3\% \\
\rowcolor[HTML]{CBCEFB}
3 & resume X redundancy & 27,44 & 39,9\% \\
\rowcolor[HTML]{CBCEFB}
3 & resume X redundancyAndReordering & 52,69 & 39,9\% \\
\rowcolor[HTML]{CBCEFB}
3 & resume X original & 20,29 & 24,4\% \\
4 & resume X reordering & 15,24 & 92,1\% \\
4 & resume X redundancy & 16,46 & 57,0\% \\
4 & resume X redundancyAndReordering & 20,06 & 57,0\% \\
4 & resume X original & 35,11 & 27,2\% \\
\rowcolor[HTML]{CBCEFB}
5 & resume X reordering & 15,18 & 94,9\% \\
\rowcolor[HTML]{CBCEFB}
5 & resume X redundancy & 44,47 & 34,5\% \\
\rowcolor[HTML]{CBCEFB}
5 & resume X redundancyAndReordering & 54,08 & 34,5\% \\
\rowcolor[HTML]{CBCEFB}
5 & resume X original & 15,12 & 44,6\% \\
6 & resume X reordering & 8,31 & 93,2\% \\
6 & resume X redundancy & 35,85 & 26,2\% \\
6 & resume X redundancyAndReordering & 56,41 & 26,2\% \\
6 & resume X original & 43,14 & 15,2\%
\end{tabular}
\caption[Resultado dos testes]{Resultado dos testes}
\end{table}
Na \hyperref[table:tests]{Tabela 1} pode-se perceber que a mudança de ordem (\texttt{reordering.txt} e \texttt{redundancyAndReordering.txt}) em uma \textit{palavra} não é um empecilho para a detecção do plágio, já que, após a mudança de ordem em do sumário(\texttt{reordering.txt}), a pior similaridade encontrada foi de 93,2\% e a mudança de ordem após a geração de redundância no resumo (\texttt{redundancyAndReordering.txt}) teve uma influência ínfima na similaridade.
A geração de redundância teve uma grande influência na similaridade, mas vale salientar que a redundância adicionada ao sumário em todos os grupos de teste possuíam tamanho muito superior ao tamanho do sumário. Criar redundâncias deste porte em códigos-fonte de tamanho médio e grande requerem grande esforço, além de, pela quantidade de \textit{letras} necessárias, se tornar perceptível facilmente.
\section{Considerações Finais}
Através deste trabalho foi possível criar o programa \nameOfProgram. Ele possui licença GNU GPL e é melhor documentado do que o Plaggie, outro programa que utiliza a mesma licença, o que facilita o seu estudo e extensão.
Como sugestão de trabalho futuro, está a extensão do \nameOfProgram \ para a detecção de plágio em códigos-fonte e que seja utilizado durante a correção de trabalhos práticos na Faculdade de Computação da Universidade Federal de Mato Grosso do Sul.
As alterações necessárias para que \nameOfProgram \ seja utilizado para detecção de plágio em código-fonte consistem basicamente na a alteração da classe Reader para a leitura, remoção de comentários e espaços, tokenização do código-fonte e inclusão das \textit{palavras} geradas através dos tokens criados em um objeto da classe Box.
Outra alteração importante é a sobrecarga de operadores da classe que representará o token para que possua os mesmos operadores utilizados neste trabalho em operações com \textit{letra}. Entre as operações utilizadas estão comparação entre \textit{letras} e o uso da operação de atribuição para atribuir a uma variável inteira o valor correspondente a uma \textit{letra}.
neste programa pertencentes ao tipo \textit{char}, o tipo paramétrico utilizado para a representação das \textit{letras} neste trabalho.
O código-fonte, a sua documentação e os casos de teste utilizados foram disponibilizados\footnote{Endereço eletrônico: https://github.com/iruynarak/rorschach.} via GitHub \cite{gitHub}.
\bibliographystyle{sbc}
\bibliography{sbc-template}
\end{document}
