详解用于相似和剽窃检测的技术Shingling

本文将向你引见shingling的概念、Shingling技术的基础常识、Jaccard相似性、以及初级技术和优化。

在数字时代，消息随时可用且易于访问，须要一种能够检测剽窃（有意或有意）的技术，从内容复制到增强人造言语处置才干。Shingling的配置异乎寻常之处在于它裁减到各种运行程序的模式，包括但不限于文档集群、消息检索和内容介绍系统。

本文概述了以下内容：

一、了解Shingling的概念

Shingling技术是一种宽泛用于检测和减轻文本相似性的技术。它是将文档中的一串文本转换为一组堆叠的单词或字母序列的环节。在编程上，可以将其看作是字符串值中的子字符串列表。

让咱们举个例子：“Generative AI is evolving rapidly.”。咱们用k示意Shingle的长度，并将k的值设为5。

结果是一组五个字母：

{'i is ', ' evol', 'apidl', 'e ai ', 'ai is', 'erati', 've ai', 'rapid', 'idly.', 'ing r', ' ai i', 's evo', 'volvi', 'nerat', ' is e', 'ving ', 'tive ', 'enera', 'ng ra', 'is ev', 'gener', 'ative', 'evolv', 'pidly', ' rapi', 'olvin', 'rativ', 'lving', 'ive a', 'g rap'}

这组堆叠的序列被称为“shingles”或“n-grams”。Shingles由文本中延续的单词或字符组成，创立了一系列堆叠的片段。下面称为“k”的Shingle的长度依据剖析的详细要求而不同，经常出现的做法是创立蕴含三到五个单词或字符的shingles。

二、探求Shingling的基本常识

Shingling是三步骤环节的一部分。

标志化

假设你相熟揭示式工程，那么应该据说过标志化。它是将一系列文本合成成被称为标志的更小单位的环节。标志可以是单词、子词、字符或其余有意义的单位。此步骤为模型的进一步处置预备了文本数据。经过单词标志化，下面的例子“Generative AI is evolving rapidly”将被标志化为：

['Generative', 'AI', 'is', 'evolving', 'rapidly', '.']

关于标志化，你可以经常使用便捷的Python的split方法或Regex方法。有像NLTK（人造言语工具包）和spaCy这样的库提供停用词等初级选项。

正如如今所知的，Shingling，也被称为n-gramming，是从标志文本中创立一组延续的标志序列（n-grams or shingles）的环节。例如，经常使用k=3，句子“Generative AI is evolving rapidly.”将会生成如下shingles：

[['Generative', 'AI', 'is'], ['AI', 'is', 'evolving'], ['is', 'evolving', 'rapidly.']]

ingling有助于捕捉此时的词序和高低文。

哈希（Hashing）

哈希仅仅象征着经常使用不凡的函数将任何类型的数据，如文本或shingles，转换为固定大小的代码。一些盛行的哈希方法包括MinHash、SimHash和部分敏感哈希（LSH）。哈希支持对相似的文本段启动高效的比拟、索引和检索。当你将文档转换成一组shingles代码时，比拟它们并发现相似之处或或者的剽窃要便捷得多。

便捷的Shingling

让咱们看看两个被宽泛用于解释便捷shingling的短文：

00001●第一段：“The quick brown fox jumps over the lazy dog.”

00002●第二段：“The quick brown fox jumps over the sleeping cat.”

k值大小为4，经常使用下面的w-shingle Python，第1段的shingles是：

1python w_shingle.py "The quick brown fox jumps over the lazy dog." -w 4[['The', 'quick', 'brown', 'fox'], ['quick', 'brown', 'fox', 'jumps'], ['brown', 'fox', 'jumps', 'over'], ['fox', 'jumps', 'over', 'the'], ['jumps', 'over', 'the', 'lazy'], ['over', 'the', 'lazy', 'dog.']]

关于第2段，shingles应为：

1 python w_shingle.py "The quick brown fox jumps over the sleeping cat" -w 4[['The', 'quick', 'brown', 'fox'], ['quick', 'brown', 'fox', 'jumps'], ['brown', 'fox', 'jumps', 'over'], ['fox', 'jumps', 'over', 'the'], ['jumps', 'over', 'the', 'sleeping'], ['over', 'the', 'sleeping', 'cat']]

经过比拟shingles组，你可以看到前四个shingles是相反的，这标明了两个短文之间的高度相似性。

Shingling为更详细的剖析奠定了基础，比如经常使用Jaccard相似性来权衡相似性。选用适合的shingle尺寸“k”是至关关键的。较小的shingle可以捕捉小的言语细节，而较大的shingle或者显示更大的画面咨询。

三、Jaccard相似性：测量文本相似性

在文本剖析中，Jaccard相似度被以为是一个关键的度量目的。经过两个样本中共享的shingles数量与惟一的shingle总数的比率，来计算两个样本之间的相似性。

J(A,B) = (A ∩ B) / (A ∪ B)

