Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 背景介绍

由于篇幅太长,这篇文章的讲述了文章的Introduction和Related Work部分。而文章的主体部分在Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 实现与分析 这篇文章里面。


摘要

这篇论文讲的是在高维空间的最近点搜索问题(ANN)的一个实现算法,该算法继承自 乘积量化(Product Quantization) 算法。在该算法中,提出了如下几点:

  • 将原来的乘积量化算法进行分层,使用树形结构减少向量的比较次数
  • 提出了一个重排序算法,该算法有更好的并行度

简介

最近点搜索问题(NN)就是在D维空间中,对于一个向量y,找寻样本集合\mathcal{X}中,最近点的问题,形式化表达——

(1)   \begin{equation*} N(y) =\mathop{\arg\min}_{x \in \mathcal{X}} d(y,x) \end{equation*}

在视觉识别的领域的很多课题中,该问题的维数D变得非常大,引入了一种称之为 “维数灾难” 的现象。形象的解释这个问题,对于一个体积a^128的128维高维立方体,一个体积0.1 \times a^128的立方体,边长也是0.1^{\frac{1}{128}} = 0.982\times a。从这个例子可以看到,由于高维立方体体积增长速度过于迅速,我们基本不可能通过遍历区域的方式进行搜索。例如,在128维空间中,即使我们只要访问10%的体积,这些体积分配到单维度上也超过了98%。

给予上述瓶颈,大多数应用中,我们都是用了临近点搜索的方式(ANN),搜索一个相对较近的邻居。对于该问题,人们已经研究出了很多基于CPU的实现,从KD树(KD-tree),到随机KD森林(Randomized KD forest),和KD-mean Trees。这一系列算法都试图将搜索空间缩减到一个包含询问点的尽量小的邻域。

另一个截然不同的实现方式是局部敏感哈希算法(Local Sensitive Hashing),这个方法将整个数据库的向量的一系列随机投影使用哈希表储存,在询问中,对于和询问向量落在了同一个哈希项中的样本向量进行额外的距离检查。

上述基于CPU的ANN算法在像GPU迁移的时候都会遇到或多或少的问题,而基于GPU的算法则很多都是纯粹暴力算法。而在这篇文章中提出的算法,不仅高效利用了GPU,甚至其CPU版本都和上述算法匹敌。

在效率评估上,由于在实际生产中,存在一个“离线预处理”阶段计算所有询问无关的数据,以及一个“在线计算”阶段,实时处理询问相关的计算。因此,最科学的方式应该是将两个阶段的用时分别测量。

向量量化(Vector Quantization)是一个简单的ANN算法,它将样本集\mathcal{X}中所有的向量进行聚类。对于某个询问向量,距离其最近的聚类中心所对应的样本集子集\mathcal{X}_k \subset \mathcal{X}是最有可能存在最近点的。然而倘若询问点恰好位于两个聚类的边界上,则算法就不那么容易找到最近点了。另一方面,一个聚类簇在V图上的相邻聚类簇的个数随着维数的增加指数级增长。

乘积量化(Product Quantization)算法是当下很多最前沿ANN算法的核心,一般来说,基于PQ的算法都有如下几步

  1. 通过一个高效但是低精度的算法,选出一系列候选点集。
  2. 在重排序过程(re-ranking step)中,使用近似距离将候选点集进一步排序。
  3. 排序后的前面K个候选点重新计算实际距离并取最近者。

在PQ类算法的基础上,我们平行提出了一个称之为Product Quantization Tree的算法(PQT),这个算法的贡献点有

  1. 二级乘积和树形结构,减少计算量
  2. 引入Dijkstra算法的松弛操作
  3. 一个O(P)复杂度的近似排序算法,其中P为询问向量的分段数

背景

向量量化与乘积量化

由于我们的算法是基于PQ算法的,因此下面将介绍PQ算法。

