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

From AdonaiMedrado.Pro.Br
Jump to: navigation, search
(Saída)
(Dificuldade 2)
 
(7 intermediate revisions by the same user not shown)
Line 8: Line 8:
 
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." <ref name="arquivo_readme">Arquivo README_hyph_pt_BR.txt em http://www.broffice.org/files/hyph_pt_BR-203.zip</ref>
 
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." <ref name="arquivo_readme">Arquivo README_hyph_pt_BR.txt em http://www.broffice.org/files/hyph_pt_BR-203.zip</ref>
  
Segundo <ref name="arquivo_readme" /> ele funciona conforme o algoristmo de Frank M. Liang da seguinte forma:
+
Segundo <ref name="arquivo_readme" />, ele funciona conforme o algoritmo de Frank M. Liang da seguinte forma:
 
#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.
 
#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.
#quando uma palavra precisa ser divida as particulas são utilizadas e processadas para identificar os pontos de divisão.
+
#quando uma palavra precisa ser divida as partículas são utilizadas e processadas para identificar os pontos de divisão.
  
 
Cada partícula possui o seguinte formato:
 
Cada partícula possui o seguinte formato:
Line 16: Line 16:
  
 
Onde:
 
Onde:
*.<sub>0</sub> (caractere ponto) caso presente no início indica que a partícula deve ocorrer no início da palavra.
+
*.<sub>0</sub> (caractere ponto) caso presente no início da partícula indica que ela deve ocorrer no início da palavra.
 
*<letra<sub>n</sub>> é uma letra minúscula do alfabeto.
 
*<letra<sub>n</sub>> é uma letra minúscula do alfabeto.
 
*<digito<sub>n</sub>> pode ser omitido e é um dígito de inteiro positivo no intervalo fechado entre 1 e 9.
 
*<digito<sub>n</sub>> pode ser omitido e é um dígito de inteiro positivo no intervalo fechado entre 1 e 9.
*.<sub>1</sub> (caractere ponto) caso presente no final indica que a partícula deve ocorrer no final da palavra.
+
*.<sub>1</sub> (caractere ponto) caso presente no final da partícula indica que ela deve ocorrer no final da palavra.
  
 
Caso <digito<sub>n</sub>> 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).
 
Caso <digito<sub>n</sub>> 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 <ref name="arquivo_readme" /> para o processamento da palavra '''silábicas'''. As particulas pertinentes são: s2i, i3l2á, l4á, á1b2, 3b2i, i1c4, 3c2a, 2s.
+
O processamento é realizando sobrepondo-se as partículas na palavra considerando-se o maior dígito em caso de partículas que tratem de uma mesma subcadeia da palavra. Observe abaixo o exemplo de <ref name="arquivo_readme" /> para o processamento da palavra '''silábicas'''. As partículas pertinentes são: s2i, i3l2á, l4á, á1b2, 3b2i, i1c4, 3c2a, 2s.
  
 
  s i l á b i c a s
 
  s i l á b i c a s
Line 38: Line 38:
 
  s2i3l4á3b2i3c4a2s  <--- Resultado
 
  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  
+
Faça um programa que, recebendo um número N, um conjunto R de N partículas e uma palavra P, mostre:
  
 
#o resultado do processamento.
 
#o resultado do processamento.
Line 68: Line 68:
 
  silábi-cas
 
  silábi-cas
 
  si-lá-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 ==
 
== 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 [http://www.adonaimedrado.pro.br/wiki/documentos/outros/hyph_pt_BR.dic hyph_pt_BR.dic].
+
Resolva o mesmo problema só que desta vez, ao invés de você receber uma lista de partículas para cada palavra, você deverá ler uma lista fixa no arquivo [http://www.adonaimedrado.pro.br/wiki/documentos/outros/hyph_pt_BR.dic 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).
+
Este arquivo também é do projeto VERO do BrOffice (http://www.broffice.org/verortografico), porém sofreu 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.
+
Nesta dificuldade, o programa só receberá a palavra como entrada e retornará além do solicitado na dificuldade 1 as partículas de fato utilizadas no processamento da palavra.
  
 
=== Exemplo 1 ===
 
=== Exemplo 1 ===
Line 88: Line 104:
 
  r2o
 
  r2o
 
  r4a
 
  r4a
  p0r2o3g4r4a1m2a
+
  pr2o3g4r4a1m2a
 
  pro-grama
 
  pro-grama
 
  progra-ma
 
  progra-ma
Line 95: Line 111:
 
=== Exemplo 2 ===
 
=== Exemplo 2 ===
 
==== Entrada ====
 
==== Entrada ====
  capturar
+
  computador
  
 
==== Saída ====
 
==== Saída ====
  1t2u
+
  1d2o
  2p3t4
+
  1p2u
 +
1t2a
 +
2m3p4
 
  4r.
 
  4r.
  a2r.
+
  a1d2o
  a3p2
+
  o2m1p2u
  r2a2r.
+
  o4r.
  r4a
+
  u3t2
  u1r2a
+
  co2m3p4u3t2a1d2o4r
  c0a3p3t4u1r4a4r
+
  com-putador
  ca-pturar
+
  compu-tador
  cap-turar
+
  computa-dor
  captu-rar
+
  com-pu-ta-dor
  
 
=== Exemplo 3 ===
 
=== Exemplo 3 ===

Latest revision as of 13:18, 15 July 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 algoritmo 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 partículas 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 da partícula indica que ela 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 da partícula indica que ela 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 o maior dígito em caso de partículas que tratem de uma mesma subcadeia da palavra. Observe abaixo o exemplo de [1] para o processamento da palavra silábicas. As partículas 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 partículas 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 sofreu uma pequena alteração para este problema (exclusão da primeira linha).

Nesta dificuldade, o programa só receberá a palavra como entrada e retornará além do solicitado na dificuldade 1 as partículas 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