前言：

在計(jì)算機(jī)圖形學(xué)中，位圖（Bitmap）也稱為光柵圖，是由像素點(diǎn)組成的圖像表示方式。在 C++ 編程中，位圖可以通過特定的函數(shù)和數(shù)據(jù)結(jié)構(gòu)來進(jìn)行處理和操作。

BitMap

• 位圖（BitMap）是一種數(shù)據(jù)結(jié)構(gòu)，它使用每一位二進(jìn)制數(shù)來表示一個(gè)數(shù)據(jù)項(xiàng)的存在狀態(tài)。
• 在C++中，位圖通常用于處理大量的布爾值或整數(shù)集合，以實(shí)現(xiàn)高效的空間和時(shí)間性能。
• 位圖通過使用一組整數(shù)數(shù)組來表示一組元素的狀態(tài)，其中每個(gè)整數(shù)可以表示多個(gè)元素的存在狀態(tài)，通常是8個(gè)或更多。

BitMap常見操作

• 位圖提供了幾種基本操作，包括設(shè)置（set）、重置（reset）和測(cè)試（test）。
• 設(shè)置操作將指定的位設(shè)置為1，重置操作將指定的位設(shè)置為0，而測(cè)試操作則檢查指定的位是否為1。
• 這些操作通常涉及位運(yùn)算符，如按位或（|=）、按位與（&=）和按位異或（^=）。

BitMap實(shí)現(xiàn)

• 位圖的精髓在于利于一個(gè)比特位確定一個(gè)值是否存在，更改的是比特位，就需要利用位操作符。
• 給一個(gè)非類型模板參數(shù)進(jìn)行空間的開辟。
• 位圖進(jìn)行初始化，每個(gè)位置初始化為0，經(jīng)過計(jì)算映射到對(duì)應(yīng)的比特位。
• 初始化除以一個(gè)32（以整形開辟的空間），+1是為了防止空間除后空間少32位。
• set 和reset就是進(jìn)行位圖的核心操作。test的檢測(cè)有很多方法，提供一個(gè)比較容易理解的檢測(cè)。

template<size_t N >
class bitset
{
public:

	birset()
	{
		_a.resize(N / 32 + 1);
	}

	void set(const size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;

		_a[i]|= (i<<j)
	}
	void reset(const size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;

		_a[i] &= (~(i << 32));
	}

	bool test(const size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;

		return  _a[i] & (1 << j);
	}
private:
	vector<int> _a;
};

BitMap應(yīng)用

一、圖形圖像領(lǐng)域

• 圖像編輯軟件：在圖像編輯軟件中，位圖是存儲(chǔ)圖像數(shù)據(jù)的主要方式。C++ 可以用于讀取、處理和保存各種位圖格式的圖像，如 BMP、JPEG、PNG 等。通過對(duì)位圖數(shù)據(jù)的操作，可以實(shí)現(xiàn)圖像的裁剪、旋轉(zhuǎn)、縮放、色彩調(diào)整等功能。例如，使用 C++ 和特定的圖像庫(kù)，可以加載一幅位圖圖像，對(duì)其進(jìn)行亮度和對(duì)比度的調(diào)整，然后保存為新的圖像文件。
• 游戲開發(fā)：在游戲開發(fā)中，位圖用于存儲(chǔ)游戲中的角色、場(chǎng)景、道具等圖像資源。C++ 可以高效地處理位圖圖像，實(shí)現(xiàn)游戲中的各種圖形效果。例如，在 2D 游戲中，可以使用位圖來繪制游戲角色和背景；在 3D 游戲中，位圖可以用于紋理映射，為 3D 模型添加真實(shí)感的表面紋理。
• 圖形界面設(shè)計(jì)：在圖形界面設(shè)計(jì)中，位圖可以用于按鈕、圖標(biāo)、背景等的顯示。C++ 結(jié)合圖形庫(kù)可以實(shí)現(xiàn)豐富的圖形界面效果。例如，使用 C++ 和 Qt 框架，可以加載位圖圖像作為按鈕的圖標(biāo)，為用戶界面增添美觀性。

二、數(shù)據(jù)處理領(lǐng)域

