Class: MiniFTS

Inherits:
Object
  • Object
show all
Defined in:
lib/minifts.rb,
lib/minifts/version.rb,
lib/minifts/searchable_map.rb

Overview

A tiny, dependency-free full-text search engine, held entirely in memory.

This is a Ruby port of the JavaScript MiniSearch library, preserving its BM25+ scoring, prefix and fuzzy matching, query combinators, auto-suggestions, and JSON index format (indexes are interchangeable with the JS library).

The public API mirrors the original, translated to Ruby conventions: options are passed as a Hash with snake_case symbol keys, callables are anything responding to call (lambdas, procs, method objects), and field names are strings.

Examples:

ms = MiniFTS.new(fields: ["title", "text"], store_fields: ["title"])
ms.add_all([
  { "id" => 1, "title" => "Moby Dick",   "text" => "Call me Ishmael" },
  { "id" => 2, "title" => "Neuromancer", "text" => "The sky above the port" },
])
ms.search("ishmael")       # => [{ id: 1, score: ..., ... }]
ms.search("neuro", prefix: true)

Defined Under Namespace

Classes: Error, SearchableMap

Constant Summary collapse

OR =

Combination operators.

"or"
AND = 
"and"
AND_NOT = 
"and_not"
WILDCARD =

The special value passed to #search to match every document.

Object.new
VERSION = 
"1.0.0"
DEFAULT_BM25_PARAMS =

BM25+ scoring parameters (see #search).

{ k: 1.2, b: 0.7, d: 0.5 }.freeze
SPACE_OR_PUNCTUATION =

This regular expression matches any Unicode space, newline, or punctuation character. It mirrors the JavaScript source's SPACE_OR_PUNCTUATION.

/[\n\r\p{Z}\p{P}]+/.freeze
DEFAULT_TOKENIZE =

Default tokenizer: split on whitespace and punctuation. Mirrors JavaScript's String.prototype.split, which keeps leading/trailing empty tokens (limit -1) and yields [""] for the empty string.

lambda do |text, _field_name = nil|
  text.empty? ? [""] : text.split(SPACE_OR_PUNCTUATION, -1)
end
DEFAULT_PROCESS_TERM =

Default term processor: downcase. Ruby performs full Unicode case folding.

lambda do |term, _field_name = nil|
  term.downcase
end
DEFAULT_EXTRACT_FIELD =

Default field extractor: index documents as Hashes keyed by field name.

lambda do |document, field_name|
  document[field_name]
end
DEFAULT_STRINGIFY_FIELD =

Default field stringifier.

lambda do |field_value, _field_name|
  field_value.to_s
end
DEFAULT_LOGGER =

Default logger: write warnings to $stderr.

lambda do |level, message, _code = nil|
  warn("[minifts] #{level}: #{message}")
end
DEFAULT_OPTIONS = 
{
  id_field: "id",
  extract_field: DEFAULT_EXTRACT_FIELD,
  stringify_field: DEFAULT_STRINGIFY_FIELD,
  tokenize: DEFAULT_TOKENIZE,
  process_term: DEFAULT_PROCESS_TERM,
  fields: nil,
  search_options: nil,
  store_fields: [],
  logger: DEFAULT_LOGGER,
  auto_vacuum: true
}.freeze
DEFAULT_SEARCH_OPTIONS = 
{
  combine_with: OR,
  prefix: false,
  fuzzy: false,
  max_fuzzy: 6,
  boost: {},
  weights: { fuzzy: 0.45, prefix: 0.375 },
  bm25: DEFAULT_BM25_PARAMS
}.freeze
DEFAULT_AUTO_SUGGEST_OPTIONS = 
{
  combine_with: AND,
  prefix: ->(_term, i, terms) { i == terms.length - 1 }
}.freeze
DEFAULT_VACUUM_OPTIONS = 
{ batch_size: 1000, batch_wait: 10 }.freeze
DEFAULT_VACUUM_CONDITIONS = 
{ min_dirt_factor: 0.1, min_dirt_count: 20 }.freeze
DEFAULT_AUTO_VACUUM_OPTIONS = 
DEFAULT_VACUUM_OPTIONS.merge(DEFAULT_VACUUM_CONDITIONS).freeze

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options = {}) ⇒ MiniFTS

Returns a new instance of MiniFTS.

Parameters:

  • options (Hash) (defaults to: {}) —

    configuration. :fields (an Array of field-name strings to index) is required. See the README for the full list.

Raises:



122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/minifts.rb', line 122

