本文將向你介紹shingling的概念、Shingling技術(shù)的基礎(chǔ)知識、Jaccard相似性、以及高級技術(shù)和優(yōu)化。

在數(shù)字時代，信息隨時可用且易于訪問，需要一種能夠檢測抄襲（有意或無意）的技術(shù)，從內(nèi)容復(fù)制到增強(qiáng)自然語言處理能力。Shingling的功能與眾不同之處在于它擴(kuò)展到各種應(yīng)用程序的方式，包括但不限于文檔集群、信息檢索和內(nèi)容推薦系統(tǒng)。

本文概述了以下內(nèi)容：

• 理解Shingling的概念
• 探索Shingling的基礎(chǔ)知識
• Jaccard相似度：測量文本相似度
• 高級技術(shù)和優(yōu)化
• 結(jié)論及進(jìn)一步閱讀

一、 理解Shingling的概念

Shingling技術(shù)是一種廣泛用于檢測和減輕文本相似性的技術(shù)。它是將文檔中的一串文本轉(zhuǎn)換為一組重疊的單詞或字母序列的過程。在編程上，可以將其看作是字符串值中的子字符串列表。

讓我們舉個例子：“Generative AI is evolving rapidly.”。我們用k表示Shingle 的長度，并將k的值設(shè)為5。

結(jié)果是一組五個字母：

{'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由文本中連續(xù)的單詞或字符組成，創(chuàng)建了一系列重疊的片段。上面稱為“k”的Shingle的長度根據(jù)分析的具體要求而不同，常見的做法是創(chuàng)建包含三到五個單詞或字符的shingles。

二、 探索Shingling的基本知識

Shingling是三步驟過程的一部分。

標(biāo)記化

如果你熟悉提示式工程，那么應(yīng)該聽說過標(biāo)記化。它是將一系列文本分解成被稱為標(biāo)記的更小單位的過程。標(biāo)記可以是單詞、子詞、字符或其他有意義的單位。此步驟為模型的進(jìn)一步處理準(zhǔn)備了文本數(shù)據(jù)。通過單詞標(biāo)記化，上面的例子“Generative AI is evolving rapidly”將被標(biāo)記化為：

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

對于標(biāo)記化，你可以使用簡單的Python的split方法或Regex方法。有像NLTK（自然語言工具包）和spaCy這樣的庫提供停用詞等高級選項。

Shingling

正如現(xiàn)在所知的，Shingling，也被稱為n-gramming，是從標(biāo)記文本中創(chuàng)建一組連續(xù)的標(biāo)記序列（n-grams or shingles）的過程。例如，使用k=3，句子“Generative AI is evolving rapidly.”將會生成如下shingles：

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

ingling有助于捕捉此時的詞序和上下文。

哈希（Hashing）

哈希僅僅意味著使用特殊的函數(shù)將任何類型的數(shù)據(jù)，如文本或shingles，轉(zhuǎn)換為固定大小的代碼。一些流行的哈希方法包括MinHash、SimHash和局部敏感哈希（LSH）。哈希支持對類似的文本段進(jìn)行高效的比較、索引和檢索。當(dāng)你將文檔轉(zhuǎn)換成一組shingles代碼時，比較它們并發(fā)現(xiàn)相似之處或可能的剽竊要簡單得多。

簡單的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是：

Shell

1
python 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應(yīng)為：

Shell

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為更詳細(xì)的分析奠定了基礎(chǔ)，比如使用Jaccard相似性來衡量相似性。選擇合適的shingle尺寸“k”是至關(guān)重要的。較小的shingle可以捕捉小的語言細(xì)節(jié)，而較大的shingle可能顯示更大的畫面聯(lián)系。

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

在文本分析中，Jaccard相似度被認(rèn)為是一個關(guān)鍵的度量指標(biāo)。通過兩個樣本中共享的shingles數(shù)量與唯一的shingle總數(shù)的比率，來計算兩個樣本之間的相似性。

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

Jaccard相似度定義為交集的大小除以每個文本的組合集的大小。雖然聽起來簡單明了，但這種技術(shù)非常強(qiáng)大，因為它提供了一種計算文本相似度的方法，可以根據(jù)兩段文本的內(nèi)容了解它們之間的關(guān)系有多密切。使用Jaccard相似性使研究人員和人工智能模型能夠精確地比較文本數(shù)據(jù)的分析。它用于文檔聚類、相似性檢測和內(nèi)容分類等任務(wù)。

Shingling也可以用來將相似的文檔聚類在一起。通過將每個文檔表示為一組碎片并計算這些集合之間的相似性（例如，使用Jaccard系數(shù)或余弦相似性），你可以將具有高相似性分?jǐn)?shù)的文檔分組到簇中。這種方法在各種應(yīng)用程序中都很有用，比如搜索引擎結(jié)果聚類、主題建模和文檔分類。

