譯者 | 涂承燁

審校 | 重樓

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

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

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

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

一、 理解Shingling的概念

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

讓我們舉個例子：“Generative AI is evolving rapidly.”。我們用k表示Shingle 的長度，并將k的值設為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是三步驟過程的一部分。

標記化

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

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

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

Shingling

正如現(xiàn)在所知的，Shingling，也被稱為n-gramming，是從標記文本中創(chuàng)建一組連續(xù)的標記序列（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）。哈希支持對類似的文本段進行高效的比較、索引和檢索。當你將文檔轉(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應為：

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

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

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

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

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

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

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

讓我們計算兩個句子之間的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%。

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

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

局部敏感哈希（LSH）

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

LSH背后的關鍵思想是將相似的項目以高概率散列到同一個桶（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"}

我們可以通過以下方式應用LSH：

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

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

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

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

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

生成簽名矩陣

• 給定一組項目，將每個項目表示為一組shingle。
• 構造一個簽名矩陣，其中每一行對應一個哈希函數(shù)，每一列對應一個shingle。
• 將哈希函數(shù)應用于集合中的每個shingle，并且對于每個哈希函數(shù)，在矩陣的相應行中記錄第一個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ù)據(jù)集中的相似集。在處理大量文檔或數(shù)據(jù)點時，這些技術尤其有價值。

Banding

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

Bucketing

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

示例

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

收益

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

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

候選配對

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

Shingling

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

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

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

Banding

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

Bucketing

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

候選配對生成

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

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

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

文檔相似性

結(jié)論

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

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

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

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

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

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

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

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

進一步閱讀

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

譯者介紹

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

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