def initialize(options = {})
  raise Error, 'MiniFTS: option "fields" must be provided' if options[:fields].nil?

  auto_vacuum =
    if options[:auto_vacuum].nil? || options[:auto_vacuum] == true
      DEFAULT_AUTO_VACUUM_OPTIONS
    else
      options[:auto_vacuum]
    end

  @options = DEFAULT_OPTIONS.merge(options)
  @options[:auto_vacuum] = auto_vacuum
  @options[:search_options] = DEFAULT_SEARCH_OPTIONS.merge(options[:search_options] || {})
  @options[:auto_suggest_options] = DEFAULT_AUTO_SUGGEST_OPTIONS.merge(options[:auto_suggest_options] || {})

  reset_index
  add_fields(@options[:fields])
end

Instance Attribute Details

#dirt_count ⇒ Integer (readonly)

Returns documents discarded since the last vacuum.

Returns:

  • (Integer) —

    documents discarded since the last vacuum



297
298
299
 
# File 'lib/minifts.rb', line 297

def dirt_count
  @dirt_count
end

#document_count ⇒ Integer (readonly)

Returns number of searchable documents.

Returns:

  • (Integer) —

    number of searchable documents



305
306
307
 
# File 'lib/minifts.rb', line 305

def document_count
  @document_count
end

Class Method Details

.get_default(option_name) ⇒ Object

Returns the default value of a constructor option, or raises for unknown names.

Raises:



395
396
397
398
399
400
 
# File 'lib/minifts.rb', line 395

def self.get_default(option_name)
  key = option_name.to_sym
  raise Error, "MiniFTS: unknown option \"#{option_name}\"" unless DEFAULT_OPTIONS.key?(key)

  DEFAULT_OPTIONS[key]
end

.load(js, options) ⇒ Object

Deserializes an already-parsed plain-object index (string keys), given the same options originally used.



450
451
452
453
454
455
456
457
458
459
 
# File 'lib/minifts.rb', line 450

def self.load(js, options)
  serialization_version = js["serializationVersion"]
  unless [1, 2].include?(serialization_version)
    raise Error, "MiniFTS: cannot deserialize an index created with an incompatible version"
  end

  ms = new(options)
  ms.send(:load_plain_object, js)
  ms
end

.load_json(json, options = {}) ⇒ Object

Deserializes a JSON index produced by #to_json (or by the JS library), given the same options originally used.

Raises:



442
443
444
445
446
 
# File 'lib/minifts.rb', line 442

def self.load_json(json, options = {})
  raise Error, "MiniFTS: loadJSON should be given the same options used when serializing the index" if options.nil?

  load(JSON.parse(json), options)
end

.wildcard ⇒ Object

The wildcard symbol, mirroring MiniSearch.wildcard.



116
117
118
 
# File 'lib/minifts.rb', line 116

def self.wildcard
  WILDCARD
end

Instance Method Details

#add(document) ⇒ Object

Adds a document to the index.

Raises:



142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
# File 'lib/minifts.rb', line 142

def add(document)
  extract_field = @options[:extract_field]
  stringify_field = @options[:stringify_field]
  tokenize = @options[:tokenize]
  process_term = @options[:process_term]

  id = extract_field.call(document, @options[:id_field])
  raise Error, "MiniFTS: document does not have ID field \"#{@options[:id_field]}\"" if id.nil?
  raise Error, "MiniFTS: duplicate ID #{id}" if @id_to_short_id.key?(id)

  short_document_id = add_document_id(id)
  save_stored_fields(short_document_id, document)

  @options[:fields].each do |field|
    field_value = extract_field.call(document, field)
    next if field_value.nil?

    tokens = tokenize.call(stringify_field.call(field_value, field), field)
    field_id = @field_ids[field]

    unique_terms = tokens.uniq.length
    add_field_length(short_document_id, field_id, @document_count - 1, unique_terms)

    tokens.each do |term|
      processed_term = process_term.call(term, field)
      if processed_term.is_a?(Array)
        processed_term.each { |t| add_term(field_id, short_document_id, t) }
      elsif truthy?(processed_term)
        add_term(field_id, short_document_id, processed_term)
      end
    end
  end

  nil
end

#add_all(documents) ⇒ Object

Adds all the given documents to the index.



179
180
181
182
 
# File 'lib/minifts.rb', line 179

def add_all(documents)
  documents.each { |document| add(document) }
  nil
end

#as_plain_object ⇒ Object

Serializes the index to a plain Hash matching the JavaScript AsPlainObject shape (string keys, serializationVersion: 2).



404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
 
# File 'lib/minifts.rb', line 404