首先,乘积算法(Product Quantization)的鼻祖是向量量化(Vector Quantization)算法。已知最初的样本集合\mathcal{X} = \{x_1,x_2,x_3,\dots,x_n\},以及一个码表(codebook)\mathcal{C} = \{c_1,c_2,\dots,c_k\},我们可以定义映射c(x) = \arg \min _{c \in \mathcal{C}} d(x,c),将每个样本点映射到最近的码字。同时,对于每个码字也控制了一系列样本点,令这些点集为C_kC_k =\ {x \in \mathbb{R}^D | c(x) = c_k\},这个点集也成为簇(cluster)或盒子(bin)。直接使用码字代表样本点,虽然引入了一些距离上的不精确,但是在后续寻找相似向量中很有用。在上述算法中,关键点集合可以通过一个叫Lloyd Iteration的算法得到。

在PQ算法中,高维的向量空间可以等价于若干低维向量空间的乘积,假设D = P \cdot m,那么对于所有的样本向量都可以进行分解,x \in ([x]_1,[x]_2,\dots,[x]_p)^T, [x]_i \in \mathbb{R}^m. 对于x \in \mathbb{R}^D,我们可以将该高维空间中的码表定义为C = C_1 \times C_2 \times \dots \times C_P,这个集合里面实际上包含了k^P个D维码字,但是却只需要k \cdot P个m维码字。由于码字变得非常非常多,我们可以对于高维向量进行更加精细的匹配。最终,一个向量的编码(Canonical Projection)定义为其P个独立组成部分的码字组合而成——

    \[c_p : \mathcal{X} \rightarrow \mathcal{C}_p, x\mapsto c_p(x) := \mathop{\arg \min}_{c \in C_p}  d([x]_p,c)\]

    \[c(x) = (c_1(x),c_2(x), c_3(x), \dots, c_p(x))^T\]

从上式可以发现,对于P个部分的量化操作使用了不同的码书,这些码书和VQ一样,都可以使用Lloyd Iteration生成。

诚然,查询任意一个向量处于哪一个簇是非常简单的。但是任意向量所归属的簇在大部分情况下都是空的,这是因为数据分布的稀疏性。不过,在实际使用中,查询向量通常和样本有相同分布,在这个条件下,我们确实可以成功的依照簇找到最近的向量。即使如此,我们还是需要考虑最坏的情况。

一些研究者为了实现更加精确的乘积量化方式,找到了一些解决方式,比如对于所有询问x,统一使用一个线性变换R修饰。及每次查询Rx。不过这个方法在GPU上并不怎么方便。

右图的四部分就分别介绍了“向量量化(Vector Quantization)”和“乘积量化(Product Quantization)”对应的中心点分布图。下层的两幅图则尝试按照不同的“粒度”实现树状查询,在之后会详细讨论。

 

倒排文件系统

对于一个询问y \in \mathbb{R}^D,有的文章使用了含“非对称距离计算”的倒排系统实现。在这个实现中,首先一次VQ,在规模k的码书中提取一系列候选码字(原文中是在8192个向量中,提取0.05%,即64个候选)。不过,即使是64个候选码字也廊括了524288个样本向量。

在这个实现中,选择一组合理的码字消耗了k个D维向量距离运算,在计算了k次距离之后,其中最近的w个码字对应的样本集合的并集\mathcal{L}_c \in \mathcal{X}就是“极有可能包含答案的向量集合”。这一系列向量进一步在基于PQ算法的重排序(re-ranking)。按照中心向量c_wy的距离r_w = y-c_w,从小到大排序,在之前文章中,由于询问向量y事先知道,所以这个距离被放在了查找表(lookup-table)中。

询问向量y和其最近的候选向量可以在集合\mathcal{L}_c中使用相似的方式查找到。只不过这一次,候选集合\mathcal{L}_c小了很多,而码书包含了更多(k_2个词).通过新的码书对应的距离函数,重排序得到更加靠谱的候选集合\mathcal{L}_s,最终,在\mathcal{L}_s中,选择前几个进行最精确的距离计算。

上述步骤意味着共有k_1 + w \cdot k_2次距离计算,在论文默认的规模中,意味着24576次高维向量距离计算每询问。

