Module: DSR::Recognizer

Defined in:

lib/dsr/recognizer.rb

Class Method Summary

• .detect_distant_groups(_array, goal: nil, ratio: nil) {|item| ... } ⇒ Object

  sorts an array by a block and splits in chunks gauranteed to split into at least two chunks if you pass ratio then recursively splits if there is another gap_size > prev_gap_size * ratio if you pass goal then tries ratios from 0.0 to 1.0 to find the goal number of chunks if you pass nothing then it uses PCBR to chose the ratio for both goal and nothing variants it checks the result to be the same for all fitting ratios ratio: 0 is effectively the same as just Ruby stdlib sort and chunk by block.

• .detect_many_after_many(keys, values, &block) ⇒ Hash{Object => Array<Object>}

  joins two arrays of objects into a Hash of parents and children, sorted by passed block it is possible for parent to have no children examples: Discord search results HTML page -- based on node.rect.y, channel names become keys, messages become values.

• .injective_mapping(domain, codomain) {|domain_item,| ... } ⇒ Array<Array(Object, Object)>

  https://en.wikipedia.org/wiki/Injective_function picks the closest item from codomain for each domain element raises exception if picks intersect.

Class Method Details

.detect_distant_groups(_array, goal: nil, ratio: nil) {|item| ... } ⇒ Object

sorts an array by a block and splits in chunks gauranteed to split into at least two chunks if you pass ratio then recursively splits if there is another gap_size > prev_gap_size * ratio if you pass goal then tries ratios from 0.0 to 1.0 to find the goal number of chunks if you pass nothing then it uses PCBR to chose the ratio for both goal and nothing variants it checks the result to be the same for all fitting ratios ratio: 0 is effectively the same as just Ruby stdlib sort and chunk by block

Parameters:

• _array (Array<Object>)
• ratio (Float) (defaults to: nil)
• goal (Integer) (defaults to: nil)

Yield Parameters:

• item (Object) —

  an item of _array

Yield Returns:

• (Numeric) —

  something that can subtract from each other to measure a gap

# File 'lib/dsr/recognizer.rb', line 62

def self.detect_distant_groups _array, goal: nil, ratio: nil

  array = ::Struct.new(:item, :value, :i, :dist_left).then do |struct|
    _array.map{ |e| struct.new e, yield(e) }.sort_by(&:value)
  end
  array.each_with_index{ |e, i| e.i = i }
  array.each_cons(2){ |e1, e2| e2.dist_left = e2.value - e1.value }
  f = lambda do |from, to, r: ratio, threshold: 0|
    # next [] if from > to
    next [[array[from]]] if from == to
    max = array[from + 1..to].max_by(&:dist_left)
    # next [] unless max
    if threshold * r < max.dist_left
      [*f[from, max.i - 1, r: r, threshold: max.dist_left], *f[max.i, to, r: r, threshold: max.dist_left]]
    else
      [array[from..to]]
    end
  end

  if ratio
    f[0, array.size - 1].map{ |_| _.map &:item }
  elsif goal
    0.step(1, 0.01).map do |r|
      f[0, array.size - 1, r: r].map{ |_| _.map &:item }
    end.tap do |ratios|
      fail unless ratios.first.size == array.map(&:value).uniq.size
      ratios.each_cons(2){ |a, b| fail if a.size < b.size }
    end.select{ |_| _.size == goal }.tap do |splits|
      fail if 1 < splits.uniq.size
    end.first
  else
    require "pcbr"
    pcbr = ::PCBR.new
    0.step(1, 0.01).map.with_index do |r, i|
      [i, f[0, array.size - 1, r: r].map{ |_| _.map &:item }]
    end.tap do |ratios|
      fail unless ratios.first.last.size == array.map(&:value).uniq.size
      ratios.each_cons(2){ |(_, a), (_, b)| fail if a.size < b.size }
    end.chunk{ |_, split| split.size }.each do |_, splits|
      # v = [splits.first.first, splits.size]
      v = [
        splits.first.first,
        -splits.map(&:last).mean do |split|
          split.map(&:size).then do |sizes|
            sizes.map do |size|
              (sizes.max - sizes.min).then do |_|
                # otherwise it makes Infinity, then NaN
                _.zero? ? size : size.fdiv(_)
              end
            end.then do |sizes|
              # σ²
              sizes.mean{ |_| (_ - sizes.mean) ** 2 }
            end
          end
        end
      ]
      pcbr.store splits.map(&:last), v
    end
    (best, _, score) = pcbr.table.reverse.max_by(&:last)
    fail unless 0 < score
    fail if 1 < best.uniq.size
    best.first
  end

end

.detect_many_after_many(keys, values, &block) ⇒ Hash{Object => Array<Object>}

joins two arrays of objects into a Hash of parents and children, sorted by passed block it is possible for parent to have no children examples:

Discord search results HTML page -- based on `node.rect.y`, channel names become keys, messages become values

Parameters:

• keys (Array) —

  these become keys

• values (Array) —

  these become values

Returns:

• (Hash{Object => Array<Object>}) —

  Hash=> Array