一、信息指纹的由来

    提到“指纹”就想到了人手的指纹。那么指纹能干嘛呢？我们看到最多的是警匪片中验指纹，还有公司考勤打卡用指纹等。其目的在于识别个体。当然作为指纹特征，需要它是可唯一确定的、不容易更改的、方便携带的。

    信息需要“指纹”的目的也有两个：一是检索，二是防假。指纹可用于检索，主要是在做一些关键字查询时不可能拿这些关键字与所有的信息原文进行比对，时间上是不可能的，比对的一定是事前整理好的特征信息，能“代表”信息的规律的信息，这就是信息的指纹。所以信息提取指纹是我们在信息海洋中搜寻的前提。信息指纹技术也是搜索公司特别关注的新技术之一。信息指纹还可以用于防假。将信息打上相关的指纹就可以防止他人侵占革命成果，这有此类似于数据签名、CA验证之类的。例如，对博客文章进行语义指纹提取就能很好地识别重复，另如将不同密级的信息进行指纹提取给信息本身一个指纹更方便而且安全的识别信息密级。

二、语义指纹提取的几种方法

    语义指纹是一种高效率的信息处理方式，它不仅节约了时间成本还节约了计算成本，在现实生活中应用较多，例如搜索引擎、全文检索系统、论文防剽窃系统等。指纹是对有用的信息进行的提取，故在此将信息指纹称为“语义指纹”。不同的应用需求，会有不同的语义指纹提取方法。

（一）文本信息指纹提取

    统计信息表明：对一个文本信息提取指纹，当选取8个关键词及其词频作为其指纹时，准确度在98%以上，查全率在30%左右。这说明要能“概括”该信息，找出其8个使用频率最高的词汇，基本可以代表这个信息。

因此文字信息提取指纹的要素一般为下面信息：

n         标题

n         作者

n         发布时期、修改日期

n         主要关键词

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

★       作者提供的关键词

★       作者提供的摘要，或整理人员编写的摘要

★       提取信息中出现频率高的8个关键词

★       文章开头或结尾一段话

★       文章中固定位置的一段话(如第5行的第一句话)

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

    具体应用例如：运用一种基于网页关键词概念之间关系的关键词选取方法，来计算出网页中关键词权重并进行排序，然后选取权重最高的L个关键词，并称这L个关键词为长度为L的网页指纹或者因为如果以这一关键词集合来描述网页文本时，它们是具有最丰富的网页语义表达的选择。

    下面给出一个具体的算法：

    该方法通过分解文档、构建文本块序列、Hash文本块序列、指纹提取等步骤自动检测文档间的重叠信息。文本块是检测的基本单位，较大的粒度可以有效地减少检测结果中误差的数目，但是粒度越大，丢失复制文本的机率越大。因此文本块的长度直接关系检测结果的准确性和精确程度。本文分别选取两种检测粒度的文本块：

    1）句子文本块。句子作为文本块，不仅可以减少块的数量，降低存储空间消耗，提高检测效率，同时句子也是位置相对独立的结构单元，改变它在文档中的顺序，不影响检测结果。短句包含较少的语义知识，对文档的贡献也少，因此没必要参与计算。这就需要方法对句子的选择进行限制，即句子中应该包含一定数量的有效关键词。定义噪声粒度，从检测文档中消解噪声。例如对句子进行分词后去除停用词，如果其关键词的数目不小于，则认为是有效的，否则丢弃；

    2） k-words文本块。对长句进行分解，使用连续的k个词语构建重叠的文本块序列。不仅能够发现文档句子间的重叠文本，同时又抑制噪声有效地提高了检测结果的精确度。例如，对于句子 ，构建的文本块序列分别为 。同时方法定义检测粒度g，目的是要检测出文档间任何大于该粒度的复制文本。

    把文本块看作是一个k位的数字，使各个词语取其词汇库中对应的映射值，利用Karp-Rabin函数可以把文本块数值化。令散列值序列为h1h2h3h4…hn（n为句子长度）。如果要找出所有粒度大于g的文本匹配，那么当n>g-k时，在该序列中应该至少选择出一个hi才能满足条件。令窗口长度为g-k+1。散列值序列h1h2h3h4…hi…hn中对于任意的1<=i<=n-g+k(重叠窗口个数)都定义了一个散列值窗口hihi+1…hi+g-k，如果在各个窗口中提取相应的文本特征，方法就可以保证发现所有粒度大于g的文本匹配。选择出的文本特征称为指纹。

    本文的指纹提取算法如下：

    输入：句子序列、噪声粒度k和检测粒度g

    输出：[指纹，全局位置]

    1）利用Hash函数把关键词数目不小于k的句子数值化，选择所有句子散列值作为指纹并标记全局位置；

    2）分解句子，构建 k-words文本块序列。并标记散列值所在的全局位置，将散列值分配到长度为g-k+1的重叠窗口中；

    3）提取文本块指纹：

    ①在第一个窗口中选择最小的数值作为指纹，并记录指纹的全局位置。若存在相同的最小值，选择全局位置最大的数值作为指纹（指针指在指纹位置）；

    ②若指针不大于窗口的个数（句子散列没有结束），则指针后移。否则，转4）；

    ③设前一个提取出的指纹为fi，若fi不存在于当前窗口中，从右向左查找最小的数值（当前最小的最大位置），并记录该值以及全局位置，返回②；

    ④若fi存在于当前窗口中，比较fi和窗口中位置最大的数值hg-k。若fi<hg-k，返回②；否则选择hg-k作为指纹，返回②；（感觉像是最小值所负责的范围）

    4）算法结束。

    该算法的优势在于算法能检测出任何，粒度大于的复制文本。算法的时间复杂度为o(n)。

