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

在数字图书馆中搜索字符串是一项基本操作。人们可以在文本编辑器正在处理的文件中查找短语，通过搜索引擎在网络上查找句子，或者在人类DNA序列中查找基因组。这一基本工具已经得到了很好的研究，确实在数据处理中无处不在。然而，在通用数据库中处理搜索的字符串匹配和模体发现算法(Stringology)总是假设搜索的字符串是有序的。研究的方向是精确匹配、近似匹配，或者努力应对数据中的错误。但数据的顺序一直被认为是铁板一块的。然而，一些不一致的问题一直在侵蚀这一假设的墙壁。一些应用程序假定数据顺序错误的领域是：文本编辑，在文本编辑中，错误如交换或换位，假设数据没有改变--相反，它被重新排列；计算生物学，基因组子序列的颠倒或换位是进化过程的一部分；语言学，通过考虑各种顺序的词性集合来辅助词汇分类任务。上述应用领域表明，完美有序的模式匹配世界可能过于僵化，无法应对新的挑战。该项目引入了一种全新的字符串匹配模型，在该模型中，输入模式中符号的顺序可能会受到干扰，但内容保持不变。该模型研究无序模式匹配领域，为上述应用领域提供合适的计算工具。无序匹配理论将给出所有上述问题的一般框架。本项目将置换Stringology视为从完全有序的数据一直到完全无序的数据的一条线。在历史上，人们对有序的一面进行了充分的研究。该项目的具体技术目标是：1。开发置换序列学的理论和框架。找出比有序语系学更难的无序问题的类型，使其更难的条件，以及原因。在无序集群中定义术语‘’相似性‘’。定义“几乎有序序列”的世界，并将其与无序序列和有序序列进行比较。设计工具，这些工具将成为所提出问题的解决方案中的关键要素，并将被多个算法共享。问题清单包括索引、词典和近似。这个项目的目的是研究模式匹配和重排模型所产生的基本问题。对该领域的直接好处是一个全新的、但非常基础的研究方向，似乎无视最先进的工具包。历史上的模式匹配工具，如动态编程、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.