Making plain binaryfiles using a C compiler(i386+)Cornelis FrankApril10,2000I wrote this article because there isn’t much information on the Internet concerning this topic and I needed this for the EduOS project.No liability is assumed for incidental or consequential damages in connection with or arising out of use of the information or programs contained herein.So if you blow up your computer because of my bad“English”that’s your problem not mine. 1Which tools do you need?An i386PC or higher.A Linux distribution like Red Hat or Slackware.GNU GCC compiler.This C compiler usually comes with Linux.To check if you’re having GCC type the following at the prompt:gcc--versionThis should give an output like:2.7.2.3The number probably will not match the above one,but that doesn’t really matter.The binutils for Linux.NASM Version0.97or higher.The Netwide Assembler,NASM,is an80x86assembler designed for portability and modularity.It supports a range of objectfile formats,including Linux‘a.out’and ELF,NetBSD/FreeBSD,COFF,Microsoft16-bit OBJ and Win32.It will also output plain binaryfiles.Its syntax is designed to be simple and easy to understand, similar to Intel’s but less complex.It supports Pentium,P6and MMX opcodes,and has macro capability.Normally you don’t have NASM on your system.Download it from:/pub/Linux/devel/lang/assemblers/A text editor like pico or emacs.1See also:Intel Architecture Software Developer’s Manual,V olume1:Basic Architecture,1.4.1.Bit and Byte Order2See also:Intel Architecture Software Developer’s Manual,V olume1:Basic Architecture,4.2.2.Stack Alignment00000000211111111121000000002010Wherein x stands for a number represented in base x.Notice also that negative numbers are characterized by having the high bit on.Of course you don’t have to do the conversion to a negative version of a certain number yourself.The IA-32architecture has a specific instruction for this,called NEG.Table1shows us the two’s complement representation of a char.The advantageRangeunsigned128255011273See also:Intel Architecture Software Developer’s Manual,V olume1:Basic Architecture,6.3.2.1.Type Conver-sion Instructions4See also:Intel Architecture Software Developer’s Manual,V olume1:Basic Architecture,3.3.Memory Organi-zation5See also:Intel Architecture Software Developer’s Manual,V olume3:System Programming Guide,Chapter3: Protected-mode memory management6Source:A Book on C,fourth edition,A.10.Variable Argumentsstart ,the variable v is the last argument that is declared in the header to yourvariable argument function definition.This variable cannot be of storage class register ,and it cannot be an array type or a type such as char that is widened by automatic conversions.The macro va arg accesses the next argument in the list.The macro varoundedstart will let theargumentebp ebp + 0x4ebp + 0x8Figure 2:The arguments on the IA-32stackpointer ap point to the variable after the given (first)variable v .This macro doesn’t return anything (indicated by the leading (void)).The macro vaend will reset the argument pointer ap without returning anything.23。
( American Standard Code for Information Interchange, ASCII )在计算机中，所有的数据在存储和运算时都要使用二进制数表示（因为计算机用高电平和低电平分别表示1和0），例如，象a、b、c、d这样的52个字母（包括大写）、以及0、1等数字还有一些常用的符号（例如*、#、@等）在计算机中存储时也要使用二进制数来表示，而具体用哪些二进制数字表示哪个符号，当然每个人都可以约定自己的一套（这就叫编码），而大家如果要想互相通信而不造成混乱，那么大家就必须使用相同的编码规则，于是美国有关的标准化组织就出台了所谓的ASCI I编码，统一规定了上述常用符号用哪些二进制数来表示。
美国标准信息交换代码是由美国国家标准学会(American National Standard Institute , ANSI )制定的，标准的单字节字符编码方案，用于基于文本的数据。
起始于50年代后期，在1967年定案。
它最初是美国国家标准，供不同计算机在相互通信时用作共同遵守的西文字符编码标准，它已被国际标准化组织（International Organization for Standardization, ISO）定为国际标准，称为ISO 646标准。
适用于所有拉丁文字字母。
ASCII 码使用指定的7 位或8 位二进制数组合来表示128 或256 种可能的字符。
标准ASCII 码也叫基础ASCII码，使用7 位二进制数来表示所有的大写和小写字母，数字0 到9、标点符号，以及在美式英语中使用的特殊控制字符。
其中：0～31及127(共33个)是控制字符或通信专用字符（其余为可显示字符），如控制符：LF（换行）、CR（回车）、FF（换页）、DEL（删除）、BS（退格)、BEL （振铃）等；通信专用字符：SOH（文头）、EOT（文尾）、ACK（确认）等；AS CII值为8、9、10 和13 分别转换为退格、制表、换行和回车字符。
第42卷 第4期 JOURNAL OF XIDIAN UNIVERSITY V ol.42 No.4 ______________________________收稿日期： 网络出版时间： 基金项目：国家自然科学基金资助项目(61170161，61303171，61271406)作者简介：马艳萍(1975-), 女, 博士研究生, E-mail ：myp74920@网络出版地址： doi ：10.3969/j.issn.1001-2400.2015.04.026数据依赖的多索引哈希算法马艳萍2,1，姬光荣1，邹海林2，谢洪涛3(1. 中国海洋大学信息科学与工程学院，山东 青岛 266100；2．鲁东大学信息与电气工程学院，山东 烟台 2640253．中国科学院信息工程研究所 信息内容安全技术国家工程实验室，北京，100093)摘要：多索引哈希是目前使用最广泛的针对二进制码的索引算法. 由于多索引哈希基于数据集中的二进制码呈均匀分布这一假设，不能有效处理非均匀分布的数据集. 针对这一问题，提出数据依赖的多索引哈希算法. 首先把二进制码划分为多个连续不重合的子串，并通过计算二进制码每位之间的相关性为每一个子串学习得到自适应投影向量. 在为每个子串建立哈希表时，使用投影向量对子串进行投影从而得到哈希表中的下标. 采用自适应投影的方法可以使得哈希表中的元素接近于均匀分布，进而提升查询速度. 此外，提出一个基于熵的分布度量方法，以评价哈希表中数据元素的分布情况. 在大规模数据集上的实验表明，与多索引哈希算法相比数据依赖的多索引哈希算法可以使查询速度提升36.9%–87.4%.关键词：最近邻查询；二进制码；索引；多索引哈希中图分类号：TP183 文献标识码：A 文章编号：1001-2400(2015)04-0177-07Data-oriented multi-index HashingMA Y anping 1,2, JI Guangrong 1, ZOU Hailin 2, XIE Hongtao 3(1School of Information Science and Engineering, Ocean University of China, Qingdao, 2661002Scholol of Information and Electrical Engineering, Ludong University, Y antai, 2640253Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093)Abstract: Multi-index hashing (MIH) is the state-of-the-art method for indexing binary codes. However, MIH isbased on the dataset codes uniform distribution assumption, and will lose efficiency in dealing with non-uniformlydistributed codes. In this paper, we propose a data-oriented multi-index hashing method. W e first compute thecorrelations between bits and learn adaptive projection vector for each binary substring. Then, instead of usingsubstrings as direct indices into hash tables, we project them with corresponding projection vectors to generate newindices. With adaptive projection, the indices in each hash table are near uniformly distributed. Besides, we putforward an entropy based measurement to evaluate the distribution of data items in each hash table. Experimentsbe improved by 36.9%–87.4%.Key Words: nearest neighbor search; binary codes; indexing; multi-index Hashing在大规模的数据集中进行最近邻查询是图像检索[1][14]、计算机视觉[2][15]、目标检测[3]等领域的一个基础工作. 由于二进制码特征计算快速、节省存储空间、特征之间的匹配操作仅需要几个机器指令就能完成，目前越来越多的研究采用二进制码特征来描述视觉内容[4][5][6]. 在一个具有百万规模的二进制码数据集中查找一个查询的最近邻可以在不到一秒的时间内完成[7].虽然二进制码之间的海明距离可以快速计算，但是线性查询只能处理小规模的数据集. 因为计算机处2014-11-05 16:16/kcms/doi/10.3969/j.issn.1001-2400.2015.04.026.html理器的计算能力有限而数据集的规模是无限的，随着数据集的增长（数以百亿）线性查询将变得很慢. 为了提高大规模数据环境下二进制码的最近邻查询性能，Salakhutdinov等人提出了二进制哈希方法[4][8]. 该方法在建索引时，直接使用二进制码作为哈希表的下标（存储地址）. 在查询时，通过不断增加查询半径即可返回与查询相似的最近邻. 但是随着查询半径的增加，该方法需要比对的待检测数据呈指数级的增长. 当二进制码的位数大于32维时，即使采用一个很小的查询半径二进制哈希在理论上需要比对的数据规模可能比整个数据集的容量还要大[7]. 在这种情况下，二进制哈希比线性查询的速度还要慢. 针对这一问题，W eiss 等人提出了多索引哈希算法[8]. 多索引哈希算法在建立索引时将二进制码划分为多个连续不重合的子串，并为每个子串建立一个哈希表. 在查询时，按照同样的方式把待查询二进制码划分为多个子串，然后在相应的哈希表中进行查找以返回候选结果. 最后，根据候选结果和查询之间的海明距离对候选结果排序从而得到最近邻. 对每一个子串，其所需的查询半径与整个二进制码相比大大减小. 因此，多索引哈希算法极大地降低了需要比对的待检测数据量，从而提高查找最近邻的速度. 由于多索引哈希算法基于数据集中的二进制码呈均匀分布这一假设[7]，不能有效处理非均匀分布的数据集. 在多媒体检索中，数据集的分布往往都是非均匀的[1], 因此多索引哈希算法在处理这些数据集时，查询速度受到一定的影响和限制[7][11].针对多索引哈希算法不能有效应对非均匀分布的数据集这一问题，作者提出数据依赖的多索引哈希算法，算法框架图如图1所示. 首先把二进制码划分为多个连续不重合的子串. 然后构建一个训练数据集并计算二进制码每位之间的相关性，为每一个子串学习得到自适应投影向量. 在为每个子串建立哈希表时，使用投影向量对子串进行投影从而得到哈希表中的下标. 采用自适应投影的方法可以使得哈希表中的元素接近于均匀分布，进而提升查询速度. 此外，作者还提出一个基于熵的分布度量方法，以评价哈希表中数据元素的分布情况. 在大规模数据集上的实验表明，与多索引哈希算法相比数据依赖的多索引哈希算法可以使查询速度提升36.9%–87.4%.图1 数据依赖的多索引哈希算法示意图.1算法描述本节首先简要介绍多索引哈希算法[7]，然后详细描述数据依赖的多索引哈希算法. 除此以外，作者还提出了一个基于熵[1]的数据分布度量方法.1.1多索引哈希算法虽然计算二进制码之间的海明距离只需要几个异或操作，但是线性查找不能有效地应对大规模的数据集. 因此，Norouzi结合二进制码和哈希表提出了二进制哈希方法[4][7][8]. 二进制哈希把海明空间下的最近邻查询问题转化为R近邻问题：第4期 马艳萍等：数据依赖的多索引哈希算法 179 , 1,2,...,,i i H q p r i N p D −≤=∈ , (1)其中q 是查询向量，D 是数据集，N 是数据集中元素的个数，H •代表海明距离. 通过不断增加查询半径r ，二进制哈希算法可以返回查询向量q 的R 近邻. 为了提高查询速度，二进制哈希算法建立一个哈希表，并直接使用二进制码作为数据元素在哈希表中的下标. 这样，R 近邻问题就可以通过不断增加查询半径r 得到解决. 此时，需要比对的待检测数据量为：0ri l i num C ==∑, (2)其中l 是二进制码的维度. 当二进制码的维数很长时，即使采用一个很小的查询半径r ，二进制哈希在理论上需要比对的数据规模可能比整个数据集的容量还要大[7]. 比如当l=256, r =5，1010num ≈. 而在很多应用中，二进制码的长度都大于256维并且查询半径一般都大于10，以满足检索精度的需求[6]. 在这种情况下，二进制哈希比线性查找还要慢.针对上述问题，Norouzi 提出多索引哈希算法[7]. 该算法在建立索引时将长度为 l 维的二进制码划分为m 个连续不重合的子串，每个子串的长度为l ⎡⎤⎢⎥或者l m ⎢⎥⎣⎦；然后为每个子串建立一个哈希表. 在查询时，按照同样的方式把待查询二进制码划分为 m 个子串，然后在相应的哈希表中进行查找以返回候选结果. 最后根据候选结果和查询之间的海明距离对候选结果排序并得到最近邻. 多索引哈希算法[7]的理论基础是：当两个二进制码 q 和 p 有r 位不相同时，那么至少它们的一个子串最多有r m ⎢⎥⎣⎦位不同：1 .. k kH k m s t q p r m ∃≤≤−≤⎢⎥⎣⎦, (3)其中k q 是q 的第k 个子串. 通过这种方式，多索引哈希算法可以极大地降低了需要比对的待检测数据量. 比如当l=256, r =5 , m=2, 需要比对的数据量为21280*i i m C =∑=16,512, 远远小于1010. 因此多索引哈希算法在索引长二进制码时具有明显的优势. 但是多索引哈希算法基于数据集中的二进制码呈均匀分布这一假设[7]，不能有效处理非均匀分布的数据集. 在多媒体检索中，数据集的分布往往都是非均匀的[1][11]. 因此多索引哈希算法具有两个缺点：z 如果待检测区间分布的数据元素比较密集，那么在对候选结果计算距离并排序时需要很多额外的时间开销，从而增加计算量.z 如果待检测区间分布的数据元素比较稀疏，那么候选结果太少. 为了保证足够多的候选结果，不得不增加查询半径r , 这样增加了索引查询时间.1.2 多索引哈希算法通过1.1节的分析可以看出，多索引哈希算法的时间性能依赖于数据集的分布. 为了得到最优的时间性能，需要使哈希表中元素下标的分布尽可能呈均匀分布. 因此，作者在多索引哈希算法的基础上提出数据依赖的多索引哈希算法，算法框架如图1所示. 通过构建一个训练数据集并计算二进制码每位之间的相关性，为每一个子串学习得到自适应投影向量. 在为每个子串建立哈希表时，使用投影向量对子串进行投影从而得到哈希表中的下标. 采用自适应投影的方法可以使得哈希表中的元素下标接近于均匀分布，进而提升查询速度.数据集的非均匀分布是由于二进制码的各个位之间具有相关性造成的[7][11]. 主成分分析（PrincipalComponent Analysis ，PCA ）[10] 是一种用来揭示复杂数据潜在的简单结构的数据分析技术. PCA 通过计算新的一组基对原有数据进行线性变换，变换后的数据尽量揭示原有数据之间的关系，且具有线性不相关性.PCA 的优点是简单有效且无参数设置，因此在计算机视觉领域应用广泛. 基于这一理论基础，作者采用PCA 来生成投影向量，以得到分布均匀的投影数据. 从而在尽量保留原始数据近邻关系的前提下，将索引均衡化. 数据依赖的多索引哈希算法执行步骤如下：a. 构建一个训练数据集1[,,,]i n T x x x ="用于PCA 训练. i x 是一个l 维二进制码，用一个列向量表示.为了算法的普适性，训练集和用于建立索引的基准数据集没有重合.b. 计算训练集T 的均值向量μ和协方差矩阵S ：西安电子科技大学学报（自然科学版） 第42卷 180 11n i i x n μ==∑,,1()()n T i j i j S x x μμ==−−∑. (4) c. 对于每一个子串，获取其对应的协方差矩阵'S .'S 是S 的一个子矩阵. 然后对矩阵'S 进行特征值分解，得到对应最大特征值的特征向量V .向量V 即为该子串的自适应投影向量.d. 在建立索引和查询时，使用投影向量对子串进行投影从而得到哈希表中的下标. 假设某一子串为1[,,...,]i d p p p p =，那么新的下标值为：1**2dd i i i i indice p V −==∑ (5)由于投影向量包含数据集的分布信息，并去除数据之间的相关性，生成的哈希表中元素下标接近于均匀分布，从而提升查询速度.1.3 数据分布度量在信息论中，熵是对不确定性的测量. 信息熵越高，能传输的信息越多，信息熵越低，意味着传输的信息越少. 为了度量哈希表中数据元素的分布情况，作者提出一个基于熵的分布度量函数. 对于一个哈希表h , 假设数据集的大小为N , 哈希表h 有num_b 个哈希桶，第i 个哈希桶有()n i 个数据元素. 那么把某一个二进制串分配到第i 个哈希桶的概率估算为()()p i n i N =. 哈希表h 的分布熵定义为：_1()(()*log(()))num bi E h p i p i ==−∑. (6)直观上，如果哈希表的分布熵值比较大，那么其中的数据元素更接近于均匀分布. 通过这一度量公式，可以近似地量化和对比哈希表中数据元素的分布情况.2 实 验本节通过大量实验验证本文算法的有效性. 在实验的第1 部分, 首先介绍实验所用的数据集和评测方法；第2部分分析训练集的大小对算法性能的影响；第3部分验证算法的有效性和扩展性.2.1 实验数据集和评测方法实验在著名的ANN_SIFT1B 数据集[12]上开展. 该数据集的元素是128维的SIFT 描述子[13], 其中包含910的基准数据集用于建立索引，810的训练集和410的查询集. 实验数据集的具体描述如表1所述.表1 实验数据集描述数据集大小 基准数据集910 训练集810 查询集 410由于SIFT 描述子是浮点型的向量，作者采用文献[7]提供的开源代码得到原始数据集对应的二进制码数据集，每个二进制码为128维. 在实验中，首先由训练集计算二进制码各位的相关性并学习投影向量. 在性能对比时，训练集和基准数据集没有重合，以保证算法的普适性.为了验证本文提出的数据依赖的多索引哈希算法（Data-Oriented Multi-Index Hashing ，DOMIH ）的性能，本文与多索引哈希算法（Multi-Index Hashing ，MIH ）[7]和数据驱动的多索引哈希算法(Data Driven Multi-Index Hashing ，DDMIH) [11]进行实验对比. 数据驱动的多索引哈希算法把二进制码划分为多个不连续且不重合的子串，以去除数据的相关性.实验的硬件环境如下：Intel Xeon E5-2620*2(2.00 GHz, 7.2GT/s, 15M cache, 6cores)，64G 内存， 上述三个算法都在相同的软硬件环境下运行. 由于这三个算法都返回查询的精确最近邻，因此它们具有相同的精度[11]. 所以在性能对比中，本文主要比较它们的平均查询时间和扩展性.第4期 马艳萍等：数据依赖的多索引哈希算法 1812.2 训练集大小对算法的影响由于本文构建训练集计算二进制码各位的相关性并学习自适应投影向量，那么训练集的大小对算法的性能有一定的影响. 直观上地，训练集越大得到的投影向量越能反应二进制码各位的相关性，算法的性能越好；训练集越小则算法的性能较差. 但是训练集越大计算协方差矩阵的时间就越长，即使这些操作是离线完成不影响在线查询时间. 表2 展示了随着训练集大小的变化本文算法的@1000recall NN 值.@1000recall NN 值度量索引算法返回的前1000个候选结果中正确结果的个数，即召回率. @1000recall NN定义如下：_1000_1000@1000_1000DOMIH NN Linear NN recall NN Linear NN∩= , (7) 其中_1000DOMIH NN 是本文算法返回的前1000个候选结果，即没有根据与查询之间的海明距离对候选结果排序；_1000Linear NN 是线性查找算法返回的前1000个结果，即精确的1000近邻. 对于每个查询，本文计算它的@1000recall NN 值，然后对所有查询求均值.表2 训练集大小对算法性能的影响，基准数据集为910.训练集大小310410510610 710810@1000recall NN 0.4470.5240.5720.623 0.6260.627通过表2 可以看出当训练集中元素个数从310增加到810时，本文算法的@1000recall NN 值不断提升. 当训练集从310增加到610时，@1000recall NN 值的增加幅度很大；当训练集从610增加到810时，@1000recall NN 值的增加幅度很小；即当训练集的大小为610时，@1000recall NN 值趋于稳定. 综合考虑算法精度和时间性能，本文把训练集的大小设置为610.2.3 算法有效性和扩展性验证为了验证本文算法的有效性，本文首先根据公式(6)对比DOMIH 、MIH 和DDMIH 中各个哈希表的数据分布情况；然后对比随着基准数据集和返回结果数量的增加，这三个算法对单查询的平均响应时间. 由于基准数据集的大小为910，那么每个二进制串的长度为9102log 32≈错误！未找到引用源。
