压缩正弦波表

Question

压缩正弦波表

pythoncompressiontrigonometryrun-length-encoding

5

我有一个大数组，包含1024个条目，这些条目具有在range(14, 86)内的7位值。

这意味着存在多个索引范围具有相同的值。

例如,

consider the index range 741 to 795. It maps to 14
consider the index range 721 to 740. It maps to 15
consider the index range 796 to 815. It maps to 15

我希望将这张地图输入到一个Python程序中，然后输出以下内容：

if((index >= 741) and (index <= 795)) return 14;
if((index >= 721) and (index <= 740)) return 15;
if((index >= 796) and (index <= 815)) return 15;

一些使用groupby映射值的代码已准备好，但我在编写使用pairwise的表达式时遇到了困难。

有人以前做过类似的事情吗？

我已经上传了两种形式的数据集：

通常，按索引排序。

按映射值分组。

- PoorLuzer

这将在8位8051核心上运行。 - PoorLuzer

一个非常糟糕的表压缩尝试，我必须说。如果有人可以建议一种更好的方法（RLE和delta编码的混合？）来压缩数据集，并具有与数组查找相当的性能，那将不胜感激！ - PoorLuzer

2

RLE 编码可以在 g(n)=36 时对 228..255 进行进一步压缩，对 208..227 进行 35 压缩，对 195..207 进行 34 压缩，对 183..194 进行 33 压缩，对 173..182 进行 32 压缩，对 164..172 进行 31 压缩，对 156..163 进行 30 压缩。这取决于表大小和代码大小之间的权衡。在极端情况下，您可以使用压缩表实现完整的二分搜索。 - smci

1

他说CORDIC将适用于周期函数，他还添加了模拟噪声。将函数和噪声分别制表可能会更紧凑。在我们看到数据之前，他需要“show us teh dataz”才能告诉我们;-) - smci

1

我添加了存储表格四分之一的算术运算。 - agf

显示剩余10条评论

2个回答

2

关闭后，我迟迟才发现这个解决方案“什么是最Pythonic的方法来识别列表中连续的重复项？”。

NB：使用像sine这样的周期性函数，您只需存储四分之一（即256个值）或半个表格，然后在查找时对索引进行一些（定点）算术运算即可。正如我所评论的，如果进一步不存储+50的偏移量，则需要少一个位，在查找时间后代价为一个整数加法。因此，可以轻松实现79％的压缩。 RLE将给你更多。即使fn有噪声，您仍然可以通过这种通用方法获得良好的压缩效果。

正如agf指出的那样，您的f(n) = 50 + 36*sin(72*pi*n/1024) = 50 + g(n)。

因此，将g(n) = 36*sin(72*pi*n/1024)的256个值进行制表，仅适用于范围n = 0..255

然后，可以通过以下方式轻松计算f(n):

if 0 <= n < 256, f(n) = 50 + g(n)
if 256 <= n < 512, f(n) = 50 + g(511-n)
if 512 <= n < 768, f(n) = 50 - g(n-512)
if 768 <= n < 1024, f(n) = 50 - g(1023-n)

以下是一个通用的表格压缩器解决方案，它将生成 (istart,iend,value) 三元组。

我想了很久如何使用列表推导和itertools.takewhile() 更加Pythonic地完成这个任务；需要进一步优化。

#import itertools

table_="""
    0       50
    1       50
    ...
    1021    49
    1022    50
    1023    50""".split()

# Convert values to int. Throw away the indices - will recover them with enumerate()
table = [int(x) for x in table_[1::2]]

compressed_table = []
istart = 0
for i,v in enumerate(table):
    if v != table[i-1]:
        iend = i-1
        compressed_table.append((istart,iend,table[i-1]))
        istart = i
    else:
        continue # skip identical values
# Slightly ugly: append the last value, when the iterator was exhausted
compressed_table.append((istart,i,table[i]))

注意：在agf改变他的方法之前，我已经开始使用表格压缩方法了……我试图得到一个itertools或列表推导式的解决方案。

- smci

干得好。你的解决方案在功能上是一样的。我知道利用波形对称性的方法，但表格也可以保存一些不对称的样本，包括模拟噪声。然而，成对偏差不会超过3-4个LSB比特位。否则，如果我只对正弦感兴趣，使用多项式插值和少量查找表也可以起作用。 - PoorLuzer

1

@PoorLuzer，也许可以将高位和低位分别制表。你能否向我们展示一些实际的样本噪声数据？在数据紧凑性和代码之间，你希望达到什么样的折衷？ - smci

1

举例可以让人们想到具体的事情，但是考虑DTMF波形表。不要考虑一个音调是两个正弦波的总和的具体细节，而是以一位数字=1个独特的波形的抽象层面思考。对于噪声，考虑声音“嗨”的wav编码。 - PoorLuzer

1

256-511和768-1023的计算结果偏差为1。 - agf

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- agf · Accepted Answer

如果您不介意由于四舍五入而出现略微不同的值，我可以为您压缩得非常好。

from math import pi, sin
interval=2*pi/1024
sinval=lambda i:int(round(sin(i*interval)*36))+50

这里是实际执行你想要的操作的代码；它可以使用。

vals = sorted((sinval(i), i) for i in range(1024))

作为测试数据。如果第一列包含索引，您需要在此处交换val和index的顺序以进行循环。

ranges, oldval, oldidx = [[0, 0]], 0, 0
for val, index in vals:
    if not (val == oldval and index == oldidx + 1):
        ranges[-1].append(oldidx)
        ranges.append([val, index])
    oldval, oldidx = val, index
ranges[-1].append(oldidx)
ranges.pop(0)
ifs = ('if((index >= {1}) and (index <= {2})) return {0};\n'.format(val, start, end)
            for val, start, end in ranges)
print ''.join(ifs)

编辑：

哎呀，我漏了一行。已经修复。另外，你的倍增器实际上是36而不是35，我可能在脑海中将（14, 86）四舍五入为（15, 85）。

编辑2：为您展示如何仅存储表格的四分之一。

from math import pi, sin

full = 1024
half = 512
quarter = 256
mag = 72
offset = 50

interval = 2 * pi / full

def sinval(i):
    return int(round(sin(i * interval) * (mag // 2))) + offset

vals = [sinval(i) for i in range(quarter)]

def sintable(i):
    if  i >= half + quarter:
        return 2 * offset - vals[full - i - 1]
    elif  i >= half:
        return 2 * offset - vals[i - half]
    elif i >= quarter:
        return vals[half - i - 1]
    else:
        return vals[i]

for i in range(full):
    assert -1 <= sinval(i) - sintable(i) <= 1

如果你从表中减去偏移量，只需将前两个 -vals[...] 替换即可。

另外，底部的比较有些模糊，因为我会因此出现 72 个 off-by-one 错误。这仅仅是因为你的值被舍入为整数；它们都是处于两个值之间的地方，所以精度几乎没有减少。