Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #3087
| Path | csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder2.hal-mli.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.freenet.ag!feeder2.ecngs.de!ecngs!feeder.ecngs.de!Xl.tags.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!local2.nntp.ams.giganews.com!nntp.bt.com!news.bt.com.POSTED!not-for-mail |
|---|---|
| NNTP-Posting-Date | Fri, 22 Feb 2013 02:24:30 -0600 |
| From | "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> |
| Newsgroups | comp.programming |
| References | <e02f014f-ccf3-410c-a6bf-93ca7fa212c1@googlegroups.com> |
| Subject | Re: Modified Levenshtein Distance Algorithm |
| Date | Fri, 22 Feb 2013 08:22:35 -0000 |
| X-Priority | 3 |
| X-MSMail-Priority | Normal |
| X-Newsreader | Microsoft Outlook Express 6.00.2900.5512 |
| X-MimeOLE | Produced By Microsoft MimeOLE V6.00.2900.5512 |
| X-RFC2646 | Format=Flowed; Original |
| Message-ID | <LdWdnYFTW4ajtrrMnZ2dnUVZ8nSdnZ2d@bt.com> (permalink) |
| Lines | 19 |
| X-Usenet-Provider | http://www.giganews.com |
| X-AuthenticatedUsername | NoAuthUser |
| X-Trace | sv3-1lPw2Ozex4X1/028Y9lS3zic46F7YE6Nn7yav/kaY2gOJNDEJ0OPqMW/tViZrYf5xB3/+nkKNLG6h1S!KnnQM7aFc4bGwb+BsjxUekKMT/qFTsH97y8TuQmz/swBwiak9ph3hA0P7bQCHsqELdkVo26CskI= |
| X-Complaints-To | abuse@btinternet.com |
| X-DMCA-Complaints-To | abuse@btinternet.com |
| X-Abuse-and-DMCA-Info | Please be sure to forward a copy of ALL headers |
| X-Abuse-and-DMCA-Info | Otherwise we will be unable to process your complaint properly |
| X-Postfilter | 1.3.40 |
| X-Original-Bytes | 1752 |
| Xref | csiph.com comp.programming:3087 |
Show key headers only | 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
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