info.info-tt info.info-ir
Elvys Linhares Pontes 
email: elvyslpontes@gmail.com
  
Andréa Carneiro Linhares 
email: andrea.linhares@ufc.br
  
Juan-Manuel Torres-Moreno 
email: juan-manuel.torres@univ-avignon.fr
  
Palavras Chave 
  
  
  
  
  
  
  
SASI: sumarizador automático de documentos baseado no problema do subconjunto independente de vértices

Keywords: . Independent vertex subset, Automatic summarization, Phrases graph. Main Area: Theory and Algorithms in Graphs, Other applications in OR

This article discusses a summarizer system of documents named SASI. This system features an innovative approach to provide automatic summaries, based on the determination of the maximum independent subset of vertices, modeling the problem a graph of phrases (vertices) and the relationships between them (edges). The concepts and operation of the proposed summarizer and a series of tests comparing the results provided by SASI with others summarizer systems are described. Initial results are promising, evaluating questions of informativeness of the produced summaries on the parameters of time and algorithmic complexity.

Introduc ¸ão

Resumir consiste em condensar as informac ¸ões mais importantes de um ou vários documentos, a fim de produzir uma versão reduzida do seu conteúdo com as partes importantes do texto original e que seja gramaticalmente correto [START_REF] Mani | Advances in Automatic Text Summarization[END_REF], [START_REF] Das | A survey on automatic text summarization[END_REF], [START_REF] Filippova | Multi-sentence compression: finding shortest paths in word graphs[END_REF]]. Os títulos de revistas, as propagandas e as sinopses são alguns exemplos de resumos que utilizamos cotidianamente. De modo geral, as pessoas são excelentes "resumidores" em termos de qualidade do resumo produzido. Baseando-se em estudos do comportamento de resumidores profissionais, os pesquisadores tentaram imitar o processo cognitivo de criac ¸ão de um resumo [START_REF] Pollock | Automatic abstracting research at chemical abstracts service[END_REF], [START_REF] Mihalcea | Graph-based ranking algorithms for sentence extraction, applied to text summarization[END_REF], [START_REF] Wann | Improving grammaticality in statistical sentence generation: introducing a dependency spanning tree algorithm with an argument satisfaction model[END_REF]].

Atualmente, há uma grande necessidade de se obter resumos de documentos nas mais diversas áreas do conhecimento, pois isso facilita a busca por textos de referência bem como acelera o processo de compreensão do mesmo. O trabalho aqui descrito objetivou a criac ¸ão de um sumarizador automático denotado por SASI (Sumarizador Automático baseado em Subconjunto Independente), utilizando a teoria e algoritmos de grafos como ferramenta básica conceitual. Nesse intuito, modelou-se o problema como um grafo e implementou-se um algoritmo a partir de ideias clássicas utilizadas na obtenc ¸ão do Subconjunto Independente Máximo de vértices de um grafo. Técnicas estatísticas foram igualmente consideradas para cálculos de similaridade e para a avaliac ¸ão da qualidade dos resumos produzidos.

A sec ¸ão 2 introduz formalmente o problema do Subconjunto Independente Máximo (SIM), enquanto a sec ¸ão 3 fará um breve estado da arte sobre sumarizac ¸ão automática de textos. A sec ¸ão 4 introduz a notac ¸ão matemática adotada e a modelagem do problema. Em 5, o sistema SASI é apresentado, onde sua fundamentac ¸ão e funcionamento são detalhados. Os resultados são discutidos na sec ¸ão 6 e as conclusões apresentadas na sec ¸ão 7.

Problema do Subconjunto Independente Máximo

Considere um grafo G = (V, E), onde V é o conjunto de vértices e E o conjunto de arestas não orientadas de G. Conceitualmente, vértices adjacentes ou vizinhos são aqueles ligados diretamente por uma aresta. Desse modo, um Subconjunto Independente de Vértices (denotado como SIV neste trabalho) é formado por um subconjunto dos vértices do grafo que não são adjacentes [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]], ou seja, vértices que não possuem aresta ligando-os.