Jaccard相似度定义为交加的大小除以每个文本的组合集的大小。只管听起来便捷明了，但这种技术十分弱小，由于它提供了一种计算文本相似度的方法，可以依据两段文本的内容了解它们之间的相关有多亲密。经常使用Jaccard相似性使钻研人员和人工自动模型能够准确地比拟文本数据的剖析。它用于文档聚类、相似性检测和内容分类等义务。

Shingling也可以用来将相似的文档聚类在一同。经过将每个文档示意为一组碎片并计算这些汇合之间的相似性（例如，经常使用Jaccard系数或余弦相似性），你可以将具备高相似性分数的文档分组到簇中。这种方法在各种运行程序中都很有用，比如搜查引擎结果聚类、主题建模和文档分类。

在Python等编程言语中成功Jaccard相似性时，选用单字大小（k）和转换为小写字母确保了比拟的分歧基础，展现了该技术在识别文本相似性方面的适用性。

让咱们计算两个句子之间的Jaccard相似度：

def create_shingles(text, k=5)："""Generates a set of shingles for given text."""return set(text[i ： i + k] for i in range(len(text) - k + 1))def compute_jaccard_similarity(text_a, text_b, k)："""Calculates the Jaccard similarity between two shingle sets."""shingles_a = create_shingles(text_a.lower(), k)print("Shingles for text_a is ", shingles_a)shingles_b = create_shingles(text_b.lower(), k)print("Shingles for text_b is ", shingles_b)intersection = len(shingles_a & shingles_b)union = len(shingles_a | shingles_b)print("Intersection - text_a ∩ text_b： ", intersection)print("Union - text_a ∪ text_b： ", union)return intersection / union

示例

text_a = "Generative AI is evolving rapidly."text_b = "The field of generative AI evolves swiftly."shingles_a = {'enera', 's evo', 'evolv', 'rativ', 'ving ', 'idly.', 'ative', 'nerat', ' is e', 'is ev', 'olvin', 'i is ', 'pidly', 'ing r', 'rapid', 'apidl', 've ai', ' rapi', 'tive ', 'gener', ' evol', 'volvi', 'erati', 'ive a', ' ai i', 'g rap', 'ng ra', 'e ai ', 'lving', 'ai is'}shingles_b = {'enera', 'e fie', 'evolv', 'volve', 'wiftl', 'olves', 'rativ', 'f gen', 'he fi', ' ai e', ' fiel', 'lves ', 'ield ', ' gene', 'ative', ' swif', 'nerat', 'es sw', ' of g', 'ftly.', 'ld of', 've ai', 'ves s', 'of ge', 'ai ev', 'tive ', 'gener', 'the f', ' evol', 'erati', 'iftly', 's swi', 'ive a', 'swift', 'd of ', 'e ai ', 'i evo', 'field', 'eld o'}

J(A,B) = (A ∩ B) / (A ∪ B) = 12 / 57 = 0.2105

所以，Jaccard的相似度是0.2105。得分示意两组相似度为21.05 %（0.2105 * 100）。

示例

让咱们来看看两组数字，而不是段落：

A = { 1,3,6,9}

B = {0,1,4,5,6,8}

（A∩B）=两个汇合中的公共数= {1,6} = 2

（A∪B）=汇合的总数={0、1、3、4、5、6、8、9}=8

计算Jaccard相似度，看看这两组数字有多相似：

(A ∩ B) / (A ∪ B) = 2/8 = 0.25

要计算差异，只有从1中减去这个相似度的值。

1- 0.25 = 0.75

所以这两组的状况，相似是25%，不同是75%。

四、初级技术和优化

先进的拼接、哈希技术和优化，关于在大型数据集中启动高效的相似检测和剽窃检测至关关键。以下是一些初级技术和优化，以及示例和代码成功链接：

部分敏感哈希（LSH）

位置敏感哈希（LSH）是一种先进的技术，它提高了相似性检测的叠加和哈希效率。它触及到创立一个签名矩阵，并经常使用多个哈希函数来降落数据的维数，从而有效地找到相似的文档。

LSH面前的关键思维是将相似的名目以高概率散列到同一个桶（bucket）中，而不相似的名目散列到不同的桶（bucket）中。这是经过经常使用一系列LSH来成功的，这些散列函数将相似的项散列到相反值的概率高于不相似的项。

示例

看以下两个文件A和B，用一组shingles示意：

咱们可以经过以下模式运行LSH：

这一环节清楚增加了须要启动比拟的文档对的数量，使相似度检测更有效。

最小哈希（minhashing，也称散列）

最小哈希是一种经过经常使用一组散列函数来极速预计两个汇合之间相似性的技术。它理论运行于大规模数据处置义务，在这些义务中，计算汇合之间的准确相似性的计算老本是很高的。最小散列近似于汇合之间的Jaccard相似性，它测量两个汇合之间的堆叠。

以下是最小哈希的上班原理：

生成签名矩阵

预计相似性

最小哈希准许清楚增加示意汇合所需的数据量，同时提供它们相似度的良好近似值。

示例：两个汇合

咱们可以用shingles来示意这些汇合：

