• 文献检索
  • 文档翻译
  • 深度研究
  • 学术资讯
  • Suppr Zotero 插件Zotero 插件
  • 邀请有礼
  • 套餐&价格
  • 历史记录
应用&插件
Suppr Zotero 插件Zotero 插件浏览器插件Mac 客户端Windows 客户端微信小程序
定价
高级版会员购买积分包购买API积分包
服务
文献检索文档翻译深度研究API 文档MCP 服务
关于我们
关于 Suppr公司介绍联系我们用户协议隐私条款
关注我们

Suppr 超能文献

核心技术专利：CN118964589B侵权必究
粤ICP备2023148730 号-1Suppr @ 2026

文献检索

告别复杂PubMed语法，用中文像聊天一样搜索，搜遍4000万医学文献。AI智能推荐，让科研检索更轻松。

立即免费搜索

文件翻译

保留排版，准确专业，支持PDF/Word/PPT等文件格式，支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述，25分钟生成高质量综述，智能提取关键信息，辅助科研写作。

立即免费体验

一种用于香农熵全局评估和算法复杂度局部估计的分解方法。

A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity.

作者信息

Zenil Hector, Hernández-Orozco Santiago, Kiani Narsis A, Soler-Toscano Fernando, Rueda-Toicen Antonio, Tegnér Jesper

机构信息

Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute and SciLifeLab, SE-171 77 Stockholm, Sweden.

Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France.

出版信息

Entropy (Basel). 2018 Aug 15;20(8):605. doi: 10.3390/e20080605.

DOI:10.3390/e20080605
PMID:33265694
原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC7513128/
Abstract

We investigate the properties of a Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity based on Solomonoff-Levin's theory of algorithmic probability providing a closer connection to algorithmic complexity than previous attempts based on statistical regularities such as popular lossless compression schemes. The strategy behind BDM is to find small computer programs that produce the components of a larger, decomposed object. The set of short computer programs can then be artfully arranged in sequence so as to produce the original object. We show that the method provides efficient estimations of algorithmic complexity but that it performs like Shannon entropy when it loses accuracy. We estimate errors and study the behaviour of BDM for different boundary conditions, all of which are compared and assessed in detail. The measure may be adapted for use with more multi-dimensional objects than strings, objects such as arrays and tensors. To test the measure we demonstrate the power of CTM on low algorithmic-randomness objects that are assigned maximal entropy (e.g., π ) but whose numerical approximations are closer to the theoretical low algorithmic-randomness expectation. We also test the measure on larger objects including dual, isomorphic and cospectral graphs for which we know that algorithmic randomness is low. We also release implementations of the methods in most major programming languages- (Mathematica), , , , , , , and -and an online algorithmic complexity calculator.

摘要

我们研究了一种块分解方法（BDM）的性质，该方法扩展了编码定理方法（CTM）的能力。CTM基于所罗门诺夫 - 莱文的算法概率理论来近似算法复杂度的局部估计，与基于统计规律（如流行的无损压缩方案）的先前尝试相比，它与算法复杂度的联系更为紧密。BDM背后的策略是找到能生成更大的分解对象组件的小型计算机程序。然后，可以巧妙地将这些短计算机程序按顺序排列以生成原始对象。我们表明，该方法能提供算法复杂度的有效估计，但在失去准确性时其表现类似于香农熵。我们估计了误差，并研究了BDM在不同边界条件下的行为，所有这些都进行了详细的比较和评估。该度量可适用于比字符串更多的多维对象，例如数组和张量等对象。为了测试该度量，我们展示了CTM对具有最大熵（例如π）但数值近似更接近理论低算法随机性预期的低算法随机性对象的能力。我们还对包括对偶、同构和共谱图在内的更大对象进行了测试,我们知道这些对象的算法随机性较低。我们还发布了该方法在大多数主要编程语言（Mathematica）以及其他语言中的实现，以及一个在线算法复杂度计算器。

