Processamento de Texto
Pedro Barahona
DI/FCT/UNL
Introdução aos Computadores e à Programação
2º Semestre 2008/2009
8 Maio 2008
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,
procurar, ordenar, passar para maiúsculas, etc...).
•
Este é apenas um exemplo de situações em que se pretende que os programas
efectuem processamento de texto.
•
Assim, todas as linguagens de programação prevêem tipos de dados para este
fim, nomeadamente
– Caracteres;
– sequências de caracteres (“strings”).
8 Maio 2008
Processamento de Texto
2
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”)
8 Maio 2008
Processamento de Texto
3
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 (‘ ’), devendo abrir-se e fechar-se com o
mesmo tipo de delimitadores.
•
Quando se pretende incluir um dos delimitadores no texto, pode usar-se o outro
delimitador
nome = “João d’Eça”
ou
frase= ‘ disse “Basta”’
•
...ou usarem-se sequências de escape
nome = ‘João d’’Eça’
•
ou
frase = “disse \“Basta\””
... que por vezes não se podem evitar
– frase_toda = “João d’Eça disse \”Basta\””
– frase_toda = ‘João d’’Eça disse “Basta”’
8 Maio 2008
Processamento de Texto
ou
4
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 = [65,66,67]
>> a = toascii(“ABC”)
– Sequências em vectores :
setstr: <vector>  <sequência>
>> b = setstr([97,98,99])
•
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
•
 b = ‘abc’
 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)
8 Maio 2008
Processamento de Texto
5
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.
8 Maio 2008
Processamento de Texto
6
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 ”
8 Maio 2008
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, separados por um espaço.
>> np = “Rui”; ap = “Lopes”; nome= strcat(np,“ ”,ap)
 nome = “Rui Lopes”
•
Dada a representação de sequências como vectores em Octave, o mesmo efeito
se conseguiria através da concatenação de vectores:
>> np = “Rui”; ap = “Lopes”; nome = [np,“ ”,ap]
8 Maio 2008
Processamento de Texto
8
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.
>> n = “Rui Andrade”; n1 = substr(n,1,3), n2 = substr(n,5,7),
 nm1= “Rui”, nm2= “Andrade”
•
O mesmo efeito se obteria pala definição de intervalos no vector, isto é
>> n = “Rui Andrade”; n1 = n(1:3), n2 = n(5:lenght(n))
 nm1= “Rui”, nm2= “Andrade”
•
Que utiliza afunção predefinida length.
>> x = length(nome)
 x= 17
