论文标题
了解和压缩音乐的最大变化模式
Understanding and Compressing Music with Maximal Transformable Patterns
论文作者
论文摘要
我们提出了一种多项式时间算法，该算法在点集中发现了所有最大模式，$ d \ subset \ mathbb {r}^k $，通过用户指定类中的转换（$ f $）在$ \ mathbb {r}^k $上的$ f $中的转换相关。我们还提出了第二种算法，该算法发现了每种最大模式的出现集合，然后使用这些出现集的紧凑编码来计算输入点集的无损压缩编码。该编码采用一组对的形式，$ e = \ left \ lbrace \ left \ langle p_1，t_1 \ right \ rangle，\ left \ left \ langle p_2，t_2 \ ryn \ right \ rangle，\ ldots \ ldots \ ldots \ lew \ weft \ langle p _ { T_{\ell}\right\rangle\right\rbrace$, where each $\langle P_i,T_i\rangle$ consists of a maximal pattern, $P_i\subseteq D$, and a set, $T_i\subset F$, of transformations that map $P_i$ onto other subsets of $D$.每个转换都由真实值的向量编码，该向量将其独特地标识在$ f $之内，并且该向量的长度被用作$ f $的复杂性的度量。我们通过将民间歌曲旋律分为曲调的任务，通过三个转换类别的复杂性转换类别来评估新的压缩算法。测试的类中最复杂的类别包括换位，反转，逆行，增强和减少的音乐转换的所有组合。我们发现，扩大转型类别改善了这项任务的性能。但是，平均而言，它并不能改善压缩因子，这可能是由于数据集（在这种情况下为民间歌曲旋律）太短而简单，无法从较大的转换类别中发现的可能会发现的模式关系数量更大。
We present a polynomial-time algorithm that discovers all maximal patterns in a point set, $D\subset\mathbb{R}^k$, that are related by transformations in a user-specified class, $F$, of bijections over $\mathbb{R}^k$. We also present a second algorithm that discovers the set of occurrences for each of these maximal patterns and then uses compact encodings of these occurrence sets to compute a losslessly compressed encoding of the input point set. This encoding takes the form of a set of pairs, $E=\left\lbrace\left\langle P_1, T_1\right\rangle,\left\langle P_2, T_2\right\rangle,\ldots\left\langle P_{\ell}, T_{\ell}\right\rangle\right\rbrace$, where each $\langle P_i,T_i\rangle$ consists of a maximal pattern, $P_i\subseteq D$, and a set, $T_i\subset F$, of transformations that map $P_i$ onto other subsets of $D$. Each transformation is encoded by a vector of real values that uniquely identifies it within $F$ and the length of this vector is used as a measure of the complexity of $F$. We evaluate the new compression algorithm with three transformation classes of differing complexity, on the task of classifying folk-song melodies into tune families. The most complex of the classes tested includes all combinations of the musical transformations of transposition, inversion, retrograde, augmentation and diminution. We found that broadening the transformation class improved performance on this task. However, it did not, on average, improve compression factor, which may be due to the datasets (in this case, folk-song melodies) being too short and simple to benefit from the potentially greater number of pattern relationships that are discoverable with larger transformation classes.
