Processamento de Texto
Jorge Cruz
DI/FCT/UNL
Programação para as Ciências Experimentais
1º Semestre 2005/2006
11 Novembro 2005
Processamento de Texto
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”).
11 Novembro 2005
Processamento de Texto
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”)
11 Novembro 2005
Processamento de Texto
3
Cadeias de Caracteres
• Cadeias de caracteres são sequências (ordenadas) de
caracteres.
• Em quase todas as linguagens, dados do tipo caracteres 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’
11 Novembro 2005
Processamento de Texto
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)
11 Novembro 2005
Processamento de Texto
5
Conversão de Cadeias de Caracteres
• Cadeias de caracteres podem ser processados de várias formas.
Para as mais comuns, existem funções predefinidas.
• 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
 b = [64,100,102,92,110,108,64,64]
• A conversão oposta, pode fazer-se com a função num2str.
11 Novembro 2005
Processamento de Texto
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.
11 Novembro 2005
Processamento de Texto
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 ”
11 Novembro 2005
Processamento de Texto
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
11 Novembro 2005
Processamento de Texto
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
11 Novembro 2005
Processamento de Texto
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
forma
1
my_str_before (s1,s2) =
0
-1
11 Novembro 2005
my_str_before da seguinte
se s1 << s2
se s1 = s2
se s1 >> s2
Processamento de Texto
11
Comparação de Cadeias de Caracteres
• Dada a natureza recursiva da função my_str_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_str_before compara os primeiros caracteres das
cadeias (se existirem). Se estes forem iguais, compara as caudas
das cadeias (chamada recursiva).
11 Novembro 2005
Processamento de Texto
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;
11 Novembro 2005
Processamento de Texto
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.
11 Novembro 2005
Processamento de Texto
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
for 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 predefinidas podem auxiliar na normalização,
mas o Octave não tem esta função predefinida.
11 Novembro 2005
Processamento de Texto
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;
11 Novembro 2005
Processamento de Texto
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;
11 Novembro 2005
Processamento de Texto
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 for espaço não o copia (seria repetido).
function t = my_str_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;
11 Novembro 2005
Processamento de Texto
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;
11 Novembro 2005
Processamento de Texto
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
11 Novembro 2005
Processamento de Texto
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
11 Novembro 2005
=
=
=
=
“\n RUI \t LOPES”
“RUI LOPES”
-1
0
Processamento de Texto
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 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.
11 Novembro 2005
Processamento de Texto
22
Conversão independente do Código
• Algumas dessas primitivas são
– isalpha(s) 1 se s for alfabético (maiúscula ou minúscula)
– islower(s) 1 se s for uma minúscula
– isupper(s) 1 se s for uma maiúscula
– isdigit(s)
1 se s for um dígito
– isalnum(s) 1 se s for dígito ou alfabético
– ispucnt
1 se s for um caracter de pontuação
– iscntrl(s)
1 se s for 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)
11 Novembro 2005
Processamento de Texto
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”
11 Novembro 2005
Processamento de Texto
24