ulrik@kaizer.se/
log

-- relevance.lua
-- Copyright (C) 2009--2010 Ulrik Sverdrup <ulrik.sverdrup@gmail.com>
--               2008  Christian Hergert <chris@dronelabs.com>
--               2007  Chris Halse Rogers, DR Colkitt
--                     David Siegel, James Walker
--                     Jason Smith, Miguel de Icaza
--                     Rick Harding, Thomsen Anders
--                     Volker Braun, Jonathon Anderson
--
-- This program is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program.  If not, see <http://www.gnu.org/licenses/>.

-- Ported to Lua 5.1 by Ulrik Sverdrup


-- Take all builtins we need
local sub = string.sub
local find = string.find

-- If being executed as script, return true
local function is_script()
  return arg and arg[0]:find("relevance.lua", 1, true)
end

if not is_script() then
  module(...)
end

--[[
-- score (s, q)
--  A relevancy score for the string ranging from 0 to 1

--  @s: a string to be scored
--  @q: a string query to score against

--  `s' and `query' are interpreted literally, including case and whitespace.

--  Returns: a number between 0 and 1
--]]
local doctest_score = [[
  = score('terminal', 'trml')
  0.73509868421053
  = score('terminal', 'term')
  0.99230263157895
  = score('terminal', 'try')
  0
  = score('terminal', '')
  1
]]

function score(s, q)
  local qlen = #q
  local slen = #s

  if qlen == 0 then
    return 1
  end

  -- we don't lowercase here in the lua version
  local ls = s

  -- Find the shortest possible substring that matches the query
  -- and get the ratio of their lengths for a base score
  first, last = find_best_match(ls, q)
  if first == -1 then
    return 0
  end

  local score = qlen / (last - first + 1)

  -- Now we weight by string length so shorter strings are better
  score = score * (0.7 + qlen/slen * 0.3)
  -- Bonus points if the characters start words
  local good = 0
  local bad = 1
  local firstCount = 0
  for i = first, last do
    local lsi = sub(ls, i, i)
    if lsi == " " or lsi == "-" then
      if find(q, sub(ls, i+1, i+1), 1, true) then
        firstCount = firstCount + 1
      else
        bad = bad + 1
      end
    end
  end
  -- A first character match counts extra
  if sub(q, 1, 1) == sub(ls, 1, 1) then
    firstCount = firstCount + 2
  end

  -- The longer the acronym, the better it scores
  good = good + firstCount * firstCount * 4

  -- Better yet if the match itself started there
  if first == 1 then
    good = good + 2
  end

  -- Super duper bonus if it is a perfect match
  if query == ls then
    good = good + last*2 + 4
  end

  score = (score + 3 * good / (good + bad)) / 4

  -- This fix makes sure that perfect matches always rank higher
  -- than split matches.  Perfect matches get the .9 - 1.0 range
  -- everything else lower

  if last - first + 1 == qlen then
    score = .9 + .1 * score
  else
    score = .9 * score
  end

  return score
end


--[[
--  find_best_match(s, q)
--
--  Finds the shortest substring of @s that contains all characters of @q
--  in order.
--
--  @s: a string to search
--  @q: a string query to search for
--
--  Returns: a two-item tuple containing the start and end indicies of
--           the match.  No match returns (-1,-1).
--]]

local doctest_find_best_match = [[
  = find_best_match('terminal', 'trml')
  1       8
  = find_best_match('total told', 'tl')
  3       5
  = find_best_match('terminal', 'yl')
  -1       -1
  = find_best_match('terminal', 't')
  1       1
]]

function find_best_match(s, q)
  local qlen = #q
  local first, last = -1, -1
  local index = find(s, sub(q, 1, 1), 1, true)
  while index do
    -- See if we can fit the whole query into the tail of s
    -- We already know where the first char of q is in s (@index),
    -- so we start with char number two.
    local cur = index
    for qcur = 2, qlen do
      cur = find(s, sub(q, qcur, qcur), cur + 1, true)
      if not cur then
        return first, last
      end
    end

    -- take match if it is shorter
    -- if perfect match, we are done
    if first == -1 or (cur - index < (last - first)) then
      first, last = index, cur
      if (cur - index + 1) == qlen then
        break
      end
    end
    index = find(s, sub(q, 1, 1), index+1, true)
  end
  return first, last
end


-- Check if we are run as a script
if is_script() then
  require "doctests"
  doctests.test()
end