O SIM é o subconjunto independente de vértices com maior cardinalidade no grafo. Ele é um problema NP-Difícil. Uma forma simples de tentar calcular o SIM é através do método guloso abaixo, descrito no trabalho de [START_REF] Halldon | Greed is good: Approximating independent sets in sparse and bounded-degree graphs[END_REF]]. Esse problema é complementar ao problema da clique máxima [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]].

Algoritmo

Entrada Grafo G. Saída Subconjunto Independente de Vértices do grafo G. Em [START_REF] Butenko | Maximum independent set and related problems, with applications[END_REF]], o SIM é abordado com mais detalhes, explorando questões acerca da complexidade algorítmica e de possíveis soluc ¸ões, adaptadas às características do grafo. O SIM está presente em várias aplicac ¸ões, como colorac ¸ão de grafos, agendamento de tarefas, atribuic ¸ão de canais de rádio, entre outras. Em [START_REF] Yutao | Maximal independent set based channel allocation algorithm in cognitive radios[END_REF]], o SIM é utilizado para alocac ¸ão de canal em sistemas de rádio cognitivos.

1 SIV ← null 2 enquanto G = ∅ fac ¸a 3 v é vértice de G tal que d(v) = min u∈V (G) d(u) 4 G ← G -({v} ∪ N (v))

Sumarizador Automático de Documentos

Nos primeiros trabalhos acerca da sumarizac ¸ão automática de documentos, o trabalho [START_REF] Luhn | The automatic creation of literature abstracts[END_REF]] descreve uma técnica simples e específica aos artigos científicos que utiliza a distribuic ¸ão das frequências das palavras no documento para ponderac ¸ão de frases. Ele apresenta algumas das vantagens que os resumos produzidos de modo automático têm com relac ¸ão aos manuais: custo de produc ¸ão bem reduzido, inexistência de problemas de subjetividade e de variabilidade observadas nos "resumidores" profissionais, dentre outros. A grande maioria dos sistemas resumidores de hoje continuam baseados nessa mesma ideia.

[ [START_REF] Edmundson | New methods in automatic extracting[END_REF]] deu continuidade aos trabalhos de Luhn, adicionando ao processo de produc ¸ão de resumos considerac ¸ões sobre posic ¸ão das frases e presenc ¸a de palavras provenientes da estrutura do documento (por exemplo, títulos, sub-títulos, etc.). As pesquisas desenvolvidas em [START_REF] Pollock | Automatic abstracting research at chemical abstracts service[END_REF]] no Chemical Abstracts Service (CAS) concernentes à produc ¸ão de sumários a partir de artigos científicos de Química permitiram validar a viabilidade das abordagens de extrac ¸ão automática de frases. Uma "limpeza" das frases -uso de operac ¸ões de eliminac ¸ão, foi introduzida pela primeira vez. No intuito de adequar os resumos aos padrões impostos pela CAS, uma normalizac ¸ão do vocabulário era efetuada. A normalizac ¸ão inclui a substituic ¸ão de palavras/frases por suas abreviac ¸ões e uma padronizac ¸ão das variantes ortográficas. Em seguida, os estudos sobre sumarizac ¸ão automática de textos foram divididos em dois grupos, extrac ¸ão e abstrac ¸ão de texto. Na primeira, há a identificac ¸ão das partes mais relevantes em um ou mais textos, através de técnicas de recuperac ¸ão de informac ¸ão estatística. O trabalho de [START_REF] Wu | A survey on statistical approaches to natural language processing[END_REF]] descreve vários métodos estatísticos utilizados no processo de sumarizac ¸ão de textos. A abstrac ¸ão analisa o texto original de uma forma linguística profunda, interpreta o texto semanticamente em uma representac ¸ão formal, encontra novos conceitos mais concisos para descrevê-lo e, em seguida, gera um novo texto mais curto com o mesmo sentido do texto original [START_REF] Hovy | Automated text summarization and the summarist system[END_REF]].

