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

From AdonaiMedrado.Pro.Br
Jump to: navigation, search
(New page: == Dificuldade 1 == == 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 n...)
 
(→‎Dificuldade 2)
 
(14 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
== Dificuldade 1 ==
 
== 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." <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 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.
 +
#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:
 +
.<sub>0</sub><letra<sub>0</sub>><digito<sub>0</sub>><letra<sub>1</sub>><digito<sub>1</sub>>...<letra<sub>n</sub>><digito<sub>n</sub>>.<sub>1</sub>
 +
 +
Onde:
 +
*.<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.
 +
*<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 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).
 +
 +
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
 +
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:
 +
 +
#o resultado do processamento.
 +
#todas as divisões silábicas possíveis (uma por linha) em ordem de preferência.
 +
#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 ==
 
== 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 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
  
−
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).
+
==== 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
  
−
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.
+
== Referências ==
 +
<references/>

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
Retrieved from "https://www.adonaimedrado.pro.br/wiki/index.php?title=Problema_da_separação_das_sílabas&oldid=3331"