palindrome - 到最近回文的距离

Question

我想要一种算法来提供某种衡量字符串对称程度的方法。在查看以前的问题时，我发现了一个关于找到需要添加到字符串中以将其变成回文的字母数量的算法。这与我正在寻找的内容很接近，但在允许的编辑操作中过于严格。

我这样做的动机是，我想制作一个改进版的视频，放在 Youtube 上，名为“数字是多彩的”。该视频展示了黄金比例基数和其他几个使用非理性基数的相关系统。令人惊讶的是，一个系统开始时是完全对称的。但其他人表现出部分对称，我想强调一下。

Answer 1

你在寻找重复还是对称？到目前为止，我还没有看到任何例子表明对称性只是重复。1001010.0010101 不对称。它们通过循环移位相关，即取第一组数字 [1001010]，将其向左移动 1 [0010101]，现在你有了右侧。

除非您明确说明您要确定的内容，否则这个问题的定义太差，无法给出合理的答案。如果你真的是说对称，给我看一个对称的例子。您也可以说“我可以在这里看到一些有趣的模式”，它的定义很差，很难量化。

也就是说，数字信号处理是您可能会研究的用于识别有趣模式的领域。例如，如果您正在寻找重复，那么我建议您尝试使用为检测重复模式而设计的算法。

将您号码中的数字视为输入信号。对此信号执行频率分析以检测数字的重复部分。如果您的数字序列中有很强的重复分量，这应该与分析中的强频率分量有关。您可以通过执行傅里叶变换来识别基频，并对最重要频率区间的所有谐波求和来测量此模式的强度。将其除以信号的总能量，这将为您提供一个介于 0 和 1 之间的衡量信号的“重复性”程度，并且还将识别信号的周期性。使用自相关、AMDF 或 YIN 估计器等时域算法可能会更好。（特别是 AMDF）

如果您要考虑实际对称性（即当您反转它们时数字仍然非常相似），可以采用类似的方法。获取您的输入数字，通过反转它创建一个新信号，然后在每个离散测量它们的“相同性”阶段。如果您有一个长度为 N 的数字，您可以考虑在将信号与其反转的自身进行比较之前用 0 填充它到长度 2N，以考虑数字位于数字长度之外的可能性。

时域技术更有可能发挥作用，因为它们不受不连续性的影响太大。他们确实通过计算每个相位的所有点的差异或将每个相位的数字相乘来比较信号的“相同性”。在减法的情况下，当它们相似时，您希望达到 0。在乘法的情况下，您希望在数字回到同相时在函数中获得一个峰值。然而，它们更容易产生噪音（在这种情况下，这意味着不完全正确的数字）。