信息指纹

欢迎支持笔者新作：《深入理解Kafka:核心设计与实践原理》和《RabbitMQ实战指南》，同时欢迎关注笔者的微信公众号：朱小厮的博客。

##信息指纹的由来

信息有“指纹”吗？信息要“指纹”做什么呢？
"指纹”一般特指我们识别人所采用各种方式的一个总称。生活中我们需要辨认出周围的每一个人，即使是非常相似的双胞胎，因为辨别是我们进行相互交流的前提。无论是通过名字、长相、声音的辨认，还是通过有技术依据的指纹与虹膜辨认，甚至是通过DNA鉴定，目的都只有一个，就是能准确确认对方。
可见指纹的首要用途就是识别个体，当然作为指纹特征，需要它是可唯一确定的、不容易更改的、方便携带的。另外一个重要用途是检索，我们需要找哪个朋友的时候，可呼叫他的名字找到他，也可以把他的指纹输入电脑，很快就查询到他的详细信息。
我们说：信息需要“指纹”的目的也有两个：一是检索，二是防止有假。前一个目的容易理解，我们现在都习惯网上搜索，找寻我们需要的各种信息。搜索有两种模式：一种是将信息都先分类，先选择信息类别是科技的还是文学的，是文字的还是图像的；先大类再小类，逐渐细化，直到你找到需要的信息。但这种方式需要对信息做预处理，并且分类要科学，合乎大部分人的逻辑，否则就象迷宫一样，进去就难出来了。另一种是提供一些搜寻的关键字，查询时不可能拿这些关键字与所有的信息原文进行比对，时间上是不可能的，比对的一定是事前整理好的特征信息，能“代表”信息的规律的信息，这就是信息的指纹。所以信息提取指纹是我们在信息海洋中搜寻的前提。这个需求产生了Yahoo、Google、百度等搜索公司。理所当然，信息指纹技术也是搜索公司特别关注的新技术之一。
信息需要指纹的另一个目的也是互联网带来的。我们生活在金钱驱动的阶级时代，免费的午餐是没有的，虽然信息的提供者大多的奉献的，但当信息的价值显现时，版权的问题就来了，最起码的，你使用人家的信息，也应该给人家署名吧，尊敬也好，版权也好，反正信息需要带上其“出身”的标签。这在从前是相对容易的，因为信息的载体是纸张、广播、电视，这些都比较好管理，互联网的兴起，信息变为电子流，一个人人都可以编辑的电子文档，使用者说是他自己的写的，你很难说是你的。若能在你发布的电子信息中，生成自身的“指纹”，别人就不容易冒充了。我们听说过影像光盘中的“电子水印”，就是在视频信息中隐藏制作者的特别信息，作为识别的“指纹”，但对普通的电子文档，大家似乎没有好的方法，现在流行的pdf文档(只能读不能改的一种文档格式，把文字变成类似图像的信息)是一些厂家提供手册、说明书的保护方法，但对于互联网上的丰富信息来说不适用的。
我们很容易联想到CA证书的方式，在电子信息中放入证书，具有防篡改和抗抵赖的功效，然而在普通的文档中，证书与信息本身是很容易分离的，也就是说我只要信息，抛弃证书，把一次“合法”得到的信息，变成自己的，再进行N次复制发布，对信息的拥有者来说，是个“头痛”的问题。互联网是一个虚拟的世界，有些现实中的法律与道德规范很难落实，变化各种虚拟的身份在互联网上就想玩游戏一样方便。所以信息指纹不仅应该源自信息，信息改变了，指纹就能反应出来；而且还要廉价、容易实现。
我们都知道互联网是信息的海洋，但它也有大量的垃圾数据、重复数据，如何有效地在检索中减少重复、剪除垃圾，就需要信息指纹的技术。比如对一个博客文章的搜索，原始发布的应该最需要的，转载的基本属于重复的，引用的则属于有关联的，只是偶尔出现该关键词的不相关信息的就是用户不需要的了。
从另一个需求角度讲，在涉密信息系统中，有一项重要的防护要求，就是高密级的信息不能流向低密级保护的网络区域，但如何防护却是个大问题。信息中的密级标识是很敏感的，只是在文档中标识，则很容易删除或修改，标识被修改了，防泄密就成了问题。信息指纹具有不可篡改的特性，把密级标识放在信息指纹中，就很容易通过密级过滤的“网络防火墙”，自动检索出高密级信息，防止信息的泄密。
综观各种需求与目的，信息不仅需要指纹，而且信息指纹将是互联网上“信息海洋”的必然技术。