• 數(shù)據(jù)可視化：在數(shù)據(jù)可視化中，位圖可以用于將數(shù)據(jù)以圖像的形式展示出來。C++ 可以處理大量的數(shù)據(jù)，并將其轉(zhuǎn)換為位圖圖像進(jìn)行可視化。例如，通過將數(shù)據(jù)點(diǎn)映射到位圖的像素上，可以創(chuàng)建熱力圖、散點(diǎn)圖等可視化圖表。
• 數(shù)據(jù)庫(kù)存儲(chǔ)：在某些數(shù)據(jù)庫(kù)系統(tǒng)中，位圖索引是一種高效的數(shù)據(jù)存儲(chǔ)和查詢方式。C++ 可以用于實(shí)現(xiàn)位圖索引的創(chuàng)建、維護(hù)和查詢操作。例如，在處理大量的布爾型數(shù)據(jù)時(shí)，可以使用位圖索引來快速查詢滿足特定條件的數(shù)據(jù)記錄。
• 數(shù)據(jù)壓縮：位圖可以通過壓縮算法來減少存儲(chǔ)空間。C++ 可以實(shí)現(xiàn)各種位圖壓縮算法，如游程編碼、霍夫曼編碼等。例如，對(duì)于包含大量重復(fù)數(shù)據(jù)的位圖圖像，可以使用游程編碼算法進(jìn)行壓縮，顯著減少存儲(chǔ)空間。

三、其他領(lǐng)域

• 醫(yī)學(xué)影像處理：在醫(yī)學(xué)影像處理中，位圖用于存儲(chǔ) X 光片、CT 掃描、MRI 等圖像數(shù)據(jù)。C++ 可以對(duì)醫(yī)學(xué)位圖圖像進(jìn)行處理和分析，幫助醫(yī)生進(jìn)行疾病診斷。例如，使用 C++ 和特定的醫(yī)學(xué)影像處理庫(kù)，可以對(duì)醫(yī)學(xué)位圖圖像進(jìn)行增強(qiáng)、分割、特征提取等操作，為醫(yī)生提供更準(zhǔn)確的診斷信息。
• 地理信息系統(tǒng)（GIS）：在 GIS 中，位圖可以用于存儲(chǔ)地圖數(shù)據(jù)、衛(wèi)星圖像等。C++ 可以處理和顯示位圖地圖數(shù)據(jù)，實(shí)現(xiàn)地圖的縮放、平移、查詢等功能。例如，使用 C++ 和 GIS 庫(kù)，可以加載位圖地圖圖像，為用戶提供地理信息查詢和導(dǎo)航服務(wù)。
• 數(shù)字信號(hào)處理：在數(shù)字信號(hào)處理中，位圖可以用于存儲(chǔ)音頻、視頻等信號(hào)數(shù)據(jù)。C++ 可以對(duì)數(shù)字信號(hào)進(jìn)行處理和分析，實(shí)現(xiàn)音頻、視頻的編碼、解碼、濾波等功能。例如，使用 C++ 和音頻處理庫(kù)，可以對(duì)音頻信號(hào)進(jìn)行濾波處理，去除噪聲，提高音頻質(zhì)量。

布隆過濾器

布隆過濾器（Bloom Filter）作為一種高效的數(shù)據(jù)結(jié)構(gòu)，在大規(guī)模數(shù)據(jù)處理中有著廣泛的應(yīng)用。尤其是在 C++ 語言環(huán)境下，其性能表現(xiàn)備受關(guān)注。然而，要確定 C++ 布隆過濾器在大規(guī)模數(shù)據(jù)處理中的性能極限并非易事，需要綜合考慮多個(gè)因素。

• 布隆過濾器是一種空間效率高的概率型數(shù)據(jù)結(jié)構(gòu)，用于判斷一個(gè)元素是否是某個(gè)集合的成員。
• 它由布爾型數(shù)組、多個(gè)哈希函數(shù)和插入、查詢操作組成。
• 布隆過濾器的核心思想是通過多個(gè)哈希函數(shù)將輸入元素映射到位數(shù)組的多個(gè)位置，并將這些位置設(shè)置為1。
• 查詢時(shí)，如果所有對(duì)應(yīng)的位都為1，則元素可能存在；如果有任何一個(gè)位為0，則元素一定不存在.

位圖和布隆過濾器區(qū)別

• 用哈希表存儲(chǔ)用戶記錄，缺點(diǎn)：浪費(fèi)空間。
• 用位圖存儲(chǔ)用戶記錄，缺點(diǎn)：位圖一般只能處理整形，如果內(nèi)容編號(hào)是字符串，就無法處理 了。
• 將哈希與位圖結(jié)合，即布隆過濾器。

布隆過濾器的實(shí)現(xiàn)

在C++中實(shí)現(xiàn)布隆過濾器，通常涉及以下步驟：

