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

点击翻译按钮获取中文摘要

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.