<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>Calculate Levenshtein distance between two strings</title>
</head>
<body><div class="manualnavbar" style="text-align: center;">
<div class="prev" style="text-align: left; float: left;"><a href="function.lcfirst.html">lcfirst</a></div>
<div class="next" style="text-align: right; float: right;"><a href="function.localeconv.html">localeconv</a></div>
<div class="up"><a href="ref.strings.html">String Functions</a></div>
<div class="home"><a href="index.html">PHP Manual</a></div>
</div><hr /><div id="function.levenshtein" class="refentry">
<div class="refnamediv">
<h1 class="refname">levenshtein</h1>
<p class="verinfo">(PHP 4 >= 4.0.1, PHP 5)</p><p class="refpurpose"><span class="refname">levenshtein</span> — <span class="dc-title">Calculate Levenshtein distance between two strings</span></p>
</div>
<div class="refsect1 description" id="refsect1-function.levenshtein-description">
<h3 class="title">Description</h3>
<div class="methodsynopsis dc-description">
<span class="type">int</span> <span class="methodname"><strong>levenshtein</strong></span>
( <span class="methodparam"><span class="type">string</span> <code class="parameter">$str1</code></span>
, <span class="methodparam"><span class="type">string</span> <code class="parameter">$str2</code></span>
)</div>
<div class="methodsynopsis dc-description">
<span class="type">int</span> <span class="methodname"><strong>levenshtein</strong></span>
( <span class="methodparam"><span class="type">string</span> <code class="parameter">$str1</code></span>
, <span class="methodparam"><span class="type">string</span> <code class="parameter">$str2</code></span>
, <span class="methodparam"><span class="type">int</span> <code class="parameter">$cost_ins</code></span>
, <span class="methodparam"><span class="type">int</span> <code class="parameter">$cost_rep</code></span>
, <span class="methodparam"><span class="type">int</span> <code class="parameter">$cost_del</code></span>
)</div>
<p class="para rdfs-comment">
The Levenshtein distance is defined as the minimal number of
characters you have to replace, insert or delete to transform
<em><code class="parameter">str1</code></em> into <em><code class="parameter">str2</code></em>.
The complexity of the algorithm is <em>O(m*n)</em>,
where <em>n</em> and <em>m</em> are the
length of <em><code class="parameter">str1</code></em> and
<em><code class="parameter">str2</code></em> (rather good when compared to
<span class="function"><a href="function.similar-text.html" class="function">similar_text()</a></span>, which is O(max(n,m)**3),
but still expensive).
</p>
<p class="para">
In its simplest form the function will take only the two
strings as parameter and will calculate just the number of
insert, replace and delete operations needed to transform
<em><code class="parameter">str1</code></em> into <em><code class="parameter">str2</code></em>.
</p>
<p class="para">
A second variant will take three additional parameters that
define the cost of insert, replace and delete operations. This
is more general and adaptive than variant one, but not as
efficient.
</p>
</div>
<div class="refsect1 parameters" id="refsect1-function.levenshtein-parameters">
<h3 class="title">Parameters</h3>
<p class="para">
<dl>
<dt>
<span class="term"><em><code class="parameter">str1</code></em></span>
<dd>
<p class="para">
One of the strings being evaluated for Levenshtein distance.
</p>
</dd>
</dt>
<dt>
<span class="term"><em><code class="parameter">str2</code></em></span>
<dd>
<p class="para">
One of the strings being evaluated for Levenshtein distance.
</p>
</dd>
</dt>
<dt>
<span class="term"><em><code class="parameter">cost_ins</code></em></span>
<dd>
<p class="para">
Defines the cost of insertion.
</p>
</dd>
</dt>
<dt>
<span class="term"><em><code class="parameter">cost_rep</code></em></span>
<dd>
<p class="para">
Defines the cost of replacement.
</p>
</dd>
</dt>
<dt>
<span class="term"><em><code class="parameter">cost_del</code></em></span>
<dd>
<p class="para">
Defines the cost of deletion.
</p>
</dd>
</dt>
</dl>
</p>
</div>
<div class="refsect1 returnvalues" id="refsect1-function.levenshtein-returnvalues">
<h3 class="title">Return Values</h3>
<p class="para">
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.
</p>
</div>
<div class="refsect1 examples" id="refsect1-function.levenshtein-examples">
<h3 class="title">Examples</h3>
<p class="para">
<div class="example" id="example-4842">
<p><strong>Example #1 <span class="function"><strong>levenshtein()</strong></span> example</strong></p>
<div class="example-contents">
<div class="phpcode"><code><span style="color: #000000">
<span style="color: #0000BB"><?php<br /></span><span style="color: #FF8000">// input misspelled word<br /></span><span style="color: #0000BB">$input </span><span style="color: #007700">= </span><span style="color: #DD0000">'carrrot'</span><span style="color: #007700">;<br /><br /></span><span style="color: #FF8000">// array of words to check against<br /></span><span style="color: #0000BB">$words </span><span style="color: #007700">= array(</span><span style="color: #DD0000">'apple'</span><span style="color: #007700">,</span><span style="color: #DD0000">'pineapple'</span><span style="color: #007700">,</span><span style="color: #DD0000">'banana'</span><span style="color: #007700">,</span><span style="color: #DD0000">'orange'</span><span style="color: #007700">,<br /> </span><span style="color: #DD0000">'radish'</span><span style="color: #007700">,</span><span style="color: #DD0000">'carrot'</span><span style="color: #007700">,</span><span style="color: #DD0000">'pea'</span><span style="color: #007700">,</span><span style="color: #DD0000">'bean'</span><span style="color: #007700">,</span><span style="color: #DD0000">'potato'</span><span style="color: #007700">);<br /><br /></span><span style="color: #FF8000">// no shortest distance found, yet<br /></span><span style="color: #0000BB">$shortest </span><span style="color: #007700">= -</span><span style="color: #0000BB">1</span><span style="color: #007700">;<br /><br /></span><span style="color: #FF8000">// loop through words to find the closest<br /></span><span style="color: #007700">foreach (</span><span style="color: #0000BB">$words </span><span style="color: #007700">as </span><span style="color: #0000BB">$word</span><span style="color: #007700">) {<br /><br /> </span><span style="color: #FF8000">// calculate the distance between the input word,<br /> // and the current word<br /> </span><span style="color: #0000BB">$lev </span><span style="color: #007700">= </span><span style="color: #0000BB">levenshtein</span><span style="color: #007700">(</span><span style="color: #0000BB">$input</span><span style="color: #007700">, </span><span style="color: #0000BB">$word</span><span style="color: #007700">);<br /><br /> </span><span style="color: #FF8000">// check for an exact match<br /> </span><span style="color: #007700">if (</span><span style="color: #0000BB">$lev </span><span style="color: #007700">== </span><span style="color: #0000BB">0</span><span style="color: #007700">) {<br /><br /> </span><span style="color: #FF8000">// closest word is this one (exact match)<br /> </span><span style="color: #0000BB">$closest </span><span style="color: #007700">= </span><span style="color: #0000BB">$word</span><span style="color: #007700">;<br /> </span><span style="color: #0000BB">$shortest </span><span style="color: #007700">= </span><span style="color: #0000BB">0</span><span style="color: #007700">;<br /><br /> </span><span style="color: #FF8000">// break out of the loop; we've found an exact match<br /> </span><span style="color: #007700">break;<br /> }<br /><br /> </span><span style="color: #FF8000">// if this distance is less than the next found shortest<br /> // distance, OR if a next shortest word has not yet been found<br /> </span><span style="color: #007700">if (</span><span style="color: #0000BB">$lev </span><span style="color: #007700"><= </span><span style="color: #0000BB">$shortest </span><span style="color: #007700">|| </span><span style="color: #0000BB">$shortest </span><span style="color: #007700">< </span><span style="color: #0000BB">0</span><span style="color: #007700">) {<br /> </span><span style="color: #FF8000">// set the closest match, and shortest distance<br /> </span><span style="color: #0000BB">$closest </span><span style="color: #007700">= </span><span style="color: #0000BB">$word</span><span style="color: #007700">;<br /> </span><span style="color: #0000BB">$shortest </span><span style="color: #007700">= </span><span style="color: #0000BB">$lev</span><span style="color: #007700">;<br /> }<br />}<br /><br />echo </span><span style="color: #DD0000">"Input word: </span><span style="color: #0000BB">$input</span><span style="color: #DD0000">\n"</span><span style="color: #007700">;<br />if (</span><span style="color: #0000BB">$shortest </span><span style="color: #007700">== </span><span style="color: #0000BB">0</span><span style="color: #007700">) {<br /> echo </span><span style="color: #DD0000">"Exact match found: </span><span style="color: #0000BB">$closest</span><span style="color: #DD0000">\n"</span><span style="color: #007700">;<br />} else {<br /> echo </span><span style="color: #DD0000">"Did you mean: </span><span style="color: #0000BB">$closest</span><span style="color: #DD0000">?\n"</span><span style="color: #007700">;<br />}<br /><br /></span><span style="color: #0000BB">?></span>
</span>
</code></div>
</div>
<div class="example-contents"><p>The above example will output:</p></div>
<div class="example-contents screen">
<div class="cdata"><pre>
Input word: carrrot
Did you mean: carrot?
</pre></div>
</div>
</div>
</p>
</div>
<div class="refsect1 seealso" id="refsect1-function.levenshtein-seealso">
<h3 class="title">See Also</h3>
<p class="para">
<ul class="simplelist">
<li class="member"> <span class="function"><a href="function.soundex.html" class="function" rel="rdfs-seeAlso">soundex()</a> - Calculate the soundex key of a string</span></li>
<li class="member"> <span class="function"><a href="function.similar-text.html" class="function" rel="rdfs-seeAlso">similar_text()</a> - Calculate the similarity between two strings</span></li>
<li class="member"> <span class="function"><a href="function.metaphone.html" class="function" rel="rdfs-seeAlso">metaphone()</a> - Calculate the metaphone key of a string</span></li>
</ul>
</p>
</div>
</div><hr /><div class="manualnavbar" style="text-align: center;">
<div class="prev" style="text-align: left; float: left;"><a href="function.lcfirst.html">lcfirst</a></div>
<div class="next" style="text-align: right; float: right;"><a href="function.localeconv.html">localeconv</a></div>
<div class="up"><a href="ref.strings.html">String Functions</a></div>
<div class="home"><a href="index.html">PHP Manual</a></div>
</div></body></html>
