O vetor de sufixo é uma estrutura de dados importante utilizada em muitos problemas que envolvem cadeias de caracteres. Na literatura, muitos trabalhos têm sido propostos para a construção de vetores de sufixo em memória externa. Entretanto, esses trabalhos não enfocam conjuntos de cadeias, ou seja, não consideram vetores de sufixo generalizados. Essa limitação motiva esta dissertação, a qual avança no estado da arte apresentando o algoritmo eGSA, o primeiro algoritmo proposto para a construção de vetores de sufixo generalizados aumentado com o vetor de prefixo comum mais longo (LCP) e com a transformada de Burrows-Wheeler (BWT) em memória externa. A dissertação foi desenvolvida dentro do contexto de bioinformática, já que avanços tecnológicos recentes têm aumentado o volume de dados biológicos disponíveis, os quais são armazenados como cadeias de caracteres. O algoritmo eGSA foi validado por meio de testes de desempenho com dados reais envolvendo sequências grandes, como DNA, e sequências pequenas, como proteínas. Com relação aos testes comparativos com conjuntos de grandes cadeias de DNA, o algoritmo proposto foi comparado com o algoritmo correlato mais eficiente na literatura de construção de vetores de sufixo, o qual foi adaptado para construção de vetores generalizados. O algoritmo eGSA obteve um tempo médio de 3,2 a 8,3 vezes menor do que o algoritmo correlato e consumiu 50% menos de memória. Para conjuntos de cadeias pequenas de proteínas, foram realizados testes de desempenho apenas com o eGSA, já que no melhor do nosso conhecimento, não existem trabalhos correlatos que possam ser adaptados. Comparado com o tempo médio para conjuntos de cadeias grandes, o eGSA obteve tempos competitivos para conjuntos de cadeias pequenas. Portanto, os resultados dos testes demonstraram que o algoritmo proposto pode ser aplicado eficientemente para indexar tanto conjuntos de cadeias grandes quanto conjuntos de cadeias pequenas / The suffix array is an important data structure used in several string processing problems. In the literature, several approaches have been proposed to deal with external memory suffix array construction. However, these approaches are not specifically aimed to index sets of strings, that is, they do not consider generalized suffix arrays. This limitation motivates this masters thesis, which presents eGSA, the first external memory algorithm developed to construct generalized suffix arrays enhanced with the longest common prefix array (LCP) and the Burrows-Wheeler transform (BWT). We especially focus on the context of bioinformatics, as recent technological advances have increased the volume of biological data available, which are stored as strings. The eGSA algorithm was validated through performance tests with real data from DNA and proteins sequences. Regarding performance tests with large strings of DNA, we compared our algorithm with the most efficient and related suffix array construction algorithm in the literature, which was adapted to construct generalized arrays. The results demonstrated that our algorithm reduced the time spent by a factor of 3.2 to 8.3 and consumed 50% less memory. For sets of small strings of proteins, tests were performed only with the eGSA, since to the best of our knowledge, there is no related work that can be adapted. Compared to the average time spent to index sets of large strings, the eGSA obtained competitive times to index sets of small strings. Therefore, the performance tests demonstrated that the proposed algorithm can be applied efficiently to index both sets of large strings and sets of small strings