一个层次化的实现会将总共的距离计算次数将至200,不过,在NVIDIA Titan X架构下,16k的向量距离计算比256次计算慢62倍,因此,在这个问题上,就近多少次距离计算是运行效率的瓶颈。

多索引倒排

相比于之前,在整个数据及上使用VQ,多层次倒排索算法使用了PQ算法,减少了询问向量与中心向量的距离计算次数,而增加了Cluster的总数。

对于y的每一部分,都给定了其到k个中心向量的距离。这些距离经过排序生成如下表格——

(2)   \begin{align*} [y]_1 \rightarrow \{i_{10}, i_{11}, i_{12}, \dots, i_{1k-1}\} \\ [y]_2 \rightarrow \{i_{20}, i_{21}, i_{22}, \dots, i_{2k-1}\} \\ \vdots \\ [y]_P \rightarrow \{i_{P0}, i_{P1}, i_{P}, \dots, i_{Pk-1}\} \\ \end{align*}

上面式子中i_{23}指的是询问向量第二部分的第三近的向量。在此基础上的NN搜索,使用启发式算法,从i=(i_{10},i_{20},\dots,i_{P0})开始。可以使用优先队列,一次访问最近的一个簇中的向量,直到足够多的向量被访问。

讨论

上述的基于VQ和基于PQ的查询算法都能达到很好的精准度。基于VQ的算法需要很大的内含D维向量的码书,即使基于PQ算法的码书会小一些,但是从总量上也非常大。另一方面,两个算法都需要与询问相关的离线初始化操作。这在实时的查询中是不可行的。

对于之前提到的诸多问题,在接下来一章中,我们将使用乘积量化树(Product Quantization Tree)来解决上述的问题,并提出不同的Cluster选择算法,和基于投影的重排序算法。最后,我们将讨论该算法如何在GPU上面运算。

参考文章

理解 product quantization 算法

K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比

Separating Style and Content for Generalized Style Transfer 阅读笔记

【由于笔者在尝试优化这个模型,因此在一些步骤中会加入自己的一些点评,以方括号指示,读者尽可无视他们。同时,如果你想要了解本文模型的复现结果,以及汉字风格迁移的其他模型,不妨看看这篇文章SelectorGAN


在汉字风格迁移领域,有很多不同的尝试,学者在网络结构,损失计算等模块,都有不同的尝试。在之前的实现中,汉字的风格通常在训练过程中被记忆在了网络结构中,当需要生成一个新风格的字体时,网络需要在新的数据集下重新训练。而在本文中,汉字风格由给定的少数输入样本给定,由模型实时提取并输出。

文中的模型称之为EMD,在结构上包含风格编码器、内容编码器、混合器和解码器。训练数据集的每一项都是由R_S_i,R_C_j,I_{ij}组成,其中R_S_iR_C_j分别是风格(Style)和内容(Content)的指示集合,而I_{ij}是目标图像。换句话来说,模型通过同一汉字不同风格的一组图像刻画了内容,又用同一风格不同汉字的一组图像刻画了风格,再将两个模块的特征向量组合,形成字体和内容的融合。

模型的详细结构如下图——

实际上,这张图片已经描述了几乎所有的细节。图中提及了down-sampling 和 up-sampling,这两个过程实际上就是图像的“压缩”和“放大”,在文中使用了经典的卷积层和反卷积层

【反卷积层或许可以搞一些花样提高模型效果】

在Encoder模块,两个集合的所有输入数据,拼接在一起,每张图片作为一个Channel,传入后续的卷积层中。

【这里有一些小问题,不知道实现的时候有没有解决,由于输入的图片集合是无序的,而Channel本身是有序的,若将每一个图片都视为一个独特的Channel,则每一个不同位置的图片都会有不同的卷积层提取特征,这个情况本身就是不靠谱的。】

在Mixer模块,使用了BiLinear层。用数学语言来描述,设两个特征器提取出的向量分别是S_iC_j,那么Mixer层的输出应该是S_i W C_j^T,其中W是一个形状(dim(S_i),dim(C_j))的向量。