如今，让咱们经常使用散列生成签名矩阵：

如今，让咱们预计汇合A和B之间的相似性：

代码成功：你可以经常使用NumPy和datasketch等库在Python中成功最小哈希。

Banding 和Bucketing

Banding和Bucketing是与最小哈希联合经常使用的初级优化技术，可有效识别大型数据集中的相似集。在处置少量文档或数据点时，这些技术尤其有价值。

Banding是将散列签名矩阵分红多个带，每个带蕴含几行。经过将矩阵垂直划分为带，咱们增加了汇合之间须要的比拟次数。咱们只比拟同一频带内的行，而不是比拟整个矩阵中的每对行。这大大增加了计算开支，特意是关于大型数据集，由于咱们一次性只有要思考一个子集的行。

Bucketing经过进一步增加每个波段内的比拟环节来补充波段。在每个带内，咱们将行散列到固定数量的桶（bucket）中。每个桶（bucket）都蕴含Banding中带的行子集。在比拟汇合的相似性时，咱们只有要比拟每个带内哈希到同一桶（bucket）的汇合对。这大大增加了所需的成对比拟次数，使环节愈加高效。

示例

假定咱们有一个100行和20个波段的散列（Minhash）签名矩阵。在每个带内，咱们将行散列到10个桶（bucket）中。在比拟汇合时，不须要比拟一切100行，咱们只有要比拟每个带（band）内散列到同一桶（bucket）的汇合对。这大大增加了所需的比拟次数，从而清楚提高了性能，特意是关于大型数据集。

收益

一些开源软件提供了shingling、minhashing将LSH与Bucketing联合的配置，如Python中的datasketch库和Java中的lsh库。

候选配对

候选配对是一种初级技术，与shingling和minhashing联合经常使用，可成功高效的剽窃检测和近乎重复的识别。在shingling的高低文中，候选配对的上班模式如下：

文档首先被转换成k-shingles汇合，k-shingles是从文本中提取的k个标志(单词或字符)的延续序列。这个步骤将文档示意为堆叠的k-gram集，从而成功相似性比拟。

最小哈希（Minhashing，也称散列）

而后经常使用散列技术将shingles集转换为紧凑的散列签名，这些签名是固定长度的向量。散列签名坚持文档之间的相似性，准许有效地预计Jaccard相似性。

散列签名被分红多个波段，每个波段是原始签名的一个较小的子向量。

在每个带（band）内，经常使用散列函数将子向量散列到桶（bucket）中。具备特定频带相反散列值的文档被搁置在同一存储桶（bucket）中。

候选配对生成

假设两个文档在一切频带上共享至少一个桶（bucket），则将它们视为相似性比拟的候选对。换句话说，假设它们的子向量在至少一个频带（band）内碰撞，它们被以为是候选对。

经常使用候选对的好处关键是它大大增加了须要比拟相似性的文档对的数量，由于只思考候选对。这使得剽窃检测环节愈加有效，特意是关于大型数据集。

经过细心选用频带数和频带大小，可以在相似性检测的准确性和计算复杂度之间做出权衡。频带越多，精度越高，但也会参与计算老本。

文档相似性

论断

综上所述，shingling、minhashing、banding和Locality Sensitive Hashing (LSH)的联合为大型文档汇合中的剽窃检测和近重复识别提供了一种弱小而有效的方法。

Shingling将文档转换为k-shingles汇合，k-shingles是k个标志(单词或字符)的延续序列，支持相似性比拟。而后，散列（Minhashing）将这些块集紧缩成紧凑的签名，坚持文档之间的相似性。

为了进一步提高效率，将散列（Minhashing）签名分红多个带，并将每个带的散列分红桶（bucket），将相似的文档分组在一同。这个环节生成候选对，候选对是在一切频带上共享至少一个桶（bucket）的文档对，这大大增加了须要比拟相似性的文档对的数量。

而后只对候选对口头实践的相似性计算，经常使用原始的散列签名来预计Jaccard相似性。相似度高于特定阈值的配对被以为是潜在的剽窃案例或近重复。

这种方法有几个好处：

一些开源软件，如Python中的datasketch库和Java中的lsh库，提供了shingling、minhashing将LSH与Bucketing联合的配置，使这些技术更容易集成到剽窃检测系统或其余须要高效相似性搜查的运行程序中。

总的来说，Shingling、Minhashing、Banding和LSH的联合为剽窃检测和近重复识别提供了一个弱小而有效的处置打算，可运行于学术界、出版和内容治理系统。

进一步阅读

译者引见

涂承烨，社区编辑，省政府洽购专家、省综合性评标专家、公 E 采招标洽购专家，取得消息系统名目治理师、消息系统监理师、PMP，CSPM-2等认证，领有15年以上的开发、名目治理、咨询设计等阅历。对名目治理、前后端开发、微服务、架构设计、物联网、大数据、咨询设计等较为关注。

原文题目：​ ​ Shingling for Similarity and Plagiarism Detection ​ ​，作者：Vidyasagar (Sarath Chandra) Machupalli FBCS