"Regularities in Strings: New Combinatorial Properties, More Efficient Algorithms, Applications"

“字符串中的规则：新的组合属性、更高效的算法、应用程序”

• 批准号: 8180-2012
• 负责人: Smyth, William
• 金额: $ 1.24万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568564
• 关键词: Regularities; Strings; New; Combinatorial; Properties

One of the prominent features of the last quarter-century, especially the last ten years, has been the "information explosion", the vast increase in data that is stored, transmitted, processed by computers and communications devices. With such huge data sets, efficiency of processing matters very much. The operations that must be performed are often very simple, usually describable as computing "patterns" in strings, but collectively they must be performed quickly. What mathematicians call a "string" (or "word") is a sequence of letters drawn from some alphabet; for example, a day's e-mail traffic (trillions of binary digits), the Internet (tens of billions of web pages, averaging thousands of characters each), the human genome (three billion letters A, C, G, or T) and other genomes (up to a trillion letters). At present much of the processing of strings depends on the computation of global data structures called "suffix arrays", while at the same time the pattern being sought is local and small. In a sense, then, current methods, sophisticated and powerful as they are, are nevertheless still "brute force" -- they do not use the local combinatorial properties of the string that determine whether the pattern is there or not. The basic idea of this proposal is to provide local combinatorial analysis that will determine the existence (or not) of the desired patterns as the string is traversed from left to right. This analysis depends on a simple, partially-proved conjecture (12 out of 14 subcases have been established within one of several cases): three independent squares cannot occur in a confined neighbourhood within a string. In recent papers the applicant's results go far beyond what was known before; this project's purpose is to take the combinatorial analysis to its conclusion, then make use of the results to design algorithms that are sensitive to local conditions in the string, and that therefore can execute much more quickly by means of a simple left-to-right scan.

在过去的四分之一世纪，特别是过去十年，一个突出的特点是“信息爆炸”，大量增加的数据存储，传输，处理计算机和通信设备。 对于如此庞大的数据集，处理效率非常重要。 必须执行的操作通常非常简单，通常可以描述为计算字符串中的“模式”，但它们必须快速执行。 数学家所谓的“字符串”（或“单词”）是从某种字母表中提取的字母序列;例如，一天的电子邮件流量（数万亿个二进制数字），互联网（数百亿个网页，平均每个网页有数千个字符），人类基因组（30亿个字母A，C，G或T）和其他基因组（高达1万亿个字母）。 目前，字符串的大部分处理都依赖于被称为“后缀数组”的全局数据结构的计算，而与此同时，所寻求的模式是局部的和小的。 从某种意义上说，当前的方法虽然复杂而强大，但仍然是“蛮力”--它们没有使用字符串的局部组合属性来确定模式是否存在。 这个提议的基本思想是提供局部组合分析，当从左到右遍历字符串时，该分析将确定所需模式的存在（或不存在）。 这种分析依赖于一个简单的、部分证明的猜想（14个子情况中的12个子情况已经在几种情况中的一种情况下建立）：三个独立的正方形不可能出现在一个弦内的一个封闭的邻域中。 在最近的论文中，申请人的结果远远超出了以前所知的;该项目的目的是将组合分析带到其结论，然后利用结果设计对字符串中的局部条件敏感的算法，因此可以通过简单的从左到右扫描更快地执行。