Processamento de Texto Pedro Barahona DI/FCT/UNL Introdução aos Computadores e à Programação 2º Semestre 2007/2008

Processamento de Texto


Pedro BarahonaDI/FCT/UNL

Introdução aos Computadores e à Programação2º Semestre 2007/2008

7 Maio 2008 Processamento de Texto 2


• 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”).


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”)


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’


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)


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.


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.


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 ”


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


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


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


Comparação de Sequências 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;

• Desta forma, a função my_str_before compara os primeiros caracteres das

sequências (se existirem). Se estes forem iguais, compara as caudas das

sequências (chamada recursiva).



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;



• 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.


Comparação de Sequências com Brancos

• Os caracteres brancos servem para separar os caracteres “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.


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;


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;


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;


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 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 = 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;


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 esapços repetidos

nem 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;


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


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.


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

– ispunct(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(s(i))


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”

Documents

Processamento de Texto Pedro Barahona DI/FCT/UNL Introdução aos Computadores e à Programação 2º Semestre 2007/2008