Decoder模块使用了若干反卷积层。具体细节图片已经说得很明白了。上述的多层卷积和反卷积层中间都间隔了BatchNorm和LeakyReLU。

还有一些实现上的细节,诸如从Content Encoder的第一层连了一条通路到Decoder的最后一层。及Content Encoder进过粗特征可直接被答案的生成所运用。

【这一步骤会让人比较怀疑这条通路中间的东西是不是真的学到了东西,模型本身很容易直接学到“和输入一模一样”的输出(因为这样的输出只经过两层),而不容易学到风格信息(风格信息的传输至少会经过十多层)。】

评价:结构简单,有极强的可优化性,经试验,可以很容易做到比论文公开代码更好的效果。但是论文中的图片有严重浮夸,实际模型输出完全无法达到论文中的效果。

Codewars C++练习:Insane Coloured Triangles

题目

题目链接:

This Kata is an insane step-up from Avanta’s Kata, so I recommend to solve it first before trying this one.

A coloured triangle is created from a row of colours, each of which is red, green or blue. Successive rows, each containing one fewer colour than the last, are generated by considering the two touching colours in the previous row. If these colours are identical, the same colour is used in the new row. If they are different, the missing colour is used in the new row. This is continued until the final row, with only a single colour, is generated.

For example, different possibilities are:

With a bigger example:

You will be given the first row of the triangle as a string and its your job to return the final colour which would appear in the bottom row as a string. In the case of the example above, you would be given ‘RRGBRGBB’, and you should return ‘G’.

1 <= length(row) <= 10 ** 5

题解

核心规律

找到所有递推方程的共性:“所有递推小三角形,都满足RGB的个数在模3意义下相同”。

单独考虑任意一个大三角形的第一行和第二行,倘若我们知道了第一行RGB分别有多少个,我们也可以通过“RGB的个数在模3意义下相同”这个性质,计算出第二行分别有多少个RGB。这个是一个很有启发作用的思路,虽然这个思路无法解决更多的行,但是从该思路出发,我们可以得到如下的算法——

用三元组S_{x,y}=(r,g,b)表示一个位置的颜色。一方面,我们定义映射f来求任意三元组对应的颜色.

f = \{(r,g,b) r,g,b \in \mathbb{Z}\} \rightarrow \{\boldsymbol{R},\boldsymbol{G},\boldsymbol{B}\}

另一方面,不同的三元组有很多,但是颜色的种类总共就3种,所以我们需要对于该三元组建立若干“等价类”,规则如下:

  1. (1,0,0)\rightarrow \boldsymbol{R}(0,1,0) \rightarrow  \boldsymbol{G}(0,0,1)\rightarrow \boldsymbol{B}
  2. f((r,g,b)) = f((r \bmod 3, g \bmod 3, b \bmod 3))
  3. f((r,g,b)) = f((r-v,g-v,b-v))

规则1定义了三元组到颜色的映射,而规则2和规则3将所有三元组分为了3类。

仔细理解一下这三条规则,我们很容易求出一个三元组对应的颜色,例如f((123,123,400)) = f((0,0,277))=f((0,0,1)) \rightarrow \boldsymbol{B}。当然,并不是所有三元组都可以通过这种方法计算出值,倘若一个三元组无法求出值,如(0,0,0),那么在本题中,它就是不合法的。

但看三元组的定义或许会莫名其妙,但是我们可以将本题的规则引入,得到一个暴力的迭代方式——

对于整个三角形的第一行,可以直接按照定义式生成:

S_{0,y} = ([row[0]==\boldsymbol{R}],[row[0]==\boldsymbol{G}],[row[0]==\boldsymbol{B}])

例如,一个\boldsymbol{G}颜色可以用三元组(0,1,0)表示。

对于后续的行,我们可以按照递推式生成——

S_{x,y} = -S_{x-1,y} - S_{x-1,y+1}