Existem autores que consideram os sufixos como unidades mínimas vazias de significado que não alteram a classe gramatical da base a que se integram para formar novos vocábulos. Todavia, inúmeros exemplos refutam tais afirmações (de adjetivos podemos derivar substantivos abstratos: feliz felicidade; o sufixo eiro pode compor substantivos, como pedreiro, assim como adjetivos, interesseiro). Desta forma, percebemos que os sufixos possuem significado autônomo e que fazem mais do que alterar a classe gramatical de um termo. O objetivo desta pesquisa é tratar do sufixo dade na língua portuguesa, ressaltando, por meio de paráfrases semânticas, os sentidos diacronicamente atestados em gramáticas e dicionários de língua portuguesa, especialmente no Dicionário eletrônico Houaiss da língua portuguesa (2001). Acreditamos que este tipo de análise colabora com estudos de sentidos e de datações atribuídos ao sufixo. Esta pesquisa se enquadra nas propostas do Grupo de Morfologia Histórica do Português da Universidade de São Paulo (GMHP/USP, http://www.usp.br/gmhp), sob a coordenação do Prof. Dr. Mário Eduardo Viaro. / There are some authors who consider suffixes as minimum units with no meaning that cannot form a word with a different morphological category from its basis. However, a lot of examples could be easily taken to refute such ideas (from adjectives abstract nouns can be derived: feliz felicidade; the Portuguese suffix eiro can be a compound of nouns, such as pedreiro, or adjectives, interesseiro). This shows us how suffixes carry an autonomy in their meaning and not only change the grammatical category of a derived word. The aim of this research is to analyze the Portuguese suffix dade, showing, through semantic paraphrases, the meanings diachronically presented in grammar books and dictionaries on Portuguese, especially in the Dicionário eletrônico Houaiss da língua portuguesa (2001). We argue that this type of analysis could enrich the studies about meanings and date occurrences associated to this particular suffix. This work is inserted within the purposes of the Grupo de Morfologia Histórica do Português da Universidade de São Paulo (GMHP/USP, Group of Historical Morphology of the Portuguese Language, http://www.usp.br/gmhp), under PhD. Mário Eduardo Viaro coordination.

O presente trabalho, resultado das pesquisas do GMHP, Grupo de Mofologia Histórica do Português, procura estudar os aspectos sincrônicos e diacrônicos do sufixo -ístico(a), bem como as relações existentes com o seu desdobramento -ística e com os sufixos -ismo e -ista, no português e no galego, para justificar, então, sua mudança morfológica de atuação deverbal para denominal, bem como as suas demais mudanças semânticas e as línguas responsáveis pela sua disseminação. Para tanto, utilizando-se a metodologia desenvolvida pelo grupo, e com corpora lexicográfico, historiográfico, ademais de literário e jornalístico, procura-se inicialmente por meio da elaboração de uma prospecção geral, estabelecer o período de início de atuação do sufixo além de verificar como é entendido pelas obras lingüísticas atuais nas duas línguas em estudo. Em seguida, estuda-se a sua gênese greco-latina e, posteriormente, sua atuação em outras línguas, como também suas relações sintagmáticas e paradigmáticas com os demais sufixos envolvidos, para se estabelecer uma evolução ao longo dos séculos, por meio da elaboração de classificações semântico-funcionais de cada período estudado, bem como avaliar a importância das línguas de cultura e dos processos de tradução na disseminação dos sufixos em questão. Nesse sentido, com a construção do glossário de datações e abonações de palavras formadas com o sufixo -ística, desdobramento de -ístico(a), pode-se verificar a grande importância da língua alemã, em detrimento da francesa, na veiculação do sufixo. Finalmente, com a análise da produtividade de -ístico(a) no português, mostra-se que um sufixo não é apenas provido de significado semântico e funcional, mas também é constituído vários outros matizes, dentre eles os que caracterizam o gênero textual em que atua. / The present work, a result of researches carried out by the GHMP (GMHP in Portuguese) - Group of Historical Morphology of the Portuguese Language - aims at studying both the synchronic and diachronic aspects of the suffix -ístico(a), as well as its existing relations with its evolution -ística and with the suffixes -ismo and -ista in Portuguese and Galician, in order to justify its morphological change from a deverbal to a denominal nature, its further semantic changes as well as the languages responsible for its dissemination. For such, by making use of the method evolved by the group and with lexicographical, historiographical, not to mention literary and journalistic corpora, initially we aim by means of the elaboration of a general prospection, to establish the initial period of functioning of the suffix besides observing how it is understood by the present linguistic works in the two languages under study. Then, its Greco-Latin genesis and subsequently its functioning in other languages are analyzed as well as its syntagmatic and paradigmatic relations with the other suffixes involved in order to establish an evolution throughout the centuries by means of the elaboration of functional-semantic classifications of each period under study, as well as to assess the importance of languages of culture and of processes of translations in the dissemination of the suffixes in question. Thus, with the construction of a glossary of dating and sample sentences of formations with -ística, the evolution of -ístico(a), the great importance of the German language, unlike the French language, in the diffusion of the suffix can be observed. Finally, with the analysis of the productivity of -ístico(a) in Portuguese, it can be demonstrated that a suffix is not only possessed by both a semantic and functional meaning, but is also constituted by various other nuances, among which the ones that characterize the textual gender in which it functions.

O vetor de sufixo é uma estrutura de dados importante utilizada em muitos problemas que envolvem cadeias de caracteres. Na literatura, muitos trabalhos têm sido propostos para a construção de vetores de sufixo em memória externa. Entretanto, esses trabalhos não enfocam conjuntos de cadeias, ou seja, não consideram vetores de sufixo generalizados. Essa limitação motiva esta dissertação, a qual avança no estado da arte apresentando o algoritmo eGSA, o primeiro algoritmo proposto para a construção de vetores de sufixo generalizados aumentado com o vetor de prefixo comum mais longo (LCP) e com a transformada de Burrows-Wheeler (BWT) em memória externa. A dissertação foi desenvolvida dentro do contexto de bioinformática, já que avanços tecnológicos recentes têm aumentado o volume de dados biológicos disponíveis, os quais são armazenados como cadeias de caracteres. O algoritmo eGSA foi validado por meio de testes de desempenho com dados reais envolvendo sequências grandes, como DNA, e sequências pequenas, como proteínas. Com relação aos testes comparativos com conjuntos de grandes cadeias de DNA, o algoritmo proposto foi comparado com o algoritmo correlato mais eficiente na literatura de construção de vetores de sufixo, o qual foi adaptado para construção de vetores generalizados. O algoritmo eGSA obteve um tempo médio de 3,2 a 8,3 vezes menor do que o algoritmo correlato e consumiu 50% menos de memória. Para conjuntos de cadeias pequenas de proteínas, foram realizados testes de desempenho apenas com o eGSA, já que no melhor do nosso conhecimento, não existem trabalhos correlatos que possam ser adaptados. Comparado com o tempo médio para conjuntos de cadeias grandes, o eGSA obteve tempos competitivos para conjuntos de cadeias pequenas. Portanto, os resultados dos testes demonstraram que o algoritmo proposto pode ser aplicado eficientemente para indexar tanto conjuntos de cadeias grandes quanto conjuntos de cadeias pequenas / The suffix array is an important data structure used in several string processing problems. In the literature, several approaches have been proposed to deal with external memory suffix array construction. However, these approaches are not specifically aimed to index sets of strings, that is, they do not consider generalized suffix arrays. This limitation motivates this masters thesis, which presents eGSA, the first external memory algorithm developed to construct generalized suffix arrays enhanced with the longest common prefix array (LCP) and the Burrows-Wheeler transform (BWT). We especially focus on the context of bioinformatics, as recent technological advances have increased the volume of biological data available, which are stored as strings. The eGSA algorithm was validated through performance tests with real data from DNA and proteins sequences. Regarding performance tests with large strings of DNA, we compared our algorithm with the most efficient and related suffix array construction algorithm in the literature, which was adapted to construct generalized arrays. The results demonstrated that our algorithm reduced the time spent by a factor of 3.2 to 8.3 and consumed 50% less memory. For sets of small strings of proteins, tests were performed only with the eGSA, since to the best of our knowledge, there is no related work that can be adapted. Compared to the average time spent to index sets of large strings, the eGSA obtained competitive times to index sets of small strings. Therefore, the performance tests demonstrated that the proposed algorithm can be applied efficiently to index both sets of large strings and sets of small strings