UNIVERSIDADE CATÓLICA DE PELOTAS
ESCOLA DE INFORMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA
Adaptação do Algoritmo Levenshtein Distance
para o Cálculo de Similaridade entre Frases
por
Taís da Veiga Oliveira
Trabalho Individual I
TI-2009/2-007
Orientador Prof. Dr. Stanley Loh
Pelotas, fevereiro de 2010
SUMÁRIO
1.
INTRODUÇÃO .....................................................................................................6
1.1. OBJETIVOS..................................................................................................7
1.2. ORGANIZAÇÃO DO TEXTO ........................................................................7
2. SIMILARIDADE ENTRE STRINGS/TEXTOS.......................................................8
2.1. BUSCA APROXIMADA POR STRINGS........................................................8
2.2. REUSO DE TEXTOS E PLÁGIO ..................................................................9
3. ESTADO DA ARTE............................................................................................. 11
3.1. CONCEITOS............................................................................................... 11
3.2. TRABALHOS RELACIONADOS.....................................................................15
4. ALGORITMO LEVENSHTEIN DISTANCE .........................................................20
4.1. COMPARAÇÃO DE DIALETOS......................................................................20
4.2. CORREÇÃO ORTOGRÁFICA ........................................................................20
4.3. RECONHECIMENTO DA FALA ......................................................................21
4.4. ANÁLISE DE DNA ..........................................................................................21
4.5. VINCULAÇÃO DE REGISTROS ....................................................................21
4.6. AUTENTICAÇÃO DE ASSINATURAS ON-LINE.............................................22
5. METODOLOGIA PROPOSTA ............................................................................23
5.1. ALGORITMO ..................................................................................................23
5.2. REMOÇÃO DE STOPWORDS .......................................................................23
5.3. STEMMING ....................................................................................................23
5.4. PERCENTUAL DE SIMILARIDADE................................................................23
6. EXPERIMENTOS...............................................................................................25
7. CONCLUSÃO E TRABALHOS FUTUROS ........................................................29
8. REFERÊNCIAS..................................................................................................30
LISTA DE FIGURAS
FIGURA 1 - NÍVEIS DE REUSO DE TEXTOS (BENDERSKY, CROFT, 2009)............7
FIGURA 2 - EXEMPLO DE ÍNDICE INVERTIDO (MATOS ET AL., 2008 )................12
FIGURA 3 - FORMAÇÃO DE LRS (PITKOW, PIROLLI, 1999) .................................13
FIGURA 4 - HIPERNIMIA DA PALAVRA “AUTOMOBILE” - WORDNET (NAVEGA,
2004) .........................................................................................................................15
FIGURA 5 - RANKING PARA A STRING “ABCD” COM K = 2...................................19
FIGURA 6 - EXPERIMENTO 1..................................................................................25
FIGURA 7 - EXPERIMENTO 2..................................................................................25
FIGURA 8 - EXPERIMENTO 3..................................................................................26
FIGURA 9 - EXPERIMENTO 4..................................................................................27
FIGURA 10 - EXPERIMENTO 5................................................................................27
RESUMO
Este trabalho sugere a aplicação do algoritmo Levenshtein Distance para a
identificação de similaridade entre frases. Na literatura, este algoritmo tem sido aplicado
considerando caracteres como unidade básica para o cálculo da distancia entre duas strings.
Este artigo sugere a aplicação desta técnica para o cálculo da distância entre frases, tomando
como unidade básica de comparação base as próprias palavras.
Palavras-chave: Algoritmo Levenshtein Distance, Similaridade, String
TITLE: “Proposal Adaptation Algorithm Levenshtein Distance
for the calculation of similarity between phrases”
ABSTRACT
This work suggests an adaptation of the Levenshtein Distance algorithm for the
identification of similarity between sentences. In literature, this algorithm has been applied
considering characters as the basic unit for calculating the distance between two strings. This
article suggests the application of this technique to calculate the distance between sentences,
taking as the basic unit of comparison own words.
Keywords: Algorithm Levenshtein Distance, Similarity, String.
6
1. INTRODUÇÃO
Com o acesso cada vez mais facilitado às mídias digitais, tem ocorrido também um
grande acúmulo de informações, muitas vezes, semelhantes ou até mesmo idênticas, estando
as mesmas armazenadas localmente ou disponíveis na Web.
O reuso de textos pode ter diversas abordagens. Na Internet, é bastante comum que
sejam encontradas informações semelhantes, um exemplo disso são os portais de notícias, que
costumam disponibilizar as mesmas informações escritas de formas diferentes. Documentos
idênticos também podem ser facilmente encontrados na Web, devido ao fato de terem sido
armazenados por diversas fontes diferentes. Outra abordagem do reuso ocorre no ambiente
corporativo, principalmente no que se trata de grandes organizações. Muitas vezes, em um
ambiente distribuído, onde equipes distintas contribuem com o mesmo repositório de
informações, o número de duplicações pode ocasionar um volume bastante extenso de
conteúdo, dificultando o posterior gerenciamento destas informações.
Atualmente, na Internet, um grande número de textos com conteúdos semelhantes ou
relacionados estão sendo produzidos todos os dias, muitas vezes, através do reuso de outros
textos. Sentenças, frases ou fatos são copiados de outros documentos e alterados, ou, muitas
vezes, nem chegam a ser modificados.
Enquanto que copiar um texto e reutilizá-lo pode ser considerado por alguns como
uma forma de plágio, é freqüentemente uma prática completamente legal (PIAO; MCENERY,
2003, p. 637). O reuso de textos pode indicar até mesmo a qualidade de uma informação,
considerando que, uma vez que a mesma foi afirmada por mais de um autor, existem maiores
probabilidades de que esteja correta.
Bendersky e Croft (2009) sugerem três níveis do reuso de textos. O primeiro nível é a
duplicação da sentença, ou seja, um fragmento do texto é escrito de forma exatamente igual
ao encontrado no texto original. O segundo nível representa uma reafirmação do mesmo fato,
porém reformulações e adição de outras informações. Por último, o terceiro nível caracteriza
apenas uma semelhança tópica com a frase original. A Figura 1, mostra uma tabela, disponível
neste mesmo trabalho, que exemplifica a diferença entre estes 3 níveis. Na imagem, a
sentença original é mostrada em negrito e as categorias C1, C2 e C3 representam os três tipos
de reuso descritos.
7
Figura 1 - Níveis de Reuso de Textos (BENDERSKY, CROFT, 2009)
1.1. Objetivos
Este trabalho tem como objetivo principal realizar um estudo sobre o Estado da Arte
da comparação entre textos, sentenças e strings.
Seus objetivos específicos consistem em:
•
Estudar as técnicas utilizadas atualmente, considerando a finalidade descrita
anteriormente;
•
Propor uma adaptação do algoritmo Levenshtein Distance, utilizando as próprias
palavras como unidade básica para a comparação;
•
Identificar, nas técnicas estudadas, possíveis aperfeiçoamentos para o algoritmo
proposto.
1.2. Organização do texto
O texto está organizado da seguinte forma. No capítulo 2, são abordados o reuso de
textos e o plágio, descrevendo algumas das técnicas utilizadas atualmente com a finalidade de
identificar estes tipos de similaridade. O capítulo 3 descreve o algoritmo Levenshtein
Distance, em sua forma original, bem como algumas de suas aplicações. No capítulo 4, é
proposta uma adaptação deste algoritmo. Por último, no capítulo 5, são mostrados os
resultados de alguns testes realizados com base no algoritmo proposto.
8
2. SIMILARIDADE ENTRE STRINGS/TEXTOS
Dados texto são ubíquos. A gestão de dados texto em bancos de dados e sistemas de
informação tem recebido uma particular importância recentemente (HADJIELEFTHERIOU,
LI, 2009).
Atualmente, têm sido estudados diversos temas relacionados à identificação de
similaridade entre strings ou textos. Dentre eles pode-se citar: busca aproximada por strings e
a detecção de plágios e reuso de textos.
2.1.
Busca aproximada por strings
Dada uma coleção de strings, a busca aproximada por strings tem o objetivo de
identificar, de forma eficiente, strings similares àquelas informadas em uma dada consulta.
Abaixo, são listadas algumas de suas aplicações.
Flexibilização de consultas (Query Relaxation) – Muitas vezes, ao serem executadas
consultas, os termos de busca não coincidem com os dados existentes no banco de dados.
Estas divergências podem ter diversas causas, dentre elas erros nos termos utilizados na
consulta ou conhecimento limitado do usuário sobre o assunto pesquisado, inconsistências nos
dados da base de dados, entre outros motivos. A partir da Query Relaxation, é possível
retornar dados potencialmente interessantes ao usuário, com base na similaridade destes com
os especificados na consulta.
Limpeza de dados (Data Cleaning) – Informações provenientes de diversas fontes podem
acarretar em dados inconsistentes, ou seja, um mesmo objeto do mundo real pode ter diversas
representações. Estas inconsistências podem ser geradas por inúmeros motivos, como erros no
processo de coleta de dados ou falhas humanas. A limpeza de dados tem o objetivo o de
detectar, e, então, corrigir ou remover os registros incorretos ou imprecisos. Por estas razões,
uma das principais metas do Data Cleaning é encontrar entidades similares em uma coleção,
ou todos os pares de entidades similares em várias coleções (HADJIELEFTHERIOU, LI,
2009).
9
Verificação ortográfica (Spell Checking) – Neste processo, com base em uma determinada
entrada, um corretor ortográfico identifica possíveis candidatos para uma palavra digitada
incorretamente.
Busca interativa (Interactive Search) – uma importante muito importante aplicação recente é
fornecer respostas para os resultados da consulta em tempo real, como os usuários estão
digitando a sua consulta. Essas caixas de pesquisa interativa são ubíquas e têm se mostrado
muito importantes na prática, porque limitam o número de erros cometidos pelos usuários e
também reduzem o número de reformulações consulta enviada a fim de encontrar o que trará
resultados satisfatórios (HADJIELEFTHERIOU, LI, 2009).
2.2.
Reuso de Textos e Plágio
Na literatura, existem diversos trabalhos cujo foco é a identificação de similaridade
entre textos. Muitos destes trabalhos abordam esta similaridade como identificação do reuso
das informações, outros, porém, tratam como forma de detecção de plágios.
Conforme Uzuner, Katz e Nahnsen (2005), Plagiar é "roubar e passar as idéias ou
palavras de outro, como o próprio; para utilizar a produção de outro, sem creditar a fonte, ou
para cometer roubo literário pela apresentação de uma nova e original idéia ou produto
derivado de uma fonte existente.
O plágio tem se tornado um fato bastante comum, principalmente, entre a comunidade
acadêmica, o que acaba por ocasionar uma diminuição na qualidade do ensino, sobretudo nos
ambientes de EAD.
O reuso de textos também tem sua contribuição negativa. No ambiente corporativo,
principalmente, em grandes organizações, é comum que a duplicação das informações acabe
por gerar um repositório bastante grande, aumentando a dificuldade para o gerenciamento
deste conteúdo. Os motores de busca, da Internet, também sofrem a influência negativa desta
duplicação, pois, geralmente, seus usuários não desejam encontrar informações repetidas.
Por outro lado, o reuso de textos pode representar uma característica da qualidade da
informação, partindo-se do princípio de que, quanto mais autores afirmarem o mesmo fato,
maior é a probabilidade de que a mesmo seja verídico.
Independentemente da abordagem adotada, os métodos utilizados para identificação de
10
similaridade entre textos são bastante semelhantes, podendo serem aplicados em ambas as
abordagens, dependendo apenas da aplicação que se deseja dar a eles. A seguir, são descritos
alguns temas, encontrados na literatura, referentes à identificação de similaridade entre textos.
Para comparar dois ou mais documentos e raciocinar sobre o grau de similaridade
entre eles, é necessário atribuir valor numérico, chamados escore de similaridade, para cada
documento. Este escore pode ser baseado em diferentes métricas. Há muitos parâmetros e
aspectos do documento que podem ser utilizados como métricas (LUKASHENKO,
GRAUDINA, GRUNDSPENKIS, 2007).
Existem diversos métodos para a comparação de textos, podendo ser classificados em
métodos estatísticos ou semânticos. Os métodos estatísticos não consideram o significado dos
documentos. Geralmente, são baseados em vetores que contém termos selecionados a partir
de características como, por exemplo, a freqüência com que estes termos ocorrem no
documento. Quanto aos métodos semânticos, normalmente, costumam possuir uma maior
complexidade, devido à análise mais aprofundada do relacionamento entre as palavras do
texto, considerando aspectos como a morfologia das palavras, a estrutura sintática e semântica
das frases.
11
3. ESTADO DA ARTE
Nesta seção, serão comentados alguns dos trabalhos realizados recentemente, que
estão relacionados com a identificação de similaridade entre strings ou textos. Para uma
melhor compreensão, primeiramente, são especificados os principais conceitos abordados
nestes trabalhos, em seguida, é apresentada um resumo dos mesmos.
3.1.
Conceitos
A seguir são apresentados alguns conceitos que serão abordados ao longo do presente
trabalho.
Stopwords - Em um documento, existem muitos tokens que não possuem nenhum valor
semântico, sendo úteis apenas para o entendimento e compreensão geral do texto. Estes
tokens são palavras classificadas como stopwords e fazem parte do que é chamado de stoplist
de um sistema de Mineração de Textos (BASTOS, 2006, apud JUNIOR, 2007, p. 46). Uma
stoplist bem elaborada permite a eliminação de muitos termos irrelevantes, tornando mais
eficiente o resultado obtido pelo processo de Mineração de Textos. Normalmente, 40 a 50%
do total de palavras de um texto são removidas com uma stoplist (SILVA, 2007, apud
JUNIOR, 2007, p. 46).
Stemming ou lematização - Qualquer documento textual apresenta muitas palavras
flexionadas nas mais diversas formas. Na Língua Portuguesa, um substantivo pode ser
flexionado em gênero, número e grau, e apresentar o mesmo valor semântico. O processo de
formação de palavras é, na maior parte das vezes, realizado pela derivação de radicais,
resultando na criação de palavras que também exprimem o mesmo significado (CEGALLA,
2005, apud JUNIOR, 2007, p. 49). O processo de lematização consiste em reduzir uma
palavra ao seu radical.
Fingerprints - Fingerprints são pequenas unidades de texto, que podem se tratar de
substrings ou mesmo subsequências de palavras são convertidas para a sua forma numérica
através de algoritmos de hashing, como, por exemplo, o MD5 e o Rabin fingerprinting.
12
Modelo de Índice Invertido – Um banco de dados textual é uma coleção de documentos, que
pode ser representada por um conjunto de registros. Cada registro contém uma lista de
palavras. Uma estratégia de recuperação textual é comparar a lista de palavras de uma
consulta com a lista de palavras dos registros. Entretanto, em grandes coleções a comparação
direta da consulta com todos os registros é computacionalmente cara. Com o objetivo de
acelerar este cálculo, limitando a comparação a um subconjunto de registros, utiliza-se o
índice invertido (MATOS et al. apud ZOBEL, 1998). Esta técnica baseia-se na utilização de
vetores. O índice invertido possui duas partes principais: uma estrutura de busca, chamada de
vocabulário, contendo todos os termos distintos existentes nos textos indexados e, para cada
termo, uma lista invertida que armazena os identificadores dos registros contendo o termo
(MATOS et al. apud BAEZA-YATES, 1999).
Figura 2 - Exemplo de Índice Invertido (MATOS et al., 2008 )
Modelo de Representação Vetorial - No Modelo de Representação Vetorial, o
processamento de uma consulta é realizado através de um cálculo de similaridade entre cada
documento da coleção e a própria consulta, ou seja, toda consulta é também representada de
forma vetorial, e através de um cálculo de similaridade entre cada documento da coleção e a
consulta, obtém-se uma lista dos documentos relevantes para aquela necessidade de
informação (SOARES, 2008).
Latent Semantic Indexing - O processo denominado Latent Semantic Indexing (LSI) é uma
técnica que permite encontrar uma estrutura semântica associada a uma coleção de
documentos indexados em uma matriz. Para isso, leva-se em conta não apenas a ocorrência
dos termos em documentos, mas a co-ocorrência desses termos, isto é, conjuntos de termos
13
que freqüentemente são encontrados nos mesmos documentos. (OLIVEIRA, OLIVEIRA)
Longest Repeating Sequences – A técnica LRS (Longest Repeating Sequences) tem o
objetivo de identificar padrões significativos de navegação. A seguir é apresentado um
exemplo retirado de (PITKOW, PIROLLI, 1999).
Figura 3 - Formação de LRS (PITKOW, PIROLLI, 1999)
Na ilustração 3, as setas mais grossas indicam mais de uma passagem, ao contrário das
setas mais finas, que ilustram apenas uma passagem. Supondo a existência de um website que
contém as páginas A, B, C e D, onde A contém um hiperlink para B e B contém hiperlinks
para C e D. Se os usuários, repetidamente, navegarem de A para B, mas somente um usuário
navegar para C e apenas um usuário navegar para D (caso 1), a LRS será AB. Se, no entanto,
mais de um usuário clicar em D através de D (caso 2), então AB e ABD serão as LRSs. Neste
caso, AB é uma LRS, desde que, em outra ocasião, AB não tenha sido seguido por ABD. No
terceiro caso, ABC e ABD são LRSs, uma vez que ambas ocorrem mais de uma vez. No
quarto caso, AB não é uma LRS, uma vez que nunca é a longest repeating subsequence.
Algoritmo Smith-Waterman - Baseado em programação dinâmica, o algoritmo SmithWaterman é um método utilizado para o alinhamento de seqüências local, ou seja, o mesmo
identifica as regiões comuns em seqüências que compartilham características locais de
similaridade. É considerado o algoritmo mais preciso de alinhamento de seqüência disponível,
mas a sua complexidade computacional o torna bastante lento.
Processamento de Liguagem Natural - O PLN (Processamento de Liguagem Natural) é uma
14
área da Inteligência Artificial, que lida com problemas relacionados à automação da
interpretação e da geração da língua humana em diversas aplicações. Este processo,
geralmente, pode ser constituído por 4 diferentes etapas de análise. Na análise morfológica,
são identificadas palavras ou expressões isoladas em uma sentença, sendo através de
delimitadores (pontuação e espaços em branco). Estas palavras, são, então, classificadas de
acordo com a sua categoria gramatical. A análise sintática tem como objetivo a construção de
árvores de derivação para cada sentença, mostrando o relacionamento das palavras entre si.
Porém, esta análise não tem nenhuma relação com a semântica das palavras, uma vez que uma
frase pode ser, gramaticamente, correta, mas não ser compreensível. O objetivo da análise
semântica, então, é identificar os conceitos semânticos da frase, com base na árvore gerada
pela análise sintática. Geralmente, o conteúdo das frases estão relacionados com as
propriedades de um evento como "onde", "quando", "o que", "quem", "como", etc. Na análise
pragmática, é realizada a interpretação do todo, não mais o significado apenas de suas partes.
Wordnet - WordNet é uma Base de Dados Léxica que contém informações sobre palavras,
palavras compostas, verbos, frases idiomáticas, relações hierárquicas entre palavras e outras
propriedades. Essa base de dados possui, por exemplo, informações sobre sinônimos (palavras
diferentes que significam a mesma coisa), hiperônimos/hipônimos (a derivação hierárquica
das palavras), merônimos (as “partes” associadas ao sentido de uma palavra), etc. Com o
WordNet diversas aplicações tornam-se possíveis, não apenas na recuperação de informação
mas também na análise do significado de frases (NAVEGA, 2004).
15
Figura 4 - Hipernimia da palavra “automobile” - Wordnet (NAVEGA, 2004)
Escores de Similaridade - Funções de comparação retornam escores de similaridade entre
segmentos de texto. A partir destes escores, é considerado um limiar, geralmente, estabelecido
pelo usuário, para determinar se um determinado segmento de texto é ou não similar a outro.
3.2. Trabalhos Relacionados
Em Seo e Croft (2008), a quantidade de conteúdo compartilhado entre dois
documentos se dá pelo número de fingerprints compartilhados entre os mesmos pelo total de
fingerprints do documento base da comparação. Se o total de fingerprints compartilhados
forem superiores a 80%, 50% ou 10%, considera-se, respectivamente, que o texto de um
documento A foi muito, consideravelmente, ou parcialmente reutilizado em um documento B.
Para encontrar os documentos com relação de reuso, é gerado um índice invertido com os
fingerprints extraídos dos documentos e, então, feito o merge destes documentos. O tamanho
16
da lista invertida é o total de fingerprints mais frequentes nos documentos, porém, para uma
comparação mais eficiente, podem ser definidas uma lista de “stop-fingerprints”, cuja função
é idêntica às stopwords. Segundo os autores, boas técnicas de fingerprinting devem gerar
fingerprints que representem fielmente os documentos (precisão) e gerar o menor número
possível de fingerprints (eficiência). Com base nestes princípios, existem dois tipos de
métodos: métodos de sobreposição e métodos de não-sobreposição.
Os métodos de
sobreposição utilizam o conceito de janela deslizante. Basicamente, a janela é deslocada por
uma palavra, e uma seqüência de palavras na janela ou o seu valor hash é tratado como um
bloco (SEO, CROFT, 2008). Como alguns dos métodos que utilizam esta técnica estão kgram, 0 mod p e Winnowing. A técnica de não-sobreposição consiste em dividir o texto em
segmentos significativos, ao invés de gerar muitas subsequências de palavras, não havendo,
portanto, a sobreposição de blocos. A posição em que uma quebra de palavra ocorre é referido
como um ponto de interrupção (SEO, CROFT, 2008).
Oliveira e Oliveira (2008) apresentam uma abordagem para a detecção de plágio em
ambientes de EAD (Ensino à Distância). A metodologia proposta sugere a aplicação do
Modelo de Representação Vetorial, como forma de representar os documentos a serem
comparados, posteriormente a esta representação é aplicado o processo de Latent Semantic
Indexing (LSI). Neste trabalho, os pesos dos termos são representados pelas freqüências com
que eles ocorrem nos documentos a que pertencem. O cálculo do produto vetorial dos vetores
de pesos indica o grau de similaridade entre dois documentos. O resultado do produto
vetorial entre dois vetores é o cosseno do ângulo, formado entre esses vetores. Quanto mais
próximo de 1 for o resultado, mais semelhantes podem ser considerados os documentos
utilizados como base para a comparação. Sendo assim, o valor 0 indica dissimilaridade total e
1 indica que os documentos são idênticos.
De acordo com Leung e Chan (2007), o plágio, no ambiente acadêmico, pode ocorrer
em 3 situações: cópia de uma fonte sem versão eletrônica, cópia direta de uma fonte com
versão eletrônica e cópia de uma fonte com versão eletrônica e modificação intencional do
conteúdo. Neste trabalho, o processamento de linguagem natural é aplicado como forma de
detecção de plágios, visando a identificação da terceira situação citada. A estrutura sintática
básica e o significado semântico de duas sentenças podem ser comparados a fim de revelar
sua similaridade (LEUNG, CHAN, 2007). Esta abordagem, primeiramente, adota a utilização
de um thesaurus, como forma de identificação de sinônimos, termos mais amplos ou
específicos, relacionados aos termos existentes no documento analisado. O Wordnet é um
exemplo típico de thesaurus que pode ser usado para esta finalidade. Pontuações diferentes
17
são atribuídas aos diferentes tipos de palavras relacionadas. Com base no resultado do cálculo
obtido a partir destas pontuações, se o valor de similaridade encontrado for maior que um
determinado limiar, a frase é suspeita de ser plágio, sendo, então, analisada sintática e
semanticamente.
No trabalho de Metzler (2007), foram utilizados resultados da web para expandir a
representação de textos curtos. Para cada um destes segmentos de texto, foram executadas
consultas em uma ferramenta de busca, recuperando os primeiros 200 resultados. Os títulos e
snippets associados com estes resultados foram então concatenados e utilizados para expandir
a representação. No trabalho de Tsatsou (2009), também foi utilizada uma fonte externa, mais
especificamente, a Wikipedia, com a finalidade de encontrar variações nos utilizados para
designar determinadas entidades nomeadas. Esta abordagem também pode ser bastante
interessante no sentido de encontrar palavras relacionadas, auxiliando assim na diminuição do
efeito negativo dos sinônimos na comparação entre frases.
Segundo Uzuner, Katz e Nahnsen (2005), informações lingüísticas pode ser uma
poderosa fonte para medir a similaridade entre trabalhos com base na expressão de seu
conteúdo. Neste trabalho, são abordados os aspectos criativos da escrita como forma de
reconhecer ocorrências de plágio. Neste trabalho, é identificado um conjunto de
características relacionadas com as escolhas lingüísticas dos autores, utilizando, para isso,
diferentes expressões sintáticas do mesmo conteúdo. Após terem sido identificadas as
características relevantes, são analisados os padrões de utilização desses recursos,
possibilitando, assim, o reconhecimento de paráfrases.
Para identificar esses aspectos
criativos, foram utilizadas diferentes traduções de obras literárias. Estas traduções têm a
característica de serem escritas de formas diferentes, transmitindo, porém, o mesmo conteúdo.
Ota e Masuyama (2009) também propõe uma abordagem baseada no algoritmo SmithWaterman, porém, com foco em papers escritos na língua japonesa. O método proposto
identifica partes plagiadas dispersas no texto, através da repetida aplicação do algoritmo em
questão. Irving (2004) propõe a aplicação do algoritmo Smith-Waterman considerando, como
unidade básica para o cálculo da distância, palavras ou sentenças. No entanto, no trabalho de
(OTA; MASUYAMA, 2009), não foi considerada adequada a utilização das palavras como
unidade básica de processamento, dada a facilidade de alteração da ordem das palavras em
japonês.
Em Su et al., é apresentado um método de detecção de plágio híbrido. Este trabalho
analisa a utilização do algoritmo Levenshtein Distance e o algoritmo Smith-Waterman
simplificado, como forma de detecção de plágio. Esta abordagem evita a comparação de
18
strings envolvidas globalmente e considera também fatores psicológicos.
Uma outra aplicação interessante do algoritmo Levenshtein Distance é abordada no
trabalho de Ruddle (2006), que propõe um método que utiliza matching de strings com a
finalidade de analisar o log de navegação do website. O método divide-se em duas
abordagens. Na primeira, é utilizado o matching exato de strings para identificar as
subseqüências de links que foram repetidas em diferentes sessões de navegação,
identificando, assim os caminhos comuns através do site. Nesta abordagem é utilizado o
conceito de LRSs. Na segunda, é realizado o matching inexato para encontrar sessões
similares, identificando, por exemplo, comunidades de usuários com interesses semelhantes.
Para o matching inexato, foi utilizado o algoritmo Levenshtein Distance, considerando 4
parâmetros, sendo eles bônus por pares de elementos correspondentes ou penalizações por
substituição e inserções. O número de matchings, inserções ou substituições é multiplicado
pelos valores atribuídos a estes parâmetros.
No que diz respeito à definição de limiares de similaridade, Nunes (2009) apresenta
uma padronização para escores de similaridade, mapeando estes escores para valores de
precisão. Permitindo, assim, que o usuário possa informar, não um limiar como base de
comparação, ma a precisão esperada para os resultados considerados relevantes. A técnica
resume-se na construção de uma tabela de mapeamento, considerando um determinado
domínio, bem como uma determinada função de similaridade. Tal tabela é obtida a partir do
treinamento dos dados, utiliza um conjunto de valores representativos. Cada consulta, então, é
comparada com o conjunto de atributos do domínio, gerando, então, um ranking com os
valores originais de similaridade resultantes da função. A precisão é calculada para cada
posição destes rankings. Para cada ranking, é realizado o cálculo da precisão interpolada em
cada um dos pontos estabelecidos, que, no caso deste trabalho, inicialmente, eram 11 pontos
([0, 0.1, . . . , 0.9, 1.0]). Então, a média de todos valores de precisão interpolada é calculada
para cada um desses pontos sobre todos os rankings, obtendo-se, desta forma, a tabela de
mapeamento de escores. Considerando os experimentos realizados no trabalho citado, um dos
algoritmos que obteve respostas mais significativas à técnica aplicada foi o Levenshtein
Distance.
Em Vernica e Li (2009), o limiar pode variar de acordo com o número de resultados
obtidos. Este trabalho propõe uma forma de flexibilizar consultas, encontrando as strings mais
relevantes, considerando a similaridade com a string original e a importância das possíveis
candidatas. Neste trabalho, são apresentados três algoritmos. O primeiro algoritmo calcula a
similaridade entre a string da consulta e a coleção de strings, com base em um limiar pré-
19
estabelecido. Este limiar pode ser diminuído, dependendo do número de resultados obtidos.
Após a obtenção do resultado, são calculados os escores para cada elemento retornado, sendo
ordenados pelo seu escore de similaridade. Então, é realizado o cálculo considerando o escore
de similaridade e a importância da string candidata. Na Figura 5, é mostrado um exemplo
onde são mostrados os resultados a partir da string “abcd”, utilizando o algoritmo Jaccard
Similarity, e considerando k = 2.
Figura 5 - Ranking para a string “abcd” com k = 2.
No segundo algoritmo, então, é apresentado o conceito de índice invertido, utilizando
q-grams. Q-grams podem ser descritas como pequenas substrings de tamanho fixo q. Para
cada gram, tem-se uma lista invertida das strings que contém este gram. O terceiro algoritmo
é baseia-se na junção dos dois primeiros algoritmos.
20
4. ALGORITMO LEVENSHTEIN DISTANCE
O algoritmo Levenshtein Distance foi criado pelo cientista russo Vladimir
Levenshtein, em 1965. O foco desta técnica é a avaliação da similaridade entre duas strings
com base no número de operações necessárias para transformar uma string em outra, sendo
que as operações possíveis são a inserção, a exclusão e a substituição. A distância zero indica
que as strings são idênticas. A partir do tamanho de cada string é montada uma matriz, onde
serão setados os custos de cada operação, geralmente, cada uma delas possui custo 1. Ao final
das comparações, a distância é dada pela última posição da matriz.
Apesar de ser um algoritmo relativamente antigo, o Levenshtein Distance ainda é
bastante utilizado atualmente. Na literatura, é comum encontrar a sua aplicação em tarefas
como comparação de dialetos, correção ortográfica, reconhecimento da fala, análise de DNA,
detecção de plágios, autenticação de assinaturas e vinculação de registros. A seguir, são
descritos alguns trabalhos que abordam o estudo da sua aplicação.
4.1. Comparação de dialetos
O trabalho de Freeman (2006) apresenta uma solução para o problema do matching de
nomes pessoais em Inglês para a representação dos mesmos nomes em códigos Árabes. Neste
estudo são realizadas uma série de etapas como, por exemplo, a transliteração dos nomes, a
aplicação do algoritmo Levenshtein, com posterior normalização de seu resultado. Esta
normalização considera o tamanho das strings sobre as quais será realizado o matching, ou
seja, o valor retornado pelo algoritmo LD é dividido pela soma do número de caracteres das
strings. Este valor, então, é diminuído de 1, tendo assim, o valor normalizado. A intenção da
divisão pelo tamanho de ambos os nomes é minimizar o peso de caracteres incompatíveis em
strings longas (FREEMAN, 2006). A normalização também é aplicada às próprias strings.
4.2. Correção ortográfica
Segundo estudo de Damerau (1964), aproximadamente 80% das palavras digitadas
incorretamente, possuíam pelo menos um erro relacionado à inserção, remoção, substituição
ou transposição. Tais descobertas passaram, então, a serem largamente aplicadas em técnicas
para correção ortográfica. No trabalho de Piltcher et al. (2005), o algoritmo Levenshtein foi
21
utilizado em conjunto com os algoritmos Metaphone e Soundex, para a análise de um
corretor ortográfico para ambientes de chat.
4.3. Reconhecimento da Fala
No estudo de Fiscus (2006), o algoritmo de distância de edição é utilizado para
realizar a comparação entre dois gráficos lineares, onde os nodos são palavras ao invés de
strings de caracteres.
4.4. Análise de DNA
Atualmente, até mesmo os melhores métodos de seqüenciamento de DNA apresentam
imperfeições. Segundo Troncoso-Pastoriza (2007), devido às imperfeições de seqüenciamento
químico, pode ocorrer 3 tipos de erros: substituição de símbolos (um símbolo errado é
gravado), inserções (um símbolo que não está presente no genoma é relatada no registro
digital) e a exclusão (o processo de seqüenciamento falha ao representar bases que estão
presentes no genoma).
Na literatura, o algoritmo LD é bastante utilizado para a comparação destas seqüências
de símbolos.
4.5. Vinculação de Registros
A vinculação de registros é um campo em crescente expansão com aplicações em
muitas áreas da saúde e pesquisa biomédica (Bell and Sethi 2001 apud Kelman et al 2002).
Ela pode ser vista como a metodologia para identificar em dois ou mais arquivos registros que
pertencem à mesma entidade ou encontrar duplicatas dentro de um mesmo arquivo (Freire et
al., 2009). O algoritmo de Levenshtein, bem como os algoritmos Levenshtein, Subsequência
Comum mais Longa (SCL), Monge-Elkan, e uma combinação de SCL com Levenshtein, e
também o algoritmo Jaro, e algumas de suas variantes, como, por exemplo, Winkler, Lynch,
McClaughlin foram estudados quanto à sua aplicação na área. O algoritmo Levenshtein
mostrou-se bastante veloz em comparação aos demais. O estudo conclui que o algoritmo
Levensthein pode não ser o mais adequado à vinculação de registros, porém os próprios
autores reconhecem que a amostra estudada foi bastante pequena. Em contrapartida, existe um
software, denominado Reclink, o qual utiliza o algoritmo de Levenshtein para a comparação
22
de registros e o algoritmo soundex para a blocagem, sendo bastante utilizado no Brasil para
realizar vinculação de registros na área de saúde, sugerindo, portanto, a eficácia destes
algoritmos na área.
4.6. Autenticação de Assinaturas On-line
O algoritmo LD também tem sido estudado no reconhecimento de assinaturas on-line.
No trabalho de Schimke et al. (2004), as assinaturas são convertidas para uma sequência de
códigos, que considera fatores como a posição da escrita e a pressão da mesma. Uma vez
definidas estas sequências, as mesmas são, então, analisadas pelo Levenshtein. Após a
comparação das assinaturas, a classificação das mesmas é realizada pelo classificador Nearest
Neighbor. Foi analisado um conjunto de 1376 assinaturas referentes à 41 pessoas. Segundo o
estudo, os resultados são bastante animadores, com 96% de identificações corretas contra
nenhuma classificação falsa.
23
5. METODOLOGIA PROPOSTA
Na metodologia proposta, além do algoritmo, foram utilizadas algumas técnicas de
pré-processamento de textos, como a remoção de stopwords e o Stemming, conforme descrito
a seguir.
5.1. Algoritmo
A única alteração no comportamento do algoritmo foi quanto à sua unidade básica de
comparação. Normalmente, esta técnica é utilizada para comparar todos os caracteres de duas
strings. Neste trabalho, o algoritmo compara todas as palavras de duas frases.
5.2. Remoção de stopwords
Considerando que as stopwords podem influenciar de forma negativa no resultado da
comparação, uma vez estas palavras não são relevantes e podem se repetir diversas vezes ao
longo de um texto, optou-se por removê-las. A stoplist é informada no momento em que o
algoritmo é executado.
5.3. Stemming
As diversas possibilidades de flexão das palavras também podem influenciar no
resultado final da comparação, pois qualquer diferença morfológica entre duas palavras, ainda
que o significado semântico permaneça idêntico, é considerada pelo algoritmo, aumentando a
distância entre as frases. Tendo em vista o exposto, é notória a importância do processo de
lematização para a metodologia proposta.
5.4. Percentual de Similaridade
24
Para o cálculo percentual de similaridade, são considerados o total de palavras entre a
frase original e a frase comparada e a distância encontrada pelo algoritmo. Desta forma,
supondo que temos um total de 10 palavras, e distância encontrada fosse 2, teríamos o
seguinte cálculo:
Percentual de Distância = ( 2 * 100 ) / 10 = 20 %
Similaridade = 100 % - 20 % = 80 %
25
6. EXPERIMENTOS
No exemplo mostrado na Figura 6, foi realizado o cálculo da distância entre as frases
“Muitos consideram Maradona como o melhor jogador de futebol na história do futebol” e
“Maradona é um dos melhores jogadores de futebol”. De acordo com a stoplist, foram
removidas palavras como: muitos, como, o, na, é, um, dos. As palavras restantes foram
reduzidas ao seu radical. Após a execução do algoritmo, pode-se observar que a distância
calculada foi equivalente a 2. Esta distância deve-se aos custos de exclusão dos radicais das
palavras “consideram” e “história”.
Figura 6 - Experimento 1
No segundo experimento, mostrado pela Figura 7, pode-se observar a influência da
localização da palavra “Brasil” na distância resultante da comparação entre a frase original e
as 3 primeiras frases, sendo que, semanticamente, estas frases são idênticas. Na comparação
entre a frase original e a última frase comparada a distância foi 3, diferindo muito pouco da
distância das duas frases anteriores, sendo que esta última frase é bastante diferente da frase
original, ao contrário das demais.
Figura 7 - Experimento 2
26
Para resolver o problema ilustrado pela Figura 7, bastaria que fossem ordenadas,
automaticamente, as três primeiras frases, tornando-as, portanto, idênticas à frase original.
Sendo assim, a distância resultante seria equivalente a zero, o que seria mais correto. Porém, a
ordenação das frases somente seria válida em casos onde ocorressem pequenas diferenças
entre as frases.
A seguir são mostrados alguns exemplos comparando duas descrições do curso de
Tecnologia em Análise e Desenvolvimento de Sistemas, extraídas de diferentes universidades.
Figura 8 - Experimento 3
Na figura 8, é possível identificar a importância da identificação de sinônimos para a
implementação proposta. Neste caso, os termos “visa” e “objetiva” possuem o mesmo
significado, portanto, para comparação, um termo poderia ser substituído pelo outro. Esta
substituição ocasionaria o aumento da similaridade entre as frases, passando de 57% para
61%.
27
Figura 9 - Experimento 4
Na Figura 9, pode-se notar que a parte inicial destas frases é bastante semelhante
(“Visa a formação de profissionais para atuação” e “Objetiva formar profissionais para
atuar”). Com a ordenação das frases, foi perdida completamente a relação sintática destas
estruturas e ocorreu redução da similaridade entre as duas frases.
Figura 10 - Experimento 5
No exemplo mostrado na figura 10, pode-se observar que a distância retornada pelo
28
algoritmo aumentou consideravelmente, ao contrário do percentual de similaridade, que
variou relativamente pouco. Isto ocorre devido ao fato de que o percentual de similaridade, no
cálculo utilizado, está intimamente relacionado ao tamanho do texto, de forma que, quanto
menor for o tamanho dos textos comparados, maior será o impacto da distância retornada pelo
algoritmo. Este é um fator importante para determinar se a melhor alternativa é comparar
textos inteiros ou segmentos menores, como é o caso das frases.
Para a continuação do testes, foi considerando a divisão do texto em frases, sendo elas
representadas por f1, f2, f3, f4, conforme mostrado a seguir:
Primeira descrição: Visa a formação de profissionais para atuação em pesquisa, gestão,
desenvolvimento, uso e avaliação de tecnologias da informação aplicadas nas organizações
(f1). A finalidade principal é preparar profissionais para os setores que necessitem lançar mão
da tecnologia da informação, dotando-os de uma formação básica, prática e humanística (f2).
Segunda descrição: Objetiva formar profissionais para atuar na área de Informática com
visão global e multidisciplinar do setor, instrumentalizados com embasamento teórico, prático
e tecnológico (f3). Estes profissionais estarão habilitados a identificar, planejar e executar
atividades de desenvolvimento, implementação e gerenciamento de sistemas de informação,
dando ênfase a conhecimentos práticos em TI e suas áreas de conhecimento, como Análise de
Sistemas, Desenvolvimento de Software, Programação Web, entre outras (f4).
Primeiramente, foi estabelecido um limiar para o percentual de similaridade a ser
retornado. O limiar utilizado foi 60%. Neste caso, foi retornada apenas a comparação das
frases f1 e f3, considerando que o percentual de similaridade entre elas é de exatamente 60%.
Reduzindo este limiar para 50%, foi retornada também a comparação entre as frases f2 e f3,
tendo sido obtido um percentual de 55% de similaridade. Um fator interessante a ser
considerado neste teste é o fato de ambas as frases da descrição tomada como base (f1 e f2)
são mais semelhantes à mesma frase da segunda descrição (f3). As comparações das frases f1
e f2 com a frase f4, obtiveram, respectivamente, 43% e 44% de similaridade.
29
7. CONCLUSÃO E TRABALHOS FUTUROS
Tendo em vista o exposto, pode-se concluir que o algoritmo tradicional possui potencial
para a avaliação de similaridade entre textos, porém ainda é necessário aperfeiçoá-lo para esta
finalidade. A seguir são apresentados alguns possíveis problemas desta abordagem, sugerindo
para cada problema uma solução a ser implementada futuramente.
A existência de diversos sinônimos para uma mesma palavra pode interferir bastante
no resultado final, pois qualquer diferença entre duas palavras, ainda que sejam
semanticamente iguais, resulta no aumento da distância retornada pelo algoritmo. Para
resolver este problema, poderiam ser utilizadas ferramentas como, por exemplo, o WordNet.
Embora o Stemming ajude a superar o problema de incompatibilidade de vocabulário
de certa forma, ele não resolve o problema contextual (METZLER et al., 2007). Para
amenizar este problema, pode ser utilizada a expansão de representações com base em fontes
externas, como as abordadas nos trabalhos de Metzler et al. (2007) e Tsatsou (2009).
30
8. REFERÊNCIAS
BATU, T.; ERGÜN, F.; KILIAN, J.; MAGEN, A.; RASKHODNIKOVA, S.; RUBINFELD,
R.; SAMI, R. A sublinear algorithm for weakly approximating edit distance In: Proceedings
of the thirty-fifth annual ACM symposium on Theory of computing, San Diego, 2003, pp. 316
-324.
BENDERSKY, M.; CROFT W. B. Finding Text Reuse on the Web In: Proceedings of the
Second ACM International Conference on Web Search and Data Mining, Barcelona, 2009, pp.
262-271.
BUENO, R.; TRAINA, A.; TRAINA, C. Accelerating approximate similarity queries using
genetic algorithms In: Proceedings of the 2005 ACM symposium on Applied computing,
Santa Fe, 2005, pp. 617-622.
CELIKIK, M.; BAST, H. Fast error-tolerant search on very large texts In: Proceedings of the
ACM symposium on Applied Computing, Honolulu, 2009, pp. 1724-1731.
FREEMAN, A. T.; CONDON, S. L.; ACKERMAN, C. M. Cross linguistic name matching in
English and Arabic: a "one to many mapping" extension of the Levenshtein edit distance
algorithm In: Proceedings of the main conference on Human Language Technology
Conference of the North American Chapter of the Association of Computational Linguistics,
New York, 2006, pp. 471-478.
HADJIELEFTHERIOU, M.; LI, C. Efficient Approximate Search on String Collections
IRVING, R. Plagiarism and collusion detection using the smith-waterman algorithm In:
International Conference on Computer Systems and Technologies, 2004, pp. 1-24.
JUNIOR, J.R.C. Desenvolvimento de uma Metodologia para Mineração de Textos. Rio de
Janeiro: PUC-Rio, 2007, 113 f. Dissertação (Mestrado em Engenharia Elétrica) - Programa de
Pós-graduação em Engenharia Elétrica, Departamento de Engenharia Elétrica, Pontifícia
Universidade Católica do Rio de Janeiro, Rio de Janeiro, 2007.
LUKASHENKO, R.; GRAUDINA, V.; GRUNDSPENKIS, J. Computer-Based Plagiarism
Detection Methods and Tools: An Overview In: Proceedings of the 2007 International
Conference on Computer Systems and Technologies, Rousse, 2007.
LEUNG, C.; CHAN, Y. A Natural Language Processing Approach to Automatic Plagiarism
Detection In: Proceedings of the 8th ACM SIGITE conference on Information technology
education Destin, 2007, pp. 213-218.
LU, J.; HAN, J.; MENG, X. Efficient algorithms for approximate member extraction using
signature-based inverted lists In: Proceeding of the 18th ACM conference on Information and
knowledge management, Hong Kong, 2009, pp. 315-324.
MATOS, T.; SILVA, I.; BARCELOS, C.; PROENÇA, P. Índice Invertido para Recuperaçãao
de Imagens Baseada em Conteúdo In: 31. Congresso Nacional de Matemática Aplicada e
Computacional, Belém, 2008, pp. 20-25.
31
METZLER, D.; DUMAIS, S.; MEEK, C. Similarity Measures for Short Segments of Text In:
Proceedings of the European Conference on Information Retrieval, Amherst, 2007.
NAVEGA, S. Manipulação Semântica de Textos: Os Projetos WordNet e LSA. In: Infoimagem
2004, 2004, São Paulo. Anais Infoimagem 2004.
OLIVEIRA, M.. ; OLIVEIRA, E. Uma Metodologia para Detecção Automática de Plágios
em Ambientes de Educação a Distância. In: Congresso Brasileiro de Ensino Superior a
Distância - ESuD, 2008, Gramado, no Rio Grande do Sul. Anais do ESuD, 2008. p. 1-20.
OTA, T.; MASUYAMA, S. Automatic Plagiarism Detection among Term Papers In:
Proceedings of the 3rd International Universal Communication Symposium, Tokyo, 2009, pp.
395-399.
PIAO, S. S. L.; MCENERY, A. M. A tool for text comparison. In: Proceedings of the corpus
linguistics 2003 conference, Lancaster, pp. 637-646.
PIROLLI, P.; PITKOW, J. Mining Longest Repeating Subsequences Predict World Wide Web
Surfing In: Proceedings of USITS' 99: The 2nd USENIX Symposium on Internet
Technologies & Systems, Boulder, 1999.
RUDDLE, R. Using string-matching to analyze hypertext navigation In: Proceedings of the
seventeenth conference on Hypertext and hypermedia, Odense, 2006, pp. 49-52.
SEO, J.; CROFT, W. Local Text Reuse Detection In: Proceedings of the 31st annual
international ACM SIGIR conference on Research and development in information retrieval,
Singapore, 2008, pp. 571-578.
SOARES, F. A. Mineração de Textos na Coleta Inteligente de Dados na Web. Rio de Janeiro:
PUCRio, 2008, 113 f. Dissertação (Mestrado em Engenharia Elétrica) - Programa de Pósgraduação em Engenharia Elétrica, Departamento de Engenharia Elétrica, Pontifícia
Universidade Católica do Rio de Janeiro, Rio de Janeiro, 2008.
SU, Z.; AHN, B.; EOM, K.; KANG, M.; KIM, J.; KIM, M. Plagiarism Detection Using the
Levenshtein Distance and Smith-Waterman Algorithm In: Proceedings of the 3rd International
Conference on Innovative Computing Information and Control, 2008.
TSATSOU, D.; MENEMENIS, F.; KOMPATSIARIS, I.; DAVIS, P.C. A Semantic
Framework for Personalized Ad Recommendation based on Advanced Textual Analysis. In:
Proceedings of the 3. ACM Conference on Recommender Systems, Nova York, 2009.
VERNICA, R.; LI, C. Efficient top-k algorithms for fuzzy search in string collections In:
Proceedings of the First International Workshop on Keyword Search on Structured Data
Providence, 2009, pp. 9-14