Вероятностные структуры

<?php

declare(strict_types=1);

/**
 * HyperLogLog with 2^b registers.
 * Standard error ≈ 1.04 / sqrt(m).
 */
final class HyperLogLog
{
    private const B = 14; // 16384 registers
    private const M = 1 << self::B; // number of registers
    private const ALPHA = 0.7213 / (1 + 1.079 / self::M);

    /** @var list<int> */
    private array $registers;

    public function __construct()
    {
        $this->registers = array_fill(0, self::M, 0);
    }

    public function add(string $item): void
    {
        // 64-bit hash (xxh3 or similar would be better; using fnv1a + seed)
        $hash = hexdec(substr(hash('sha256', $item), 0, 16)); // 64 bits

        // First B bits → register index
        $idx = $hash >> (64 - self::B);

        // Remaining bits, count leading zeros + 1
        $remaining = $hash & ((1 << (64 - self::B)) - 1);
        $w = $this->leadingZeros($remaining, 64 - self::B) + 1;

        if ($w > $this->registers[$idx]) {
            $this->registers[$idx] = $w;
        }
    }

    public function count(): int
    {
        $sum = 0.0;
        foreach ($this->registers as $r) {
            $sum += 2 ** (-$r);
        }
        $estimate = self::ALPHA * self::M * self::M / $sum;

        // Small range correction
        if ($estimate <= 2.5 * self::M) {
            $zeros = count(array_filter($this->registers, fn(int $r): bool => $r === 0));
            if ($zeros > 0) {
                $estimate = self::M * log(self::M / $zeros);
            }
        }

        return (int) round($estimate);
    }

    /** Count leading zeros in a number of $width bits. */
    private function leadingZeros(int $n, int $width): int
    {
        if ($n === 0) {
            return $width;
        }
        $lz = 0;
        for ($i = $width - 1; $i >= 0; $i--) {
            if (($n & (1 << $i)) !== 0) {
                break;
            }
            $lz++;
        }
        return $lz;
    }

    /** Merge another HLL into this one (element-wise max). */
    public function merge(self $other): void
    {
        for ($i = 0; $i < self::M; $i++) {
            if ($other->registers[$i] > $this->registers[$i]) {
                $this->registers[$i] = $other->registers[$i];
            }
        }
    }
}

package hll

import (
	"hash/fnv"
	"math"
)

const (
	b     = 14
	m     = 1 << b
	alpha = 0.7213 / (1.0 + 1.079/float64(m))
)

// HLL is a HyperLogLog cardinality estimator.
type HLL struct {
	registers [m]uint8
}

// New returns an empty HLL.
func New() *HLL { return &HLL{} }

// Add includes an item in the estimate.
func (h *HLL) Add(data []byte) {
	hasher := fnv.New64a()
	_, _ = hasher.Write(data)
	x := hasher.Sum64()

	idx := x >> (64 - b)
	w := x<<b | 1<<(b-1) // push remaining bits to top; add 1-bit sentinel
	lz := uint8(leadingZeros64(w)) + 1
	if lz > h.registers[idx] {
		h.registers[idx] = lz
	}
}

// Count returns estimated cardinality.
func (h *HLL) Count() uint64 {
	sum := 0.0
	zeros := 0
	for _, r := range h.registers {
		sum += math.Pow(2, -float64(r))
		if r == 0 {
			zeros++
		}
	}
	est := alpha * float64(m) * float64(m) / sum

	if est <= 2.5*float64(m) && zeros > 0 {
		est = float64(m) * math.Log(float64(m)/float64(zeros))
	}
	return uint64(math.Round(est))
}

// Merge combines another HLL by element-wise max.
func (h *HLL) Merge(other *HLL) {
	for i := 0; i < m; i++ {
		if other.registers[i] > h.registers[i] {
			h.registers[i] = other.registers[i]
		}
	}
}

func leadingZeros64(x uint64) int {
	if x == 0 {
		return 64
	}
	n := 0
	for x&(1<<63) == 0 {
		n++
		x <<= 1
	}
	return n
}

using System;
using System.Numerics;
using System.Security.Cryptography;
using System.Text;

// HyperLogLog with 2^B registers. Standard error ~= 1.04 / sqrt(M).
public sealed class HyperLogLog
{
    private const int B = 14;          // register index bits
    private const int M = 1 << B;      // 16384 registers
    private static readonly double Alpha = 0.7213 / (1 + 1.079 / M);

    private readonly byte[] _registers = new byte[M];