Os trabalhos voltados para a extrac ¸ão de frases se baseiam na seguinte metodologia de produc ¸ão de sumários:

• Pré-processamento do texto;

• Identificac ¸ão das frases em destaque no documento;

• Construc ¸ão do sumário por concatenac ¸ão das frases extraídas.

Outro campo de estudo uniu os conceitos de Processamento de Linguagem Natural (PLN) com os conceitos de grafos, como em [START_REF] Mihalcea | Graph-based ranking algorithms for sentence extraction, applied to text summarization[END_REF]], que desenvolveu algoritmos de classificac ¸ão baseados em grafos tais como PageRank. Esses algoritmos foram utilizados com sucesso nas redes sociais, na análise do número de citac ¸ões ou no estudo da estrutura da Web. Eles permitem tomar decisões acerca da importância de um vértice, baseando-se na informac ¸ão global advinda da análise recursiva do grafo completo, e não na análise local do vértice. No âmbito da sumarizac ¸ão automática, observa-se que o documento é representado por um grafo de unidades textuais (frases) conectadas entre elas através de relac ¸ões oriundas de cálculos de similaridade. As frases são em seguida selecionadas segundo critérios de centralidade ou de prestígio no grafo, e em seguida reunidas a fim de produzir os extratos do texto.

Outra metodologia utilizada com grafos e PLN é descrita em [START_REF] Filippova | Multi-sentence compression: finding shortest paths in word graphs[END_REF]]. Esse artigo descreve uma forma de obter o resumo do texto através do menor caminho num grafo de palavras juntamente com processos de sintática. Em [Laureano-Cruces and Ramírez-Rodríguez(2012)], os autores modelam o texto através de um grafo e calculam o peso entre as frases. A partir dessa modelagem, um resumo é produzido.

Além de gerar resumos, tem-se que analisar a qualidade deles. Um bom resumo deve ser significativamente menor do que o documento original, transmitir o máximo de informac ¸ão possível do documento original e ser gramaticalmente correto [START_REF] Almeida | A new multi-document summarization corpus for european portuguese[END_REF]]. Para isso, são analisadas três características do resumo: concisão, informatividade e gramaticalidade. A concisão representa que o resumo deve ser significativamente menor do que o texto original. Normalmente utiliza-se uma quantidade máxima de palavras ou de frases para gerar um resumo. A informatividade descreve a quantidade de informac ¸ões importantes que o resumo possui em relac ¸ão ao texto original. A gramaticalidade verifica a corretude gramatical do resumo [START_REF] Boudin | Exploration d'approches statistiques pour le résumé automatique de texte[END_REF]].

Modelagem Matemática

Neste trabalho, objetivou-se a concepc ¸ão de um sistema de sumarizac ¸ão automática genérico. Esse sistema utilizou algoritmos oriundos da Teoria dos Grafos (através dos trabalhos descritos na sec ¸ão 2 para calcular o SIM), a fim de determinar no texto suas frases mais importantes. Foi utilizado tratamento estatístico no intuito de construir um sistema o mais independente possível da linguagem. Os métodos propostos têm como base um pré-tratamento específico das palavras e uma func ¸ão de ponderac ¸ão das frases baseada na estrutura do grafo e na relac ¸ão de vizinhanc ¸a das mesmas (frases).

Foi utilizado o modelo de saco-de-palavras para representar o texto. Esse modelo utiliza uma matriz S [m×n] construída a partir do documento, em que m é o número de frases e n é a quantidade de palavras distintas do texto. A célula s ij da matriz representa a frequência da palavra j na frase i (F P ij ). 

