AF: Medium: Collaborative Research: The Role of Order in Search

在数字图书馆中搜索字符串是一项基本操作。人们可以在文本编辑器处理的文件中寻找短语，通过搜索引擎在网络上寻找句子，或者在人类DNA序列中寻找基因组。这个基本的工具已经被很好地研究过了，事实上，它在数据处理中无处不在。然而，处理一般数据库中搜索的字符串匹配和主题发现算法（“Stringology”）总是假设所搜索的字符串是有序的。研究的重点是精确匹配、近似匹配或应对数据错误的挑战。但是，数据的顺序总是被假定为铁一般的，然而，一些不符合要求的问题一直在啃噬着这个假设的墙壁。一些应用程序假设数据顺序错误的领域是：文本编辑，其中错误如交换或换位，假设数据没有被改变-而是被重新排列;计算生物学，其中基因组序列的逆转或换位是进化过程的一部分;和语言学，其中词汇分类的任务是通过考虑部分的集合来帮助的，上述应用领域表明，模式匹配的奇妙有序世界可能过于僵化，无法应对新的挑战。该项目引入了一种全新的字符串匹配模型，其中输入模式中的符号顺序可能会受到干扰，但内容保持不变。该模型研究无序模式匹配宇宙，为上述应用领域提供合适的计算工具。无序匹配理论将为上述所有问题提供一个通用框架。本项目将置换字符串学视为从完全有序的数据一直到完全无序的数据的一条线。有序的一面在历史上已经得到了充分的研究。本项目的具体技术目标是：1.建立置换字符学的理论和框架.找出无序问题的类型比有序弦学更难，使它们更难的条件，以及原因。在无序聚类中定义术语"相似性“。4.定义了“几乎有序序列”的世界，并将其与无序序列和有序序列进行了比较.设计工具，这些工具将成为所提出问题的解决方案中的关键要素，并将由多个算法共享。问题列表包括索引，字典和近似。这个项目的目的是研究的基本问题所产生的模式匹配与重排模型。对该领域的直接好处是一个全新的，但非常基本的研究方向，似乎无视最先进的工具包。传统的模式匹配工具，如动态规划、FFT、子字树、重命名、编码和嵌入，似乎不适合处理这些问题。需要新的算法工具和数据结构。事实上，这一方向已经取得了意想不到的有趣成果--数学家凯莱在1849年提出的图论中的一个开放问题的解决方案！到目前为止，非标准卷积、分组测试和图论算法等技术已经成为解决一些问题的必要手段。由于该项目定义了一个新的模型，因此有许多方向需要探索。预计这一项目将标志着在一个新的范式密集研究的开始。

Searching for a string in a digital library is a fundamental operation. One may seek a phrase in a file that is being manipulated by a text editor, a sentence on the web via a search engine, or a genome in the human DNA sequence. This basic tool has been well researched and, indeed, is ubiquitous in data processing.However, string matching and motif discovery algorithms ("Stringology") that have dealt with searches in general databases, have always assumed that the sought string is ordered. The research thrusts were in directions such as exact matching, approximate matching, or grappling with the challenge of coping with errors in the data. But always the order of the data was assumed to be iron-clad.Nevertheless, some non-conforming problems have been gnawing at the walls of this assumption. Some of the areas where applications assume erroneous order of the data are: Text Editing, where errors such as swaps or transpositions, assume that the data has not been changed -- it has rather been rearranged; Computational Biology, where reversals or transpositions of genome subsequences are part of the evolutionary process; and Linguistics, where the task of lexical categorization is aided by considering sets of parts-of-speech in various orders.The above application areas suggest that the wonderfully ordered world of pattern matching may be too rigid to handle new challenges. This project introduces a fundamentally new model of string matching, where the order of symbols in the input pattern may be perturbed, but the content remains unchanged. This model studies unordered pattern matching universes in order to supply the above mentioned application areas with appropriate computational tools. A theory of unordered matching will give a general framework for all the above problems.This project considers permuted Stringology as a line leading from fully ordered data all the way to data with no order at all. The ordered side has been historically amply researched. The specific technical goals of the project are:1. To develop a theory and framework for permuted Stringology.2. To identify the types of unordered problems that are more difficult than ordered Stringology, the conditions that make them harder, and the reason why.3. To define the term ``Similarity'' in unordered clusters.4. To define the world of ``almost ordered sequences'', and to compare it with unordered and ordered sequences.5. To design tools that will be key elements in the solution for the proposed problems, and will be shared by more than one algorithm. The list of problems includes Indexing, Dictionary and Approximations.This project's aim is to study the fundamental problems arising from a model of pattern matching with rearrangement. The immediate benefit to the field is a totally new, yet very basic, research direction that seems to defy the state-of-the-art toolkit. The historical tools of pattern matching, such as dynamic programming, FFT, sub-word trees, renaming, encodings, and embeddings do not seem suitable to handle these problems. New algorithmic tools and data structures are required. In fact, this direction already bore unexpected interesting fruits -- the solution of an open problem in graph theory posed by the mathematician Cayley in 1849! Techniques such as non-standard convolutions, group testing, and graph theoretic algorithms, have been necessary to solve some of the problems thus far.Since this project defines a new model, there are many directions to explore. It is expected that this project will mark the beginning of intensive research in a new paradigm.