levenshtein

Calculate Levenshtein distance between two strings

The Levenshtein distance is defined as the minimal number of characters you have to replace, insert, or delete to transform str1 into str2.

Syntax

levenshtein ( string $str1 , string $str2 ) : int
levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del ) : int

Parameters

str1

One of the strings being evaluated for Levenshtein distance.

str2

One of the strings being evaluated for Levenshtein distance.

cost_ins

Defines the cost of insertion.

cost_rep

Defines the cost of replacement.

cost_del

Defines the cost of deletion.

Return

This function returns the Levenshtein-Distance between the two argument strings or -1, if one of the argument strings is longer than the limit of 255 characters.

Examples

1

<?

$str1 = 'same';
$str2 = 'same';

$return = levenshtein($str1, $str2);
echo $return;

?>
0

2

<?

$str1 = 'same';
$str2 = 'different';

$return = levenshtein($str1, $str2);
echo $return;

?>
8

3

<?

$str1 = 'same';
$str2 = 'different';
$cost_ins = 1;
$cost_rep = 1;
$cost_del = 1;

$return = levenshtein($str1, $str2, $cost_ins, $cost_rep, $cost_del);
echo $return;

?>
8

4

<?

$str1 = 'same';
$str2 = 'different';
$cost_ins = 1;
$cost_rep = 10;
$cost_del = 100;

$return = levenshtein($str1, $str2, $cost_ins, $cost_rep, $cost_del);
echo $return;

?>
35

5

<?

// input misspelled word
$input = 'carrrot';

// words to check
$words  = array('apple','pineapple','banana','orange', 'radish','carrot','pea','bean','potato');

// shortest distance not found
$shortest = -1;

// loop through words to find closest match
foreach ($words as $word) {

    // calculate distance between input word and current word
    $lev = levenshtein($input, $word);

    // check for exact match
    if ($lev == 0) {

        // exact match found
        // set closest match and shortest distance
        $closest = $word;
        $shortest = $lev;

        // break out of loop
        break;
    }

    // check if current distance is less than shortest distance or if shortest distance not found
    if (($lev <= $shortest) || ($shortest == -1)) {

        // closest match found
        // set closest match and shortest distance
        $closest  = $word;
        $shortest = $lev;
    }
}

echo "input: $input\n";

if ($shortest == 0) {
    echo "exact match: $closest";
} else {
    echo "closest match: $closest";
}

?>
input: carrrot
closest match: carrot

addcslashes

addslashes

bin2hex

chop

chr

chunk_split

convert_uudecode

convert_uuencode

count_chars

crc32

crypt

echo

explode

fprintf

get_html_translation_table

hebrev

hebrevc

hex2bin

html_entity_decode

htmlentities

htmlspecialchars

htmlspecialchars_decode

implode

join

lcfirst

localeconv

ltrim

md5

md5_file

metaphone

nl_langinfo

nl2br

number_format

ord

parse_str

print

printf

quoted_printable_decode

quoted_printable_encode

quotemeta

rtrim

setlocale

sha1

sha1_file

similar_text

soundex

sprintf

sscanf

str_contains

str_ends_with

str_getcsv

str_ireplace

str_pad

str_repeat

str_replace

str_rot13

str_shuffle

str_split

str_starts_with

str_word_count

strcasecmp

strchr

strcmp

strcoll

strcspn

strip_tags

stripcslashes

stripos

stripslashes

stristr

strlen

strnatcasecmp

strnatcmp

strncasecmp

strncmp

strpbrk

strpos

strrchr

strrev

strripos

strrpos

strspn

strstr

strtok

strtolower

strtoupper

strtr

substr

substr_compare

substr_count

substr_replace

trim

ucfirst

ucwords

vfprintf

vprintf

vsprintf

wordwrap

PHP

Home Menu