Defesa de Dissertação de Mestrado de Mário Veronesi Medina, 26/02/26, 14h, sala 215, bloco R, Instituto de Computação, e por videoconferência
Link para defesa: https://meet.google.com/gxr-izjo-vza
Abordagens Computacionais para Indexação de Conjuntos de Parikh em Alfabetos Binário e de Tamanho Constante
Resumo:
Esta dissertação investiga o problema de Jumbled Pattern Indexing (JPI), também conhecido como problema do histograma ou dos vetores de Parikh, que consiste em determinar se uma palavra contém um fator cuja composição de símbolos coincide com um vetor dado, independentemente da ordem. Inicialmente, são apresentados os fundamentos teóricos do problema e os principais resultados da literatura, com distinção explícita entre o caso binário e o caso de alfabetos de tamanho constante, destacando-se propriedades estruturais, limites inferiores conhecidos e os trade-offs entre tempo de indexação e tempo de consulta. No regime binário, propõe-se o algoritmo exato SfTree, baseado em árvores de sufixos, que explora a compactação de fatores distintos para eliminar o processamento redundante de subcadeias repetidas durante a construção das tabelas de indexação; embora o limite inferior clássico permaneça válido no pior caso, a análise teórica e os resultados experimentais demonstram ganhos práticos substanciais, com comportamento linear em instâncias altamente repetitivas e desempenho robusto em cenários adversos. Para alfabetos de tamanho constante, o trabalho introduz o conceito de palavras normais de raiz (Radix Normal Words – RNWs), que generaliza as palavras normais de prefixo, estabelecendo propriedades combinatórias fundamentais dessa classe; com base nessa estrutura, é apresentado o algoritmo heurístico E-Cut, que constrói, em tempo linear por símbolo, um índice aproximado baseado em intervalos, cujo tempo de consulta no pior caso permanece linear. Os experimentos empíricos indicam que a heurística produz estimativas numericamente próximas dos valores corretos das tabelas de indexação, com erro absoluto e relativo controlado, que tende a diminuir à medida que crescem o comprimento da palavra e a cardinalidade do alfabeto. Em conjunto, os resultados evidenciam que a exploração consciente da estrutura combinatória das palavras é central para o desenvolvimento de algoritmos eficientes de indexação embaralhada, tanto em abordagens exatas quanto heurísticas.
Abstract:
This dissertation investigates the Jumbled Pattern Indexing (JPI) problem, also known as the histogram or Parikh vector problem, which consists of determining whether a string contains a factor whose symbol composition matches a given vector, regardless of order. We first review the theoretical foundations of the problem and the main results from the literature, explicitly distinguishing between the binary case and the case of constant-size alphabets, highlighting structural properties, known lower bounds, and trade-offs between indexing and query times. In the binary setting, we introduce the exact SfTree algorithm, based on suffix trees, which exploits the compact representation of distinct factors to eliminate redundant processing during index construction; although the classical worst-case lower bound still applies, theoretical analysis and experimental results demonstrate substantial practical improvements, with linear-time behavior on highly repetitive instances and robust performance on adversarial inputs. For constant-size alphabets, we introduce the notion of Radix Normal Words (RNWs), which generalize prefix normal words and exhibit fundamental combinatorial properties; building on this structure, we present the heuristic E-Cut algorithm, which constructs an interval-based approximate index in linear time per symbol, while maintaining linear worst-case query time. Empirical evaluations show that the heuristic produces estimates that are numerically close to the exact index values, with controlled absolute and relative errors that tend to decrease as both the input length and the alphabet size increase. Overall, the results demonstrate that leveraging the combinatorial structure of strings is central to the design of efficient algorithms for jumbled pattern indexing, encompassing both exact and heuristic approaches.
Banca examinadora:
Prof. Luís Felipe Ignácio Cunha, UFF – Presidente
Prof. Leandro Santiago de Araújo, UFF
Prof. Daniel Fabio Domingues Posner, UFRRJ