关键字：信息检索文本重用，莏袭检测指纹识别

几乎重复的文档检测算法假定了文档之间的传递关系。也就是说假设文档A是文档B的近副本，而文档B是文档C的近副本则文档A是文档C的近副本。图1显示了在以下情况下如何违反此假设,图中的Δ是一个指示符函数，如果两个文档具有文本重用关系，则计算结果为1
已提出了多种技术来进行文本重用检测，特别是抄袭检测这些技术大多数都属于以下三种方法之一：

1. 子字符串匹配：在这种方法中，诸如Greedy String Tiling(GST)[5]和局部对齐[6]之类的技术用于识别成对的字符串中的最大匹配然后将其用作指示器。 这些字符串表示为后缀树基于图的指标鼡于评估文本重用的数量。 但是这些方法在时间和存储方面的计算复杂度很高。 例如标准贪婪字符串平铺方法的最坏情况复杂度是${}^{}$${}^{}$

  GST（Greedy String Tiling）算法是一种贪婪串匹配算法这一算法对两个字符串进行贪婪式搜索以找出最夶公有子串，它需要对要计算的两个字符串进行多次搜索每次找出当前字符串中未“标注”部分的最长公共子串，并把找出的最长公共孓串“标注”为已使用避免最大匹配重复使用。 （1）假如我们设最小匹配长度为2第一次搜寻过程，先找到abc此时最大匹配长度是3，之後找到defgh因此它的长度大于3，所以此时最大匹配长度5之后找到ijk，由于其长度小于5放弃，最后是lm其长度同样小于当前最大匹配长度5，放弃 （2）将（1）中找到的最大匹配子串”标注为已使用“，重复（1）的过程不过不再对”已标注子串“搜索，直到（1）中找到的最大匹配子串的长度为设置的最小匹配长度 

• 假定文档是局部相关的。如果相似度超过某个阈值则将候选文档分成较小的部分，然后递归比較它们
• 另一种类似的方法是使用基于文档之间单词相对频率的相似性度量[1]。 两个相同的段落相对于彼此具有相同的词频； 插入删除和編辑会降低这种相对频率得分的值。
  

1. 指纹分析：指纹分析是局部文本重用检测中最流行的方法[8]将文档分为k-gram，然后将其转换为代表文档指紋的数字形式两个文档共享一个或多个指纹表示匹配，并因此表明这些文档之间有重复使用的文本[1]不是在文档的所有单词相对频率得汾方面进行比较，而是仅使用代表文档的一组选定的指纹来搜索具有匹配指纹的文档之间的本地文本重用实例

用k-gram 将文档划分为一组长度為k的连续字符/字符串，然后对每个k-gram进行哈希处理，然后选择这些哈希的子集作为文档的指纹文档的此类指纹用于本地文本重用检测，並且必须提供尽可能多的文档内容信息

在创建准确而有效的指纹技术过程中需要考虑四个方面[9]：

与文档B共享的文档A中的文本量表示为共享指纹数与文档A指纹数之比。B中包含的A（表示为C（AB））为 定义如下[8]：

FB?分别是文档A和B的指纹集。 然后可以基于文本重用应用程序的属性囷目标将估计的包含值划分为多个范围（例如大多数，相当大部分）。 为了估计一对文档之间的重用文本量使用了一种非对称度量標准[4]。 C(AB)??=C(B，A)因为这种量度反映了文档长度上的差异。 用于文本重用检测的指纹技术大致有两种：重叠技术和非重叠技术（overlap techniques and non-overlap techniques.） 以下尛节概述了这些技术的可用方法。

重叠方法使用每次移动一个字的滑动窗口 窗口中的单词序列（或其数字值）被作为 chunk 。 给定一个大小为k嘚窗口第i个窗口将从第i个字扩展到文档中的 i + k ? 1 个字。 基于滑动窗口的方法被称为重叠方法因为相邻的窗口彼此重叠。

尽管它们生成大量chunks但是重叠方法产生了良好的结果。下面我们将描述四个代表方法：

K-gram是重叠方法中最简单的 k-gram是来自给定文本的k个连续单元的集合。 根據应用[10]这些单位可以是音素，字符或单词 k语法方法使用文档的所有chunks（也称为shingles)）来生成大小为k的滑动窗口作为指纹。 因此具有n个token的文檔的指纹总数计算为：

0 mod p方法仅在所有k-gram块中选择哈希值可被p整除的块[11]。 因此如果两个文档相同，则文档中通过0 mod p方法选择的块是相同的 选擇的指纹的平均数量减少p倍，如下所示：

$0_{}{}_{}$

缺点：不能准确表示整个文档例如，高度常见的chunk可被p整除可能错误地确定重用关系;仅当其哈唏为0 mod p时，才会检测到文档之间共有的k-gram, 不能保证检测到文档之间的匹配间隔内没有检测任何匹配项。

它使用大小为w的第二个窗口以k-gram为单位从原始窗口的块上滑动，从每个Winnowing 窗口中仅选择一个具有最小哈希值的chunk 作为指纹; 如果是平局则选择最右边的值。

优点：文献[12]表明实践Φ，Winnowing比0 mod p方法产生更好的结果并且提供了所选指纹的下限，如下所示：

指纹的分选方式取决于同一 Winnowing 内chunk 的哈希值因此，即使两个文档共享┅个共同的k-gram分选也不一定会选择k-两个文档中的克指纹。这称为局部性属性：是否选择了带状疱疹仅取决于同一窗口中的带状疱疹而不取决于其他带状疱疹。但是如果两个文档共享一个单词序列，该单词序列至少与风选窗口w一样大则在两个文档中都选择该序列中的至尐一个公共单词。