s m1 s m2 . . . s mn      , s ij = F P ij , se ∃ palavra j na f rase i 0, caso contrário (1) 
Na modelagem do problema, W é conjunto das palavras contidas nos conjuntos P e Q. P e Q podem representar frases ou conjunto de frases, conforme o cálculo da divergência que se deseja efetuar: entre duas frases; entre uma frase e um documento; entre documentos. A divergência Kullback-Leibler (KL) calcula a informac ¸ão perdida ao aproximar uma distribuic ¸ão P a uma distribuic ¸ão Q (equac ¸ão 2) [START_REF] Søgaard | Semi-Supervised Learning and Domain Adaptation in Natural Language Processing[END_REF]]. Esse cálculo permite calcular a divergência entre dois conjuntos de palavras distintos, entretanto essa divergência é assimétrica (DKL(P ||Q) = DKL(Q||P )). Essa assimetria não garante uma análise correta entre duas distribuic ¸ões, pois teriam valores diferentes dependendo da análise realizada. Entretanto, a divergência Jensen-Shannon (JS) é uma versão simétrica e suavizada da divergência KL fornecendo uma forma mais estável para mensurar a diferenc ¸a entre duas distribuic ¸ões. Portanto, utilizou-se a divergência Jensen-Shannon e variac ¸ões da mesma, a fim de mensurar a divergência (inverso da similaridade) entre duas distribuic ¸ões P e Q (equac ¸ão 3) [Torres-Moreno et al.(2010), [START_REF] Saggion | Multilingual summarization evaluation without human models[END_REF]].

DKL(P ||Q) = 1 2 w∈W P w log P w Q w (2) DJS(P ||Q) = 1 2 w∈W P w log 2 * P w P w + Q w + Q w log 2 * Q w P w + Q w (3)
Supondo-se P e Q duas frases do documento e R seja o conjunto formado pelas palavras das frases P e Q, P w representa a distribuic ¸ão do conjunto de palavras da frase P relacionadas a todas as palavras do conjunto R. Respectivamente, Q w será a distribuic ¸ão do conjunto de palavras da frase Q relacionadas às palavras do conjunto R. A divergência JS calcula a divergência entre duas distribuic ¸ões, onde seu valor varia de [0, ∞+). Os valores da divergência JS são mais próximos a zero quando as distribuic ¸ões são semelhantes e mais próximo do valor 1 quando elas diferem. Desse modo, para as frases P e Q, quanto maior o valor de DJS(P ||Q) mais uma frase diverge da outra.

A divergência JS será utilizada para calcular a divergência entre duas frases, analisando a frequência de cada palavra presente nelas. No caso de haver uma palavra em uma frase que seja inexistente na outra, será utilizado um smooth (ponderac ¸ão diferenciada) para evitar valores nulos e ter uma distribuic ¸ão mais suave [START_REF] Hiemstra | Probability smoothing[END_REF]]. Caso uma palavra w não esteja presente na frase Q, então o smooth é dado abaixo:

Q w = P w + γ N + γ * β (4) 
onde β = 1.5 * V ocabulário, V ocabulário é a quantidade de palavras distintas de R, γ é a variável que controla a relevância da ausência de uma palavra na frase e N o número de palavras presente em R.

Os cálculos descritos em (3) e (4) são utilizados no processo de pré-selec ¸ão de frases no documento, bem como na criac ¸ão de arestas do grafo resultante, as quais representarão a existência de similaridade entre duas frases.

Sistema SASI

A etapa de pré-processamento é efetivada pelo SASI através do processo stemming (segmentac ¸ão), onde são removidas todas as partes assumidas desnecessárias (conjunc ¸ões, artigos, pontuac ¸ão). Em seguida, realiza-se o processo de lematizac ¸ão para analisar os radicais das palavras e evitar diferenc ¸as entre palavras derivadas. Por fim, verifica-se cada palavra do texto, analisando-se sua frequência no texto e em cada frase através da matriz S (matriz de saco de palavras).