    public void Add(string item)
    {
        var digest = SHA256.HashData(Encoding.UTF8.GetBytes(item));
        var x = BitConverter.ToUInt64(digest, 0);

        var idx = (int)(x >> (64 - B));
        // Push remaining bits to the top and add a sentinel so the run is bounded.
        var w = (x << B) | (1UL << (B - 1));
        var rank = (byte)(BitOperations.LeadingZeroCount(w) + 1);

        if (rank > _registers[idx])
        {
            _registers[idx] = rank;
        }
    }

    public ulong Count()
    {
        var sum = 0.0;
        var zeros = 0;
        foreach (var r in _registers)
        {
            sum += Math.Pow(2, -r);
            if (r == 0)
            {
                zeros++;
            }
        }

        var estimate = Alpha * M * M / sum;

        // Small-range correction (linear counting).
        if (estimate <= 2.5 * M && zeros > 0)
        {
            estimate = M * Math.Log((double)M / zeros);
        }

        return (ulong)Math.Round(estimate);
    }

    // Merge another HLL element-wise; the sketch is a mergeable monoid.
    public void Merge(HyperLogLog other)
    {
        for (var i = 0; i < M; i++)
        {
            if (other._registers[i] > _registers[i])
            {
                _registers[i] = other._registers[i];
            }
        }
    }
}

from __future__ import annotations

import hashlib
import math

B = 14           # register index bits
M = 1 << B       # 16384 registers
ALPHA = 0.7213 / (1 + 1.079 / M)
MASK64 = (1 << 64) - 1

class HyperLogLog:
    """HyperLogLog cardinality estimator. Standard error ~= 1.04 / sqrt(M)."""

    __slots__ = ("_registers",)

    def __init__(self) -> None:
        # bytearray: one byte per register, ~16 KB total
        self._registers = bytearray(M)

    def add(self, item: bytes) -> None:
        x = int.from_bytes(hashlib.sha256(item).digest()[:8], "big")

        idx = x >> (64 - B)
        # Push remaining bits to the top and add a sentinel so the run is bounded
        w = ((x << B) | (1 << (B - 1))) & MASK64
        rank = 64 - w.bit_length() + 1

        if rank > self._registers[idx]:
            self._registers[idx] = rank

    def count(self) -> int:
        harmonic = sum(2.0 ** -r for r in self._registers)
        estimate = ALPHA * M * M / harmonic

        # Small-range correction (linear counting)
        zeros = self._registers.count(0)
        if estimate <= 2.5 * M and zeros > 0:
            estimate = M * math.log(M / zeros)

        return round(estimate)

    def merge(self, other: "HyperLogLog") -> None:
        """Element-wise max: the sketch is a mergeable monoid."""
        self._registers = bytearray(
            max(a, b) for a, b in zip(self._registers, other._registers)
        )

<?php

declare(strict_types=1);

/**
 * Count-Min Sketch: d rows × w columns of counters.
 * Queries return an upper bound on true frequency.
 */
final class CountMinSketch
{
    /** @var list<list<int>> */
    private array $counters;

    /** @var list<int> */
    private array $seeds;

    public function __construct(
        public readonly int $d,
        public readonly int $w,
    ) {
        $this->counters = array_fill(0, $d, array_fill(0, $w, 0));
        $this->seeds = [];
        for ($i = 0; $i < $d; $i++) {
            $this->seeds[] = (int) hexdec(substr(hash('sha256', "seed:$i"), 0, 8));
        }
    }

    public static function forAccuracy(float $epsilon, float $delta): self
    {
        $w = (int) ceil(M_E / $epsilon);
        $d = (int) ceil(log(1 / $delta));
        return new self($d, $w);
    }

    public function add(string $item, int $count = 1): void
    {
        for ($i = 0; $i < $this->d; $i++) {
            $idx = $this->hash($item, $this->seeds[$i]);
            $this->counters[$i][$idx] += $count;
        }
    }

    public function estimate(string $item): int
    {
        $min = PHP_INT_MAX;
        for ($i = 0; $i < $this->d; $i++) {
            $idx = $this->hash($item, $this->seeds[$i]);
            if ($this->counters[$i][$idx] < $min) {
                $min = $this->counters[$i][$idx];
            }
        }
        return $min;
    }

    private function hash(string $item, int $seed): int
    {
        $h = hexdec(substr(hash('sha256', $item . ':' . $seed), 0, 15));
        return $h % $this->w;
    }
}

package cms

import (
	"hash/fnv"
	"math"
)

// Sketch is a Count-Min Sketch with d rows and w columns.
type Sketch struct {
	d, w     int
	counters [][]uint64
	seeds    []uint64
}

