bloom.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f85d4440-7fe1-400f-be44-7380ced9e1a2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bit array:\n",
      "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n",
      "Testing Bit Array:\n",
      "11111010000101010010100111011001100101100001100111001111101000110100110101010110000111001110100011000011010011101001101011100010\n",
      "Contains 'apple': True\n",
      "Contains 'banana': True\n",
      "Contains 'cherry': False\n",
      "Contains 'sherry': False\n"
     ]
    }
   ],
   "source": [
    "import hashlib\n",
    "import math\n",
    "from bitarray import bitarray\n",
    "\n",
    "\n",
    "class SimpleBloomFilter:\n",
    "    def __init__(self, size, num_hash_functions):\n",
    "        \"\"\"\n",
    "        Initialize the Bloom Filter\n",
    "        :param size: The size of the bit array\n",
    "        :param num_hash_functions: The number of hash functions to use\n",
    "        \"\"\"\n",
    "        self.size = size\n",
    "        self.num_hash_functions = num_hash_functions\n",
    "        self.bit_array = bitarray(size)\n",
    "        self.bit_array.setall(0)  # Initialize all bits to 0\n",
    "\n",
    "    def _hash(self, item, seed):\n",
    "        \"\"\"\n",
    "        A simple hash function that uses MD5 with a seed\n",
    "        :param item: The item to hash\n",
    "        :param seed: A seed to ensure different hash results\n",
    "        :return: A hash value in the range of the bit array\n",
    "        \"\"\"\n",
    "        item_hash = hashlib.md5((item + str(seed)).encode()).hexdigest()\n",
    "        return int(item_hash, 16) % self.size\n",
    "\n",
    "    def add(self, item):\n",
    "        \"\"\"\n",
    "        Add an item to the Bloom Filter\n",
    "        :param item: The item to add\n",
    "        \"\"\"\n",
    "        for i in range(self.num_hash_functions):\n",
    "            pos = self._hash(item, i)\n",
    "            self.bit_array[pos] = True\n",
    "\n",
    "    def contains(self, item):\n",
    "        \"\"\"\n",
    "        Check if an item is in the Bloom Filter\n",
    "        :param item: The item to check\n",
    "        :return: True if the item is likely in the set, False otherwise\n",
    "        \"\"\"\n",
    "        for i in range(self.num_hash_functions):\n",
    "            pos = self._hash(item, i)\n",
    "            if not self.bit_array[pos]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def __str__(self):\n",
    "        \"\"\"\n",
    "        Return a string representation of the bit array\n",
    "        \"\"\"\n",
    "        return self.bit_array.to01()  # Converts the bitarray to a string of 0s and 1s\n",
    "\n",
    "\n",
    "    def index_list(self, char):\n",
    "        positions = [i for i in range(len(self.bit_array)) if self.bit_array[i] == 1]\n",
    "        return char.join([str(id) for id in positions])\n",
    "\n",
    "\n",
    "# Create a bloom map from in_file into out_file\n",
    "\n",
    "def generate_bloom_map(n_bits, n_hash, in_file, out_file, split_char):\n",
    "\n",
    "    with open(in_file, 'r') as file:\n",
    "        with open(out_file, 'w', encoding='utf-8') as file2:\n",
    "        # Read the file line by line\n",
    "            count = 0\n",
    "            for line in file:\n",
    "                bloom_filter = SimpleBloomFilter(size=n_bits, num_hash_functions=n_hash)\n",
    "\n",
    "                # Strip newline characters and split by commas\n",
    "                values = line.strip().split(split_char)\n",
    "\n",
    "                for val in values:\n",
    "                    bloom_filter.add(val)\n",
    "\n",
    "                file2.write(bloom_filter.index_list(split_char) + '\\n')\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Example usage\n",
    "bloom_filter = SimpleBloomFilter(size=128, num_hash_functions=5)\n",
    "print(\"Bit array:\")\n",
    "print(bloom_filter)  # Calls __str__\n",
    "\n",
    "# Add some items\n",
    "bloom_filter.add(\"apple\")\n",
    "bloom_filter.add(\"banana\")\n",
    "bloom_filter.add(\"car\")\n",
    "bloom_filter.add(\"bike\")\n",
    "bloom_filter.add(\"bake\")\n",
    "bloom_filter.add(\"bark\")\n",
    "bloom_filter.add(\"bus\")\n",
    "bloom_filter.add(\"banana\")\n",
    "bloom_filter.add(\"motor\")\n",
    "bloom_filter.add(\"cycle\")\n",
    "bloom_filter.add(\"swim\")\n",
    "bloom_filter.add(\"bad\")\n",
    "bloom_filter.add(\"omen\")\n",
    "bloom_filter.add(\"oman\")\n",
    "bloom_filter.add(\"modi\")\n",
    "bloom_filter.add(\"narendar\")\n",
    "bloom_filter.add(\"suren\")\n",
    "bloom_filter.add(\"deven\")\n",
    "bloom_filter.add(\"dharmen\")\n",
    "bloom_filter.add(\"briti\")\n",
    "\n",
    "\n",
    "\n",
    "# Print the bit array\n",
    "print(\"Testing Bit Array:\")\n",
    "print(bloom_filter)  # Calls __str__\n",
    "\n",
    "# Check if the items are in the set\n",
    "print(\"Contains 'apple':\", bloom_filter.contains(\"apple\"))  # Should be True\n",
    "print(\"Contains 'banana':\", bloom_filter.contains(\"oman\"))  # Should be True\n",
    "print(\"Contains 'cherry':\", bloom_filter.contains(\"cherry\"))  # Likely False\n",
    "print(\"Contains 'sherry':\", bloom_filter.contains(\"sherry\"))  # Likely False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ace1245e-0a76-4f2a-a8a4-2c2f7fb6d5fc",
   "metadata": {},
   "outputs": [],
   "source": [
    "n_bits = 512\n",
    "n_hash = 4    \n",
    "\n",
    "in_file = '/home/rakri/wiki_rnd1m/wikipedia_rnd1m_labels.txt'\n",
    "#in_file = '/home/rakri/wiki_rnd1m/wikipedia_query_labels_numeric_double_common.txt'\n",
    "\n",
    "\n",
    "out_file = '/home/rakri/wiki_rnd1m/wikipedia_rnd1m_labels_bloom_' + str(n_hash) + '_' + str(n_bits) + '.txt'\n",
    "#out_file = '/home/rakri/wiki_rnd1m/wikipedia_query_labels_numeric_double_common_bloom_' + str(n_hash) + '_' + str(n_bits) + '.txt'\n",
    "\n",
    "generate_bloom_map(n_bits, n_hash, in_file, out_file, ',')\n",
    "#generate_bloom_map(n_bits, n_hash, in_file, out_file, '&')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "44c7e7ca-ebbf-4098-8168-195f9a3fa7ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('/home/rakri/filt_labels_to_medoids.txt', 'w', encoding='utf-8') as file2:\n",
    "    # Read the file line by line\n",
    "    count = 0\n",
    "    for i in range(0,4000):\n",
    "        file2.write(str(i) + '\\t' + str(0) + '\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3c9bde3-76fb-40ef-8dfc-354cb522cdfd",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}