Inicialmente P e Q referenciam, respectivamente, o texto completo e cada frase isolada do mesmo. Assim, P w será o conjunto de distribuic ¸ões de palavras do texto P e Q w será o conjunto de distribuic ¸ões de palavras da frase Q. Dessa forma, DJS(P ||Q) calculará a divergência entre cada frase e o texto, verificando se uma frase é importante para o documento por meio da estatística das palavras existentes:

• Se a divergência JS da frase for pequena (próximo a zero) em relac ¸ão ao texto completo, a frase será relevante;

• Caso contrário, uma nova análise de similaridade é realizada com relac ¸ão ao título do documento. Se a DJS entre a frase e o título for pequena, a frase será considerada relevante, senão, ela será descartada da análise e assim do grafo.

Após selecionarmos as frases relevantes para o documento, verificamos a divergência entre as mesmas. Nessa etapa, P e Q correspondem a cada par de frases selecionadas. Em seguida, identifica-se o conjunto de palavras pertencentes a cada frase e calcula-se a DJS(P ||Q).

O grafo do problema é construído a partir do conjunto de frases relevantes (vértices) e o valor da divergência JS entre duas frases será utilizado para a criac ¸ão e ponderac ¸ão de arestas. Para a inserc ¸ão de arestas, analisa-se todas as combinac ¸ões possíveis de duas frases. Caso a divergência entre elas for "pequena" (parâmetro do algoritmo), uma aresta interligando-as será inserida. Ao final desse processo, teremos um grafo onde as ligac ¸ões (arestas) representam a similaridade entre as frases.

Como o processo de sumarizac ¸ão objetiva a produc ¸ão de um resumo de tamanho menor que o conteúdo original e com as principais informac ¸ões do texto, seria interessante escolher somente as frases que trazem informac ¸ão adicional ao resumo. A escolha de vértices adjacentes implica na selec ¸ão de frases com conteúdo redundante, o que não é interessante para o resumo. Por isso, a determinac ¸ão do subconjunto independente de vértices do grafo fornecerá a soluc ¸ão para o problema. Assim, a ideia é que o sistema selecione as frases com conteúdo distinto entre si, descartando aquelas com conteúdo repetitivo ou que trazem pouco informac ¸ão adicional ao resumo. No término do algoritmo, temos o subconjunto de vértices representando as frases do texto resumido.

O algoritmo abaixo descreve o funcionamento do sistema SASI. É importante destacar que neste trabalho tenciona-se a obtenc ¸ão de um resumo de um documento, sem preocupar-se com um tamanho máximo ou mínimo de frases selecionadas.

Algoritmo Entrada Texto. Saída Resumo do texto. 1 Pré-processamento do texto 2 Resumo ← ∅ 3 para Cada frase f ∈ texto fac ¸a 4 se DJS(f ||texto) < DJST exto então 5 Resumo ← Resumo ∪ f 6 senão se DJS(f ||titulo) < DJST itulo então 7 Resumo ← Resumo ∪ f 8 Cria grafo G[Resumo] 9 para Cada par de vértices P e Q (frases) ∈ G fac ¸a 10 se DJS(P ||Q) < DJSF rase então 11 A(P, Q) ← A(Q, P ) ← 1 12 senão 13 A(P, Q) ← A(Q, P ) ← 0 14 Calcula o SIM (G)

Resultados

O desempenho do sistema descrito na sec ¸ão 5 foi analisado a partir de diversos valores dos parâmetros associados ao cálculo da divergência JS. Os testes foram realizados num computador com processador i5 2.6 GHz e 4 GB de memória RAM no sistema operacional Debian de 64 bits. Os algoritmos foram implementados utilizando a linguagem de programac ¸ão Perl. As similaridades foram analisadas entre: uma frase e outra (DJSF rase); uma frase e o título (DJST itulo); e uma frase e o documento (DJST exto). A tabela 1 descreve o nível de similaridade relacionado ao valor da divergência JS e os valores selecionados nos experimentos aqui descritos. Analisou-se o γ variando entre 0, 01 e 0, 20 e, a partir dos resultados, utilizou-se γ = 0, 1.

