Improved algorithms on strings

改进的字符串算法

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

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).

我研究处理被称为字符串的字母序列的方法（算法）——对象如此简单，似乎不需要“算法”！但是，首先，字符串无处不在：文本文件、计算机程序（数百万个字母）、一本书（英文或中文）、人类基因组（30亿个字母）、一天的电子邮件流量（数万亿个字母）。其次，字符串的有效处理是必不可少的：基因组中重复的子字符串可能具有重要的生物学/遗传学意义，短语可能需要在文本文件或计算机程序中识别/更改，书籍可能需要搜索重要的短语，电子邮件流量可能需要搜索不受欢迎的消息（垃圾邮件）。