例如,倘若S_{x-1,y} = (1,0,0) \rightarrow \boldsymbol{R}S_{x-1,y+1} = (0,1,0) \rightarrow \boldsymbol{G},那么S_{x,y} = (-1,-1,0) \equiv (0,0,1) \rightarrow \boldsymbol{B}

读者到这里应该就可以发现,实际上我们的三元组完全是为了反映递推方程中的等价信息而设计的。这里,我们已经可以设计出时间复杂度O(N^2)的算法了。

既然我们已经借助三元组的加减运算,定义出了一个新的数域来解决这个问题,并且该数域很容易证明满足封闭性。反映到代码上,就是我们成功定义出了一个支持加操作和相反数操作的“数”status,那么我们完全可以不再考虑status类的实现细节。

所有细节略去之后,我们的代码实际上就是上面的65-69这5行。有一些编程基础的读者已经发现这里非常像一个组合数的递推方程(或者说是杨辉三角形的生成代码)。

对于一个稍微简单一些的例子,我们对于第一行的所有值赋予一个标号,看看最终结果长什么样的:

上表中,a,b,c,d,e分别是我们读入的第一行的三元组表示,而最后一行就是答案!因此,假设读入三元组列表为s_i那么答案就是

ans =(-1)^{n-1}\sum_{i=0}^{n-1} C(n-1,i) \cdot S_i

最后一步比较tricky,需要一些较深的数论知识,最后一步我们需要求出C(n-1,i)在模3意义下的值。这一步有两个做法——

  • 有现成的Lucas定理专门用来计算这个问题。
  • 可以手工迭代求出C(n-1,0),\dots,C(n-1,n-1)的值,可以用递推式C(n-1,i+1) = C(n-1,i) \cdot (i+1) / (n-1-i)求,这其中又有两个要点
    • 在迭代的乘法需要将所有的因子3提出来
    • 在迭代的除法中需要计算除数在模3同余系下的逆元

在标程中使用了第二种做法。

 

汇编解析C语言函数结构体struct参数的方式

本文介绍在x86汇编中没有加优化选项时的函数体struct传参和返回的方法。

结构体返回值

测试代码

我们先讲讲较为简单的函数返回结构体的方法——

上面的代码实现了一个非常简单的返回结构体的例子,对应的汇编代码如下——

分析

在上面的程序中,内层  return_struct 函数在被调用时,有两个有意义的寄存器,分别是 %rdi 记录了在function1中定义的那个结构体的位置, %rsi 记录传入的n。

在函数进入时,两个寄存器都被保存到了内存里面,接下来按部就班实现C++中的逻辑。重点部分在第30-35行,使用了三个位移操作赋值了五个值。最初理解代码,尝试寻找拷贝内存的语句时,将这三句话直接排除在外,实际上,由于结构体里面是5个整形,而使用64位寄存器,一次可以拷贝两个整数,因此三次拷贝恰好可以用最快的时间完成拷贝。

结论

因此,结构体返回的方式是将返回的结构体的起始位置指针放入 %rdi 寄存器,并在子程序中通过该寄存器定位修改结构体的内容。

结构体传参

测试代码

首先设计样例代码如下——

反汇编出的信息如下——

分析

有了上面的铺垫,我们可以迅速找到在30-35行有一段结构体的拷贝——将位于局部变量中的结构体拷贝到了在28行分配的一段连续空间中,而拷贝操作都是由 %rax 定位的。有意思的是,当我们认为 %rax 正是一个向子程序定位结构体的指针是,发现在子程序中 %rax 的寄存器中的值并没有被使用,反而是使用了 %rsp 进行定位。从另一个方面思考其实也并不奇怪,结构体参数本身是不能通过寄存器传参的,实际上,传参使用了最简单的方式——“通过压栈方式传参”,参数按照“从右到左”的顺序压栈,倘若遇到结构体,则压栈的内容变得多一些而已。

结论

结构体作为参数传入使用压栈方式传参,参数按照“从右到左”的顺序压栈,特别的,当参数为结构体,将结构体整体压栈。

Recurrent Attention Network on Memory for Aspect Sentiment Analysis 阅读笔记

