Modified Levenshtein Distance Algorithm

Newsgroups	comp.programming
Date	2013-02-20 15:55 -0800
Message-ID	<e02f014f-ccf3-410c-a6bf-93ca7fa212c1@googlegroups.com> (permalink)
Subject	Modified Levenshtein Distance Algorithm
From	billmann <willmann817@gmail.com>

Show all headers | View raw

How can I change this algorithm so the distance only inserts.
For example:  If I have the words CAT and BAT you would need to insert a B in CAT and a C in BAT for the words to be equals so the distance would be 2.  The actual algorithm would return 1 because it allows you to substitute.  Is there anyway to change the algorithm below to only do insertion?

int LevenshteinDistance(string s, string t)
{
  int len_s = length(s), len_t = length(t)

  if(len_s == 0) then return len_t
  if(len_t == 0) then return len_s
  if(s[len_s-1] == t[len_t-1]) then cost = 0
  else                              cost = 1
  return minimum(LevenshteinDistance(s[0..len_s-1], t) + 1,
                 LevenshteinDistance(s, t[0..len_t-1]) + 1,
                 LevenshteinDistance(s[0..len_s-1], t[0..len_t-1]) + cost)
}

Back to comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Modified Levenshtein Distance Algorithm billmann <willmann817@gmail.com> - 2013-02-20 15:55 -0800
  Re: Modified Levenshtein Distance Algorithm bob <bob@coolfone.comze.com> - 2013-02-21 11:06 -0800
    Re: Modified Levenshtein Distance Algorithm billmann <willmann817@gmail.com> - 2013-02-21 18:51 -0800
      Re: Modified Levenshtein Distance Algorithm bob <bob@coolfone.comze.com> - 2013-02-22 07:29 -0800
  Re: Modified Levenshtein Distance Algorithm "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-02-22 08:22 +0000
    Re: Modified Levenshtein Distance Algorithm Jongware <jongware@no-spam.plz> - 2013-02-25 11:03 +0100
      Re: Modified Levenshtein Distance Algorithm Jongware <jongware@no-spam.plz> - 2013-02-25 11:06 +0100
        Re: Modified Levenshtein Distance Algorithm bob <bob@coolfone.comze.com> - 2013-02-25 07:24 -0800

csiph-web