前言：

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

BitMap

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

BitMap常見操作

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

BitMap實現(xiàn)

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

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)域

• 圖像編輯軟件：在圖像編輯軟件中，位圖是存儲圖像數(shù)據(jù)的主要方式。C++ 可以用于讀取、處理和保存各種位圖格式的圖像，如 BMP、JPEG、PNG 等。通過對位圖數(shù)據(jù)的操作，可以實現(xiàn)圖像的裁剪、旋轉(zhuǎn)、縮放、色彩調(diào)整等功能。例如，使用 C++ 和特定的圖像庫，可以加載一幅位圖圖像，對其進(jìn)行亮度和對比度的調(diào)整，然后保存為新的圖像文件。
• 游戲開發(fā)：在游戲開發(fā)中，位圖用于存儲游戲中的角色、場景、道具等圖像資源。C++ 可以高效地處理位圖圖像，實現(xiàn)游戲中的各種圖形效果。例如，在 2D 游戲中，可以使用位圖來繪制游戲角色和背景；在 3D 游戲中，位圖可以用于紋理映射，為 3D 模型添加真實感的表面紋理。
• 圖形界面設(shè)計：在圖形界面設(shè)計中，位圖可以用于按鈕、圖標(biāo)、背景等的顯示。C++ 結(jié)合圖形庫可以實現(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ù)點映射到位圖的像素上，可以創(chuàng)建熱力圖、散點圖等可視化圖表。
• 數(shù)據(jù)庫存儲：在某些數(shù)據(jù)庫系統(tǒng)中，位圖索引是一種高效的數(shù)據(jù)存儲和查詢方式。C++ 可以用于實現(xiàn)位圖索引的創(chuàng)建、維護(hù)和查詢操作。例如，在處理大量的布爾型數(shù)據(jù)時，可以使用位圖索引來快速查詢滿足特定條件的數(shù)據(jù)記錄。
• 數(shù)據(jù)壓縮：位圖可以通過壓縮算法來減少存儲空間。C++ 可以實現(xiàn)各種位圖壓縮算法，如游程編碼、霍夫曼編碼等。例如，對于包含大量重復(fù)數(shù)據(jù)的位圖圖像，可以使用游程編碼算法進(jìn)行壓縮，顯著減少存儲空間。

三、其他領(lǐng)域

• 醫(yī)學(xué)影像處理：在醫(yī)學(xué)影像處理中，位圖用于存儲 X 光片、CT 掃描、MRI 等圖像數(shù)據(jù)。C++ 可以對醫(yī)學(xué)位圖圖像進(jìn)行處理和分析，幫助醫(yī)生進(jìn)行疾病診斷。例如，使用 C++ 和特定的醫(yī)學(xué)影像處理庫，可以對醫(yī)學(xué)位圖圖像進(jìn)行增強、分割、特征提取等操作，為醫(yī)生提供更準(zhǔn)確的診斷信息。
• 地理信息系統(tǒng)（GIS）：在 GIS 中，位圖可以用于存儲地圖數(shù)據(jù)、衛(wèi)星圖像等。C++ 可以處理和顯示位圖地圖數(shù)據(jù)，實現(xiàn)地圖的縮放、平移、查詢等功能。例如，使用 C++ 和 GIS 庫，可以加載位圖地圖圖像，為用戶提供地理信息查詢和導(dǎo)航服務(wù)。
• 數(shù)字信號處理：在數(shù)字信號處理中，位圖可以用于存儲音頻、視頻等信號數(shù)據(jù)。C++ 可以對數(shù)字信號進(jìn)行處理和分析，實現(xiàn)音頻、視頻的編碼、解碼、濾波等功能。例如，使用 C++ 和音頻處理庫，可以對音頻信號進(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ù)處理中的性能極限并非易事，需要綜合考慮多個因素。

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

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

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

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

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

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

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

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;  // 存在誤判的
	}
	// 不支持刪除，刪除可能會影響其他值。
	void Reset(const K& key);
private:
	bitset<X * N> _bs;
};

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

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

Bitmap Bloom Filter區(qū)別

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

• 位圖：

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

• 布隆過濾器：

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

二、功能和用途

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

三、性能特點

• 空間復(fù)雜度：

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

• 時間復(fù)雜度：

  • 位圖：對于插入和查詢操作，時間復(fù)雜度通常為 O (1)，非常高效。因為只需要通過簡單的位運算就可以完成操作。

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

• 誤判率：

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

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

四、適用場景

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

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

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

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

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

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

最新評論