https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/06a4c4fa9210/entropy-20-00605-g011.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/c9fe47221784/entropy-20-00605-g0A1.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/feff74853d08/entropy-20-00605-g0A2.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/49472f59aeb3/entropy-20-00605-g0A3a.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/8de2854bc88c/entropy-20-00605-g0A4.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/adf6bc44f51d/entropy-20-00605-g001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/380929eecb21/entropy-20-00605-g002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/d13a87395e4f/entropy-20-00605-g003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/4e30fa7d03c3/entropy-20-00605-g004.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/64b7eba9faab/entropy-20-00605-g005.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/6a7c14b926a4/entropy-20-00605-g006.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/92aefd8d5a77/entropy-20-00605-g007.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/9ebbcda642f5/entropy-20-00605-g008.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/7e9ab96b376f/entropy-20-00605-g009.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/234de20260bb/entropy-20-00605-g010.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/06a4c4fa9210/entropy-20-00605-g011.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/c9fe47221784/entropy-20-00605-g0A1.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/feff74853d08/entropy-20-00605-g0A2.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/49472f59aeb3/entropy-20-00605-g0A3a.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/8de2854bc88c/entropy-20-00605-g0A4.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/adf6bc44f51d/entropy-20-00605-g001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/380929eecb21/entropy-20-00605-g002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/d13a87395e4f/entropy-20-00605-g003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/4e30fa7d03c3/entropy-20-00605-g004.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/64b7eba9faab/entropy-20-00605-g005.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/6a7c14b926a4/entropy-20-00605-g006.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/92aefd8d5a77/entropy-20-00605-g007.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/9ebbcda642f5/entropy-20-00605-g008.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/7e9ab96b376f/entropy-20-00605-g009.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/234de20260bb/entropy-20-00605-g010.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/f491/7513128/06a4c4fa9210/entropy-20-00605-g011.jpg

相似文献

1
A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity.一种用于香农熵全局评估和算法复杂度局部估计的分解方法。
Entropy (Basel). 2018 Aug 15;20(8):605. doi: 10.3390/e20080605.
2
Symmetry and Correspondence of Algorithmic Complexity over Geometric, Spatial and Topological Representations.算法复杂性在几何、空间和拓扑表示上的对称性与对应性。
Entropy (Basel). 2018 Jul 18;20(7):534. doi: 10.3390/e20070534.
3
Methods of information theory and algorithmic complexity for network biology.网络生物学的信息论与算法复杂性方法
Semin Cell Dev Biol. 2016 Mar;51:32-43. doi: 10.1016/j.semcdb.2016.01.011. Epub 2016 Jan 21.
4
A Review of Graph and Network Complexity from an Algorithmic Information Perspective.从算法信息视角看图与网络复杂性综述
Entropy (Basel). 2018 Jul 25;20(8):551. doi: 10.3390/e20080551.
5
An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity.一种用于逼近柯尔莫哥洛夫前缀复杂度的加法最优解释器。
Entropy (Basel). 2024 Sep 20;26(9):802. doi: 10.3390/e26090802.
6
Algorithmic complexity for short binary strings applied to psychology: a primer.短二进制字符串在心理学中的算法复杂度：简介。
Behav Res Methods. 2014 Sep;46(3):732-44. doi: 10.3758/s13428-013-0416-0.
7
The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy.网络编码的热力学以及最大熵原理的算法改进。
Entropy (Basel). 2019 Jun 3;21(6):560. doi: 10.3390/e21060560.
8
Algorithmic complexity for psychology: a user-friendly implementation of the coding theorem method.心理学的算法复杂性：编码定理方法的用户友好型实现
Behav Res Methods. 2016 Mar;48(1):314-29. doi: 10.3758/s13428-015-0574-3.
9
Low-algorithmic-complexity entropy-deceiving graphs.低算法复杂度的熵欺骗图
Phys Rev E. 2017 Jul;96(1-1):012308. doi: 10.1103/PhysRevE.96.012308. Epub 2017 Jul 7.
10
A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions.算法复杂度估计方法综述：选项、挑战与新方向
Entropy (Basel). 2020 May 30;22(6):612. doi: 10.3390/e22060612.

引用本文的文献

