Exact and Approximation Pattern Matching, and Network Routing

这一建议的主要重点是“模式匹配”，即在一个更大的主体（通常称为“文本”）中识别一个称为“模式”的对象。图案可能是一个DNA序列，而文本是DNA序列的（大）集合。虽然我们已经很好地理解了如何找到一个对象的精确匹配，但找到一个对象的类似实例却不是很好地理解，或者至少不知道如何几乎有效地找到它们。此外，我们可以很自然地假设，随着被匹配对象之间的相似性越来越高，这项任务的执行效率也会越来越高。但是，总的来说，实现这一目标仍然存在问题。这个项目的目的是开发效率随着相似性的增加而提高的方法。激励问题包括已经提到的DNA匹配、文本主体中的单词或短语匹配以及图像中的对象匹配。该提案的第二个重点是对网络交换机的研究；更具体地说，用于发送（路由）消息的方法的设计和用于促进这种路由的设计。

The main focus of this proposal is on "pattern matching", the identifying of an object, called the "pattern", in a larger body, often called the `text". The pattern might be a DNA sequence and the text a (large) collection of DNA sequences. While it is fairly well understood how to find exact matches of an object, finding similar instances of an object is not as well understood, or at least it is not known how to find them nearly as efficiently. Further, it is natural to suppose that this task can be carried out progressively more efficiently the greater the similarity between the objects being matched. But, by and large, achieving this remains problematic. The aim of this project is to develop methods whose efficiency improves in tandem with increased similarity. Motivating problems include the already mentioned DNA matching, matching of words or phrases in bodies of text, and matching of objects in images. A secondary focus for this proposal is the study of network switches; more specifically, the devising of methods for sending (routing) messages and designs for facilitating such routings.