譯者 | 涂承燁

審校 | 重樓

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

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

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

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

一、 理解Shingling的概念

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

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

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

{'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的長(zhǎng)度根據(jù)分析的具體要求而不同，常見的做法是創(chuàng)建包含三到五個(gè)單詞或字符的shingles。

二、 探索Shingling的基本知識(shí)

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', '.']

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

Shingling

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

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

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

哈希（Hashing）

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

簡(jiǎn)單的Shingling

讓我們看看兩個(gè)被廣泛用于解釋簡(jiǎn)單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.']]

對(duì)于第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組，你可以看到前四個(gè)shingles是相同的，這表明了兩個(gè)短文之間的高度相似性。

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

三、 Jaccard相似性：測(cè)量文本相似性

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

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

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

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

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

讓我們計(jì)算兩個(gè)句子之間的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）=兩個(gè)集合中的公共數(shù)= {1,6} = 2

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

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

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

要計(jì)算差異，只需從1中減去這個(gè)相似度的值。

1- 0.25 = 0.75

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

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

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

局部敏感哈希（LSH）

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

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

示例

看以下兩個(gè)文件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：

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

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

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

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

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

生成簽名矩陣

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

估計(jì)相似性

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

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

示例：兩個(gè)集合

• 集合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)在，讓我們估計(jì)集合A和B之間的相似性：

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

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

Banding 和 Bucketing

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

Banding

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

Bucketing

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

示例

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

收益

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

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

候選配對(duì)

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

Shingling

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

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

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

Banding

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

Bucketing

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

候選配對(duì)生成

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

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

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

文檔相似性

結(jié)論

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

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

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

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

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

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

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

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

進(jìn)一步閱讀

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

譯者介紹

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

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