def as_plain_object
  index = []
  @index.each do |term, field_index|
    data = {}
    # JavaScript objects iterate integer-like keys in ascending numeric order,
    # so JSON.stringify emits a term's field ids sorted; Ruby Hashes preserve
    # insertion order (a term first seen in a higher field would otherwise
    # serialize its field ids out of order). Sort to stay byte-identical.
    field_index.keys.sort.each { |field_id| data[field_id] = field_index[field_id] }
    index.push([term, data])
  end

  {
    "documentCount" => @document_count,
    "nextId" => @next_id,
    "documentIds" => @document_ids,
    "fieldIds" => @field_ids,
    "fieldLength" => @field_length,
    "averageFieldLength" => @avg_field_length,
    "storedFields" => @stored_fields,
    "dirtCount" => @dirt_count,
    "index" => index,
    "serializationVersion" => 2
  }
end

#auto_suggest(query_string, options = {}) ⇒ Object

Provides auto-suggestions for query_string: modified queries derived from it, each with a relevance score, sorted by descending score. By default prefix-searches the last term and combines terms with AND.



369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/minifts.rb', line 369

def auto_suggest(query_string, options = {})
  options = @options[:auto_suggest_options].merge(options)

  suggestions = {}

  search(query_string, options).each do |result|
    terms = result[:terms]
    phrase = terms.join(" ")
    suggestion = suggestions[phrase]
    if suggestion
      suggestion[:score] += result[:score]
      suggestion[:count] += 1
    else
      suggestions[phrase] = { score: result[:score], terms: terms, count: 1 }
    end
  end

  results = []
  suggestions.each do |suggestion, data|
    results.push(suggestion: suggestion, terms: data[:terms], score: data[:score].fdiv(data[:count]))
  end

  sort_by_score(results)
end

#dirt_factor ⇒ Float

Returns a 0..1 indication of how many index references are obsolete.

Returns:

  • (Float) —

    a 0..1 indication of how many index references are obsolete



300
301
302
 
# File 'lib/minifts.rb', line 300

def dirt_factor
  @dirt_count.fdiv(1 + @document_count + @dirt_count)
end

#discard(id) ⇒ Object