原文链接:Recurrent Attention Network on Memory for Aspect Sentiment Analysis

Abstract

文章提出了一个基于神经网络的,提取“关键词的情感倾向”的模型,拥有如下特点:

  • 创造了一种称之为“加权记忆(weighted-memory)”的机制
  • 使用GRU实现注意力(attention)

Introduction

提出问题

“I bought a mobile phone, its camera is wonderful but the battery life is short”

这一部分,以一个句子的情感分析为例进行分析。在分析中,我们需要对于每一个关键词(target),分析其情感语义,比如camera对应wonderful。选取最近情感词是通常手段,但是显然这种手段会在某些精心构造的句子中失效,比如下面这句话蕴含了中性情感而非消极情感。

“Its camera is not wonderful enough.”

针对上述问题,TD-LSTM是一个解决方案,这种解决方案也有一个缺点,就是特征的传递是逐词的,这在长句子中,当目标(target)与特征词(feature word)相距很远时,又会出现问题。进一步,注意力机制被引入,已表征特征重要性。然而,当实际的注意力点较多时,这种机制的表现也不太好。

“Except Patrick, all other actors don’t play well”

上述的问题便是这片文章准备解决的东西。

引入模型

模型层次结构依次为——

  • 一个双向LSTM生成一系列“记忆片(memory slice)”
  • 所有的内存片按照距离目标词(target)的相对距离加权,使得句子里不同的目标词拥有不同的特征向量
  • 在生成的加权记忆片中,使用注意力机制合并,这里使用的是循环层GRU

在本文中,就如何组合不同的注意力这个问题,提出了新的解决方案。从某一个方面来看,比较像一个普通人的认知——最初看到句子的最开头,然后在继续阅读的过程中不停“注意到”知识,并在最后将注意力集中的几个语言拼接。

对于Introduction中的最后一句话,我们通常会先看到“Except”,接着被“don’t play well”吸引,最终对于“Patrick”生成一种积极的情感。在本文之前,多数文章提出的结构都无法解决多注意力的问题。而我们提出结构中的GRU曾可以很好的解决。

Related Work

对于特定实体的感情分类问题,有很多传统做法基于规则、统计概率,这些做法不是有繁琐的模型构造,就是需要依赖很多额外的语法信息。

这时神经网络就可以发挥作用了~神经网络本身曾被用在语法分析,句子整体情感分析,诸如有名的递归神经网络(Recursive NN)。然而,递归神经网络在语法分析低效的非标准文本(比如推特评论等短文本)中效果不好。

对于指定目标的情感分析,曾经有人提到过TD_LSTM算法,这个算法将需要的目标词放在中间,从两边分别使用LSTM传递信息。这种做法在长句子中效果会大幅减弱,因为很远的情感词必须经过非常多层才能到达终点。

最后,神经图灵机在2014年被提出,其中定义的注意力机制被证明在很多地方适用。其创新之处是引入了外部储存,大大提高了神经网络的能力!从某种方面来说,本文就是在这个模型基础上修改而成的。

Our Model

右图是文章提出模型的结构。

在输入层,所有输入的文本都通过经典的wordtovec算法,将每个词压缩为一个d维向量。

接下来,使用了双向LSTM神经网络(BLSTM)提取每一个词的“记忆信息” u_t,实际上,这种实现方式就是普通的bi-directional-lstm。

接下来,对于不同的位置,有一个二次加权,成为“加权记忆”(weighted memory),加权的意义不太清楚,可能使得较远的信息更容易传播吧。具体来说,文中的加权含义将以中心词的两端t_{max}距离的词,按照距离中心的距离线性加权拼接在一起。

最后,文章使用GRU层将加权记忆再“捣鼓”一番,这里的“捣鼓”是指循环N词,每次通过上一次“捣鼓”的记忆e_{t-1},以及整个“加权记忆”得到第t个“注意力”的加权矩阵,进而通过GRU的形式更新e_t,关于选择GRU模型的原因,文章解释说因为GRU的参数较少。