（二）多媒体信息指纹提取

    文字信息的指纹提取不容易，对语音、图像指纹的提取就更困难了，因为对图像、语音的描述本身就比文字要麻烦。一般的思路是：在语音、图像先进行特征编码，也就是选取有代表意义的局部，语音中的某段频率(人的声音都有自己的音色特点)，图像中的明暗对比强烈的地方、或关键图像的区域等，再对编码进行变换、加密等处理，形成指纹。下面我们介绍一个图像提取指纹的简单方法：色阶图方法。

    色阶图(Color histograms)：就是从图像中产生出，可以描述图像的色彩分布。

图像与文本信息不同，是以点阵的色彩存放，信息量非常大，算法的目的就是进行信息简化，具体步骤如下：

1.         大小：对图像进行切割，根据颗粒度不同，小块大小为m*n，图像分割为M*N个块

2.         模糊：对每个图像块进行色彩的平均处理，也就是用该块最多的颜色代表该块

3.         减色：将色彩从真彩的65536色减少，合并颜色，当然颜色数量可以根据颗粒度选择8色、16色、256色等，本例选择为8色

4.         替换：简化后信息为M*N*8，每个颜色用一个字母符号替代，如：采用xpm格式，每个颜色用一个字符表示：

B 对 black   . 对blue     X 对green    o对cyan 

O 对 red    + 对magenta  @ 对yellow   # 对gray100

5.         编码：把每个图像块用其字母替代，再按顺序排列，就形成一个M*N的字符串。该字串作为图像的指纹信息。

 

三、语义指纹应用

    语义指纹应用也主要来源于它的两个功能，一是检索，二是防假。

    （1）信息复制性检测

    主要应用场景有：网页（文档）去重、文本复制检测。在网页去重应用中，通过对网页的特征信息进行提取，建立网页指纹，如果有相同指纹的网页进入，则可判断为“同一”网页。在文本复制检测中，将文本进行分块，分别对目标块和源块进行指纹提取，通过比对指纹即可判断是否存在文本抄袭或者复制。具体过程要复杂得多，可以参阅相关论文。

    （2）检索

    这一功能是指纹的反向利用，简单举例，如在新闻搜索中，相似新闻的检索就可以通过新闻指纹查到同一指纹关联的多个新闻。

参考文献[有摘录]：

1，  http://zhaisj.blog.51cto.com/219066/117168

2，  基于自然语言处理的网页去重关键技术

3，  基于指纹和语义特征的文档复制检测方法

转载本文请联系原作者获取授权，同时请注明本文来自毛进科学网博客。
链接地址：https://blog.sciencenet.cn/blog-563898-506396.html

上一篇：初识图像检索技术
下一篇：情报学相关的2011SCI分区情况