在Python等編程語言中實現(xiàn)Jaccard相似性時，選擇單字大?。╧）和轉(zhuǎn)換為小寫字母確保了比較的一致基礎(chǔ)，展示了該技術(shù)在識別文本相似性方面的實用性。

讓我們計算兩個句子之間的Jaccard相似度：

Python

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）。

示例

讓我們來看看兩組數(shù)字，而不是段落：

A = { 1,3,6,9}

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

（A∩B）=兩個集合中的公共數(shù)= {1,6} = 2

（A∪B）=集合的總數(shù)={0、1、3、4、5、6、8、9}=8

計算Jaccard相似度，看看這兩組數(shù)字有多相似：

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

要計算差異，只需從1中減去這個相似度的值。

1- 0.25 = 0.75

所以這兩組的情況，相似是25%，不同是75%。

四、 高級技術(shù)和優(yōu)化

先進(jìn)的拼接、哈希技術(shù)和優(yōu)化，對于在大型數(shù)據(jù)集中進(jìn)行高效的相似檢測和抄襲檢測至關(guān)重要。以下是一些高級技術(shù)和優(yōu)化，以及示例和代碼實現(xiàn)鏈接：

局部敏感哈希（LSH）

位置敏感哈希（LSH）是一種先進(jìn)的技術(shù)，它提高了相似性檢測的疊加和哈希效率。它涉及到創(chuàng)建一個簽名矩陣，并使用多個哈希函數(shù)來降低數(shù)據(jù)的維數(shù)，從而有效地找到類似的文檔。

LSH背后的關(guān)鍵思想是將相似的項目以高概率散列到同一個桶（bucket）中，而不相似的項目散列到不同的桶（bucket）中。這是通過使用一系列LSH來實現(xiàn)的，這些散列函數(shù)將相似的項散列到相同值的概率高于不相似的項。

示例

看以下兩個文件A和B，用一組shingles表示：

• 文件A： {"the quick brown", "quick brown fox", "brown fox jumps"}
• 文件 B： {"a fast brown", "fast brown fox", "brown fox leaps"}

我們可以通過以下方式應(yīng)用LSH：

• 使用多個哈希函數(shù)生成簽名矩陣。
• 使用哈希函數(shù)對每個shingle進(jìn)行哈希，以獲得簽名向量。
• 將特征向量分成頻帶。
• 哈希每個波段以獲得桶密鑰（bucket key）。
• 具有同樣桶密鑰（bucket key）的文檔被認(rèn)為是相似度的潛在候選。

這一過程顯著減少了需要進(jìn)行比較的文檔對的數(shù)量，使相似度檢測更有效。

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

最小哈希是一種通過使用一組散列函數(shù)來快速估計兩個集合之間相似性的技術(shù)。它通常應(yīng)用于大規(guī)模數(shù)據(jù)處理任務(wù)，在這些任務(wù)中，計算集合之間的精確相似性的計算成本是很高的。最小散列近似于集合之間的Jaccard相似性，它測量兩個集合之間的重疊。

以下是最小哈希的工作原理：

生成簽名矩陣

• 給定一組項目，將每個項目表示為一組shingle。
• 構(gòu)造一個簽名矩陣，其中每一行對應(yīng)一個哈希函數(shù)，每一列對應(yīng)一個shingle。
• 將哈希函數(shù)應(yīng)用于集合中的每個shingle，并且對于每個哈希函數(shù)，在矩陣的相應(yīng)行中記錄第一個shingle為1（最小值）的索引。

估計相似性