1
Teaching Recombinable Motifs Through Simple Examples.通过简单示例教授可重组基序
Cogn Sci. 2025 Aug;49(8):e70103. doi: 10.1111/cogs.70103.
2
Permutation Entropy and Its Niche in Hydrology: A Review.排列熵及其在水文学中的应用领域：综述
Entropy (Basel). 2025 Jun 3;27(6):598. doi: 10.3390/e27060598.
3
A Metric for the Entropic Purpose of a System.一种用于衡量系统熵目标的指标。

本文引用的文献

1
Low-algorithmic-complexity entropy-deceiving graphs.低算法复杂度的熵欺骗图
Phys Rev E. 2017 Jul;96(1-1):012308. doi: 10.1103/PhysRevE.96.012308. Epub 2017 Jul 7.
2
Methods of information theory and algorithmic complexity for network biology.网络生物学的信息论与算法复杂性方法
Semin Cell Dev Biol. 2016 Mar;51:32-43. doi: 10.1016/j.semcdb.2016.01.011. Epub 2016 Jan 21.
3
Algorithmic complexity for psychology: a user-friendly implementation of the coding theorem method.心理学的算法复杂性：编码定理方法的用户友好型实现
Entropy (Basel). 2025 Jan 26;27(2):131. doi: 10.3390/e27020131.
4
Carbon pricing drives critical transition to green growth.碳定价推动向绿色增长的关键转型。
Nat Commun. 2025 Feb 3;16(1):1321. doi: 10.1038/s41467-025-56540-3.
5
Shannon Entropy Computations in Navier-Stokes Flow Problems Using the Stochastic Finite Volume Method.基于随机有限体积法的纳维-斯托克斯流动问题中的香农熵计算
Entropy (Basel). 2025 Jan 14;27(1):67. doi: 10.3390/e27010067.
6
Key Node Identification Method Based on Multilayer Neighbor Node Gravity and Information Entropy.基于多层邻节点引力和信息熵的关键节点识别方法
Entropy (Basel). 2024 Nov 30;26(12):1041. doi: 10.3390/e26121041.
7
Cell Fate Dynamics Reconstruction Identifies TPT1 and PTPRZ1 Feedback Loops as Master Regulators of Differentiation in Pediatric Glioblastoma-Immune Cell Networks.细胞命运动力学重建确定TPT1和PTPRZ1反馈环是小儿胶质母细胞瘤-免疫细胞网络中分化的主要调节因子。
Interdiscip Sci. 2025 Mar;17(1):59-85. doi: 10.1007/s12539-024-00657-4. Epub 2024 Oct 17.
8
An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity.一种用于逼近柯尔莫哥洛夫前缀复杂度的加法最优解释器。
Entropy (Basel). 2024 Sep 20;26(9):802. doi: 10.3390/e26090802.
9
Building Test Batteries Based on Analyzing Random Number Generator Tests within the Framework of Algorithmic Information Theory.基于算法信息论框架内对随机数生成器测试的分析构建测试集。
Entropy (Basel). 2024 Jun 14;26(6):513. doi: 10.3390/e26060513.
10
Entropy-Based Methods for Motor Fault Detection: A Review.基于熵的电机故障检测方法综述
Entropy (Basel). 2024 Mar 28;26(4):299. doi: 10.3390/e26040299.
Behav Res Methods. 2016 Mar;48(1):314-29. doi: 10.3758/s13428-015-0574-3.
4
Structure emerges faster during cultural transmission in children than in adults.在文化传播过程中，儿童比成年人能更快地形成结构。
Cognition. 2015 Mar;136:247-54. doi: 10.1016/j.cognition.2014.11.038. Epub 2014 Dec 12.
5
Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines.从小型图灵机的输出频率分布计算柯尔莫哥洛夫复杂度。
PLoS One. 2014 May 8;9(5):e96223. doi: 10.1371/journal.pone.0096223. eCollection 2014.
6
Exploring statistical and population aspects of network complexity.探索网络复杂性的统计和人口方面。
PLoS One. 2012;7(5):e34523. doi: 10.1371/journal.pone.0034523. Epub 2012 May 8.
7
Novel topological descriptors for analyzing biological networks.用于分析生物网络的新型拓扑描述符。
BMC Struct Biol. 2010 Jun 17;10:18. doi: 10.1186/1472-6807-10-18.