sima/utils/leven.py

   1 # -*- coding: utf-8 -*-
   2
   3 # Copyright (c) 2009, 2010, 2013 Jack Kaliko <kaliko@azylum.org>
   4 #
   5 #  This file is part of sima
   6 #
   7 #  sima is free software: you can redistribute it and/or modify
   8 #  it under the terms of the GNU General Public License as published by
   9 #  the Free Software Foundation, either version 3 of the License, or
  10 #  (at your option) any later version.
  11 #
  12 #  sima is distributed in the hope that it will be useful,
  13 #  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 #  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 #  GNU General Public License for more details.
  16 #
  17 #  You should have received a copy of the GNU General Public License
  18 #  along with sima.  If not, see <http://www.gnu.org/licenses/>.
  19 #
  20 #
  21
  22 def levenshtein(a_st, b_st):
  23     """Computes the Levenshtein distance between two strings."""
  24     n_a, m_b = len(a_st), len(b_st)
  25     if n_a > m_b:
  26         # Make sure n <= m, to use O(min(n_a,m_b)) space
  27         a_st, b_st = b_st, a_st
  28         n_a, m_b = m_b, n_a
  29
  30     current = list(range(n_a+1))
  31     for i in range(1, m_b+1):
  32         previous, current = current, [i]+[0]*n_a
  33         for j in range(1, n_a+1):
  34             add, delete = previous[j] + 1, current[j-1] + 1
  35             change = previous[j-1]
  36             if a_st[j-1] != b_st[i-1]:
  37                 change = change + 1
  38             current[j] = min(add, delete, change)
  39
  40     return current[n_a]
  41
  42 def levenshtein_ratio(string, strong):
  43     """
  44     Compute levenshtein ratio.
  45         Ratio = levenshtein distance / lenght of longer string
  46     The longer string length is the upper bound of levenshtein distance.
  47     """
  48     lev_dist = levenshtein(string, strong)
  49     max_len = max(len(string), len(strong))
  50     ratio = 1 - (float(lev_dist) / float(max_len))
  51     return ratio
  52
  53
  54 # VIM MODLINE
  55 # vim: ai ts=4 sw=4 sts=4 expandtab