• 定義std::bitset大?。焊鶕?jù)預(yù)期的元素?cái)?shù)量和允許的誤判率，確定std::bitset的大小。
• 選擇哈希函數(shù)：布隆過濾器通常使用多個(gè)哈希函數(shù)來減少?zèng)_突?？梢允褂脴?biāo)準(zhǔn)庫(kù)中的哈希函數(shù)或自定義哈希函數(shù)。
• 初始化std::bitset：創(chuàng)建一個(gè)std::bitset實(shí)例，其大小等于哈希函數(shù)的數(shù)量乘以位數(shù)組的大小。】
• 插入元素：對(duì)于每個(gè)要插入的元素，使用每個(gè)哈希函數(shù)計(jì)算出多個(gè)位置，并將這些位置在std::bitset中設(shè)置為1。
• 查詢?cè)兀阂獧z查一個(gè)元素是否可能存在于布隆過濾器中，使用相同的哈希函數(shù)計(jì)算出該元素的位置，并檢查這些位置是否全部為1。如果所有位置都為1，則元素可能存在；如果有任何一個(gè)位置為0，則元素一定不存在。
• 優(yōu)化和調(diào)整：根據(jù)實(shí)際應(yīng)用中的性能和誤判率要求，調(diào)整哈希函數(shù)的數(shù)量和std::bitset的大小。
• 三個(gè)哈希函數(shù)具有非常良好算法性能，有效的減少哈希沖突。

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};
struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};
struct DJBHash {
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

• 底層利用bitset不需要進(jìn)行構(gòu)造函數(shù)的實(shí)現(xiàn)

• 過濾器通過映射3個(gè)位置減少哈希沖突。

class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;
		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	bool Test(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		if (_bs.test(index1) == false)
			return false;
		size_t index2 = HashFunc2()(key) % len;
		if (_bs.test(index2) == false)
			return false;
		size_t index3 = HashFunc3()(key) % len;
		if (_bs.test(index3) == false)
			return false;
		return true;  // 存在誤判的
	}
	// 不支持刪除，刪除可能會(huì)影響其他值。
	void Reset(const K& key);
private:
	bitset<X * N> _bs;
};

為什么布隆過濾器不支持元素的刪除操作？

• 布隆過濾器不支持元素刪除操作的主要原因在于其工作原理。
• 布隆過濾器通過多個(gè)哈希函數(shù)將元素映射到一個(gè)位數(shù)組中，并將相應(yīng)位置設(shè)置為1來表示元素存在。
• 由于哈希碰撞的可能性，一個(gè)位可能被多個(gè)元素共享。
• 如果嘗試刪除一個(gè)元素，將其對(duì)應(yīng)的位清零，可能會(huì)影響到其他元素，導(dǎo)致誤判。因此，布隆過濾器的設(shè)計(jì)是“添加容易，刪除困難”，以保持其高效的查詢性能和低的空間占用。

Bitmap Bloom Filter區(qū)別

一、數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)方式

• 位圖：

• 數(shù)據(jù)結(jié)構(gòu)：位圖是由一系列比特位組成的數(shù)組，每個(gè)比特位對(duì)應(yīng)一個(gè)特定的值或狀態(tài)。
• 存儲(chǔ)方式：通過一位來表示一個(gè)特定的信息，例如，用 0 和 1 分別表示某個(gè)元素的存在與否。通常使用整數(shù)數(shù)組或位集等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。

• 布隆過濾器：

• 數(shù)據(jù)結(jié)構(gòu)：布隆過濾器由一個(gè)很長(zhǎng)的二進(jìn)制向量和多個(gè)哈希函數(shù)組成。
• 存儲(chǔ)方式：通過多個(gè)哈希函數(shù)將元素映射到二進(jìn)制向量的多個(gè)位置，并將這些位置的值置為 1。查詢時(shí)，通過相同的哈希函數(shù)檢查這些位置是否都為 1，以此來判斷元素是否可能存在于集合中。

二、功能和用途

• 位圖：
  • 主要功能：用于高效地表示和處理集合中的元素存在性問題，尤其適用于海量數(shù)據(jù)且數(shù)據(jù)無重復(fù)的場(chǎng)景。例如，可以快速判斷某個(gè)整數(shù)是否在一個(gè)大的整數(shù)集合中。
  • 典型用途：在數(shù)據(jù)庫(kù)索引、數(shù)據(jù)壓縮、內(nèi)存管理等領(lǐng)域有廣泛應(yīng)用。例如，在數(shù)據(jù)庫(kù)中，可以用位圖索引來快速判斷某個(gè)記錄是否滿足特定條件。
