php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #9080 bug in weighted Levenshtein distance function
Submitted: 2001-02-02 12:04 UTC Modified: 2001-02-02 12:44 UTC
From: sb at ldc dot upenn dot edu Assigned:
Status: Closed Package: *Function Specific
PHP Version: 4.0.4pl1 OS:
Private report: No CVE-ID: None
View Developer Edit
Welcome! If you don't have a Git account, you can't do anything here.
If you reported this bug, you can edit this bug over here.
(description)
Block user comment
Status: Assign to:
Package:
Bug Type:
Summary:
From: sb at ldc dot upenn dot edu
New email:
PHP Version: OS:

 

 [2001-02-02 12:04 UTC] sb at ldc dot upenn dot edu
In function:

   static int weighted_levdist

There is a block of code: 

   118          /* if we already used up one string, then
   119        the result is the length of the other */
   120          if(*s1=='\0') return strlen(s2);
   121          if(*s2=='\0') return strlen(s1);
 
This is correct for unweighted, but not weighted Levenshtein.

The value on line 120 should be multiplied by
cost_ins, and the value on line 121 should be multiplied
by cost_del.

Steven Bird <sb@ldc.upenn.edu>
http://www.ldc.upenn.edu/sb/

Patches

Pull Requests

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2001-02-02 12:44 UTC] hholzgra@php.net
levenshtein functions in 4.04. (and at least back to 4.0.3) 
are broken in several places due to myself over-optimizing

my fix came a little late for 4.0.4 so you have to use
latest CVS or wait for 4.0.5 to get a working (but less optimized
for now) version
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Wed Dec 11 16:01:28 2024 UTC