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

# 示例：文檔"我在學習編程"
分詞后：["我", "在", "學習", "編程"]
3-shingles：{"我 在 學習", "在 學習 編程"}

import jieba


def generate_word_shingles(text, k=3):
    """
    生成詞級別的shingles
    """
    # 分詞
    words = list(jieba.cut(text))

    # 生成k個連續(xù)詞的片段
    shingles = set()
    for i in range(len(words) - k + 1):
        shingle = ' '.join(words[i:i + k])
        shingles.add(shingle)

    return shingles


# 示例
text = "我在學習編程"
shingles = generate_word_shingles(text, k=3)
print("3-shingles:", shingles)
# 輸出: {'我 在 學習', '在 學習 編程'}

text1的3-grams集合: {"我在學", "在學習", "學習編", "習編程"}
text2的3-grams集合: {"我現(xiàn)在", "現(xiàn)在學", "在學習", "學習編", "習編程"}

交集 = {"在學習", "學習編", "習編程"} = 3個
并集 = {"我在學", "在學習", "學習編", "習編程", "我現(xiàn)在", "現(xiàn)在學"} = 6個
Jaccard相似度 = 3/6 = 0.5

def generate_char_ngrams(text, n=3):
    """
    生成字符級別的n-grams

    參數(shù)：
    text: 輸入文本
    n: n-gram的大小

    返回：
    set: n-grams集合
    """
    ngrams = set()
    for i in range(len(text) - n + 1):
        ngram = text[i:i + n]
        ngrams.add(ngram)

    return ngrams


# 示例
text1 = "我在學習編程"
text2 = "我現(xiàn)在學習編程"

ngrams1 = generate_char_ngrams(text1, n=3)
ngrams2 = generate_char_ngrams(text2, n=3)

print("text1的3-grams集合:", ngrams1)
print("text2的3-grams集合:", ngrams2)

# 計算Jaccard相似度
intersection = ngrams1.intersection(ngrams2)
union = ngrams1.union(ngrams2)
jaccard_sim = len(intersection) / len(union)

print("交集:", intersection)
print("并集:", union)
print("Jaccard相似度:", jaccard_sim)

P[min(π(A)) = min(π(B))] = J(A,B)

文檔A的shingles: {"我在學", "在學習", "學習編", "習編程"}
文檔B的shingles: {"我現(xiàn)在", "現(xiàn)在學", "在學習", "學習編", "習編程"}

哈希函數(shù)h?:
h?("我在學") = 150
h?("在學習") = 80    ← 兩個文檔的最小值！
h?("學習編") = 200
h?("習編程") = 180
h?("我現(xiàn)在") = 250
h?("現(xiàn)在學") = 300

文檔A的min-hash? = min(150,80,200,180) = 80
文檔B的min-hash? = min(250,300,80,200,180) = 80
結果：相等 

哈希函數(shù)h?:
h?("我在學") = 30    ← 文檔A的最小值！
h?("在學習") = 150
h?("學習編") = 200
h?("習編程") = 180
h?("我現(xiàn)在") = 25    ← 文檔B的最小值！
h?("現(xiàn)在學") = 300

文檔A的min-hash? = 30
文檔B的min-hash? = 25
結果：不相等 

哈希函數(shù)h?:
h?("我在學") = 400
h?("在學習") = 250
h?("學習編") = 50    ← 兩個文檔的最小值！
h?("習編程") = 150
h?("我現(xiàn)在") = 300
h?("現(xiàn)在學") = 350

文檔A的min-hash? = 50
文檔B的min-hash? = 50
結果：相等 

import hashlib


def hash_shingle(shingle, hash_func_num):
    """
    對shingle進行哈希
    """
    # 使用不同的哈希函數(shù)模擬隨機排列
    # 使用不同的鹽值來模擬不同的哈希函數(shù)
    salt = f"salt_{hash_func_num}"
    data = (shingle + salt).encode('utf-8')

    # 使用MD5哈希并轉換為整數(shù)
    hash_hex = hashlib.md5(data).hexdigest()
    hash_int = int(hash_hex, 16) % (10 ** 6)  # 取模得到合適大小的整數(shù)

    return hash_int


def calculate_minhash(shingles_set, num_hash_funcs=3):
    """
    計算文檔的最小哈希簽名
    """
    # 初始化最小哈希值為無窮大
    minhash_signature = [float('inf')] * num_hash_funcs

    for shingle in shingles_set:
        for i in range(num_hash_funcs):
            hash_value = hash_shingle(shingle, i)
            if hash_value < minhash_signature[i]:
                minhash_signature[i] = hash_value

    return minhash_signature


# 文檔A和B的shingles（使用字符級別的3-grams）
docA_shingles = {"我在學", "在學習", "學習編", "習編程"}
docB_shingles = {"我現(xiàn)在", "現(xiàn)在學", "在學習", "學習編", "習編程"}

# 計算最小哈希簽名
minhash_A = calculate_minhash(docA_shingles, num_hash_funcs=300)
minhash_B = calculate_minhash(docB_shingles, num_hash_funcs=300)

print("文檔A的300維哈希簽名:", minhash_A)
print("文檔B的300維哈希簽名:", minhash_B)


# 計算簽名相似度
def signature_similarity(sigA, sigB):
    """計算兩個簽名的Jaccard相似度估計值"""
    matches = sum(1 for a, b in zip(sigA, sigB) if a == b)
    return matches / len(sigA)


similarity = signature_similarity(minhash_A, minhash_B)
print("簽名相似度估計值:", similarity)

文檔A的3維哈希簽名: [80, 30, 50]
文檔B的3維哈希簽名: [80, 25, 50]

def signature_similarity(sigA, sigB):
    """計算兩個簽名的Jaccard相似度估計值"""
    matches = sum(1 for a, b in zip(sigA, sigB) if a == b)
    return matches / len(sigA)

# 示例
similarity = signature_similarity([80, 30, 50], [80, 25, 50])
# 2/3 ≈ 0.667（接近真實值0.5）

import math


def confidence_interval(n, s=0.5):
    """計算95%置信區(qū)間"""
    std = math.sqrt(s * (1 - s) / n)
    margin = 1.96 * std
    return [max(0, s - margin), min(1, s + margin)]


print(confidence_interval(1, s=0.5))
print(confidence_interval(10, s=0.5))
print(confidence_interval(100, s=0.5))
print(confidence_interval(500, s=0.5))
print(confidence_interval(1000, s=0.5))

[0, 1]
[0.19009678930349883, 0.8099032106965012]
[0.402, 0.598]
[0.4561730676410041, 0.5438269323589959]
[0.4690096789303499, 0.5309903210696502]

假設120維原始簽名：
[123, 456, 789, 321, 654, 987, ..., 888]

以切成20個片為例（每片6維）：
片 1: [123, 456, 789, ..., ...] 
片 2: [..., ..., ..., ..., ...] 
...
片 20: [..., ..., ..., ..., 888] 

片 1: = hash(tuple(band1))  # 如 0x1a2b3c
片 2: = hash(tuple(band2))  # 如 0x4d5e6f
片 3: = hash(tuple(band3))  # 如 0x7a8b9c  
片 4: = hash(tuple(band4))  # 如 0xd1e2f3

def lsh_probability(s, r=6, b=20):
    """計算LSH匹配概率"""
    prob_one_band = s ** r          # 單個band匹配的概率
    prob_at_least_one = 1 - (1 - prob_one_band) ** b
    return prob_at_least_one

# 示例：相似度0.8的文檔
prob = lsh_probability(0.8, 6, 20)  # ≈ 0.9940
# 99.4%的概率會被LSH放到同一個桶中