• 布隆過濾器：
  • 主要功能：用于快速判斷一個(gè)元素是否可能屬于一個(gè)集合，具有較高的空間效率和查詢速度，但存在一定的誤判率。
  • 典型用途：在網(wǎng)頁(yè)緩存、網(wǎng)絡(luò)數(shù)據(jù)包過濾、分布式系統(tǒng)等領(lǐng)域中，用于快速過濾掉不可能存在的元素，減少不必要的計(jì)算和存儲(chǔ)開銷。例如，在網(wǎng)頁(yè)緩存中，可以用布隆過濾器快速判斷一個(gè) URL 是否已經(jīng)被緩存

三、性能特點(diǎn)

• 空間復(fù)雜度：

  • 位圖：空間復(fù)雜度取決于要表示的元素?cái)?shù)量和元素的取值范圍。如果元素取值范圍較小，位圖的空間效率非常高。例如，對(duì)于表示 1000 個(gè)整數(shù)是否存在，只需要 1000 位（約 125 字節(jié)）的存儲(chǔ)空間。
    • 布隆過濾器：空間復(fù)雜度相對(duì)較低，尤其是對(duì)于大規(guī)模數(shù)據(jù)集合。它的空間占用主要取決于預(yù)期元素?cái)?shù)量和可接受的誤判率。通過調(diào)整哈希函數(shù)的數(shù)量和二進(jìn)制向量的大小，可以在一定程度上控制空間占用。

• 時(shí)間復(fù)雜度：

  • 位圖：對(duì)于插入和查詢操作，時(shí)間復(fù)雜度通常為 O (1)，非常高效。因?yàn)橹恍枰ㄟ^簡(jiǎn)單的位運(yùn)算就可以完成操作。

  • 布隆過濾器：插入和查詢操作的時(shí)間復(fù)雜度也非常低，接近 O (1)。但是，由于需要進(jìn)行多次哈希函數(shù)計(jì)算，實(shí)際時(shí)間開銷可能會(huì)略高于位圖。

• 誤判率：

  • 位圖：如果正確實(shí)現(xiàn)和使用，位圖不會(huì)產(chǎn)生誤判。只要某個(gè)比特位被設(shè)置為 1，就表示對(duì)應(yīng)的元素存在；如果為 0，則表示不存在。’

  • '布隆過濾器：存在一定的誤判率，即可能會(huì)把不在集合中的元素誤判為在集合中。誤判率與哈希函數(shù)的數(shù)量、二進(jìn)制向量的大小以及元素?cái)?shù)量有關(guān)?？梢酝ㄟ^調(diào)整這些參數(shù)來降低誤判率，但同時(shí)也會(huì)增加空間占用。

四、適用場(chǎng)景

• 當(dāng)需要精確判斷元素存在性且數(shù)據(jù)無重復(fù)時(shí)：適用數(shù)據(jù)結(jié)構(gòu)：位圖。

  原因：位圖可以準(zhǔn)確地表示元素的存在與否，不會(huì)產(chǎn)生誤判。如果數(shù)據(jù)沒有重復(fù)，位圖可以非常高效地利用存儲(chǔ)空間，并且查詢速度極快。

  當(dāng)需要快速判斷元素可能存在性且可以接受一定誤判率時(shí)：
  適用數(shù)據(jù)結(jié)構(gòu)：布隆過濾器。

  原因：布隆過濾器可以在非常低的空間開銷下快速判斷元素是否可能屬于一個(gè)集合。雖然存在誤判率，但在很多應(yīng)用場(chǎng)景中，誤判的影響可以通過其他方式進(jìn)行處理或可以被接受。例如，在網(wǎng)頁(yè)緩存中，即使偶爾誤判一個(gè) URL 已經(jīng)被緩存過，也只是多進(jìn)行了一次不必要的查詢，不會(huì)對(duì)系統(tǒng)性能產(chǎn)生嚴(yán)重影響。

2. 當(dāng)需要快速判斷元素可能存在性且可以接受一定誤判率時(shí)：
適用數(shù)據(jù)結(jié)構(gòu)：布隆過濾器。
3. 原因：布隆過濾器可以在非常低的空間開銷下快速判斷元素是否可能屬于一個(gè)集合。雖然存在誤判率，但在很多應(yīng)用場(chǎng)景中，誤判的影響可以通過其他方式進(jìn)行處理或可以被接受。例如，在網(wǎng)頁(yè)緩存中，即使偶爾誤判一個(gè) URL 已經(jīng)被緩存過，也只是多進(jìn)行了一次不必要的查詢，不會(huì)對(duì)系統(tǒng)性能產(chǎn)生嚴(yán)重影響。

到此這篇關(guān)于C++中BitSet和Bloom_Filter的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ BitSet和Bloom_Filter 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論