Difference between revisions of "Problema da separação das sílabas"

Revision as of 12:01, 11 March 2009

Dificuldade 1

Geralmente um processador de textos utiliza algum algoritmo para fazer a hifenização das palavras. Neste algoritmo são consideradas posições onde a palavra pode ser divida. Por exemplo, a palavra programação têm as seguintes possibilidades para a divisão silábica:

pro-gramação
progra-mação
programa-ção

O divisor silábico do BrOffice está sob a Licença Pública Geral Menor versão 2.1 (LGPLv2.1) e funciona "com base no léxico do VERO, através de análise combinatória, extraíndo-se os casos reais e descartando-se as condições inexistentes." ^[1]

Segundo ^[1], ele funciona conforme o algoristmo de Frank M. Liang da seguinte forma:

1. são carregadas uma série de partículas indicando pontos onde a divisão é possível e onde a divisão deve ser evitada.
2. quando uma palavra precisa ser divida as particulas são utilizadas e processadas para identificar os pontos de divisão.

Cada partícula possui o seguinte formato:

.0<letra0><digito0><letra1><digito1>...<letran><digiton>.1

Onde:

• .₀ (caractere ponto) caso presente no início indica que a partícula deve ocorrer no início da palavra.
• <letra_n> é uma letra minúscula do alfabeto.
• <digito_n> pode ser omitido e é um dígito de inteiro positivo no intervalo fechado entre 1 e 9.
• .₁ (caractere ponto) caso presente no final indica que a partícula deve ocorrer no final da palavra.

Caso <digito_n> seja um número par, o ponto não é preferível para divisão silábica, caso seja impar o ponto é preferível. Quanto maior o valor, maior a preferência pela divisão (caso impar) ou pela não divisão (caso par).

O processamento é realizando sobrepondo-se as partículas na palavra considerando-se, em caso de particulas que tratem de uma mesma subcadeia da palavra, o maior dígito. Observe abaixo o exemplo de ^[1] para o processamento da palavra silábicas. As particulas pertinentes são: s2i, i3l2á, l4á, á1b2, 3b2i, i1c4, 3c2a, 2s.

s i l á b i c a s
s2i 
    l4á
  i3l2á
    l4á
      á1b2
       3b2i
          i1c4
           3c2a
               2s.
------------------
s2i3l4á3b2i3c4a2s   <--- Resultado

Faça um programa que, recebendo um número N, um conjunto R de N partículas e uma palavra P, mostre

1. o resultado do processamento.
2. todas as divisões silábicas possíveis (uma por linha) em ordem de preferência.
3. a separação das sílabas das palavras.

Considere que:

• N será um número inteiro tal que 1<=N<=1000.
• cada partícula do conjunto R tem até 10 caracteres.
• a palavra P tem até 100 caracteres.

Exemplo 1

Entrada

8
s2i
i3l2á
l4á
á1b2
3b2i
i1c4
3c2a
2s.
silábicas

Saída

s2i3l4á3b2i3c4a2s
si-lábicas
silá-bicas
silábi-cas
si-lá-bi-cas

Exemplo 2

Entrada

5
1c2i
ê2n1c2
i1ê
i2a
n3c42
ciência

Saída

ci1ê2n3c4i2a
ciên-cia
ci-ência
ci-ên-cia

Dificuldade 2

Resolva o mesmo problema só que desta vez, ao invés de você receber uma lista de particulas para cada palavra, você deverá ler uma lista fixa no arquivo hyph_pt_BR.dic.

Este arquivo também é do projeto VERO do BrOffice (http://www.broffice.org/verortografico), porém sofre uma pequena alteração para este problema (exclusão da primeira linha).

Nesta difilculdade o programa só receberá a palavra como entrada e retornará além do solicitado na dificuldade 1 as particulas de fato utilizadas no processamento da palavra.

Exemplo 1

Entrada

programa

Saída

1g4r2
1m2a
a1m2a
o3g2
o3g2
r2o
r4a
pr2o3g4r4a1m2a
pro-grama
progra-ma
pro-gra-ma

Exemplo 2

Entrada

computador

Saída

1d2o
1p2u
1t2a
2m3p4
4r.
a1d2o
o2m1p2u
o4r.
u3t2
co2m3p4u3t2a1d2o4r
com-putador
compu-tador
computa-dor
com-pu-ta-dor

Exemplo 3

Entrada

universidade

Saída

1d2a
1d2e
1n2i
1s2i
1v2e
a1d2e
e2r3s4i
i3d2
i3v2
r1s2i
u1n2i
u1n2i3v2e2r3s4i3d2a1d2e
uni-versidade
univer-sidade
universi-dade
u-niversidade
universida-de
u-ni-ver-si-da-de

Referências

1. ↑ ^{1.0 1.1 1.2} Arquivo README_hyph_pt_BR.txt em http://www.broffice.org/files/hyph_pt_BR-203.zip