Collaborative Research: Information Theory of Data Structures

1953年，信息论的创始人克劳德·香农指出，没有一种理论可以将体现在结构中的信息量化；这种情况今天仍然存在。近年来，随着各种应用产生的结构化数据集的激增，对这种理论的需求变得迫切。我们还没有回答一些基本的问题，比如：结构信息的存储和处理的基本限制是什么？从大型生物数据库中提取信息的基本限制是什么？缺乏对这些问题的理解可能会严重阻碍复杂系统科学和工程的进一步发展。这项工作的主要目标是寻找方法和算法来评估人工制品和自然物体中体现的组织和结构的数量。我们建议在数据结构的信息论方面取得进展。数据越来越多地以各种形式（例如，序列、表达式、相互作用、结构）提供，并且数量呈指数级增长。大多数此类数据是多维的，依赖于上下文；因此，从非常规数据结构中提取有意义的信息需要新颖的理论和高效的算法。在压缩这样的数据结构时，必须考虑两类信息：结构本身所传递的信息，以及结构中植入的数据标签所传递的信息。该项目的具体目标是：(i)描述数据结构所传递的信息总量（以及如何将其分解为上述两种类型的信息），以及（ii）基于(i)中所传递的信息总量设计有效的压缩算法。

In 1953, Claude Shannon, the founder of information theory, pointed out that there is no theory via which information embodied in structure can be quantified; this situation remains in effect today. The need for such a theory has become pressing in recent years with the proliferation of structured data sets arising from diverse applications. We have yet to answer fundamental questions such as:What are fundamental limits on storage and processing of structural information? What are fundamental bounds on extraction of information from large biological databases? Lack of understanding of such questions threatens to raise severe impediments to further advances in science and engineering of complex systems. The main goal of this work is to search for measures and algorithms to appraise the amount of organization and structure embodied in artifacts and natural objects.We propose to make headway in information theory of data structures.Data is increasingly available in various forms (e.g., sequences, expressions, interactions, structures) and in exponentially increasing amounts. Most of such data is multidimensional and context dependent; thus it necessitates novel theory and efficient algorithms to extract meaningful information from non-conventional data structures. In compressing such a data structure, one must take into account two types of information: the information conveyed by the structure itself, and then the information conveyed by the data labels implanted in the structure. The specific goals of this project are: (i) characterization of the total amount of information conveyed by a data structure (and how this decomposes into the two types of information mentioned above), and (ii) the design of efficient compression algorithms based upon the total amount of information conveyed in (i).