Processamento de Texto
Pedro Barahona
DI/FCT/UNL
Introdução aos Computadores e à Programação
2º Semestre 2005/2006
27 Abril de 2006
Recursividade e Iteração
1
Processamento de Texto
• 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;
– Cadeias de caracteres (“strings”).
27 Abril de 2006
Recursividade e Iteração
2
Caracteres
• 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 de 2006
Recursividade e Iteração
3
Cadeias de Caracteres
• Cadeias de caracteres (“strings”) são sequências (ordenadas)
de caracteres.
• Em quase todas as linguagens, dados do tipo caracter e cadeia
(incluindo simples caracteres) 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 de 2006
Recursividade e Iteração
4
Cadeias de Caracteres e Vectores
• Em geral, e Octave não foge à regra, cadeias 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 cadeias : toascii: <cadeia>  <vector>
>> a = toascii(“ABC”)
– Cadeias em vectores :
 a = [65,66,67]
setstr: <vector>  <cadeia>
>> 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 cadeias,
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 de 2006
Recursividade e Iteração
5
Conversão de Cadeias de Caracteres
• Cadeias de caracteres podem ser processados de várias formas.
Para as mais comuns, existem funções pré-definidas.
• Algumas dessas funções permitem converter cadeias de
caracteres que representam números para os próprios números.
• Exemplo: Dada a cadeia “ 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 de 2006
Recursividade e Iteração
6
Concatenação de Cadeias de Caracteres
• As cadeias podem ser concatenadas. Esta operação é utilizada
para juntar numa só cadeia a informação que está dispersa por
várias cadeias. 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 cadeia com um branco (“ ”) para espaçar
o nome próprio e o apelido.
27 Abril de 2006
Recursividade e Iteração
7
Partição de Cadeias de Caracteres
• As cadeias podem ser “partidas” noutras mais simples. Neste
caso pode haver várias formas de fazer a partição. Uma 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 cadeias, cada cadeia 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 de 2006
Recursividade e Iteração
8
Extracção de Cadeias de Caracteres
• Por vezes estamos interessados apenas em partes de uma cadeia.
Uma forma comum de o fazer é indicar
– o índice do primeiro caracter pretendido para a subcadeia; e
– o comprimento da subcadeia.
• 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 de 2006
Recursividade e Iteração
9
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 de 2006
Recursividade e Iteração
10
Comparação de Cadeias 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) =
27 Abril de 2006
1
0
-1
se s1 << s2
se s1 = s2
se s1 >> s2
Recursividade e Iteração
11
Comparação de Cadeias 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 cadeias
(se existirem). Se estes forem iguais, compara as caudas das
cadeias (chamada recursiva).
27 Abril de 2006
Recursividade e Iteração
12
Comparação de Cadeias 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 de 2006
Recursividade e Iteração
13
Comparação de Cadeias 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 de 2006
Recursividade e Iteração
14
Comparação de Cadeias 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 de 2006
Recursividade e Iteração
15
Substituição de Brancos por Espaços
• 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 de 2006
Recursividade e Iteração
16
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 de 2006
Recursividade e Iteração
17
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 de 2006
Recursividade e Iteração
18
Normalização de Cadeias 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 de 2006
Recursividade e Iteração
19
Comparação de Cadeias com Brancos
• 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.
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;
• 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
27 Abril de 2006
Recursividade e Iteração
20
Comparação 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
sn1
t1
t2
=
=
=
=
“\n Rui \t Lopes”; s2 = “RUI lopes”;
toupper(s1), sn2 = toupper(s2),
my_str_norm_before(s1,s2),
my_str_norm_before(sn1,sn2)
 sn1
sn2
t1
t2
27 Abril de 2006
=
=
=
=
“\n RUI \t LOPES”
“RUI LOPES”
-1
0
Recursividade e Iteração
21
Conversão entre Maiúsculas/Minúsculas
• As funções anteriores assumem um código ASCII, em que os
caracteres brancos têm códigos abiaxo 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 de 2006
Recursividade e Iteração
22
Conversão independente 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
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 de 2006
Recursividade e Iteração
23
Cadeias 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”
27 Abril de 2006
Recursividade e Iteração
24