Parâmetros

Nível de similaridade Fraca Média Forte Selecionado DJSF rase JS > 0, 75 0, 25 < JS < 0, 75 JS < 0, 25 0,32 DJST itulo JS > 0, 8 0, 4 < JS < 0, 8 JS < 0, 4 0,6 DJST exto JS > 0, 95 0, 65 < JS < 0, 95 JS < 0, 65 0,9

Tabela 1: Nível de similaridade relacionado à divergência JS Neste trabalho, o corpus, conjunto de documentos que serve como base de análise, é composto por textos de jornais e revistas científicas em inglês, francês e espanhol. Além dessas características, os resumos dos textos selecionados estão disponíveis na literatura para outros sistemas sumarizadores [START_REF] Torres-Moreno | Condensés de textes par des méthodes numériques[END_REF], [START_REF] Fernandez | Textual energy of associative memories: Performant applications of enertex algorithm in text summarization and topic segmentation[END_REF]]. O corpus utilizado é composto por 13 textos de diferentes tamanhos e assuntos. A tabela 2 mostra 4 textos do corpus detalhando a quantidade de frases dos resumos para textos de diferentes tamanhos e valores da DJSF rase. Pode-se observar, a partir dos dados dessa tabela, que quanto maior o valor da DJS entre frases menor será o resumo (número de frases) fornecido pelo algoritmo. Portanto, esse valor dependerá do tamanho do resumo que se deseja obter. Deve-se considerar que quanto menor o resumo mais informac ¸ões serão omitidas e a informatividade poderá ser reduzida. Tabela 2: Tamanho dos resumos obtidos para um conjunto de valores da DJS.

Foram usados na comparac ¸ão dos nossos resultados os valores fornecidos pelos sistemas sumarizadores Cortex, Enertex e REG. O REG modela o documento como um grafo e atribui arestas ponderadas ao grafo para gerar o resumo do texto [START_REF] Torres-Moreno | Reg : un algorithme glouton appliqué au résumé automatique de texte[END_REF]]. O Cortex é um sistema baseado em métodos numéricos, que é independente do tema e do comprimento do texto [START_REF] Torres-Moreno | Condensés de textes par des méthodes numériques[END_REF], [START_REF] Boudin | Neo-cortex: A performant user-oriented multidocument summarization system[END_REF]]. O Enertex é um sistema que utiliza a abordagem de redes neurais, inspirado na física estatística de sistemas magnéticos para sumarizar textos [START_REF] Fernandez | Textual energy of associative memories: Performant applications of enertex algorithm in text summarization and topic segmentation[END_REF][START_REF] Fernandez | Enertex: un système basé sur l'énergie textuelle[END_REF]]. Dessa forma, comparouse a informatividade dos resumos fornecidos pelo SASI, Cortex, Enertex e REG em relac ¸ão aos sumários dos resumidores profissionais (tabela 3).

A figura 1 descreve o desempenho obtido em segundos pelo sistema SASI na produc ¸ão de resumos a partir dos textos da tabela 2 com a quantidade de palavras variando entre 11 e 214. Os sistemas obtiveram os seguintes tempo de execuc ¸ão para o corpus analisado: Cortex, 58,27 segundos; Enertex, 56,80 segundos; REG, 55,70 segundos; e SASI, 38,78 segundos. Analisou-se, ainda, a qualidade dos resumos através da que foi calculada através da taxa de acerto das frases fornecidas pelos sistemas sumarizadores em relac ¸ão aos resumos dos profissionais descritos na tabela 3.