Experiments

表现优于传统模型

Conclusions and Future Work

在这一部分,作者谈到了选择固定个注意力(Attention)显得有些冗余,在未来的工作中会考虑自适应注意力个数能够得到更好的结果。

点评

在Introduction模块,文章点出了在NLP领域,各种算法面临的共同问题,这种归纳确实很有意思。关于这类模型共同的要点罗列如下——

  • 如何将单词编码,至少本文还是用的经典算法
  • 如何解决远距离传输问题,本文使用weighted-memory机制
  • 如何在不增加太多参数的条件下,增加模型的“深度”,对应了本文中多注意力机制
  • 如何尽量在模型的选择上减少训练参数,对应本文的GRU选取

这篇文章中Related Work里面提到的神经图灵机感觉会很有意思,之后可以找一找相关的论文阅读一下,虽然在NLP方面感觉有些束手束脚,但是在其他领域可能会有很大的作为。

对于本文提到的模型,却是可以看出是仿照人类对于句子阅读的认知,每一个步骤都可以通过人类阅读的认知来解释,不过这种仿照是否能够带来很好的效果就不太好说了。至少文章写的是效果很好,那就姑且相信吧。

由于读的比较粗,关于每一层输出的具体维数还是有点晕,可能也有作者没有表述清楚的锅。

rcaudio:实时录音的音频特征处理库

简介

rcaudio是一个实时的录音,并处理录制的音频的库,使用rcaudio,你可以不用自己编写任何代码,而实现——

  • 获取原始的音频数据
  • 实时监测音量
  • 实时分析录音(歌曲)的节拍,并加以预测

安装

rcaudio是我的第一个放在了pypi.org的工程,因此可以使用pip安装 pip install rcaudio .其中该工程依赖 pyaudio ,倘若出现了无法找到头文件的错误,可直接重装覆盖系统默认的

rcaudio的源码地址为:https://github.com/mhy12345/rcaudio,欢迎push&issue

使用

CoreRecorder

CoreRecorder  是提取原始音频信息的类. 其本身会额外开一个进程,当成员函数 start() 被调用后,录音开始,音频数据会出存在一个队列 CoreRecorder.buffer 中。

如下是一个以字符形式输出录音的波形图的小程序

SimpleRecorder

在多数较为复杂的情况中,我们可以使用 SimpleRecorder ,从效率角度出发,推荐只实例化一次 SimpleRecorder因为绑定了录音部分,所以他会占用掉相当一部分的运行资源。

通过调用 SimpleRecorder 的成员函数 register() ,我们可以将多个 Analyzer 类绑定。

当成员函数 start() 被调用后,录音自动开始,同时起绑定的所有 Analyzer 实例也同时开始运行。

Analyzer

所有继承于 BaseAnalyzer 的类都是一个 Analyzer ,其功能是从原始的音频数据中提取出用户希望的信息。如下例子中,一个 VolumeAnalyzer 用于实时询问音量。

下面例子中,一个 BeatAnalyzer 用于分析节拍并进行预测。(这里的预测会有1~2s的延迟)。 BeatAnalyzer 本质上是通过在当前最后可用的若干 rec_time 时间的数据,提取起节拍信息,进而校准当前的节拍器。校准的具体算法可以参考我的另一篇文章python实现音频节拍的实时识别

多个Analyzer同样可行,比如如下程序在分析节拍的同时,通过音量判断乐曲是否结束。

如果你需要自定义音频特征的提取函数,不妨试试重写 FeatureAnalyzer 的 data_process 成员函数(其传入一个一维数组表示特定时间段的音频原始数据,返回这段时见的特征)。 默认的 data_process 函数计算了过零率。

注意事项

大部分的函数都存在1-2s的延时,个人认为如果不是把所有细节都在实时环境中重写一遍,是很难避免的。在 BeatAnalyzer 中,我使用了很多技巧来让用户看起来好像是事实的,而在 FeatureAnalyzer 如果特征的处理速度太慢,可能这个延时会被无限放大。如果这种情况真的发生,你可以考虑减少采样率sr,或者自己重写一个Analyzer来取舍一些不太重要的步骤。

