Difference between revisions of "Problema da separação das sílabas"
From AdonaiMedrado.Pro.Br
(→Dificuldade 2) |
|||
| (12 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 | + | 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 | + | #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 17: | Line 16: | ||
Onde: | Onde: | ||
| − | *.<sub>0</sub> (caractere ponto) caso presente no início indica que | + | *.<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 | + | *.<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 | + | 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 51: | 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: | ||
| + | |||
| + | #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 | + | 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 | ||
| − | + | ==== 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 == | == Referências == | ||
<references/> | <references/> | ||
Latest revision as of 13:18, 15 July 2009
Contents
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:
- 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:
.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:
- 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
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.0 1.1 1.2 Arquivo README_hyph_pt_BR.txt em http://www.broffice.org/files/hyph_pt_BR-203.zip
