Upload
internet
View
109
Download
2
Embed Size (px)
Citation preview
27 Abril 2007 Processamento de Texto 1
Processamento de Texto
Pedro BarahonaDI/FCT/UNL
Introdução aos Computadores e à Programação2º Semestre 2006/2007
27 Abril 2007 Processamento de Texto 2
Regressão Linear : Um Exemplo
• Muita informação útil, nomeadamente em tarefas de gestão, não é do tipo
numérico.
• Por exemplo, variadas entidades (pessoas, empresas, disciplinas, departamentos,
etc...) têm associado um nome que se pode querer processar (por exemplo
ordenar).
• Este é apenas um exemplo de situações em que se pretende que os programas
efectuem processamento de texto.
• Todas as linguagens de programação prevêem pois tipos de dados para este fim,
nomeadamente
– Caracteres;
– sequências de caracteres (“strings”).
27 Abril 2007 Processamento de Texto 3
Caracteres e seus Códigos
• Os caracteres mais utilizados (representados no código ASCII - American
Standard Code for Information Interchange) incluem
• Letras (52), maiúsculas (26) e minúsculas (26)
• Dígitos (10)
• Espaço e outros caracteres “visíveis” (34)
– ‘ “ ( ) [ ] { } , . : ; = < > + - * \ | / ^ ~ ´ ` # $ % & _ ! ? @
• Caracteres de controle (32)
– horizontal tab (\t), new line (\n), alert (\a), ...
• Outros caracteres, (ç, ã, ñ, š , ø , ∞, , Σ, ш, غغ ,לא, ך ) só podem ser
representados em códigos mais avançados e não são “suportados” em algumas
linguagens de programação (em Octave, uma variável não pode ter o nome
“acção”)
27 Abril 2007 Processamento de Texto 4
Sequências de Caracteres
• Sequências de caracteres (“strings”) são conjuntos de caracteres, com uma
ordenação determinada.
• Em quase todas as linguagens, dados do tipo caracter e sequência (incluindo
sequências simples, com um só caracter) são representados entre delimitadores,
que podem ser aspas (“ ”) ou plicas (‘ ’).
• Devem sempre abrir-se e fechar-se com o mesmo tipo de delimitadores.
• Quando se pretende incluir um dos delimitadores no texto, podem usar-se
“sequências de escape”
– nome = ‘ Maria Martins d\’Albuquerque’
• ou usar-se o outro delimitador
– nome = “ Maria Martins d’Albuquerque”
– frase = ‘Ele exclamou: “Óptimo” e fugiu’
27 Abril 2007 Processamento de Texto 5
Sequências de Caracteres e Vectores
• Em geral, e o Octave não foge à regra, sequências de caracteres são
“implementadas” como vectores dos códigos dos caracteres.
• Muitas funções e operações em Octave exigem a utilização do tipo correcto. Duas
funções permitem transformar
– Vectores em sequências : toascii: <sequência> <vector>
>> a = toascii(“ABC”) a = [65,66,67]
– Sequências em vectores : setstr: <vector> <sequência>
>> b = setstr([97,98,99]) b = ‘abc’
• O Octave não é muito estrito no que se refere aos tipos de dados. Por exemplo,
permite operações “numéricas” com sequências, fazendo a conversão de tipos
necessária
>> c = ‘abc’ * 1 c = [97,98,99]
• Nota: Estas “facilidades” tornam difícil a detecção de erros de programação e não
devem ser usadas (ou apenas com muito cuidado)
27 Abril 2007 Processamento de Texto 6
Conversão de Sequências de Caracteres
• Sequências de caracteres podem ser processados de várias formas. Para as mais
comuns, existem funções pré-definidas.
• Algumas dessas funções permitem converter sequências de caracteres que
representam números para os próprios números.
• Exemplo: Dada a sequência “ 23.76 ” (com espaços), a sua conversão para um
número é obtida com a função str2num.
>> s = “ 23.76 “; a = str2num(s); b = 2*a
b = 47.52
• É interessante comparar o resultado acima com (porquê???)
>> s = “ 23.76 “; b = 2*s
s = [64,100,102,92,110,108,64,64]
• A conversão oposta, pode fazer-se com a função num2str.
27 Abril 2007 Processamento de Texto 7
Concatenação de Sequências de Caracteres
• As sequências podem ser concatenadas. Esta operação é utilizada para juntar
numa só sequência a informação que está dispersa por várias sequências. Por
exemplo, para juntar
– O(s) nome(s) próprio(s) ao(s) apelido(s)
– Os vários campos de um endereço (rua, nº, andar, local, etc.)
• O Octave tem uma função strcat, para esse efeito.
• Exemplo: Juntar um nome próprio e um apelido.
>> np = “Rui”; ap = “Lopes”; nome= strcat(np,“ ”,ap)
nome = “Rui Lopes”
• De notar a utilização da sequência com um branco (“ ”) para espaçar o nome
próprio e o apelido.
27 Abril 2007 Processamento de Texto 8
Partição de Sequências de Caracteres
• As sequências podem ser “partidas” noutras mais simples, havendo várias formas
de fazer essa partição.
• Uma forma possível é através de caracteres que funcionam como separadores
(tipicamente espaços).
• O Octave tem uma função, split, para esse efeito, criando uma matriz de
sequências, cada sequência na sua linha, com brancos acrescentados se
necessário
• Exemplo: Separar os nomes (próprios e apelidos) de uma pessoa.
>> nome = “Rui da Costa Pina”; nms = split(nome,“ ”)
nms = “Rui ”
“da ”
“Costa”
“Pina ”
27 Abril 2007 Processamento de Texto 9
Extracção de Sequências de Caracteres
• Por vezes estamos interessados apenas em partes de uma sequência. Uma forma
comum de o fazer é indicar
– o índice do primeiro caracter pretendido para a subsequência; e
– o comprimento da subsequência.
tendo o Octave tem uma função, substr, para esse efeito.
• Por exemplo: Separar os nomes (próprios e apelidos) de uma pessoa.
>> nome = “Rui da Costa Pina”;
nm1 = substr(nome,1,3), nm2 = substr(nome,5,2),
nm3 = substr(nome,8,5), nm4 = substr(nome,14,4),
nm1= “Rui”, nm2= “da”, nm3= “Costa”, nm4= “Pina”
• Os índices variam de 1 ao comprimento da cadeia. Este comprimento é obtido
pela função length.
>> nome = “Rui da Costa Pina”; x = length(nome)
x= 17
27 Abril 2007 Processamento de Texto 10
Comparação de Caracteres
• Uma operação vulgar no processamento de texto é a ordenação “por ordem
alfabética”.
• Esta ordenação requer a comparação “alfabética” de caracteres.
• Esta pode ser feita através da comparação “numérica” dos códigos dos
caracteres.
• A comparação só é fácil se os códigos usados respeitam a ordem alfabética, o
que acontece em todos os códigos.
• Por exemplo, em ASCII, o código dos caracteres “A” e “B” é, respectivamente, 65
e 66, pelo que se pode fazer a correspondência pretendida
o caracter c1 “vem antes do” caracter c2 c1 < c2
• Exemplo: >> teste = “a” < “b”
teste = 1
27 Abril 2007 Processamento de Texto 11
Comparação de Caracteres
• A comparação “literal” pode ser obtida a partir da comparação caracter a caracter.
• O Octave tem uma função, strcmp, para verificar se duas cadeias são idênticas.
nm1 = “Rui Costa”; nm2 = “Rui Costa”; t = strcmp(nm1,nm2)
t = 1
• Para o teste de precedência alfabética (designado por “<<“) o Octave não dispõe
de funções predefinidas. Mas elas podem ser definidas tendo em conta a
comparação caracter a caracter.
• Vamos pois definir uma função my_str_before como:
my_str_before (s1,s2) =
1 se s1 << s2
0 se s1 = s2
-1 se s1 >> s2
27 Abril 2007 Processamento de Texto 12
Comparação de Sequências de Caracteres
• Dada a natureza recursiva da função my_before, esta utiliza uma função auxiliar,
my_str_tail, para obter a “cauda da cadeia (isto é, sem o seu primeiro caracter).
function t = my_str_tail(s) c = length(s); if c == 1 t =""; else t = substr(s,2,c-1); endif;endfunction;
• A função my_before compara os primeiros caracteres das sequências (se existirem). Se estes forem iguais, compara as caudas das sequências (chamada recursiva).
27 Abril 2007 Processamento de Texto 13
Comparação de Sequências de Caracteres
function b = my_str_before(s1,s2)
c1 = length(s1); c2 = length(s2);
if c1 == 0 & c2 == 0 b = 0; elseif c1 == 0 & c2 > 0 b = 1; elseif c1 > 0 & c2 == 0 b = -1;
else % c1 > 0 & c2 > 0 if s1(1) < s2(1) b = 1; elseif s1(1) > s2(1) b = -1;
else t1 = my_str_tail(s1); t2 = my_str_tail(s2);
b = my_str_before(t1,t2);
endif; endif;endfunction;
27 Abril 2007 Processamento de Texto 14
Comparação de Sequências de Caracteres
• A comparação de cadeias de caracteres “interpretáveis” (por exemplo, de texto em
português) é mais complexa.
• Os problemas mais frequentes são de 3 tipos:
– Ocorrência de espaços (e outros caracteres brancos)
• “Rui Santos” = “ Rui Santos “ ???
– Tratamento de letras maiúsculas e minúsculas
• “Rui Santos” = “RUI SANTOS “ ???
– Caracteres especiais (com acentos e cedilhas)
• “João França” = “Joao Franca“ ???
• Estes problemas têm de ser considerados no contexto apropriado (Franca e França
são apelidos diferentes, ou o terminal (telemóvel) não tinha o caracter “ç” ?), e
requerem algoritmos dedicados.
27 Abril 2007 Processamento de Texto 15
Comparação de Sequências com Brancos
• Os caracteres brancos servem para separar os “significativos”. Os mais vulgares
são os espaços, mas existem outros para mudança de linha (“\n”, “\r” ou “\f”), ou
tabulação (“\t” e “\v”).
• No código ASCII todos têm códigos inferiores a 32 (espaço).
• A comparação de cadeias pode simplificar-se se a comparação fôr feita após
normalização. Esta normalização, consiste em
– eliminar todos os brancos prefixos/sufixos, i.e. antes/depois do primeiro/último
caracter significativo.
– Substituir todos os separadores (grupos de brancos, tabs, mudanças de linha,
etc. por um só branco).
• Algumas funções pre-definidas podem auxiliar na normalização, mas o Octave não
tem esta função predefinida.
27 Abril 2007 Processamento de Texto 16
Substituição de Espaços por Brancos
• Assumindo que todos os caracteres brancos têm código inferior a 32, podemos
utilizar a função my_str_remctr, indicada abaixo, para substituir todos os
caracteres brancos por espaços.
function t = my_str_remctr(s)
for i = 1:length(s)
if toascii(s(i)) < 32
t(i) = " ";
else
t(i) = s(i);
endif;
endfor;
endfunction;
27 Abril 2007 Processamento de Texto 17
Eliminação de Brancos Prefixos e Sufixos
• O Octave dispõe de uma função (deblank) que elimina todos os espaços sufixos.
• A eliminação dos brancos prefixos pode igualmente usar essa função se se inverter
(passá-la de trás para a frente) a cadeia. Essa inversão pode usar a função
my_str_rev, indicada abaixo
function r = my_str_rev(s)
c = length(s);
for i = 1:c
r(i) = s(c-i+1);
endfor
endfunction;
27 Abril 2007 Processamento de Texto 18
Eliminação de Espaços Repetidos
• A eliminação dos espaços repetidos pode ser feita usando a função
my_str_remrep, indicada abaixo. A função percorre toda a cadeia mantendo a
informação (na variável booleana ultimo_branco) sobre se o último caracter era
branco. Nesse caso, se o caracter fôr espaço não o copia (seria repetido).
function t = my_remrep(s) j = 1; ultimo_branco = 0; for i = 1:length(s) if s(i) != " " t(j) = s(i); j = j+1; ultimo_branco = 0; elseif !ultimo_branco t(j) = s(i); j = j+1; ultimo_branco = 1; endif; endfor;endfunction;
27 Abril 2007 Processamento de Texto 19
Normalização de Sequências de Caracteres
• A normalização de cadeias de caracteres pode ser feita usando a função
my_str_norm, indicada abaixo, que utiliza todas as funções anteriores, da forma
esperada.
• Primeiro, substitui os brancos por espaços. Depois elimina os espaços sufixos. Em
terceiro lugar elimina os brancos prefixos (eliminando os brancos sufixos da cadeia
invertida, invertendo de novo o resultado). Finalmente, os espaços repetidos são
removidos.
function sn = my_str_norm(s)
s1 = my_str_remctr(s)
s2 = deblank(s1);
s3 = my_str_rev(deblank(my_str_rev(s2)));
sn = my_str_remrep(s3);
endfunction;
27 Abril 2007 Processamento de Texto 20
Eliminação de Espaços Repetidos
• A comparação de cadeias de caracteres pode ser feita usando a função my_str_norm_before, indicada abaixo, que não considera os caracteres brancos.
• As diferenças podem ser exemplificadas em baixo.
>> t = my_str_before(“Rui Lopes”, “ Rui Lopes”)
t = -1
>> t = my_str_norm_before(“Rui Lopes”, “ Rui Lopes”)
t = 0
function b = my_str_norm_before(s1,s2) sn1 = my_str_norm(s1); sn2 = my_str_norm(s2); b = my_str_before(sn1,sn2);endfunction;
27 Abril 2007 Processamento de Texto 21
Comparações com Maiúsculas / Minúsculas
• A comparação de cadeias de caracteres pode ser igualmente prejudicada pela
existência de letras maiúsculas e minúsculas.
• O Octave tem algumas funções que facilitam o tratamento deste tipo de situações,
nomeadamente as funções tolower e toupper, que convertem os caracteres
maiúsculos / minúsculos em caracteres minúsculos / maiúsculos.
>> s1 = “\n Rui \t Lopes”; s2 = “RUI lopes”; sn1 = toupper(s1), sn2 = toupper(s2), t1 = my_str_norm_before(s1,s2), t2 = my_str_norm_before(sn1,sn2)
sn1 = “\n RUI \t LOPES” sn2 = “RUI LOPES” t1 = -1 t2 = 0
27 Abril 2007 Processamento de Texto 22
Conversões Maiúsculas / Minúsculas
• As funções anteriores assumem um código ASCII, em que os caracteres brancos
têm códigos abaixo de 32.
• Nesse código ASCII, a conversão entre maiúsculas e minúsculas pode ser feita
adicionando ou subtraindo a sua diferença aos códigos respectivos. Esta diferença
é 32, como pode ser verificado em
>> dif = toascii(“A”) – toascii(“a”)
dif = -32
• No entanto, a utilização destes valores pode ser problemática, se forem usados
outros códigos. É da responsabilidade da implementação da linguagem interpretar
ter em atenção os códigos usados (que podem não ser ASCII) e disponibilizar
primitivas independentes desses códigos.
27 Abril 2007 Processamento de Texto 23
Conversões Independentes do Código
• Algumas dessas primitivas são
– isalpha(s) 1 se s fôr alfabético (maiúscula ou minúscula)
– islower(s) 1 se s fôr uma minúscula
– isupper(s) 1 se s fôr uma maiúscula
– isdigit(s) 1 se s fôr um dígito
– isalnum(s) 1 se s fôr dígito ou alfabético
– ispucnt(s) 1 se s fôr um caracter de pontuação
– iscntrl(s) 1 se s fôr caracter de controle
• Desta forma as funções poderão ser rectificadas para se tornarem independentes
do código usado para representação dos caracteres. Em particular, o teste
toascii(s(i)) < 32
pode / deve ser substituido por
iscntrl(s2)
27 Abril 2007 Processamento de Texto 24
Sequências com Caracteres Especiais
• Os caracteres com cedilhas e acentos, típicos do português, não fazem parte do
código ASCII básico, e os seus códigos em ASCII estendido não respeitam a ordem
“natural”.
• Por exemplo, como os códigos dos caracteres “a”, “s” e “ã” são, respectivamente
97, 115 e 227, o nome João está alfabeticamente após José, ao contrário do que
acontece com Joao.
• Uma forma de manter a ordenação pretendida é utilizar, para efeitos de ordenação,
as cadeias com os caracteres acentuados substituídos pelos caracteres não
acentuados.
• O Octave dispõe de uma função (strrep) que substitui numa cadeia base, todas as
de uma (sub)cadeia por outra.
>> s1 = “João”; s2 = strrep(s1,”ã”,”a”)
s2 = “Joao”