Discards the document with the given ID: it stops appearing in searches immediately, but its references are cleaned from the index lazily (on the next search that encounters them, or by #vacuum). Only needs the ID.

Raises:



243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
 
# File 'lib/minifts.rb', line 243

def discard(id)
  short_id = @id_to_short_id[id]
  raise Error, "MiniFTS: cannot discard document with ID #{id}: it is not in the index" if short_id.nil?

  @id_to_short_id.delete(id)
  @document_ids.delete(short_id)
  @stored_fields.delete(short_id)

  (@field_length[short_id] || []).each_with_index do |field_length, field_id|
    next if field_length.nil?

    remove_field_length(short_id, field_id, @document_count, field_length)
  end

  @field_length.delete(short_id)
  @document_count -= 1
  @dirt_count += 1

  maybe_auto_vacuum
  nil
end

#discard_all(ids) ⇒ Object

Discards several documents, triggering at most one automatic vacuum at the end.



266
267
268
269
270
271
272
273
274
275
276
277
 
# File 'lib/minifts.rb', line 266

def discard_all(ids)
  auto_vacuum = @options[:auto_vacuum]
  begin
    @options[:auto_vacuum] = false
    ids.each { |id| discard(id) }
  ensure
    @options[:auto_vacuum] = auto_vacuum
  end

  maybe_auto_vacuum
  nil
end

#get_stored_fields(id) ⇒ Hash?

Returns the stored fields for the given document ID, or nil.

Returns:

  • (Hash, nil) —

    the stored fields for the given document ID, or nil



318
319
320
321
322
323
 
# File 'lib/minifts.rb', line 318

def get_stored_fields(id)
  short_id = @id_to_short_id[id]
  return nil if short_id.nil?

  @stored_fields[short_id]
end

#has?(id) ⇒ Boolean

Returns whether a document with the given ID is present and searchable.

Returns:

  • (Boolean) —

    whether a document with the given ID is present and searchable



313
314
315
 
# File 'lib/minifts.rb', line 313

def has?(id)
  @id_to_short_id.key?(id)
end

#remove(document) ⇒ Object

Removes the given document from the index. The document must NOT have changed since indexing, or the index can be corrupted. Requires the full document; see #discard for an ID-only alternative.

Raises:



187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
 
# File 'lib/minifts.rb', line 187

def remove(document)
  tokenize = @options[:tokenize]
  process_term = @options[:process_term]
  extract_field = @options[:extract_field]
  stringify_field = @options[:stringify_field]

  id = extract_field.call(document, @options[:id_field])
  raise Error, "MiniFTS: document does not have ID field \"#{@options[:id_field]}\"" if id.nil?

  short_id = @id_to_short_id[id]
  raise Error, "MiniFTS: cannot remove document with ID #{id}: it is not in the index" if short_id.nil?

  @options[:fields].each do |field|
    field_value = extract_field.call(document, field)
    next if field_value.nil?

    tokens = tokenize.call(stringify_field.call(field_value, field), field)
    field_id = @field_ids[field]

    unique_terms = tokens.uniq.length
    remove_field_length(short_id, field_id, @document_count, unique_terms)

    tokens.each do |term|
      processed_term = process_term.call(term, field)
      if processed_term.is_a?(Array)
        processed_term.each { |t| remove_term(field_id, short_id, t) }
      elsif truthy?(processed_term)
        remove_term(field_id, short_id, processed_term)
      end
    end
  end

  @stored_fields.delete(short_id)
  @document_ids.delete(short_id)
  @id_to_short_id.delete(id)
  @field_length.delete(short_id)
  @document_count -= 1
  nil
end

#remove_all(documents = NO_DOCUMENTS) ⇒ Object

Removes the given documents. Called with no argument, removes ALL documents (faster than passing them all).



229
230
231
232
233
234
235
236
237
238
 
# File 'lib/minifts.rb', line 229

def remove_all(documents = NO_DOCUMENTS)
  if documents.equal?(NO_DOCUMENTS)
    reset_index
  elsif documents.nil?
    raise Error, "Expected documents to be present. Omit the argument to remove all documents."
  else
    documents.each { |document| remove(document) }
  end
  nil
end

#replace(updated_document) ⇒ Object

Replaces an existing document with an updated version (same ID). Equivalent to #discard followed by #add.



281
282
283
284
285
286
 
# File 'lib/minifts.rb', line 281

def replace(updated_document)
  id = @options[:extract_field].call(updated_document, @options[:id_field])
  discard(id)
  add(updated_document)
  nil
end

#search(query, search_options = {}) ⇒ Array<Hash>

Searches for documents matching query.

Parameters:

  • query (String, Hash, Object) —

    a query string, a combination Hash with a :queries key, or WILDCARD

  • search_options (Hash) (defaults to: {}) —

    per-search options overriding the defaults

Returns:

  • (Array<Hash>) —

    results sorted by descending score. Each is a Hash with :id, :score, :terms (matched document terms), :query_terms, :match, plus any stored fields (under their string keys).



333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
 
# File 'lib/minifts.rb', line 333

def search(query, search_options = {})
  search_options_with_defaults = @options[:search_options].merge(search_options)

  raw_results = execute_query(query, search_options)
  results = []

  raw_results.each do |doc_id, data|
    terms = data[R_TERMS]
    quality = terms.empty? ? 1 : terms.length

    match = data[R_MATCH]
    result = {
      id: @document_ids[doc_id],
      score: data[R_SCORE] * quality,
      terms: match.keys,
      query_terms: terms,
      match: match
    }

    stored = @stored_fields[doc_id]
    result.merge!(stored) if stored

    filter = search_options_with_defaults[:filter]
    results.push(result) if filter.nil? || filter.call(result)
  end

  # For a wildcard query with no document boost, every score is equal, so
  # there is no point sorting.
  return results if wildcard_query?(query) && search_options_with_defaults[:boost_document].nil?

  sort_by_score(results)
end

#term_count ⇒ Integer

Returns number of distinct terms in the index.

Returns:

  • (Integer) —

    number of distinct terms in the index



308
309
310
 
# File 'lib/minifts.rb', line 308

def term_count
  @index.size
end

#to_json(*args) ⇒ Object

Serializes the index to a JSON string. Integer keys are rendered as strings, and whole-valued averageFieldLength entries as integers, producing output byte-interchangeable with the JavaScript library (see #whole_float_as_integer).



434
435
436
437
438
 
# File 'lib/minifts.rb', line 434

def to_json(*args)
  plain = as_plain_object
  plain["averageFieldLength"] = plain["averageFieldLength"].map { |value| whole_float_as_integer(value) }
  plain.to_json(*args)
end

#vacuum(_options = {}) ⇒ Object

Cleans up references to discarded documents from the inverted index. In this Ruby port vacuuming is synchronous (there is no main thread to protect), so the +batch_size+/+batch_wait+ options are accepted but ignored.



291
292
293
294
 
# File 'lib/minifts.rb', line 291

def vacuum(_options = {})
  perform_vacuuming
  nil
end