2012-03-11 181 views
0

我想要一个算法来提供某种程度的字符串是如何对称的。在查看前面的问题时,我找到了一个找到需要添加到字符串的字母数把它变成回文。这与我正在查找的内容很接近,但在允许的编辑操作集中限制太多。到最近的回文的距离

我的动机是我想制作一个视频的改进版本,我把它放在Youtube上,名为“数字是丰富多彩的”视频显示黄金比例基数和其他一些使用非理性基础的相关系统。令人惊讶的是,一个系统是从完全对称开始的。但其他人展现了我想强调的部分对称性。

+0

你想考虑加或减字母使字符串对称吗?直接比较中心点的字母可以提供一种对称性。如果你确实想把abcb看作“非常对称”,那么你只需要在字符串中加一个'a'来使它完全对称是很重要的。否则,你会比较[a] {b} {c} [b]并看到它完全不对称。 – 2012-03-11 00:35:16

+0

考虑:1001010.0010101。这似乎是非常对称的,因为对于每个正数,都有一个相应的负数,它不应该距离它应该是的“太远”。因此,像左右移动数字这样的操作似乎被要求。将字母作为基本操作添加和减去字母时,可以从字符串的一个边删除一个字母,然后向另一个边添加一个新字母。换句话说,需要有一个地方性的概念。 – 2012-03-11 01:30:31

+0

这对我来说没有多大意义。我仍然不明白你的对称性是什么。那是二进制数字吗?我知道有些人认为在二进制文件中,但我不默认。它们相当于向左循环移位,它不是对称的。你能否用更多的例子来更新你的问题来说清楚?你必须澄清**完全**你认为什么是“对称”之前任何人都可以帮助你。 – 2012-03-11 02:29:59

回答

0

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

除非你明确你想要识别的是什么,否则这个问题的定义太差,无法给出明智的答案。如果你确实是对称的,给我一个对称的例子。你可能也意味着“我可以在这里看到一些有趣的模式”,这是很难定量,很难量化。

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

考虑您的号码中的数字是输入信号。对此信号执行频率分析以检测重复的数字部分。如果在你的一系列数字中有强大的重复成分,这应该与分析中的强频率成分有关。您可以通过执行傅里叶变换来识别基频,并对最重要频率仓的所有谐波进行求和,从而测量这种模式的强度。除以信号的总能量,这会给你一个介于0和1之间的测量,说明信号是如何“重复”的,并且还将识别信号的周期性。使用自相关,AMDF或YIN估计器等时域算法可能会更好。 (特别是AMDF)

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

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

+0

一个完全对称的数字系统由Christiane Froughy,On乘法相关的线性数学系统和周期点描述,“R.A.I.R.O.理论信息学和应用36(2002)293-314。其他数字表示相似,但“不太对称”。这些数字系统将数字表示为离散数字的序列,因此信号处理是错误的。以黄金比例基数计算1-9(见维基百科),其中省略了基数pt:1,1001,10001,10101,10001001,10100001,10000000001,100010001,100100101,100100101。两个回文和“几乎未命中”。 – 2012-03-11 13:56:36

+0

在我的“Numbers are Colorful”YouTube视频http://bit.ly/y5pjv7中,您可以看到第三列中完全对称的数字。 我现在通过谷歌搜索发现了一些相关文献“不完美的对称性措施”。引自Zabrodsky等人的“连续相似性测量:”我们认为,根据或者当涉及到对称性特征时,对自然现象的处理可能会限制到现象学观测的一些细节和他们的理论解释可能会丢失。有些物体比其他物体更对称“ – 2012-03-11 14:48:20