##信息指纹提取的几种方法

信息按照其表征特性可以分为：文字信息、图形信息、图像信息、语音信息。按照其来源可以分为：文档信息(正式编写的信息，有标题、作者、摘要、关键字等辅助信息，如正式发表的文章、论文等)、自然信息(随意记录或编写的信息，只有信息的内容，没有或部分有辅助信息，如八卦新闻、聊天室的帖子、博客的文章等)、再生信息(对各种信息的统计信息，或通过对别人信息的重新编写，总结、联想出来的新信息，一般再生信息也都属于文档信息，有辅助说明信息)
统计信息表明：对一个文本信息提取指纹，当选取8个关键词及其词频作为其指纹时，准确度在98%以上，查全率在30%左右。这说明要能“概括”该信息，找出其8个使用频率最高的词汇，基本可以代表这个信息。
因此文字信息提取指纹的要素一般为下面信息：

标题
作者
发布时期、修改日期
主要关键词

其中关键词的选取可以有几种方法：

作者提供的关键词
作者提供的摘要，或整理人员编写的摘要
提取信息中出现频率高的8个关键词
文章开头或结尾一段话
文章中固定位置的一段话(如第5行的第一句话)

有了这些代表信息后，便可以形成指纹信息，若再对这些信息进行Hash运算、MD5等方式加密、变化，生成一段定长(如256字节)的信息，就可以作为该信息的“指纹”，经过加密主要是防止对信息内容的篡改和对指纹的替换。这种方法有些象数字签名技术，但要相对简单，并且不进行加密运算时的标题等信息可以直接作为检索的关键字使用，
这里提取信息中的高频率关键词是一个技术的难点，其原因有两个：

信息中的非特征信息关键词的剔除：如我、你、他等称谓，而且、但是等连接词，对信息标识是没有帮助的。比较“通俗”的词，如管理、学习等可以出现在任何类型的信息中，让用户搜索的信息五花八门；比较“流行”的词，如姚明、时尚等可能出现频率极高，造成搜索信息非常多。总之，若关键字搜索的信息多得难以阅读，并且杂乱无序，对于查询者就失去了意义。
词汇的提取本身就是问题：对于英文来说，词汇是空格隔离的，比较好提取，而对于中文来说，一句话中可以多种断句，得到的词汇会很多，识别结果有很大的差异。目前搜索公司大多采用巨大的词汇库方式，最长匹配也好，通俗词汇管理也好，说白了就是还没有一个模型或算法可以最好地识别词汇。这也正是Google也好，百度也好对中文的搜索结果都不尽如人意的原因。

文字信息的指纹提取不容易，对语音、图像指纹的提取就更困难了，因为对图像、语音的描述本身就比文字要麻烦。一般的思路是：在语音、图像先进行特征编码，也就是选取有代表意义的局部，语音中的某段频率(人的声音都有自己的音色特点)，图像中的明暗对比强烈的地方、或关键图像的区域等，再对编码进行变换、加密等处理，形成指纹。下面我们介绍一个图像提取指纹的简单方法：色阶图方法
色阶图(Color histograms)：就是从图像中产生出，可以描述图像的色彩分布。
图像与文本信息不同，是以点阵的色彩存放，信息量非常大，算法的目的就是进行信息简化，具体步骤如下：

大小：对图像进行切割，根据颗粒度不同，小块大小为mn，图像分割为MN个块
模糊：对每个图像块进行色彩的平均处理，也就是用该块最多的颜色代表该块
减色：将色彩从真彩的65536色减少，合并颜色，当然颜色数量可以根据颗粒度选择8色、16色、256色等，本例选择为8色
替换：简化后信息为MN8，每个颜色用一个字母符号替代，如：采用xpm格式，每个颜色用一个字符表示： B 对 black .
对blue X 对green o对cyan O 对 red + 对magenta @ 对yellow #
对gray100
编码：把每个图像块用其字母替代，再按顺序排列，就形成一个M*N的字符串。该字串作为图像的指纹信息。