最后

如果这个工程真的帮助你了的话,不妨给我一个Star哦,你的支持是我的动力!要是有pull request那我就幸福死了ovo

Codewars Python练习:Secret knock

题目

Perform the secret knock() to enter…

链接

https://www.codewars.com/kata/secret-knock/train/python

题解

近期做过的一道非常好玩的题目!实际上这道题实在一年前就看过,但是当时CodeWars没有Test Driven Development (TDD) 这个模块,因此被挡在了反汇编那一步。

首先,在solution栏目写一个knock()函数调用,运行结果如下——

那么,这道题要我们做的,就应该是用某种特殊的技巧调用knock()函数,使得Sorry, that’s not the secret knock. 输出不被触发。

在解题界面中的Test Driven Development (TDD) 有如下代码(由于习惯问题,我对于这些代码做了少量修改,使得其能运行在Python3.4.3环境下)——

这一段代码实际上是解题方法的提示(想到一年前我没有这句话能想到尝试反汇编也已经不错了),这段代码使用 RUN SAMPLE TEST 按钮运行后,得到如下输出——

代码中运用到了Python中的反汇编库dis,而使用dis作用到函数的代码储存模块 knock.__code__ , 可以输出人类可读的反汇编代码。

为了更加清楚地了解knock.__code__的构造,我们可以使用Python的dir函数查看其具体的成员变量

而我们可以在Python的安装目录(本机/anaconda3/envs/default/include/python3.6m)的code.h文件中,可以看到这些量的具体定义——

其中,co_const表示了函数中定义的常量,而co_code表示函数的代码。这时,我们就能明白 Test Driven Development (TDD) 中的代码究竟在干什么了——

  • 输出了knock函数的反汇编码
  • 输出了knock函数的常量定义
  • 发现第一个常量是一个子函数OpenDoor,进而输出其反汇编代码

Test Driven Development (TDD)  中输出的代码是如下knock()函数的反汇编代码(实际上真实的knock()函数肯定会更加复杂)。

对照反汇编理解Python机器代码的规则——

基本上就很容易理解了,唯一可能有点晕的是POP_TOP指令,出现在所有函数调用之后,个人猜测适用于处理函数返回值,只是本题中所有返回值POP出来都没有使用而已。

了解了Python机器代码的规则,我们就可以看真正的knock函数怎么写的了:一下输出源代码程序都是基于如下程序改动的,之后就不会再放了

整体输出由于太长,放在了文章末尾。不过注意的是,这一次,不只有Opendoor是子函数,还有一个LineCount()和deliverLine()子函数。

knock函数反汇编的结果中,首先注意到有如下几行

其中,将arg和全局变量knock进行了比较,WTF,全局变量knock不是函数自身吗?那是不是我们应该调用knock(knock)?

程序的输出确实变了!但是我们没有利用到其他任何的子程序啊!仔细重读Knock()函数,两次CALL_FUNCTION操作都制定了调用系统print函数,因此除非修改print函数,否则玩不出什么奇怪的花样。那么另外两个函数是怎么被调用的呢?

我尝试去搞懂Knock函数里面唯一一个自己无法理解的指令STORE_DEREF,在StackOverFlow相关问题的引导下,豁然开朗!看下面的程序

其反汇编代码如下,恰好用到了STORE_DEREF,而上面这个程序的结构,恰好就和knock函数相似,其返回值是一个可调用的程序!

knock(knock)返回了一个deliverLine函数闭包,而deliverLine函数定义如下

这个函数最后返回了自身的一个闭包,也就是说返回值又是可调用的。

每一次调用,函数调用都会增加一个变量varLineCount的值,当变量的值分别为1和2时,输出不同的内容,当变量的值为2时,门被打开了。

最终答案应该是

顺便说一句,Python版本现在有一些问题,提交了会显示错误,将该答案输出到JavaScript版本的题目中即可。

完整反汇编代码