Difference between revisions of "Problema da separação das sílabas"
(→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 | + | 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 16: | 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 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 | + | 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 | + | 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 | + | 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 | ||
− | + | pr2o3g4r4a1m2a | |
pro-grama | pro-grama | ||
progra-ma | progra-ma | ||
Line 95: | Line 111: | ||
=== Exemplo 2 === | === Exemplo 2 === | ||
==== Entrada ==== | ==== Entrada ==== | ||
− | + | computador | |
==== Saída ==== | ==== Saída ==== | ||
− | + | 1d2o | |
− | + | 1p2u | |
+ | 1t2a | ||
+ | 2m3p4 | ||
4r. | 4r. | ||
− | + | a1d2o | |
− | + | o2m1p2u | |
− | + | o4r. | |
− | + | u3t2 | |
− | + | co2m3p4u3t2a1d2o4r | |
− | + | com-putador | |
− | + | compu-tador | |
− | + | computa-dor | |
− | + | com-pu-ta-dor | |
=== Exemplo 3 === | === Exemplo 3 === |
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