<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<HTML
><HEAD
><TITLE
>levenshtein</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
REL="HOME"
TITLE="PHP 手册"
HREF="index.html"><LINK
REL="UP"
TITLE="String 字符串处理函数"
HREF="ref.strings.html"><LINK
REL="PREVIOUS"
TITLE="join"
HREF="function.join.html"><LINK
REL="NEXT"
TITLE="localeconv"
HREF="function.localeconv.html"><META
HTTP-EQUIV="Content-type"
CONTENT="text/html; charset=UTF-8"></HEAD
><BODY
CLASS="refentry"
BGCOLOR="#FFFFFF"
TEXT="#000000"
LINK="#0000FF"
VLINK="#840084"
ALINK="#0000FF"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="3"
ALIGN="center"
>PHP 手册</TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="bottom"
><A
HREF="function.join.html"
ACCESSKEY="P"
>上一页</A
></TD
><TD
WIDTH="80%"
ALIGN="center"
VALIGN="bottom"
></TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="bottom"
><A
HREF="function.localeconv.html"
ACCESSKEY="N"
>下一页</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><H1
><A
NAME="function.levenshtein"
></A
>levenshtein</H1
><DIV
CLASS="refnamediv"
><A
NAME="AEN225597"
></A
><P
> (PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5)</P
>levenshtein --
Calculate Levenshtein distance between two strings
</DIV
><DIV
CLASS="refsect1"
><A
NAME="AEN225600"
></A
><H2
>Description</H2
>int <B
CLASS="methodname"
>levenshtein</B
> ( string str1, string str2 [, int cost_ins, int cost_rep, int cost_del] )<BR
></BR
><P
> 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
><P
> The Levenshtein distance is defined as the minimal number of
characters you have to replace, insert or delete to transform
<CODE
CLASS="parameter"
>str1</CODE
> into <CODE
CLASS="parameter"
>str2</CODE
>.
The complexity of the algorithm is <TT
CLASS="literal"
>O(m*n)</TT
>,
where <TT
CLASS="literal"
>n</TT
> and <TT
CLASS="literal"
>m</TT
> are the
length of <CODE
CLASS="parameter"
>str1</CODE
> and
<CODE
CLASS="parameter"
>str2</CODE
> (rather good when compared to
<A
HREF="function.similar-text.html"
><B
CLASS="function"
>similar_text()</B
></A
>, which is O(max(n,m)**3),
but still expensive).
</P
><P
> 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
<CODE
CLASS="parameter"
>str1</CODE
> into <CODE
CLASS="parameter"
>str2</CODE
>.
</P
><P
> 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
><P
> <TABLE
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
CLASS="EXAMPLE"
><TR
><TD
><DIV
CLASS="example"
><A
NAME="AEN225635"
></A
><P
><B
>例 1. <B
CLASS="function"
>levenshtein()</B
> example</B
></P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
CELLPADDING="5"
><TR
><TD
><code><font color="#000000">
<font color="#0000BB"><?php<br /></font><font color="#FF8000">// input misspelled word<br /></font><font color="#0000BB">$input </font><font color="#007700">= </font><font color="#DD0000">'carrrot'</font><font color="#007700">;<br /><br /></font><font color="#FF8000">// array of words to check against<br /></font><font color="#0000BB">$words </font><font color="#007700">= array(</font><font color="#DD0000">'apple'</font><font color="#007700">,</font><font color="#DD0000">'pineapple'</font><font color="#007700">,</font><font color="#DD0000">'banana'</font><font color="#007700">,</font><font color="#DD0000">'orange'</font><font color="#007700">,<br /> </font><font color="#DD0000">'radish'</font><font color="#007700">,</font><font color="#DD0000">'carrot'</font><font color="#007700">,</font><font color="#DD0000">'pea'</font><font color="#007700">,</font><font color="#DD0000">'bean'</font><font color="#007700">,</font><font color="#DD0000">'potato'</font><font color="#007700">);<br /><br /></font><font color="#FF8000">// no shortest distance found, yet<br /></font><font color="#0000BB">$shortest </font><font color="#007700">= -</font><font color="#0000BB">1</font><font color="#007700">;<br /><br /></font><font color="#FF8000">// loop through words to find the closest<br /></font><font color="#007700">foreach (</font><font color="#0000BB">$words </font><font color="#007700">as </font><font color="#0000BB">$word</font><font color="#007700">) {<br /><br /> </font><font color="#FF8000">// calculate the distance between the input word,<br /> // and the current word<br /> </font><font color="#0000BB">$lev </font><font color="#007700">= </font><font color="#0000BB">levenshtein</font><font color="#007700">(</font><font color="#0000BB">$input</font><font color="#007700">, </font><font color="#0000BB">$word</font><font color="#007700">);<br /><br /> </font><font color="#FF8000">// check for an exact match<br /> </font><font color="#007700">if (</font><font color="#0000BB">$lev </font><font color="#007700">== </font><font color="#0000BB">0</font><font color="#007700">) {<br /><br /> </font><font color="#FF8000">// closest word is this one (exact match)<br /> </font><font color="#0000BB">$closest </font><font color="#007700">= </font><font color="#0000BB">$word</font><font color="#007700">;<br /> </font><font color="#0000BB">$shortest </font><font color="#007700">= </font><font color="#0000BB">0</font><font color="#007700">;<br /><br /> </font><font color="#FF8000">// break out of the loop; we've found an exact match<br /> </font><font color="#007700">break;<br /> }<br /><br /> </font><font 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 /> </font><font color="#007700">if (</font><font color="#0000BB">$lev </font><font color="#007700"><= </font><font color="#0000BB">$shortest </font><font color="#007700">|| </font><font color="#0000BB">$shortest </font><font color="#007700">< </font><font color="#0000BB">0</font><font color="#007700">) {<br /> </font><font color="#FF8000">// set the closest match, and shortest distance<br /> </font><font color="#0000BB">$closest </font><font color="#007700">= </font><font color="#0000BB">$word</font><font color="#007700">;<br /> </font><font color="#0000BB">$shortest </font><font color="#007700">= </font><font color="#0000BB">$lev</font><font color="#007700">;<br /> }<br />}<br /><br />echo </font><font color="#DD0000">"Input word: $input</font><font color="#007700">\n</font><font color="#DD0000">"</font><font color="#007700">;<br />if (</font><font color="#0000BB">$shortest </font><font color="#007700">== </font><font color="#0000BB">0</font><font color="#007700">) {<br /> echo </font><font color="#DD0000">"Exact match found: $closest</font><font color="#007700">\n</font><font color="#DD0000">"</font><font color="#007700">;<br />} else {<br /> echo </font><font color="#DD0000">"Did you mean: $closest?</font><font color="#007700">\n</font><font color="#DD0000">"</font><font color="#007700">;<br />}<br /><br /></font><font color="#0000BB">?></font>
</font>
</code></TD
></TR
></TABLE
><P
>上例将输出：</P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
CELLPADDING="5"
><TR
><TD
><PRE
CLASS="screen"
>Input word: carrrot
Did you mean: carrot?</PRE
></TD
></TR
></TABLE
></DIV
></TD
></TR
></TABLE
>
</P
><P
> See also <A
HREF="function.soundex.html"
><B
CLASS="function"
>soundex()</B
></A
>,
<A
HREF="function.similar-text.html"
><B
CLASS="function"
>similar_text()</B
></A
>, and
<A
HREF="function.metaphone.html"
><B
CLASS="function"
>metaphone()</B
></A
>.
</P
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="function.join.html"
ACCESSKEY="P"
>上一页</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="index.html"
ACCESSKEY="H"
>起始页</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="function.localeconv.html"
ACCESSKEY="N"
>下一页</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>join</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="ref.strings.html"
ACCESSKEY="U"
>上一级</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>localeconv</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>
