Improved algorithms on strings

我研究处理被称为字符串的字母序列的方法（算法）——对象如此简单，似乎不需要“算法”！但是，首先，字符串无处不在：文本文件、计算机程序（数百万个字母）、一本书（英文或中文）、人类基因组（30亿个字母）、一天的电子邮件流量（数万亿个字母）。其次，字符串的有效处理是必不可少的：基因组中重复的子字符串可能具有重要的生物学/遗传学意义，短语可能需要在文本文件或计算机程序中识别/更改，书籍可能需要搜索重要的短语，电子邮件流量可能需要搜索不受欢迎的消息（垃圾邮件）。18年来，我一直在设计这样的算法。当前和未来的研究主要集中在三个主要领域：(1)利用最近对字符串“规律”本质的见解，我寻求有效计算重复子字符串的新方法——特别是在计算生物学、数据挖掘和数据压缩方面的应用。本质上，我寻求对弦的周期性更精确的数学理解。(2)“后缀数组”是一种专门用于提高字符串算法效率的数据结构。我寻求使用后缀数组的新的高效算法，同样频繁地应用于计算生物学和许多其他领域。(3)在实践中出现的许多问题中，可能需要处理包含“不确定”（未完全定义）条目的字符串。我寻求更快更有效的算法来对这些不确定的字符串进行模式匹配和其他操作。

I conduct research into methods (algorithms) for processing sequences of letters called strings -- objects so simple that there seems to be no need of "algorithms"!  But, first of all, strings are ubiquitous: a text file, a computer program (millions of letters), a book (in English or Chinese), the human genome (3 billion letters), one day's e-mail traffic (trillions of letters).  Secondly, efficient processing of strings is essential: repeating substrings in a genome may be of great biological/genetic significance, phrases may need to be identified/changed in a text file or computer program, books may need to be searched for significant phrases, e-mail traffic may need to be searched for undesirable messages (spam).For 18 years I have been designing such algorithms.  Current and future research focusses on three main areas:(1) Using recent insights into the nature of "regularities" in strings, I seek new methods to efficiently compute repeating substrings -- with applications particularly to computational biology, data mining and data compression.  Essentially I seek a more precise mathematical understanding of periodicity in strings.(2) The "suffix array" is a specialized data structure used to improve the efficiency of string algorithms.  I seek new efficient algorithms that use suffix arrays, again with frequent application to computational biology and many other areas.(3) In many problems that arise in practice, it may be necessary to process strings that contain "indeterminate" (not fully defined) entries.  I seek faster more effective algorithms for doing pattern-matching and other operations on these indeterminate strings.