8 Maio 2008
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
8 Maio 2008
Processamento de Texto
10
Comparação de Caracteres
•
A comparação “alfabética” de caracteres está assim muito dependente do código
utilizado na sua representação..
•
Se os código ASCII preserva a ordenação dos caracteres se ambos forem
maiúsculos ou minúsculos, já o mesmo não se verifica se um for maiusculo e
outro minúsculo.( por exemplo ‘a’ > ‘B’ !).
•
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.
>> ‘a’ < ‘B’,
ans = 0
>>
>>
8 Maio 2008
a = toupper(‘a’),
a = ‘A’
b =
a = tolower(‘a’),
a = ‘a’
b =
b = toupper(‘B’), a < b
‘B’,
ans = 1
b = tolower(‘B’), a < b
‘b’,
ans = 1
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
•
Não havendo função semelhante para que indique se uma sequência precede
ourtra, vamos implementar a função my_strcomp como:
my_strcmp (s1,s2) =
•
-1
se s1 << s2
0
se s1 = s2
1
se s1 >> s2
Desta forma, a função my_strcmp compara os primeiros caracteres das
sequências (se existirem). Se estes forem iguais, compara as caudas das
sequências (chamada recursiva).
8 Maio 2008
Processamento de Texto
12
Comparação de Sequências de Caracteres
function b = my_strcmp(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 = s1(2:c1);
t2 = s2(2:c2);
b = my_strcmp(t1,t2);
endif;
endif;
endfunction;
•
8 Maio 2008
De notar o caso em que as duas cadeias são vazias ou em que uma é vazia e a
outra não.
Processamento de Texto
13
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.
8 Maio 2008
Processamento de Texto
14
Comparação de Sequências com Brancos
• Existem vários caracteres de controle que servem para dar instruções ao computador
(mudar de linha, avançar o cursor para a próxima posição de tabela, etc.).
• Os mais vulgares são os caracteres de mudança de linha (“\n”, “\r” ou “\f”), e os de
tabulação (“\t” e “\v”)
Nota: usar aspas “ para delimitar sequências com estes caracteres.
• Adicianalmente, e em conjunto com os espaços, estes caracteres são considerados
brancos (não visíveis) e usados para separar “palavras” de caracteres visíveis.
• No código ASCII os caracteres de controle têm códigos inferiores a 32 (espaço). Em
todo o caso, a função Octave iscntrl(c) indica se o caracter c é um caracter de
controle, independentemente do código usado no computador.
• Assim pode definir-se a função blank(c) que indica se o caracter c é um caracter
branco
function b = blank(c)
b = (c == ‘ ‘ | iscntrl(c));
endfunction;
8 Maio 2008
Processamento de Texto
15
Comparação de Sequências com Brancos
• A comparação do conteúdo das sequências de caracteres pode assim simplificar-se
se a comparação fôr feita após normalização. Esta normalização, consiste em
– eliminar todos os separadores prefixos e sufixos, i.e. antes e depois do primeiro
e último caracter significativo, respectivamente.
– Eliminar todos os separadores repetidos, e substituí-los por um só espaço.
• Algumas funções pre-definidas podem auxiliar na normalização, mas o Octave não
tem esta função predefinida.
• Por exemplo, o Octave dispõe de uma função (deblank) que elimina todos os
espaços sufixos. Uma função semelhante, d2blank, pode ser implementada para
eliminar todos os espaços prefixos.
function t = d2blank(s)
i = 1;
while blank(s(i)) i = i+1;
t = s(i:length(s))
endfunction;
8 Maio 2008
endwhile;
Processamento de Texto
16
Eliminação de Brancos Repetidos
• A eliminação de brancos repetidos pode ser feita pela função ssumindo que todos
os caracteres brancos têm código inferior a 32, podemos utilizar a função remdup,
indicada abaixo, para substituir todos os caracteres brancos por espaços.
• A função varre todos os caracteres de
s a partir da segunda posição (o
• Para cada um, se ele não for branco
escreve-o em t (actualizando j, o
próximo caracter de t)
• Se for branco, só o escreve se o
anterior não tiver sido branco.
8 Maio 2008
function t = remdup(s)
if length(s) >= 1
t(1) = s(1); j = 2;
for i = 2:length(s)
if ! blank(s(i))
t(j) = s(i);
j = j +1;
elseif ! blank(s(i-1))
t(j) = ' ';
j = j + 1;
endif
endfor
endif
endfunction;
Processamento de Texto
17
Normalização de Sequências de Caracteres
• A normalização de cadeias de caracteres pode ser feita usando a função 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 espaços prefixos (eliminando os espaços sufixos da cadeia
invertida, invertendo de novo o resultado). Finalmente, os espaços repetidos são
removidos.
function sn = strnorm(s)
s1 = deblank(s)
s2 = d2blank(s1);
sn = remdup(s2)));
endfunction;
8 Maio 2008
Processamento de Texto
18
Eliminação de Espaços Repetidos
• A comparação de cadeias de caracteres pode ser feita usando a função
my_strcmpnorm, indicada anteriormente, que não considera os espaços repetidos
nem os caracteres brancos.
function b = normcmp(s1,s2)
sn1 = strnorm(s1);
sn2 = strnorm(s2);
b = my_strcmp(sn1,sn2);
endfunction;
• As diferenças podem ser exemplificadas em baixo.
>> t = normcmp(“Rui Lopes”, “ Rui Lopes”)
 t = -1
>> t = my_str_norm_before(“Rui
Lopes”, “ Rui Lopes”)
 t = 0
8 Maio 2008
Processamento de Texto
19
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)

8 Maio 2008
sn1 = “\n RUI \t LOPES”
sn2 = “RUI LOPES”
t1 = -1
t2 = 0
Processamento de Texto
20
Conversões Independentes do Código
• Algumas primitivas adicionais do Octave para testar tipos de caracteres
– 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
– ispunct(s)
1 se s fôr um caracter de pontuação
– iscntrl(s)
1 se s fôr caracter de controle
8 Maio 2008
Processamento de Texto
21
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”
8 Maio 2008
Processamento de Texto
22