• 為了估計這兩個集合之間的相似性，請比較它們各自的簽名矩陣。
• 計算簽名一致的位置的數(shù)量（即，兩個集對該哈希函數(shù)具有相同的最小哈希值）。
• 將協(xié)議的計數(shù)除以哈希函數(shù)的總數(shù)來估計Jaccard相似度。

最小哈希允許顯著減少表示集合所需的數(shù)據(jù)量，同時提供它們相似度的良好近似值。

示例：兩個集合

• 集合A= {1、2、3、4、5}
• 集合B = {3、4、5、6、7}

我們可以用shingles來表示這些集合：

• 集合A shingle： {1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5}, {5}
• 集合B shingle：{3, 4}, {4, 5}, {5, 6}, {6, 7}, {3}, {4}, {5}, {6}, {7}

現(xiàn)在，讓我們使用散列生成簽名矩陣：

現(xiàn)在，讓我們估計集合A和B之間的相似性：

• 協(xié)議數(shù)量=2（適用于Shingle 3和Shingle 5）
• 哈希函數(shù)總數(shù)=3
• Jaccard相似度≈2/3≈0.67

代碼實現(xiàn)：你可以使用NumPy和datasketch等庫在Python中實現(xiàn)最小哈希。

Banding 和 Bucketing

Banding和Bucketing是與最小哈希結(jié)合使用的高級優(yōu)化技術(shù)，可有效識別大型數(shù)據(jù)集中的相似集。在處理大量文檔或數(shù)據(jù)點(diǎn)時，這些技術(shù)尤其有價值。

Banding

Banding是將散列簽名矩陣分成多個帶，每個帶包含幾行。通過將矩陣垂直劃分為帶，我們減少了集合之間需要的比較次數(shù)。我們只比較同一頻帶內(nèi)的行，而不是比較整個矩陣中的每對行。這大大減少了計算開銷，特別是對于大型數(shù)據(jù)集，因為我們一次只需要考慮一個子集的行。

Bucketing

Bucketing通過進(jìn)一步縮小每個波段內(nèi)的比較過程來補(bǔ)充波段。在每個帶內(nèi)，我們將行散列到固定數(shù)量的桶（bucket）中。每個桶（bucket）都包含Banding中帶的行子集。在比較集合的相似性時，我們只需要比較每個帶內(nèi)哈希到同一桶（bucket）的集合對。這大大減少了所需的成對比較次數(shù)，使過程更加高效。

示例

假設(shè)我們有一個100行和20個波段的散列（Minhash）簽名矩陣。在每個帶內(nèi)，我們將行散列到10個桶（bucket）中。在比較集合時，不需要比較所有100行，我們只需要比較每個帶（band）內(nèi)散列到同一桶（bucket）的集合對。這大大減少了所需的比較次數(shù)，從而顯著提高了性能，特別是對于大型數(shù)據(jù)集。

收益

• 效率：Banding和Bucketing大大減少了所需的成對比較次數(shù)，使相似性分析在計算上更加高效。
• 可擴(kuò)展性：這些技術(shù)能夠處理由于計算限制而不切實際的大型數(shù)據(jù)集。
• 內(nèi)存優(yōu)化：通過減少比較Banding和Bucketing的次數(shù)，也降低了內(nèi)存需求，使過程更高效。

一些開源軟件提供了shingling、minhashing將LSH與Bucketing結(jié)合的功能，如Python中的datasketch庫和Java中的lsh庫。

候選配對

候選配對是一種高級技術(shù)，與shingling和minhashing結(jié)合使用，可實現(xiàn)高效的抄襲檢測和近乎重復(fù)的識別。在shingling的上下文中，候選配對的工作方式如下：

Shingling

文檔首先被轉(zhuǎn)換成k-shingles集合，k-shingles是從文本中提取的k個標(biāo)記(單詞或字符)的連續(xù)序列。這個步驟將文檔表示為重疊的k-gram集，從而實現(xiàn)相似性比較。

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

然后使用散列技術(shù)將shingles集轉(zhuǎn)換為緊湊的散列簽名，這些簽名是固定長度的向量。散列簽名保持文檔之間的相似性，允許有效地估計Jaccard相似性。

Banding

散列簽名被分成多個波段，每個波段是原始簽名的一個較小的子向量。

Bucketing

在每個帶（band）內(nèi)，使用散列函數(shù)將子向量散列到桶（bucket）中。具有特定頻帶相同散列值的文檔被放置在同一存儲桶（bucket）中。

