cms.py

import hashlib
import numpy as np
import matplotlib.pyplot as plt
import random
import sys

from tqdm import tqdm

def main():
  s = str(123)
  print("Using Seed: %s" % s)
  data = []
  filename = "stream.txt"

  print("Opening File: " + filename)
  with open(filename, "r", encoding="utf-8") as f:
    data = [line.rstrip() for line in f]
 
  realCount, tags = getRealCount(data)

  print("\n\nLEAST POPULAR:")
  list.sort(data, key = lambda tag : realCount[tag])
  for i in range(20):
    s = str(i)
    count = cms()
    for d in data:
      count.Inc(d, s)

    print("%d, %d" % (count.Count("workout", s), countHH(count, tags, s)))


  print("\n\nMOST POPULAR:")
  list.sort(data, key = lambda tag : - realCount[tag])
  for i in range(20):
    s = str(i)
    count = cms()
    for d in data:
      count.Inc(d, s)

    print("%d, %d" % (count.Count("workout", s), countHH(count, tags, s)))

  print("\n\nRANDOM:")
  random.shuffle(data)
  for i in range(20):
    s = str(i)
    count = cms()
    for d in data:
      count.Inc(d, s)

    print("%d, %d" % (count.Count("workout", s), countHH(count, tags, s)))

  """
      count.Inc(line.rstrip(), s)
      tags.add(line.rstrip())

  heavyHitterThresh = int(count.Total() / 100)
  print("Heavy Hitter Threshold: %d" % heavyHitterThresh)

  for tag in tags:
    if count.Count(tag, s) > heavyHitterThresh:
      hh.add(tag)
      print(tag)
  print(len(hh))
  """

class cms:
  def __init__(self, l : int = 5, b : int = 256, conUpdate : bool = True):
    self.CMS = np.zeros((l, b), dtype=int)
    self.l = l
    self.b = b
    self.total = 0
    self.conUpdate = conUpdate

  def Inc(self, x : str, s : str) -> None:
    self.total += 1
    hx = hashlib.md5((x + s).encode("utf-8")).digest()
    if not self.conUpdate:
      for i in range(self.l):
        self.CMS[i, hx[i] % self.b] += 1
    else:
      minVal = self.CMS[0, hx[0] % self.b]
      for i in range(1, self.l):
        minVal = min(minVal, self.CMS[i, hx[i] % self.b])

      for i in range(self.l):
        if self.CMS[i, hx[i] % self.b] == minVal:
          self.CMS[i, hx[i] % self.b] += 1

  def Count(self, x : str, s : int) -> int:
    hx = hashlib.md5((x + s).encode("utf-8")).digest()
    minCount = self.CMS[0, hx[0] % self.b]

    for i in range(1, self.l):
      minCount = min(minCount, self.CMS[i, hx[i] % self.b])

    return minCount

  def Total(self) -> int:
    return self.total


def getRealCount(data : list[str]) -> (dict[str, int], set[str]):
  realCount = {}
  tags = set()
  for d in data:
    if d not in realCount:
      realCount[d] = 0
    realCount[d] += 1
    tags.add(d)
  
  return realCount, tags

def countHH(count : cms, tags : set[str], s : int) -> int:
  num = 0
  for tag in tags:
    if count.Count(tag, s) > int(count.Total() / 100):
      num += 1
  return num


if __name__ == "__main__":
  main()