// New creates a sketch for target error ε and confidence δ.
func New(epsilon, delta float64) *Sketch {
	w := int(math.Ceil(math.E / epsilon))
	d := int(math.Ceil(math.Log(1 / delta)))
	counters := make([][]uint64, d)
	seeds := make([]uint64, d)
	for i := range counters {
		counters[i] = make([]uint64, w)
		seeds[i] = uint64(i) * 0x9E3779B97F4A7C15 // golden-ratio seeds
	}
	return &Sketch{d: d, w: w, counters: counters, seeds: seeds}
}

func (s *Sketch) hash(data []byte, seed uint64) int {
	h := fnv.New64a()
	_, _ = h.Write(data)
	sum := h.Sum64() ^ seed
	return int(sum % uint64(s.w))
}

// Add increments count for item.
func (s *Sketch) Add(item []byte) {
	for i := 0; i < s.d; i++ {
		idx := s.hash(item, s.seeds[i])
		s.counters[i][idx]++
	}
}

// Estimate returns the minimum counter across rows (upper bound on true count).
func (s *Sketch) Estimate(item []byte) uint64 {
	min := uint64(math.MaxUint64)
	for i := 0; i < s.d; i++ {
		idx := s.hash(item, s.seeds[i])
		if s.counters[i][idx] < min {
			min = s.counters[i][idx]
		}
	}
	return min
}

using System;
using System.Security.Cryptography;
using System.Text;

// Count-Min Sketch: d rows x w columns of counters.
// Estimates are an upper bound on the true frequency: collisions only add.
public sealed class CountMinSketch
{
    private readonly int _d;
    private readonly int _w;
    private readonly long[][] _counters;
    private readonly ulong[] _seeds;

    public CountMinSketch(int d, int w)
    {
        _d = d;
        _w = w;
        _counters = new long[d][];
        _seeds = new ulong[d];

        for (var i = 0; i < d; i++)
        {
            _counters[i] = new long[w];
            _seeds[i] = (ulong)i * 0x9E3779B97F4A7C15UL; // golden-ratio seeds
        }
    }

    // Build a sketch for target error epsilon and confidence delta.
    public static CountMinSketch ForAccuracy(double epsilon, double delta)
    {
        var w = (int)Math.Ceiling(Math.E / epsilon);
        var d = (int)Math.Ceiling(Math.Log(1 / delta));
        return new CountMinSketch(d, w);
    }

    public void Add(string item, long count = 1)
    {
        for (var i = 0; i < _d; i++)
        {
            _counters[i][Hash(item, _seeds[i])] += count;
        }
    }

    // Estimate returns the minimum counter across rows.
    public long Estimate(string item)
    {
        var min = long.MaxValue;
        for (var i = 0; i < _d; i++)
        {
            min = Math.Min(min, _counters[i][Hash(item, _seeds[i])]);
        }
        return min;
    }

    private int Hash(string item, ulong seed)
    {
        var digest = SHA256.HashData(Encoding.UTF8.GetBytes(item));
        var sum = BitConverter.ToUInt64(digest, 0) ^ seed;
        return (int)(sum % (ulong)_w);
    }
}

from __future__ import annotations

import hashlib
import math

GOLDEN_RATIO = 0x9E3779B97F4A7C15

class CountMinSketch:
    """Count-Min Sketch: d rows x w columns of counters.

    Estimates are an upper bound on the true frequency: collisions only add.
    """

    __slots__ = ("d", "w", "_counters", "_seeds")

    def __init__(self, d: int, w: int) -> None:
        self.d = d
        self.w = w
        self._counters: list[list[int]] = [[0] * w for _ in range(d)]
        self._seeds = [i * GOLDEN_RATIO for i in range(d)]

    @classmethod
    def for_accuracy(cls, epsilon: float, delta: float) -> "CountMinSketch":
        """Size the sketch for target error epsilon and confidence delta."""
        w = math.ceil(math.e / epsilon)
        d = math.ceil(math.log(1 / delta))
        return cls(d, w)

    def add(self, item: bytes, count: int = 1) -> None:
        for row, seed in zip(self._counters, self._seeds):
            row[self._hash(item, seed)] += count

    def estimate(self, item: bytes) -> int:
        """Return the minimum counter across rows."""
        return min(
            row[self._hash(item, seed)]
            for row, seed in zip(self._counters, self._seeds)
        )

    def _hash(self, item: bytes, seed: int) -> int:
        digest = hashlib.sha256(item).digest()[:8]
        return (int.from_bytes(digest, "big") ^ seed) % self.w