Improved algorithms on strings

我研究了处理字符串的方法（算法）--字符串是如此简单，以至于似乎不需要“算法”！ 但是，首先，字符串是无处不在的：一个文本文件，一个计算机程序（数百万个字母），一本书（英语或中文），人类基因组（30亿个字母），一天的电子邮件流量（数万亿个字母）。 其次，字符串的有效处理是必不可少的：基因组中重复的子字符串可能具有很大的生物学/遗传学意义，文本文件或计算机程序中的短语可能需要识别/更改，书籍可能需要搜索重要短语，电子邮件流量可能需要搜索不受欢迎的消息（垃圾邮件）。 当前和未来的研究集中在三个主要领域：（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.