Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3087

Re: Modified Levenshtein Distance Algorithm

Show all headers | View raw

billmann wrote:
> How can I change this algorithm so the distance only inserts.

The edit-distance (various metrics) is related to the "longest common 
subsequence problem" (see your favourite search engine).

In a similar way, the metric you are looking for is related to the "shortest 
common supersequence problem".  Wikipedia has a short article on that

    http://en.wikipedia.org/wiki/Shortest_common_supersequence

and some references.

It's way too early in the morning for me to work out the details but maybe 
that's enough to get you started.

    -- chris 

Back to comp.programming | Previous | Next — Previous in thread | 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