LSH算法:高效相似性搜索的原理与Python实现I
局部敏感哈希(LSH)技术是快速近似最近邻(ANN)搜索中的一个关键方法,广泛应用于实现高效且准确的相似性搜索。这项技术对于许多全球知名的大型科技公司来说是不可或缺的,包括谷歌、Netflix、亚马逊、Spotify和Uber等。
亚马逊通过分析用户间的相似性,依据购买历史向用户推荐新产品。谷歌在用户进行搜索时,实际上是在执行一次相似性搜索,评估搜索词与谷歌索引的互联网内容之间的相似度。而Spotify之所以能够推荐符合用户口味的音乐,是因为它成功地通过相似性搜索算法将用户与品味相似的其他用户进行了匹配。
LSH技术的优势在于它能够在保证搜索速度的同时,提供高质量的搜索结果。这对于处理大规模数据集和实现实时搜索功能至关重要。在本文中,我们将深入探讨LSH算法背后的理论基础,并提供一个易于理解的Python实现示例,帮助读者更好地掌握这一技术。
搜索的复杂性
在处理包含数百万甚至数十亿条数据的数据集时,如何高效地进行样本间比较成为一个巨大挑战。
尝试逐一比较所有样本对是不切实际的,即便在最先进的硬件上。这种方法的时间复杂度为 O ( n 2 ) O(n^2) O(n2),意味着随着数据量的增加,所需的时间和资源将以平方级速度增长。即便是将单个查询与数十亿个样本进行比较,其复杂度也达到 O ( n ) O(n) O(n),这给大型数据集带来了巨大的计算负担。
此外,每个样本通常以高维向量的形式存储,这进一步加剧了计算的复杂性。高维空间中的相似性计算不仅成本高昂,而且效率低下。
面对这些挑战,一个自然的问题是:是否存在一种方法能够实现亚线性复杂度的搜索,即搜索时间不随数据量的线性增长而增长?答案是肯定的。
解决这一问题的关键在于采用近似搜索策略。不必对每个向量进行详尽的比较,而是可以通过近似方法缩小搜索范围,只关注那些最可能相关的向量。
局部敏感哈希(LSH)算法就是这样一种能够提供亚线性搜索时间的技术。它通过将相似的项映射到同一个“桶”或“哈希表”位置,从而快速识别出潜在的最近邻。在本文中,将详细介绍LSH算法,并深入探讨其背后的工作原理。
局部敏感哈希(Locality Sensitive Hashing)
在面对寻找相似向量对的计算复杂性问题时,即便是规模较小的数据集,其所需的计算量也可能变得难以处理。
考虑向量索引的场景,如果要为一个新向量找到一个最接近的匹配,就需要将它与数据库中的所有其他向量进行比较。这种方法的时间复杂度是线性的,这在大型数据集上意味着无法快速完成搜索。
理想情况下,我们只希望比较那些可能匹配的向量,也就是潜在的候选对。为了减少必要的比较次数,局部敏感哈希(LSH)算法应运而生。LSH是一种能够将相似项映射到同一个哈希桶中的技术。它包括多种不同的方法,本文将介绍一种传统方法,包括以下步骤:
- 文档分片(Shingling):将文档分割成多个片段。
- MinHashing:一种用于估计集合相似度的概率算法。
- 带状LSH函数(Banding):最终的LSH函数,用于将向量分割和哈希。
LSH算法的核心在于,当至少一次哈希操作导致两个向量映射到相同的值时,这两个向量就被认为是候选对,即可能是匹配的。
这个过程类似于Python字典中的哈希过程,其中键通过哈希函数处理并映射到特定的桶中,然后将相应的值与这个桶关联起来。
典型的哈希函数:旨在将不同的值(无论多么相似)放入不同的桶中
然而,LSH中使用的哈希函数与传统字典中的哈希函数有一个重要的区别:
在字典中,目标是尽量减少多个键映射到同一个桶的情况,以降低冲突。而LSH的理念恰恰相反,它希望最大化冲突,但这种冲突理想情况下只发生在相似的输入上。
LSH的哈希函数:目标是将相似的值放入同一个桶中
LSH中的哈希方法并不是唯一的。尽管它们都遵循通过哈希函数将相似样本放入同一个桶的基本逻辑,但它们在具体实现上可以有很大的差异。在本文中介绍的是传统方法,它包括文档分片(shingling),MinHashing和带状划分(banding)这几个步骤。
Shingling, MinHashing, LSH
局部敏感哈希(LSH)方法涵盖了三个关键步骤,用于高效地识别大规模数据集中的相似项。
- 首先使用k-shingling将文本转换为稀疏向量
- 然后通过MinHashing创建“签名”
- 最后利用LSH过程筛选出候选对
本文将详细介绍这一流程
k-Shingling:文本到shingles的转换
k-Shingling 是一种将文本字符串转换为一组“shingles”(片段)的方法。这个过程类似于在文本上滑动一个长度为k的窗口,并在每一步记录下窗口内的内容。通过这种方法,可以得到文本的shingles集合。
在Python中,可以创建一个简单的k-shingling函数,如下所示:
a = "flying fish flew by the space station"
b = "we will not allow you to bring your pet armadillo along"
c = "he figured a few sticks of dynamite were easier than a fishing pole to catch fish"def shingle(text: str, k: int=2):shingle_set = []for i in range(len(text) - k+1):shingle_set.append(text[i:i+k])return set(shingle_set)a = shingle(a, k)
b = shingle(b, k)
c = shingle(c, k)
print(a)# {'y ', 'pa', 'ng', 'yi', 'st', 'sp', 'ew', 'ce', 'th', 'sh', 'fe', 'e ', 'ta', 'fl', ' b', 'in', 'w ', ' s', ' t', 'he', ' f', 'ti', 'fi', 'is', 'on', 'ly', 'g ', 'at', 'by', 'h ', 'ac', 'io'}
有了的shingles后创建稀疏向量,需要将所有集合合并为一个包含所有集合中所有shingles的大集合词汇表(或vocab)。
所有 shingle 集合合并后,创建了词汇表(vocab)。
使用这个词汇表,为每个集合创建稀疏向量。具体来说,在词汇表长度上创建一个全零向量,然后检查哪些 shingle 出现在集合中,将相应位置的值设为 1。
为了创建 one-hot 编码,将单个 shingle 集与词汇表匹配,确定在零向量中应该放置 1 的位置。 对于每个出现的 shingle,找到它在词汇表中的位置,并将对应的零向量位置设置为 1,这就是one-hot 编码的方式。
Minhashing
MinHashing签名是通过将稀疏向量转换为密集的数值向量来创建的。这个过程涉及到以下几个关键步骤:
- 生成随机排列的计数向量:首先,创建一个从1到词汇表长度的计数向量,并对其进行随机排列。这个排列的向量将用于后续的MinHashing计算。
- 对齐稀疏向量中的1:接着,对于稀疏向量中的每个1,需要找到与之对齐的最小排列数字。这个数字将作为签名中的一个值。
通过一个具体的例子来说明这个过程:
- 假设有一个较小的词汇表,包含6个值,这有助于可视化MinHashing的过程。
- 从词汇表中随机排列计数向量,例如:
[5, 1, 3, 2, 4, 6]
。 - 然后,检查稀疏向量中的每个位置,看是否存在对应的shingle。如果存在,对应的稀疏向量值为1;如果不存在,则为0。
在这里,使用四个 minhash 函数/向量来创建一个四位数的签名向量。如果你在每个 minhash 函数中从 1 开始计数,并找出与稀疏向量中的 1 对齐的第一个值——你会得到 2412。通过这种方式,可以为稀疏向量中的每个1生成一个MinHash值。为了创建完整的MinHash签名,需要为签名中的每个位置分配一个不同的MinHash函数,并重复上述过程多次。下面用代码实现它。有三个步骤:
- 生成一个随机化的minhash向量
vocab = a.union(b).union(c)
hash_ex = list(range(1, len(vocab)+1))from random import shuffleshuffle(hash_ex)
- 遍历这个随机的 MinHash 向量(从 1 开始),将每个值的索引与稀疏向量 a_1hot 中的等效值进行匹配。如果找到 1,该索引就是签名值。
a_1hot = [1 if i in a else 0 for i in vocab]
b_1hot = [1 if i in b else 0 for i in vocab]
c_1hot = [1 if i in c else 0 for i in vocab]
print(f"7 -> {hash_ex.index(7)}")for i in range(1, 5):print(f"{i} -> {hash_ex.index(i)}")for i in range(1, len(vocab)+1):idx = hash_ex.index(i)signature_val = a_1hot[idx]print(f"{i} -> {idx} -> {signature_val}")if signature_val == 1:print('match!')break
1 -> 58 -> 0
2 -> 19 -> 0
3 -> 96 -> 0
4 -> 92 -> 0
5 -> 83 -> 0
6 -> 98 -> 1
match!
- 通过多次迭代构建签名
def create_hash_func(size: int):# 创建哈希向量/函数hash_ex = list(range(1, len(vocab)+1))shuffle(hash_ex)return hash_exdef build_minhash_func(vocab_size: int, nbits: int):# 创建多个minhash向量hashes = []for _ in range(nbits):hashes.append(create_hash_func(vocab_size))return hashes# 创建20个minhash向量
minhash_func = build_minhash_func(len(vocab), 20)def create_hash(vector: list):# 用于创建签名的函数signature = []for func in minhash_func:for i in range(1, len(vocab)+1):idx = func.index(i)signature_val = vector[idx]if signature_val == 1:signature.append(idx)breakreturn signature# 创建签名
b_1hot = [1 if i in b else 0 for i in vocab]
c_1hot = [1 if i in c else 0 for i in vocab]a_sig = create_hash(a_1hot)
b_sig = create_hash(b_1hot)
c_sig = create_hash(c_1hot)print(a_sig)
print(b_sig)
# [70, 19, 84, 88, 112, 46, 54, 75, 68, 15, 15, 85, 94, 93, 51, 29, 75, 68, 110, 108]
# [62, 14, 106, 80, 57, 114, 62, 12, 127, 39, 121, 104, 14, 23, 2, 127, 12, 33, 45, 45]
MinHashing的原理并不复杂,通过上述步骤已经将稀疏向量压缩成一个包含 20 个数字的密集签名。
从稀疏向量到签名的信息传递
一个关键问题是,当我们从原始的稀疏向量转换到MinHash签名时,是否保留了足够的信息以进行有效的相似性比较。为了验证这一点,我们可以计算原始向量和签名向量之间的Jaccard相似性。Jaccard 相似性是通过比较两个集合的交集与并集的大小来衡量它们之间的相似度的指标。可以首先使用原始的shingle集合来计算Jaccard相似性,然后对相应的MinHash签名进行相同的计算。
def jaccard(a: set, b: set):return len(a.intersection(b)) / len(a.union(b))print(jaccard(a, b), jaccard(set(a_sig), set(b_sig)))
# 0.02531645569620253, 0.0print(jaccard(a, c), jaccard(set(a_sig), set(c_sig)))
# 0.10309278350515463, 0.030303030303030304print(jaccard(b, c), jaccard(set(b_sig), set(c_sig)))
# 0.043478260869565216, 0.03225806451612903
通过比较原始shingle集合和MinHash签名集合的Jaccard相似性,可以评估信息在转换过程中的保留程度。如果签名集合的相似性与原始集合的相似性相近,则表明MinHash签名有效地保留了原始稀疏向量中的相似性信息。
带状划分和哈希
在局部敏感哈希(LSH)的最后阶段,采用带状划分的方法来处理签名向量。这种方法将签名划分为多个片段,并对每个片段进行哈希处理,以寻找哈希冲突。
带状划分通过将向量分割成称为“带”的子部分来解决直接哈希整个向量可能带来的问题。这种方法允许识别向量之间的匹配子向量,即使整个向量并不完全相同。
直接对整个向量进行哈希可能难以构建能准确识别它们相似性的哈希函数。不需要整个向量相等,只需要部分相似即可。带状划分提供了一种灵活的条件——只要有任何两个子向量碰撞,就将相应的全向量视为候选对。
带状划分的工作原理
带状方法通过将向量分割成称为带(b)的子部分来解决这个问题,然后将每个子向量通过哈希函数处理。
假设将一个100维的向量分成20个带,这提供了20次机会来识别向量之间的匹配子向量。每个子向量通过哈希函数处理并映射到一个哈希桶中。
将签名分割成b个子向量,每个子向量通过哈希函数处理并映射到一个哈希桶中,只要有任何两个子向量碰撞,就将相应的全向量视为候选对。
所有签名中的等效子向量必须通过相同的哈希函数处理,可以为所有子向量使用一个哈希函数。
可以用Python实现一个简单的版本。首先,从分割签名向量a, b, 和c开始:
def split_vector(signature, b):assert len(signature) % b == 0r = int(len(signature) / b)# code splitting signature in b partssubvecs = []for i in range(0, len(signature), r):subvecs.append(signature[i : i+r])return subvecsband_a = split_vector(a_sig, 10)
band_b = split_vector(b_sig, 10)
band_c = split_vector(c_sig, 10)
print(band_c)
[[30, 60],[84, 125],[135, 90],[130, 107],[76, 16],[44, 119],[109, 135],[30, 76],[95, 33],[41, 32]]
然后循环遍历列表来识别子向量之间的匹配。如果找到匹配项,会将这些向量作为候选对。
for b_rows, c_rows in zip(band_b, band_c):if b_rows == c_rows:print(f"Candidate pair: {b_rows} == {c_rows}")breakfor a_rows, b_rows in zip(band_a, band_b):if a_rows == b_rows:print(f"Candidate pair: {a_rows} == {b_rows}")breakfor a_rows, c_rows in zip(band_a, band_c):if a_rows == c_rows:print(f"Candidate pair: {b_rows} == {c_rows}")break
测试LSH
目前构建的实现非常低效。如果要实现LSH,应该使用专为相似性搜索设计的库,比如Faiss等。
尽管如此,通过编写代码的方式可以更清楚地了解LSH的工作原理。接下来,将使用更多的数据来重复这个过程,并使用NumPy重写代码。
获取数据
首先,需要获取数据。
import requests
import pandas as pd
import iourl = "https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/sick2014/SICK_train.txt"text = requests.get(url).textdata = pd.read_csv(io.StringIO(text), sep='\t')
data.head()def build_shingles(sentence: str, k: int):shingles = []for i in range(len(sentence) - k):shingles.append(sentence[i:i+k])return set(shingles)def build_vocab(shingle_sets: list):# convert list of shingle sets into single setfull_set = {item for set_ in shingle_sets for item in set_}vocab = {}for i, shingle in enumerate(list(full_set)):vocab[shingle] = ireturn vocabdef one_hot(shingles: set, vocab: dict):vec = np.zeros(len(vocab))for shingle in shingles:idx = vocab[shingle]vec[idx] = 1return veck = 8 # shingle size# build shingles
shingles = []
for sentence in sentences:shingles.append(build_shingles(sentence, k))# build vocab
vocab = build_vocab(shingles)# one-hot encode our shingles
shingles_1hot = []
for shingle_set in shingles:shingles_1hot.append(one_hot(shingle_set, vocab))
# stack into single numpy array
shingles_1hot = np.stack(shingles_1hot)
shingles_1hot.shape
# (4500, 36466)
转换成独热编码, shingles_1hot
数组包含500个稀疏向量,其中每个向量的长度为词汇表的大小。
MinHashing
接下来,使用minhashing将稀疏向量压缩为密集向量“签名”。
def minhash_arr(vocab: dict, resolution: int):length = len(vocab.keys())arr = np.zeros((resolution, length))for i in range(resolution):permutation = np.random.permutation(len(vocab)) + 1arr[i, :] = permutation.copy()return arr.astype(int)def get_signature(minhash, vector):# get index locations of every 1 value in vectoridx = np.nonzero(vector)[0].tolist()# use index locations to pull only +ve positions in minhashshingles = minhash[:, idx]# find minimum value in each hash vectorsignature = np.min(shingles, axis=1)return signaturearr = minhash_arr(vocab, 100)signatures = []for vector in shingles_1hot:signatures.append(get_signature(arr, vector))# merge signatures into single array
signatures = np.stack(signatures)
signatures.shape
# (4500, 100)
将稀疏向量从长度缩短到长度为100的签名,尽管这种压缩是大幅度的,但它很好地保留了相似性信息。
LSH
在这里使用 Python 字典来散列并存储候选对:
from itertools import combinationsclass LSH:buckets = []counter = 0def __init__(self, b):self.b = bfor i in range(b):self.buckets.append({})def make_subvecs(self, signature):l = len(signature)assert l % self.b == 0r = int(l / self.b)# break signature into subvectorssubvecs = []for i in range(0, l, r):subvecs.append(signature[i:i+r])return np.stack(subvecs)def add_hash(self, signature):subvecs = self.make_subvecs(signature).astype(str)for i, subvec in enumerate(subvecs):subvec = ','.join(subvec)if subvec not in self.buckets[i].keys():self.buckets[i][subvec] = []self.buckets[i][subvec].append(self.counter)self.counter += 1def check_candidates(self):candidates = []for bucket_band in self.buckets:keys = bucket_band.keys()for bucket in keys:hits = bucket_band[bucket]if len(hits) > 1:candidates.extend(combinations(hits, 2))return set(candidates)b = 20lsh = LSH(b)for signature in signatures:lsh.add_hash(signature)
lsh.buckets
为每个带包含一个单独的字典,不同带之间不会混合存储桶。在存储桶中存储向量 ID(行号),因此提取候选对时,只需遍历所有存储桶并提取对。
candidate_pairs = lsh.check_candidates()
len(candidate_pairs)
# 7327list(candidate_pairs)[:5]
# [(1063, 1582), (112, 1503), (114, 2393), (2685, 2686), (3197, 3198)]
识别出候选对后,将仅对这些对进行相似性计算,发现有些对会落在相似性阈值内,而其他的则不会。
目标是缩小搜索范围并降低复杂度,同时保持高准确性。可以通过测量候选对分类(1或0)与实际余弦(或杰卡德)相似性来可视化性能。
图表显示了候选对(1)和非候选对(0)相对于成对签名的余弦相似性的分布
优化波段值
在局部敏感哈希(LSH)中,波段值b
是一个关键参数,它决定了相似性阈值,即LSH函数将数据点从非候选对转换为候选对的界限。通过调整b
,可以改变LSH函数的敏感度,从而影响搜索结果的质量和召回率。
可以通过以下公式来形式化概率与相似性之间的关系:
其中,s
表示相似性得分,b
表示波段数量,r
表示每个波段中的行数。这个公式帮助我们理解在给定的b
和r
值下,一对数据点被识别为候选对的概率。
通过可视化概率-相似性关系,可以观察到一个明显的模式:
- 候选分类(左侧y轴)和计算出的概率P(右侧y轴)相对于相似性(计算出的或归一化的余弦相似性)。
- 在
b
和r
值分别为20和5的情况下,可以看到计算出的概率P和相似性s值指示了候选/非候选对的一般分布
尽管理论计算出的概率与真正的候选对结果之间存在相关性,但对齐并不完美。通过修改b
值,可以推动在不同相似性得分下返回候选对的概率向左或向右移动。
计算出的概率P相对于不同b值的相似性s。r是len(signature) / b(在这种情况下len(signature) == 100)。
例如,如果发现当b == 20
时,需要较高的相似性才能将对计算为候选对,可以尝试增加b
值以降低相似性阈值。当b
值调整为25时,可以观察到以下变化:
当b == 25时,真实结果和模拟结果分别用蓝色和洋红色显示。与之前的LSH结果相比,增加
b
值导致产生了更多的候选对
由于返回了更多的候选对,这会在不相似的向量上产生更多误报。可以将其可视化为:
增加
b
值会自然地导致更多的候选对被返回,这可能会增加误报(FP)的数量,同时减少漏报(FN)
通过从头开始构建LSH流程并调整相似性阈值,能够优化搜索结果的质量和召回率。本文不仅介绍了LSH的基本原理,还涵盖了分片(shingling)和MinHash函数的概念。在实际应用中,我们可能会倾向于使用专门为相似性搜索设计的库来实现LSH,以提高效率和准确性。
总结
本文介绍了局部敏感哈希(LSH)技术,这是一种在相似性搜索中实现快速且准确搜索的关键技术。LSH被广泛应用于谷歌、Netflix等大型科技公司。文章详细探讨了LSH的工作原理,包括shingling、MinHashing以及带状划分和哈希等步骤。通过这些技术,LSH能够在保持搜索速度的同时,提供高质量的搜索结果。最后,通过Python示例展示了LSH的实现过程,并讨论了如何通过调整波段值来优化LSH函数的相似性阈值。
参考
- https://youtu.be/e_SBq3s20M8
- locality-sensitive-hashing
- jupyter notebook
- Mining of Massive Datasets
相关文章:
![](https://img-blog.csdnimg.cn/img_convert/131640b5b4bb7a2ce5e46489df83fbfd.png)
LSH算法:高效相似性搜索的原理与Python实现I
局部敏感哈希(LSH)技术是快速近似最近邻(ANN)搜索中的一个关键方法,广泛应用于实现高效且准确的相似性搜索。这项技术对于许多全球知名的大型科技公司来说是不可或缺的,包括谷歌、Netflix、亚马逊、Spotify…...
![](https://img-blog.csdnimg.cn/direct/266f5456cd844e768a5a4001fd6dde6d.gif#pic_center)
cesium 添加 Echarts图层(人口迁徒图)
cesium 添加 Echarts 人口迁徒图(下面附有源码) 1、实现思路 1、在scene上面新增一个canvas画布 2、通坐标转换,将经纬度坐标转为屏幕坐标来实现 3、将ecarts 中每个series数组中元素都加 coordinateSystem: ‘cesiumEcharts’ 2、示例代码 <!DOCTYPE html> <ht…...
![](https://img-blog.csdnimg.cn/direct/959099e639fc48d0b97515e076958a27.png)
Windows下快速安装Open3D-0.18.0(python版本)详细教程
目录 一、Open3D简介 1.1主要用途 1.2应用领域 二、安装Open3D 2.1 激活环境 2.2 安装open3d 2.3测试安装是否成功 三、测试代码 3.1 代码 3.2 显示效果 一、Open3D简介 Open3D 是一个强大的开源库,专门用于处理和可视化3D数据,如点云、网格和…...
![](https://img-blog.csdnimg.cn/direct/2e160d30d1f04adebb2412b34432e7d3.png)
无法下载 https://mirrors./ubuntu/dists/bionic/main/binary-arm64/Packages
ubuntu系统执行sudo apt update命令的时候,遇到如下问题: 忽略:82 https://mirrors.tuna.tsinghua.edu.cn/ubuntu bionic-backports/universe arm64 Packages 错误:81 https://mirrors.tuna.tsinghua.edu.cn/ubuntu bionic-backports/main arm64 Packa…...
![](https://img-blog.csdnimg.cn/img_convert/9d86b5b356622acf0021f271bb490640.jpeg)
最新CRMEB商城多商户java版源码v1.6版本+前端uniapp
CRMEB 开源商城系统Java版,基于JavaVueUni-app开发,在微信公众号、小程序、H5移动端都能使用,代码全开源无加密,独立部署,二开很方便,还支持免费商用,能满足企业新零售、分销推广、拼团、砍价、…...
![](https://img-blog.csdnimg.cn/direct/bfeda55b9a65410f93641ef7232bc014.png)
【开发环境】MacBook M2安装git并拉取gitlab项目,解决gitlab出现Access Token使用无效的方法
文章目录 安装Homebrew安装git打开IDEA配置git打开IDEA拉取项目 安装Homebrew /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"在iTerm等命令行工具打开后,输入上面的命令 之后根据中文提示完成Homebrew的下载…...
![](https://www.ngui.cc/images/no-images.jpg)
Flask-Session使用Redis
Flask-Session使用Redis 一、介绍 在Flask中,session数据默认是以加密的cookie形式存储在用户的浏览器中的。但是,真正的session数据应该存储在服务器端。Django框架会将session数据存储在数据库的djangosession表中,而Flask则可以通过第三…...
![](https://img-blog.csdnimg.cn/direct/986481f3a5904cee9caf7d4b70b24d5a.png)
Redis缓存管理机制
在当今快节奏的数字世界中,性能优化对于提供无缝的用户体验至关重要。缓存在提高应用程序性能方面发挥着至关重要的作用,它通过将经常使用或处理的数据存储在临时高速存储中来减少数据库负载并缩短响应时间,从而减少系统的延迟。Redis 是一种…...
![](https://img-blog.csdnimg.cn/img_convert/d6b4dff8aa80c9dae397f5375362f4c8.jpeg)
初学嵌入式是弄linux还是单片机?
在开始前刚好我有一些资料,是我根据网友给的问题精心整理了一份「单片机的资料从专业入门到高级教程」, 点个关注在评论区回复“666”之后私信回复“666”,全部无偿共享给大家!!!1、先入门了51先学了89c52…...
![](https://img-blog.csdnimg.cn/direct/3f5c17f309b14ef6a3c9bde7f77eb9c0.png)
【基础算法总结】分治—快排
分治—快排 1.分治2.颜色分类3.排序数组4.数组中的第K个最大元素5.库存管理 III 点赞👍👍收藏🌟🌟关注💖💖 你的支持是对我最大的鼓励,我们一起努力吧!😃😃 1.分治 分治…...
![](https://img-blog.csdnimg.cn/direct/aeb54ccef61d4748a73264d678e001fc.png)
[C++]——同步异步日志系统(1)
同步异步日志系统 一、项⽬介绍二、开发环境三、核心技术四、环境搭建五、日志系统介绍5.1 为什么需要日志系统5.2 日志系统技术实现5.2.1 同步写日志5.2.2 异步写日志 日志系统: 日志:程序在运行过程中,用来记录程序运行状态信息。 作用&…...
![](https://img-blog.csdnimg.cn/direct/0f52b6c064a0455aae3dc3b968e798d9.png)
python 第6册 辅助excel 002 批量创建非空白的 Excel 文件
---用教授的方式学习 此案例主要通过使用 while 循环以及 openpyxl. load_workbook()方法和 Workbook 的 save()方法,从而实现在当前目录中根据已经存在的Excel 文件批量创建多个非空白的Excel 文件。当运行此案例的Python 代码(A002.py 文件࿰…...
![](https://img-blog.csdnimg.cn/direct/c42ce07803b94de6a3cbee66b39ac939.png)
力扣61. 旋转链表(java)
思路:用快慢指针找到最后链表k个需要移动的节点,然后中间断开节点,原尾节点连接原头节点,返回新的节点即可; 但因为k可能比节点数大,所以需要先统计节点个数,再取模,看看k到底需要移…...
![](https://img-blog.csdnimg.cn/img_convert/fd3a750aa75663142f61a9197ed9ac79.jpeg)
智慧园区综合平台解决方案PPT(75页)
## 智慧园区的理解 ### 从园区1.0到园区4.0的演进 1. 园区1.0:以土地经营为主,成本驱动,提供基本服务。 2. 园区2.0:服务驱动,关注企业成长,提供增值服务。 3. 园区3.0:智慧型园区ÿ…...
![](https://www.ngui.cc/images/no-images.jpg)
Python只读取Excel文件的一部分数据,比如特定范围的行和列?
如何只读取Excel文件的一部分数据,比如特定范围的行和列? 在Python中,如果你只想读取Excel文件的特定范围,可以使用以下方法: pandas: Pandas是一个强大的数据处理库,它有一个内置函数read_excel()用于读…...
![](https://img-blog.csdnimg.cn/direct/3be68d22a2f64f99b1336249241eb78f.png)
快速入门FreeRTOS心得(正点原子学习版)
对于FreeROTS,我第一反应想到的就是通信里的TDM(时分多址)。不同任务给予分配不同的时间间隔,也就是任务之间在每个timeslot都在来回切换。 这里有重要的一点,就是中断要短小,优先级是自高到底进行打断。 …...
![](https://img-blog.csdnimg.cn/direct/e82d4f1cd63841b096def2d887fdf384.gif?#pic_center)
【博主推荐】HTML5实现简洁好看的个人简历网页模板源码
文章目录 1.设计来源1.1 主界面1.2 关于我界面1.3 工作经验界面1.4 学习教育界面1.5 个人技能界面1.6 专业特长界面1.7 朋友评价界面1.8 获奖情况界面1.9 联系我界面 2.效果和源码2.1 动态效果2.2 源代码 源码下载万套模板,程序开发,在线开发,…...
![](https://www.ngui.cc/images/no-images.jpg)
Android应用安装过程
Android 系统源码源码-应用安装过程 Android 中应用安装的过程就是解析 AndroidManifest.xml 的过程,系统可以从 Manifest 中得到应用程序的相关信息,比如 Activity、Service、Broadcast Receiver 和 ContentProvider 等。这些工作都是由 PackageManage…...
![](https://www.ngui.cc/images/no-images.jpg)
Word中输入文字时,后面的文字消失
当在Word中输入文字时,如果发现后面的文字消失,通常是由以下3个原因造成的: 检查Insert键状态:首先确认是否误按了Insert键。如果是,请再次按下Insert键以切换回插入模式。在插入模式下,新输入的文字会插入…...
![](https://www.ngui.cc/images/no-images.jpg)
【LeetCode】合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解题思路 水题,主要用于后面的链表的归并排序做了该题 AC代码 # Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nex…...
![](https://www.ngui.cc/images/no-images.jpg)
分子AI预测赛Task1笔记
分子AI预测赛Task1笔记 实践步骤:跑通baseline → 尝试个人idea→尝试进阶baseline 一、跑通baseline 1、应当先下载数据库 下载相应的数据库 !pip install lightgbm openpyxl2、训练模型并预测结果 首先要导入相应的库和方法类,如pandas等 # 1. …...
![](https://img-blog.csdnimg.cn/direct/6a0642286227400b9e147528dad8f4ca.png)
ubuntu 安装并启用 samba
环境:ubuntu server 24.04 步骤如下: sudo apt update sudo apt install samba修改配置文件: sudo vi /etc/samba/smb.conf新增内容: [username]path /home/[username]available yesvalid users [username]read only nobrow…...
![](https://www.ngui.cc/images/no-images.jpg)
atcoder ABC 357-D题详解
atcoder ABC 357-D题详解 Problem Statement For a positive integer N, let VN be the integer formed by concatenating N exactly N times. More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get VN. For…...
![](https://img-blog.csdnimg.cn/img_convert/7e3c80b60d7d9ec566600d1b3403295d.png)
从单一到多元:EasyCVR流媒体视频汇聚技术推动安防监控智能升级
随着科技的飞速发展,视频已成为我们日常生活和工作中的重要组成部分。尤其在远程办公、在线教育、虚拟会议等领域,视频的应用愈发广泛。为了满足日益增长的视频需求,流媒体视频汇聚融合技术应运而生,它不仅改变了传统视频的观看和…...
![](https://www.ngui.cc/images/no-images.jpg)
Spring MVC数据绑定和响应——数据回写(二)JSON数据的回写
项目中已经导入了Jackson依赖,可以先调用Jackson的JSON转换的相关方法,将对象或集合转换成JSON数据,然后通过HttpServletResponse将JSON数据写入到输出流中完成回写,具体步骤如下。 1、修改文件DataController.java,在…...
![](https://img-blog.csdnimg.cn/img_convert/4216b21f252a339ff1862ae33412f86b.png)
怎么快速给他人分享图片?扫描二维码看图的简单做法
现在通过二维码来查看图片是一种很常见的方法,通过二维码来查看图片不仅能够减少对手机存储空间的占用,而且获取图片变得更加方便快捷,只需要扫码就能够查看图片,有利于图片的展现。很多的场景中都有图片二维码的应用,…...
![](https://img-blog.csdnimg.cn/img_convert/d4c8c21823511f4c1f713836e5a64927.png)
【UML用户指南】-26-对高级行为建模-状态图
目录 1、概念 2、组成结构 3、一般用法 4、常用建模技术 4.1、对反应型对象建模 一个状态图显示了一个状态机。在为对象的生命期建模中 活动图展示的是跨过不同的对象从活动到活动的控制流 状态图展示的是单个对象内从状态到状态的控制流。 在UML中,用状态图…...
![](https://img-blog.csdnimg.cn/direct/778805e0ea79423da6abb2232a13f2f6.png)
解决VSCode无法用ssh连接远程服务器的问题
原因: 因为windows自带的ssh无法连接远程服务器,需要用git底下的ssh.exe。 搜了很久,试过很多方法,包括替换掉环境变量中的ssh,但是都无效,最后发现是要在VSCode中配置需要使用哪个ssh.exe。 步骤&#…...
![](https://img-blog.csdnimg.cn/direct/d9493e34e7644dadaa52f53b5be13301.png)
【区块链+基础设施】银联云区块链服务 | FISCO BCOS应用案例
为了顺应区块链基础设施化的发展趋势,中国银联推出了银联云区块链服务——UPBaaS,为金融行业采用区块链 技术提出了解决方案,微众银行为平台提供 FISCO BCOS 区块链开源技术支持。通过银联云区块链服务,用户可 以用可视化的方式创…...
![](https://www.ngui.cc/images/no-images.jpg)
Java SE入门及基础(61) 死锁 死锁发生条件
目录 死锁 1. 死锁的概念 2. 死锁发生条件 互斥条件 不可剥夺条件 请求与保持条件 循环等待 3. 案例分析 示例 分析 死锁 1. 死锁的概念 Deadlock describes a situation where two or more threads are blocked forever, waiting for each other 死锁描述了一种情…...
![](https://img-blog.csdnimg.cn/direct/f9c33955d197497080f7aff419a07346.png)
简单爬虫案例——爬取快手视频
网址:aHR0cHM6Ly93d3cua3VhaXNob3UuY29tL3NlYXJjaC92aWRlbz9zZWFyY2hLZXk9JUU2JThCJTg5JUU5JTlEJUEy 找到视频接口: 视频链接在photourl中 完整代码: import requestsimport re url https://www.kuaishou.com/graphql cookies {did: web_…...
![](https://img-blog.csdnimg.cn/direct/4b359101716e43418c416d093d4838c1.png#pic_center)
42、nginx之nginx.conf
nginx----web服务器 一、nginx http就是apache,在国内很少。 nginx是开源的,是一款高性能,轻量级的web服务软件。 稳定性高,而且版本迭代比较快(修复bug速度比较快,安全性快) 消耗系统资源…...
![](https://www.ngui.cc/images/no-images.jpg)
高薪程序员必修课-java为什么要用并发编程
目录 前言 1. 提高性能和效率 2. 更好地响应用户 3. 优化I/O操作 具体示例 示例1:提高性能和效率 示例2:更好地响应用户 示例3:优化I/O操作 总结 前言 并发编程允许多个线程在同一时间执行任务。下面我们从多个原理角度来解释为什么J…...
![](https://www.ngui.cc/images/no-images.jpg)
postgreSQL学习
postgreSql学习 学习参考:1、命令1.1 登录1.2 关闭连接 2、常用数据类型2.1 数值类型2.2 字符串类型2.3 时间2.4 其他 3、自增主键4、sql4.1 库操作(1)创建新库(2)切换数据库(3)删库【谨慎&…...
![](https://img-blog.csdnimg.cn/direct/075bdbf7ba2d46e9a7fc223414635975.png)
【3】系统标定
文章目录 雷达标定相机主雷达标定底盘动力学标定车辆循迹验证建图 雷达标定 主要是为了获得到lidar到imu的tf关系。imu为父坐标lidar为子坐标。其他雷达标定到主lidar坐标系下。 标定的结果都是生成一个是四元数。 #mermaid-svg-crOWRnT4UE0jtJVy {font-family:"trebuch…...
![](https://img-blog.csdnimg.cn/direct/c26addcd8767477ba1d4a5b617e43bef.png)
网安小贴士(3)网安协议
一、前言 网络安全协议是构建安全网络环境的基础,它们帮助保护网络通信免受各种威胁和攻击。 二、定义 网络安全协议是指在计算机网络中用于确保网络通信和数据传输安全的协议。它们定义了在网络通信过程中的安全机制、加密算法、认证和授权流程等,以保…...
![](https://www.ngui.cc/images/no-images.jpg)
大数据面试题之HBase(1)
目录 介绍下HBase HBase优缺点 说下HBase原理 介绍下HBase架构 HBase读写数据流程 HBase的读写缓存 在删除HBase中的一个数据的时候,它什么时候真正的进行删除呢?当你进行删除操作,它是立马就把数据删除掉了吗? HBase中的二级索引 HBa…...
![](https://www.ngui.cc/images/no-images.jpg)
git回退commit的方式
在Git中,回退commit(即撤销之前的提交)可以通过多种方式来实现。以下是一些常见的方法,以及它们的详细步骤和注意事项: ### 1. 使用git revert命令 git revert命令用于撤销某次commit,但它并不会删除该comm…...
![](https://img-blog.csdnimg.cn/direct/0149dc1e13d84f81b8943b0fdd492d9c.png)
[Information Sciences 2023]用于假新闻检测的相似性感知多模态提示学习
推荐的一个视频:p-tuning P-tunning直接使用连续空间搜索 做法就是直接将在自然语言中存在的词直接替换成可以直接训练的输入向量。本身的Pretrained LLMs 可以Fine-Tuning也可以不做。 这篇论文也解释了为什么很少在其他领域结合知识图谱的原因:就是因…...
![](https://img-blog.csdnimg.cn/direct/68c1a65ff66a4de691e04925b7dd3711.png#pic_center)
自定义vue3 hooks
文章目录 hooks目录结构demo hooks 当页面内有很多的功能,js代码太多,不好维护,可以每个功能都有写一个js或者ts,这样的话,代码易读,并且容易维护,组合式setup写法与此结合👍&#…...
![](https://img-blog.csdnimg.cn/direct/de5cb5b491634ecdb3e32cd0fe0af492.png)
《昇思25天学习打卡营第21天 | 昇思MindSporePix2Pix实现图像转换》
21天 本节学习了通过Pix2Pix实现图像转换。 Pix2Pix是基于条件生成对抗网络(cGAN)实现的一种深度学习图像转换模型。可以实现语义/标签到真实图片、灰度图到彩色图、航空图到地图、白天到黑夜、线稿图到实物图的转换。Pix2Pix是将cGAN应用于有监督的图…...
![](https://img-blog.csdnimg.cn/direct/c26f06fa16d94cbe96ce3371fce2b143.png)
【文档+源码+调试讲解】科研经费管理系统
目 录 目 录 摘 要 ABSTRACT 1 绪论 1.1 课题背景 1.2 研究现状 1.3 研究内容 2 系统开发环境 2.1 vue技术 2.2 JAVA技术 2.3 MYSQL数据库 2.4 B/S结构 2.5 SSM框架技术 3 系统分析 3.1 可行性分析 3.1.1 技术可行性 3.1.2 操作可行性 3.1.3 经济可行性 3.1…...
![](https://www.ngui.cc/images/no-images.jpg)
linux 下 rm 为什么要这么写?
下面代码中的rm 为什么要写成/bin/rm? 大文件清理,高宿主含量样本可节约>90%空间/bin/rm -rf temp/qc/*contam* temp/qc/*unmatched* temp/qc/*.fqls -l temp/qc/ 这是一个很好的问题,观察很仔细, 也带着了自己的思考。 rm是 Linux 下的一个危险…...
![](https://img-blog.csdnimg.cn/direct/c0696a288dd74c229962d67fd91442ff.png)
【Spring Boot】Spring AOP中的环绕通知
目录 一、什么是AOP?二、AOP 的环绕通知2.1 切点以及切点表达式2.2 连接点2.3 通知(Advice)2.4 切面(Aspect)2.5 不同通知类型的区别2.5.1 正常情况下2.5.2异常情况下 2.6 统一管理切点PointCut 一、什么是AOP? Aspect Oriented Programmingÿ…...
![](https://img-blog.csdnimg.cn/direct/249399b92e984ecf822474930c4aa371.png)
docker部署前端,配置域名和ssl
之前使用80端口部署前端项目后,可以使用IP端口号在公网访问到部署的项目。 进行ICP域名备案后,可以通过域名解析将IP套壳,访问域名直接访问到部署的项目~ 如果使用http协议可以很容易实现这个需求,对nginx.conf文件进行修改&#…...
![](https://img-blog.csdnimg.cn/direct/cc745c55000a4582998ba0a83df2bbf7.png)
初学Spring之 IOC 控制反转
Spring 是一个轻量级的控制反转(IOC)和面向切面编程(AOP)的框架 导入 jar 包:spring-webmvc、spring-jdbc <dependency><groupId>org.springframework</groupId><artifactId>spring-webmvc&…...
![](https://www.ngui.cc/images/no-images.jpg)
rpc的仅有通信的功能,在网断的情况下,比网通情况下,内存增长会是什么原因
RPC(Remote Procedure Call,远程过程调用)主要负责在分布式系统中透明地调用远程服务,就像调用本地函数一样。它封装了网络通信的细节,使得开发者可以专注于业务逻辑而非底层通信协议。RPC通信通常包括序列化、网络传输…...
![](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=https%3A%2F%2Fmainjaylai.github.io%2FBlog%2Fstatic%2Fimages%2Fsystem%2Fchat-system%2Fpicture4.svg&pos_id=img-L6hKzEAw-1719917835036)
从零开始:如何设计一个现代化聊天系统
写在前面: 此博客内容已经同步到我的博客网站,如需要获得更优的阅读体验请前往https://mainjaylai.github.io/Blog/blog/system/chat-system 在当今数字化时代,聊天系统已成为我们日常生活和工作中不可或缺的一部分。从个人交流到团队协作,从客户服务到社交网络,聊天应用…...
![](https://img-blog.csdnimg.cn/img_convert/510da676908443e81f38df6742bf5f44.png)
香橙派OrangePi AIpro初体验:当小白拿到一块开发板第一时间会做什么?
文章目录 香橙派OrangePi AIpro初体验:当小白拿到一块高性能AI开发板第一时间会做什么前言一、香橙派OrangePi AIpro概述1.简介2.引脚图开箱图片 二、使用体验1.基础操作2.软件工具分析 三、香橙派OrangePi AIpro.测试Demo1.测试Demo1:录音和播音(USB接口…...
![](https://img-blog.csdnimg.cn/direct/d85d616a22094dcaa52a9cc994be4438.png)
【C语言内存函数】
目录 1.memcpy 使用 模拟实现 2.memmove 使用 模拟实现 3.memset 使用 4.memcmp 使用 1.memcpy 使用 void * memcpy ( void * destination, const void * source, size_t num );目的地址 源地址 字节数 destination:指向要复制内…...
![](https://img-blog.csdnimg.cn/direct/236b2657c64844979db44f4a84ecb0da.png)
MySQL/SqlServer 跨服务器 增删改查(CRUD) 的一种方法
前言:主要是利用SqlServer 的链接服务器功能 1.准备一台 SqlServer Server,服务如下图: 这台服务器专门用于 链接服务器 IP:10.x.x.3 和数据源服务器(10.x.x.5) 在一个局域网 1.1 版本 是 2017 2.在 10.…...
![](https://img-blog.csdnimg.cn/direct/999e30af005c4cc3a89e27d38b102430.jpeg)
【postgresql】索引
见的索引类型: B-tree 索引:这是最常用的索引类型,适用于大多数查询。B-tree索引可以高效地处理范围查询。 Hash 索引:适用于等值查询,但不支持范围查询。 GiST 索引:通用搜索树(GiST…...
![](https://www.ngui.cc/images/no-images.jpg)
Oh My Zsh Git 插件
以下是一些常见的别名和它们对应的 Git 命令: g: gitga: git addgaa: git add --allgapa: git add --patchgau: git add --updategb: git branchgba: git branch -agbd: git branch -dgbda: git branch --no-color --merged | command grep -vE “^(||*|\s*(main|m…...
![](https://img-blog.csdnimg.cn/direct/05dd66d6208e4e4692252d4a059ece15.png)
一文解决图论中有向图、无向图、非负加权图的单源最短路径问题【超详细】【通用模板程序】【深入分析】【无需基础】【c++】
本文致力于提供一种解决图论中所有(或绝大部分)有向图、无向图、非负加权图的单源最短路径问题的通用程序模板,本文提供的模板并不是简单的可行模板,而是经过深入分析解释的一个较高质量和性能的通用程序模版。在每个关键变量存储…...
![](https://www.ngui.cc/images/no-images.jpg)
k8s自动清理节点服务
要在 Kubernetes 中实现当某个节点的 CPU 或内存使用超过 90% 时清理该节点上的服务,你可以使用以下几种方法: 自定义脚本和 cron job:编写一个脚本监控节点的资源使用情况,并在超过阈值时触发清理操作。使用 DaemonSet 运行监控…...
![](https://www.ngui.cc/images/no-images.jpg)
必须掌握的Linux的九大命令
ifconfig 命令用于配置和查看网络接口的参数。 ping 命令用于测试主机之间的网络连通性。 telnet用于通过Telnet协议连接到远程主机。 telnet 127.0.0.1 8000 telnet example.com telnet example.com 8080 iostat 命令用于报告 CPU 统计信息和 I/O 设备负载。 iostat&…...
![](https://www.ngui.cc/images/no-images.jpg)
家人们,咱们汽车界有自己的“显眼包”!
现在想换辆新车太难了,选择太多了,挑的眼花缭乱的。就在我一筹莫展的时候,我在店里遇到了传祺新能源E8,属实是没想到虽然它的价格不到25万,但是却拥有着特别抢眼的优势。它的智能化配置很高,5月份传祺E8首次升级OTA后新增了广汽魔方场景设定功能,可以让我自定义设置2000…...
![](https://img-blog.csdnimg.cn/img_convert/0f5859b64b72b328680f2de69b0740e5.jpeg)
磁带存储:“不老的传说”依然在继续
现在是一个数据指数增长的时代,根据IDC数据预测,2025年全世界将产生175ZB的数据。 这里面大部分数据是不需要存储的,在2025预计每年需要存储11ZB的数据。换算个容易理解的说法,1ZB是10^18Bytes, 相当于要写5556万块容量18TB的硬盘…...
![](https://img-blog.csdnimg.cn/direct/2e4cda5f7e0f46f38a6c779370270e12.png)
LazyVim笔记
回到上次编辑的位置 gi非常的方便。 neo-tree KeyDescriptionMode<leader>beBuffer Explorern<leader>eExplorer NeoTree (Root Dir)n<leader>EExplorer NeoTree (cwd)n<leader>feExplorer NeoTree (Root Dir)n<leader>fEExplorer NeoTree (c…...
![](https://img-blog.csdnimg.cn/direct/dfb6ebe8cc9e49e6ab54635260f535c6.png)
qmt量化交易策略小白学习笔记第8期【qmt编程之获取股票资金流向数据--内置Python】
qmt编程之获取股票资金流向数据 qmt更加详细的教程方法,会持续慢慢梳理。 也可找寻博主的历史文章,搜索关键词查看解决方案 ! 感谢关注,需免费开通量化回测与咨询实盘权限,可以和博主联系! 获取股票资金…...
![](https://img-blog.csdnimg.cn/img_convert/ecd88a4a2d37c8df212454d449269de9.png)
【机器学习】【深度学习】正则化(Regularization)
概念 正则化(Regularization)是在机器学习模型中避免过拟合的一种技术。它通过引入一个惩罚项(即正则项)来限制模型的复杂度,以此来提防模型过度依赖训练数据,捕获数据中的噪音信息而导致过拟合现象。简单…...
![](https://img-blog.csdnimg.cn/img_convert/b3aeebbd38f769ed604c92ee0457229b.png)
OrangePi AIpro 性能测试以及使用体验
OrangePi AIpro 性能测试以及使用体验 1. 介绍 OrangePi AIpro(8T)采用昇腾AI技术路线。 具体为4核64位处理器AI处理器,集成图形处理器,支持8TOPS AI算力拥有8GB/16GB LPDDR4X,可以外接32GB/64GB/128GB/256GB eMMC模块,支持双4…...