Automato dos sufixos (1993)
- Authors:
- Autor USP: KARPISCHEK, RICARDO UEDA - IME
- Unidade: IME
- Sigla do Departamento: MAP
- DOI: 10.11606/D.45.1993.tde-20210728-235623
- Assunto: LINGUAGENS FORMAIS
- Language: Português
- Abstract: Elaboramos uma prova da correcao e linearidade no tempo do algoritmo de construcao do automato dos sufixos devido a blumer et alii. Ressaltamos o fato de que esse algoritmo tambem obtem a arvore dos sufixos do reverso da entrada, fato conhecido mas pouco explorado. Demos ainda dois resultados negativos que obtivemos para o problema da representacao do automato dos sufixos em espaco linear preservando a linearidade no tempo de construcao (exige-se independencia no tamanho do alfabeto). Desenvolvemos uma implementacao espaco-economica do algoritmo de refinamento de manber e myers para a construcao do vetor dos sufixos. Ela consome 2/3 da memoria usada por aquela apresentada pelos autores. Fizemos alguns comentarios sobre a informatizacao do dicionario de oxford, e apresentamos um algoritmo degonnet et alii, desenvolvido durante aquele projeto de processamento de textos. Concluimos a dissertacao com um capitulo contendo alguns exemplos da atual interacao entre ciencia da computacao e biologia molecular
- Imprenta:
- Data da defesa: 11.08.1993
- Este artigo possui versão em acesso aberto
- URL de acesso aberto
- PDF de acesso aberto
- Versão do Documento: Versão publicada (Published version)
-
Status: Artigo publicado em periódico de acesso aberto (Gold Open Access) -
ABNT
KARPISCHEK, Ricardo Ueda. Automato dos sufixos. 1993. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1993. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210728-235623/. Acesso em: 16 mar. 2026. -
APA
Karpischek, R. U. (1993). Automato dos sufixos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210728-235623/ -
NLM
Karpischek RU. Automato dos sufixos [Internet]. 1993 ;[citado 2026 mar. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210728-235623/ -
Vancouver
Karpischek RU. Automato dos sufixos [Internet]. 1993 ;[citado 2026 mar. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210728-235623/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