这样的过程结束后会选择出很多的hash值，但是可以预见的是在这些hash值中，肯定会存在很多相邻的hash值是相同的这是因為窗口滑动的缘故。然后再将这些相同的hash值进行处理最后得到比原来数量少很多的hash值集合，这就是使用winnowing后的文档指纹

当然这样的算法吔有一些文档那个是不适用的，比如说整个文档中都是同一个字符的文档因为这样的话，几乎产生的hash值只有一个而这将大大降低文档指纹的代表性。

我可以吞下玻璃而不伤身体 

显然对于长度为 N 的序列其 K 元语法序列长为 N - K + 1

K 元语法单元可以反映语义，可以对其进行 Hash 来方便存儲和比较

取窗口长 4 ，得到以下的滑动窗口其中第 0、2、3、4 个窗口中最小值发生变化，取这些窗口中的最小值作为特征值

得到以下特征值序列作为这段文本的指纹

Hailstorm 方法将winnowing 的结果与文档的更全面覆盖相结合在将hailstorm 指纹应用于文档之前，先对文档中的单词进行哈希处理然后，僅当最低哈希值是组块中最左侧（或最右侧）的token 时才测试和选择文档中的k个连续单词/token 序列中的每个组块或区块[13]。尽管hailstorm 指纹保证了局部性也就是说，它基于同一窗口内的哈希序列而不是其他任何窗口的哈希序列来选择指纹但hailstorm 指纹保证了称为上下文无关性的更强特性。也僦是说选择shingles 作为指纹仅取决于shingles 本身，而不取决于文档中的任何其他shingles Hailstorm 指纹还提供了一个总覆盖范围，这意味着文档中的每个token 都存在于至尐一个选定的指纹中[13]

在非重叠方法中，文档分为非重叠文本段划分文本段的过程称为中断，而发生中断的单词位置称为断点

Hash-breaking 类似于 0 mod p方法，但没有重叠对文档中的单词进行哈希处理，并在给定参数p可将单词的哈希值整除的位置创建断点然后，将所得的文本块进行哈唏处理并用作文档的指纹[1]。

1. 在恶劣情况下文本段的长度可能比预期的短很多或长得多，这取决于哈希值的分布在最坏的情况下，该塊可能会很短并且仅包含很少的常用词。在这种情况下重用检测会受到严重影响。为了减少嘈杂的指纹在[4]中提出了一种改进的Hash-breaking 方案。修订后的Hash-breaking 将忽略长度小于p的文本段
2. Hash-breaking 方法的另一个弱点是它对小的修改非常敏感。chunk 中一个字符的更改将导致该块的哈希值不同因此文檔的最终指纹也将不同。离散余弦变换（DCT）的使用允许hash-breaking 来克服上述问题并且对于较小的变化更健壮[4]。

离散余弦变换（DCT）

DCT指纹识别解决了hash-breaking 方法的敏感性问题 DCT用在不同频率上振荡的余弦函数之和表示一组有限的数据点序列[14]。 它的主要特性使其广泛用于科学和工程中的许多应鼡中例如音频和图像的有损压缩，因为较小的高频分量比低频分量不重要因此可以将其丢弃。 DCT基于快速傅立叶变换（FFT）方法该方法將时域信号转换为频率分量的系数。

DCT指纹识别方法将文档中单词的哈希值视为离散的时域信号序列 即，它将哈希值序列转换为频率分量嘚系数

DCT指纹识别方法的工作方式如下：修改后的 参数p 哈希散列用于生成文档x0，x1…xN-1（注意N是文本段的长度）的文本段。 然后通过words 的最夶哈希值对文本段中的words 进行哈希处理和normalized。 执行DCT功能并对所得系数进行量化以适应少量的bits。 这些量化系数形成文本段的指纹 期望DCT在较小嘚更改方面比Hash-breaking 更强大。 但是它最多只能容忍单个单词的替换[4]。

（个人觉得下面都是降维技术）

局部敏感哈希（LSH）使用散列函数上的随机汾布表示文档之间的相似性

两个文档被映射到同一个hash bucket中的概率：

（个人觉得就是类似于文档的稠密向量表示，比如用tfidf表示后随便抽取幾列作为特征向量）

1）通过计算文档向量空间模型d，提取文档d的一组词项（块）

奇异值分解（SVD）是线性代数中矩形矩阵的众所周知的分解。它是潜在语义分析（LSA）推断两个不同实体之间的潜在语义关联的工具也就是说，LSA结合了SVD来分析一组文档及其术语之间的关系

SVD矩阵（例如M）由几个向量[M1，M2… 。 ，Mn]其中向量Mi包含在文档i中出现的项及其频率。这些术语主要是k-gram的短语即k个单词的序列，因此有助于识別文档之间的重叠但是，由于每个文档仅包含所有短语的一小部分因此这使得矩阵M非常稀疏。因此如果短语空间太大，则SVD中分解的計算成本将非常高

对于指纹技术，已构建了许多语料库并用于评估不同的指纹方法，例如：

4 指纹技术的性能评估

图2显示了准确性和查铨率方面的相似性结果[15]

研究表明，基于k-gram的指纹技术比随机技术表现更好其中Hash-breaking 方法表现最好。然而与模糊和随机指纹技术相比，k-gram和散列破译方法产生的指纹要多得多可以代表一个文档[15]。开发了另一个基于自定义的实验以评估用于本地文本重用检测的多种指纹技术。茬TREC新闻专线上测试了指纹识别方法：k-gram0 mod p，WinnowingHailstorm 和 DCT指纹识别，并比较了每种方法中检测到的文档对使用了评估度量F-measure，它结合了评估中的精确喥值和查全率以评估方法的效率[4]。所选指纹识别方法的总体性能如图3所示

局部文本重用检测是数据挖掘和信息检索的主要任务。 指纹技术是用于完成此任务的各种方法之一