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

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

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.