def overlap_join(query_feature_set, tau, db, y_size)
      memoized_get_fn_results = query_feature_set.reduce({}) {|memo, feature| memo[feature] = get(db, y_size, feature); memo }
      query_feature_set_size = query_feature_set.size
      sorted_features = query_feature_set.sort_by {|feature| memoized_get_fn_results[feature].size }
      m = {}
      (0..(query_feature_set_size - tau)).each do |k|
        memoized_get_fn_results[sorted_features[k]].each do |s|
          m[s] ||= 0
          m[s] += 1
        end
      end
      r = []
      ((query_feature_set_size - tau + 1)..(query_feature_set_size - 1)).each do |k|
        candidate_matching_strings = m.keys
        candidate_matching_strings.each do |s|
          m[s] ||= 0
          if memoized_get_fn_results[sorted_features[k]].include?(s)
            m[s] += 1
          end
          if tau <= m[s]
            r << s
            m.delete(s)
          elsif m[s] + (query_feature_set_size - k - 1) < tau
            m.delete(s)
          end
        end
      end
      r
    end
def overlap_join(query_feature_set, tau, db, y_size)
      memoized_get_fn_results = query_feature_set.reduce({}) {|memo, feature| memo[feature] = get(db, y_size, feature); memo }
      query_feature_set_size = query_feature_set.size
      sorted_features = query_feature_set.sort_by {|feature| memoized_get_fn_results[feature].size }
      m = {}
      (0..(query_feature_set_size - tau)).each do |k|
        memoized_get_fn_results[sorted_features[k]].each do |s|
          m[s] ||= 0
          m[s] += 1
        end
      end
      r = []
      ((query_feature_set_size - tau + 1)..(query_feature_set_size - 1)).each do |k|
        candidate_matching_strings = m.keys
        candidate_matching_strings.each do |s|
          m[s] ||= 0
          if memoized_get_fn_results[sorted_features[k]].include?(s)
            m[s] += 1
          end
          if tau <= m[s]
            r << s
            m.delete(s)
          elsif m[s] + (query_feature_set_size - k - 1) < tau
            m.delete(s)
          end
        end
      end
      r
    end
implements "Algorithm 3: CPMerge algorithm" described in "Simple and Efficient Algorithm for Approximate Dictionary Matching" (see http://www.aclweb.org/anthology/C10-1096)