Fuzzy scoring algorithm adopted from Selecta as used on GitHub.com

fuzzy.coffee

# Get the shortest match (least distance between start and end index) for all
# the query characters in the given text.
#
# Returns an array in format [firstIndex, matchLength, [matchIndexes]]
shortestMatch = (text, queryChars) ->
  starts = allIndexesOf(text, queryChars[0])

  return if starts.length is 0
  return [starts[0], 1, []] if queryChars.length is 1

  match = null
  for start in starts when indexes = indexesOfChars(text, queryChars, start + 1)
    length = indexes[indexes.length - 1] - start
    match = [start, length, indexes] if !match or length < match[1]

  return match

# Find all indexes of character inside a string.
allIndexesOf = (string, char) ->
  index = 0
  index++ while (index = string.indexOf(char, index)) > -1

# Find all indexes of characters of query string in order.
indexesOfChars = (string, chars, index) ->
  indexes = []
  for i in [1...chars.length]
    index = string.indexOf(chars[i], index)
    return if index is -1
    indexes.push index++
  indexes

fixedMaxScore = -> 2.0

# Initializes the scorer object by preparing the query.
#
# Returns an object with the `score` method that takes text to be scored
# against the query.
fuzzyScorer = (query) ->
  if query
    queryChars = query.toLowerCase().split("")
    score = (text) ->
      return 0.0 unless text
      match = shortestMatch(text, queryChars)
      return 0.0 unless match

      # Penalize matches that are more spread apart
      value = query.length / match[1]
      # Penalize matches further from the beginning of string
      value = value / (match[0]/2 + 1)
  else
    score = fixedMaxScore

  return {score}