候選配對生成

如果兩個文檔在所有頻帶上共享至少一個桶（bucket），則將它們視為相似性比較的候選對。換句話說，如果它們的子向量在至少一個頻帶（band）內(nèi)碰撞，它們被認(rèn)為是候選對。

使用候選對的優(yōu)點(diǎn)主要是它大大減少了需要比較相似性的文檔對的數(shù)量，因為只考慮候選對。這使得抄襲檢測過程更加有效，特別是對于大型數(shù)據(jù)集。

通過仔細(xì)選擇頻帶數(shù)和頻帶大小，可以在相似性檢測的準(zhǔn)確性和計算復(fù)雜度之間做出權(quán)衡。頻帶越多，精度越高，但也會增加計算成本。

文檔相似性?

結(jié)論

綜上所述，shingling、minhashing、banding和Locality Sensitive Hashing (LSH)的結(jié)合為大型文檔集合中的抄襲檢測和近重復(fù)識別提供了一種強(qiáng)大而有效的方法。

Shingling將文檔轉(zhuǎn)換為k-shingles集合，k-shingles是k個標(biāo)記(單詞或字符)的連續(xù)序列，支持相似性比較。然后，散列（Minhashing）將這些塊集壓縮成緊湊的簽名，保持文檔之間的相似性。

為了進(jìn)一步提高效率，將散列（Minhashing）簽名分成多個帶，并將每個帶的散列分成桶（bucket），將相似的文檔分組在一起。這個過程生成候選對，候選對是在所有頻帶上共享至少一個桶（bucket）的文檔對，這大大減少了需要比較相似性的文檔對的數(shù)量。

然后只對候選對執(zhí)行實際的相似性計算，使用原始的散列簽名來估計Jaccard相似性。相似度高于特定閾值的配對被認(rèn)為是潛在的抄襲案例或近重復(fù)。

這種方法有幾個優(yōu)點(diǎn)：

• 可伸縮性：通過關(guān)注候選對，計算復(fù)雜性大大降低，使處理大型數(shù)據(jù)集成為可能。
• 準(zhǔn)確性：Shingling和Minhashing即使在內(nèi)容被改寫或重新排序時也能檢測到抄襲，因為它們依賴于重疊的k- shings。
• 靈活性：頻帶（band）數(shù)量和頻帶（band）大小的選擇允許在準(zhǔn)確性和計算復(fù)雜性之間進(jìn)行權(quán)衡，從而實現(xiàn)針對特定用例的優(yōu)化。

一些開源軟件，如Python中的datasketch庫和Java中的lsh庫，提供了shingling、minhashing將LSH與Bucketing結(jié)合的功能，使這些技術(shù)更容易集成到剽竊檢測系統(tǒng)或其他需要高效相似性搜索的應(yīng)用程序中。

總的來說，Shingling、Minhashing、Banding和LSH的結(jié)合為抄襲檢測和近重復(fù)識別提供了一個強(qiáng)大而有效的解決方案，可應(yīng)用于學(xué)術(shù)界、出版和內(nèi)容管理系統(tǒng)。

進(jìn)一步閱讀

• ??文集中的抄襲選擇??
• ??使用datasketch的最小哈希??
• ??chrisjmccormick/MinHash??：Python實現(xiàn)教程
• ??MinHashing - Kaggle??：對散列的全面探索
• ??堆棧溢出討論??：對散列實現(xiàn)的建議

譯者介紹

涂承燁，51CTO社區(qū)編輯，省政府采購專家、省綜合性評標(biāo)專家、公 E 采招標(biāo)采購專家，獲得信息系統(tǒng)項目管理師、信息系統(tǒng)監(jiān)理師、PMP，CSPM-2等認(rèn)證，擁有15年以上的開發(fā)、項目管理、咨詢設(shè)計等經(jīng)驗。對項目管理、前后端開發(fā)、微服務(wù)、架構(gòu)設(shè)計、物聯(lián)網(wǎng)、大數(shù)據(jù)、咨詢設(shè)計等較為關(guān)注。

原文標(biāo)題：??Shingling for Similarity and Plagiarism Detection??，作者：Vidyasagar (Sarath Chandra) Machupalli FBCS