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

From AdonaiMedrado.Pro.Br
Jump to: navigation, search
Line 80: Line 80:
  
 
==== Saída ====
 
==== Saída ====
  c0i1ê2n3c4i2a
+
  ci1ê2n3c4i2a
 
  ciên-cia
 
  ciên-cia
 
  ci-ência
 
  ci-ência
Line 104: Line 104:
 
  r2o
 
  r2o
 
  r4a
 
  r4a
  p0r2o3g4r4a1m2a
+
  pr2o3g4r4a1m2a
 
  pro-grama
 
  pro-grama
 
  progra-ma
 
  progra-ma
Line 123: Line 123:
 
  o4r.
 
  o4r.
 
  u3t2
 
  u3t2
  c0o2m3p4u3t2a1d2o4r
+
  co2m3p4u3t2a1d2o4r
 
  com-putador
 
  com-putador
 
  compu-tador
 
  compu-tador

Revision as of 02:05, 8 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:

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

Caso <digiton> 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