AF: Small: Theoretical Aspects of Repetition-Aware Text Compression and Indexing

能够高效地存储、搜索和分析海量数据集是当今紧迫的挑战之一。为此目的，本项目将研究文本压缩和索引下的一系列问题，这些问题与当前有很大的相关性，因为许多现代文本数据集中普遍存在一种称为高度重复性的具体特征。这一特性使得数据可以使用一些专门的方案进行高度压缩。然而，对这些计划的理论理解仍处于初级阶段。这个项目将解决在实践中流行的几个方案的有效性方面的一些基本的公开问题。该项目还将引入新的想法，以高度节省空间的方式索引这类数据，并快速支持各种(特定于应用程序的)查询。该项目开发的技术将适用于广泛的算法问题和应用；因此，它们将对相关领域产生持久的影响。这项研究的主要结果将通过主要会议、期刊和研讨会教程进行传播。将确保本科生和包括妇女在内的少数群体的参与。后缀树和后缀数组是文本索引的两种基本数据结构，在生物信息学中有着广泛的应用。然而，它们因其空间复杂性而臭名昭著。FM索引使用Burrow-Wheeler变换(BWT)在接近基于熵的下界的空间中对后缀数组进行编码。但是，压缩的熵模型在捕捉重复性方面效率较低。因此，现代应用程序要求使用更节省空间的编码来利用重复性。尽管社区最近在精确模式匹配方面取得了一些进展，但许多其他(更复杂的)匹配问题的解决方案仍然悬而未决。为此，该项目将尝试为不匹配、编辑和通配符情况下的模式匹配设计支持重复的索引，以及高效的构造算法。这个项目还旨在开发一个统一的框架来压缩几个高级后缀树变体(准后缀树)，这些后缀树支持更复杂的匹配范例，如参数化和顺序同构匹配。将寻求超越现有基于BWT的方法的新技术和概念。此外，该项目将尝试对BWT-RUN的各个方面以及相对的Lempel-Ziv压缩方案进行更深入的研究。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Being able to store, search, and analyze massive data sets efficiently is one of today's pressing challenges. To that end, this project will study a collection of problems under text compression and indexing with tremendous current relevance, owing to a specific characteristic prevalent in many modern text data sets, called high repetitiveness. This characteristic makes the data highly compressible using some specialized schemes. However, the theoretical understanding of those schemes is still in a nascent stage. This project will address some of the fundamental open problems on the effectiveness of several schemes that are popular in practice. This project will also introduce new ideas for indexing such data in a highly space-efficient manner and quickly support various (application-specific) queries. The techniques developed in this project will apply to a broad class of algorithmic problems and applications; therefore, they will have a lasting impact on related fields. The main results stem from this research will be disseminated through major conferences, journals, and workshop tutorials. The participation of undergraduates and minorities, including women, will be ensured. Suffix trees and suffix arrays are two fundamental data structures for text indexing with many applications in bioinformatics. However, they are notorious for their space complexity. The FM-index index encodes suffix arrays in space close to the entropy-based lower bound using the Burrows-Wheeler Transformation (BWT). But, the entropy model of compression is less effective in capturing repetitiveness. Therefore, modern applications urge even more space frugal encodings that exploit repetitiveness. Although the community has made some recent progress in exact pattern matching, solutions to many other (more complex) matching problems are still open. To that end, this project will attempt to design repetition-aware indexes for pattern matching under mismatches, edits, and wildcards, along with efficient construction algorithms. This project also aims to develop a unified framework to compress several advanced suffix-tree variants (quasi-suffix trees) that support even more complex matching paradigms such as parameterized and order-isomorphic matching. Novel techniques and concepts that go beyond the existing BWT-based methods will be sought. Additionally, the project will attempt a deeper study on various aspects of BWT-runs and the relative Lempel-Ziv compression scheme from the hardness side.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.