O SASI obteve o melhor resultado no texto Quebec e um desempenho semelhante aos outros sistemas no texto Puces. Nos textos Lewinsky e Mars, o SASI teve uma taxa de acerto inferior aos demais sistemas, pois os SIV calculados não corresponderem aos SIM dos grafos analisados e a ponderac ¸ão das frases não abordar outros elementos importantes nos textos. Nos demais textos do Corpus, os resumos tiveram a informatividade semelhante aos resultados obtidos nos resumos Puces. Assim, apesar do SASI ter obtido um desempenho inferior em 69% dos textos analisados, a informatividade dos documentos foi preservada, o que é extremamente importante na construc ¸ão de um resumo de forma automática.

O SASI é uma ferramenta que tem por base uma heurística simples e que se apoia em cálculos estatísticos menos complexos do que outros sistemas utilizados no domínio do PLN, no âmbito da sumarizac ¸ão automática de documentos. A integrac ¸ão de novas regras sintáticas e semânticas para pré-tratamento dos textos proverá melhorias no desempenho do SASI. Além disso, com base nos testes realizados, o desenvolvimento de um método mais refinado para calculo do SIV que assegure resultados mais próximos de um SIM, impactará de maneira positiva na qualidade dos sumários produzidos, visto que serão escolhidas um numero maior de "frases importantes" do texto e com conteúdo distinto, o que evitaria que frases relevantes sejam descartadas no processo.

Conclusão

Analisando o trabalho desenvolvido e as abordagens existentes na literatura, pode-se concluir que a utilizac ¸ão do SIM concomitante ao uso da divergência JS para construc ¸ão de um grafo de frases e relac ¸ões entre as mesmas é inovadora.

O SASI conseguiu resultados satisfatórios comparado aos outros sistemas na literatura. Os resultados desse sistema foram semelhantes aos demais fornecendo sempre uma boa taxa de informatividade dos resumos. Em relac ¸ão ao tempo de execuc ¸ão, o SASI conseguiu o menor tempo. Portanto, o sistema SASI é um sumarizador viável, pois forneceu maior parte das principais informac ¸ões dos resumos em tempo hábil.

A divergência JS é simétrica, e esse recurso pode ter consequências negativas sobre a tarefa de resumo automático: a frase é sempre menor do que a original. Uma nova versão da divergência KL (não simétrica e ponderada pelo comprimento da frase) poderia ser usada para melhorar o resultado. No futuro, testaremos a divergência KL modificada como descrita em [START_REF] Torres-Moreno | Automatic Text Summarization[END_REF]].

Outras perspectivas futuras são melhorar a ponderac ¸ão entre as frases analisando aspectos semânticos do texto, como também, verificar palavras sinônimas e fazer a abstrac ¸ão das principais frases do texto. Além disso, testar o SASI com um corpus em outros idiomas (Português, Espanhol, Inglês, etc.) para o qual estejam disponíveis resumos fornecidos por resumidores profissionais.

Agradecimentos

À Coordenac ¸ão de Aperfeic ¸oamento de Pessoal de Nível Superior (CAPES) e Fundac ¸ão Cearense de Apoio ao Desenvolvimento Científico e Tecnológico (FUNCAP).

5

  SIV← SIV ∪ {v} Para um grafo G, o algoritmo deverá determinar seu subconjunto independente de vértices. O algoritmo calcula o grau dos vértices de G e ordena-os de modo crescente em func ¸ão do grau. Conforme o algoritmo, o vértice v de menor grau de G é removido e adicionado ao conjunto SIV. Se algum vizinho de v, denotado por N(v), for viável, ele será removido de G. O processo se repete enquanto o conjunto G possuir vértices. Ao final do algoritmo, o subconjunto encontrado do grafo G será o melhor possível em termos de cardinalidade, mas como o algoritmo não é exato, não é possível assegurar que ele seja um SIM.

s

  11 s 12 . . . s 1n s 21 s 22 . . . s 2n . . . . . . . . .

Figura 1 :

 1 Figura 1: Desempenho do sistema SASI.