<commit_before># Easy Perfect Minimal Hashing
# By <NAME>
#
# Based on:
# Steve Hanov: http://stevehanov.ca/blog/index.php?id=119
# <NAME>, <NAME>, <NAME> and <NAME>, 
# "Practical minimal perfect hash functions for large databases", CACM, 35(1):105-121
# also a good reference:
# Compress, Hash, and Displace algorithm by <NAME>,
# <NAME>, and <NAME>

class MinPerfHash
  FNV_MAGIC_NUM = 0x01000193

  # Calculates a distinct hash function for a given string. Each value of the
  # integer d results in a different hash value.
  def hash(d, s)
    d = FNV_MAGIC_NUM if d == 0
    # Use the FNV algorithm from http://isthe.com/chongo/tech/comp/fnv/ 
    s.each_codepoint do |c|
      d = ((d * FNV_MAGIC_NUM) ^ c) & 0xffffffff
    end

    d
  end

  # Take a Ruby hash and create a minimal perfect hash.
  def initialize(h)
    size = h.size

    buckets = Array.new(size) {[]}
    intermediate = Array.new(size) {0}
    values = Array.new(size) {[nil]}

    # Step 1: Place all of the keys into buckets
    h.keys.each do |key|
      buckets[hash(0, key) % size] << key
    end

    # Step 2: Sort the buckets and process the ones with the most items first.
    buckets.sort_by! {|arr| arr.size}

    buckets.each do |bucket|
      break if bucket.size <= 1

      d, item, slots = 1, 0, []

      # Repeatedly try different values of d until we find a hash function
      # that places all items in the bucket into free slots
      while item < bucket.size
        slot = hash(d, bucket[item]) % size
        if !values[slot].nil? or slots.include? slot
          d += 1
          item, slots = 0, []
        else
          slots << slot
          item += 1
        end
      end

      intermediate[hash(0, bucket[0]) % size] = d

      # Finally store the values from this bucket
      (0...bucket.size).each do |i|
        values[slots[i]] = h[bucket[i]]
      end
    end

    # Only buckets with 1 item remain. Process them more quickly by directly
    # placing them into a free slot. Use a negative value of d to indicate
    # this.
    freelist = []
    (0...size).each do |i|
      freelist << i if values[i].nil?
    end

    #for 
      
  end
end<commit_msg>Working for hashes with size > 2...<commit_after># Easy Perfect Minimal Hashing
# By <NAME>
#
# Based on:
# <NAME>: http://stevehanov.ca/blog/index.php?id=119
# <NAME>, <NAME>, <NAME> and <NAME>, 
# "Practical minimal perfect hash functions for large databases", CACM, 35(1):105-121
# also a good reference:
# Compress, Hash, and Displace algorithm by <NAME>,
# <NAME>, and <NAME>

class MinPerfHash
  FNV_MAGIC_NUM = 0x01000193

  # Calculates a distinct hash function for a given string. Each value of the
  # integer d results in a different hash value.
  def hash(d, s)
    d = FNV_MAGIC_NUM if d == 0
    # Use the FNV algorithm from http://isthe.com/chongo/tech/comp/fnv/ 
    s.each_codepoint do |c|
      d = ((d * FNV_MAGIC_NUM) ^ c) & 0xffffffff
    end

    d
  end

  def [](key)
    d = @intermediate[hash(0, key) % @intermediate.size]
    return @values[-d - 1] if d < 0
    return @values[hash(d, key) % @values.size]
  end

  # Take a Ruby hash and create a minimal perfect hash.
  def initialize(h)
    size = h.size

    buckets = Array.new(size) {[]}
    @intermediate = Array.new(size) {0}
    @values = Array.new(size) {nil}

    # Step 1: Place all of the keys into buckets
    h.keys.each do |key|
      buckets[hash(0, key) % size] << key
    end

    # Step 2: Sort the buckets and process the ones with the most items first.
    buckets.sort_by! {|arr| arr.size}

    while (bucket = buckets.pop).size > 1
      d, item, slots = 1, 0, []
      puts "hello"

      # Repeatedly try different values of d until we find a hash function
      # that places all items in the bucket into free slots
      while item < bucket.size
        puts item
        puts slot = hash(d, bucket[item]) % size
        p !@values[slot].nil?
        p slots
        if !@values[slot].nil? or slots.include? slot
          d += 1
          item, slots = 0, []
        else
          slots << slot
          item += 1
        end
      end

      @intermediate[hash(0, bucket[0]) % size] = d

      # Finally store the values from this bucket
      (0...bucket.size).each do |i|
        @values[slots[i]] = h[bucket[i]]
      end
    end

    # Only buckets with 1 item remain. Process them more quickly by directly
    # placing them into a free slot. Use a negative value of d to indicate
    # this.
    freelist = []
    (0...size).each do |i|
      freelist << i if @values[i].nil?
    end

    buckets.each do |bucket|
      break if bucket.size == 0
      slot = freelist.pop
      @intermediate[hash(0, bucket[0]) % size] = -slot - 1
      @values[slot] = h[bucket[0]]
    end
  end
end
{'fraction_non_alphanumeric': 0.11360301823517083, 'fraction_numerical': 0.01781597149444561, 'mean_word_length': 2.3417366946778713, 'pattern_counts': {'":': 0, '<': 36, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6046382', 'n_tokens_mistral': 1655, 'n_tokens_neox': 1556, 'n_words': 566}