Длина строки в Юникоде и расстояние между строками
Совсем некогда написать даже пару мелочей, которые хочу скинуть сюда, пишу ту, что удалось сейчас доделать.
Изначальный вопрос был распространённым - как на PHP узнать длину строки, заданной в Юникоде (UTF-8).
Стандартные функции strlen и mb_strlen не помогут - они возвращают число байт, но не символов.
Точней, вторая-то из них поможет, но вот так:
mb_strlen($str,'UTF-8');
Второй нюанс - строка в PHP (как и во многих других языках) массивом символов не является. Поэтому некорректно и извлекать символ из строки Юникода так, как программисты привыкли делать для однобайтовых кодировок:
$c=$str[$i];
А вот так должно сработать (для символа с номером $i):
$c=mb_substr($str,$i,1,'UTF-8');
В качестве иллюстрации работы с многобайтовыми символами - небольшой онлайн-сервис на PHP в Юникоде, вычисляющий так называемое расстояние Левенштейна между двумя строками (лишние разделители удаляются, так что строки после обработки скриптом могут не совпадать с введёнными).
Вот полный исходник скрипта, основную работу выполняется функция D, вычисляющая искомое расстояние:
<!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>Расстояние Левенштейна между строками</title>
</head>
<body>
<?php
function D ($s1,$s2) {
if ($s1==$s2) return 0;
$m = mb_strlen($s1,'UTF-8');
$n = mb_strlen($s2,'UTF-8');
if ($m==0) return $n;
else if ($n==0) return $m;
$d0 = range(0, $n);
for ($i=0;$i<$m;$i++) {
$d = array($i+1);
$c1 = mb_substr($s1,$i,1,'UTF-8');
for ($j=0;$j<$n;$j++) {
$M = $c1==mb_substr($s2,$j,1,'UTF-8')?0:1;
$d[$j+1]=min($d0[$j+1]+1,$d[$j]+1,$d0[$j]+$M); //min(удаление,вставка,замена)
}
$d0 = $d;
}
return $d0[$j];
}
function trimall($string) { return trim(preg_replace("/\s+/"," ",$string)); }
function magic ($path) {
@ini_set('magic_quotes_runtime', '0');
@ini_set('magic_quotes_sybase', '0');
if (@get_magic_quotes_gpc()=='1') $path=stripslashes($path); return $path;
}
$params = array ('w1','w2','action');
while (list($num,$var) = each($params)) {
if (!empty($_POST[$var])) $$var = trimall(htmlspecialchars(magic($_POST[$var])));
else if (!empty($_GET[$var])) $$var = trimall(htmlspecialchars(magic($_GET[$var])));
else $$var = '';
}
$w1=mb_convert_case($w1,MB_CASE_LOWER,'UTF-8');
$w2=mb_convert_case($w2,MB_CASE_LOWER,'UTF-8');
echo '
<form name="f1" method="post" action="'.$_SERVER['PHP_SELF'].'">
<p>Слово 1: <input type="text" name="w1" maxlength="20" size="21" value="'.$w1.'">
Слово 2: <input type="text" name="w2" maxlength="20" size="21" value="'.$w2.'">
<input type="submit" name="action" value="OK"> <a href="'.$_SERVER['PHP_SELF'].'?w1=&w2=">Очистить</a>
</p></form>';
if (!empty($action)) echo '
<p>Расстояние между строками <b>'.($w1==''?'<font color="red">пусто</font>':$w1).'</b> и <b>'.
($w2==''?'<font color="red">пусто</font>':$w2).'</b>='.D($w1,$w2).'</p>';
?>
</body></html>
Онлайн-сервис определения расстояния Левенштейна между строками
Для сравнения (и без исходников): http://www.planetcalc.ru/1721/
Алгоритм старается экономить память, не создавая лишних данных, статья о подобном подходе к расчёту расстояния Левенштейна есть на Хабре.
Вариант поглупей - загонять значения $d в матрицу, скажем, по формулам из Вики будет как-то так:
function M ($a,$b) { return ($a==$b?0:1); }
function D ($s1,$s2) {
$m = mb_strlen ($s1,'UTF-8');
$n = mb_strlen ($s2,'UTF-8');
if ($m==0 and $n==0) return 0;
else if ($m==0) return $n;
else if ($n==0) return $m;
$d[0][0]=0;
for ($i=1; $i<$m; $i++) $d[$i][0]=$i;
for ($j=1; $j<$n; $j++) $d[0][$j]=$j;
for ($i=1; $i<$m; $i++)
for ($j=1; $j<$n; $j++) {
$c1=mb_substr($s1,$i,1,'UTF-8');
$c2=mb_substr($s2,$j,1,'UTF-8');
$d[$i][$j]=min($d[$i][$j-1]+1,$d[$i-1][$j]+1,$d[$i-1][$j-1]+M($c1,$c2));
}
return $d[$m-1][$n-1];
}
(не считал, может эта версия функции и неправильна).
Ещё глупее - считать рекурсивно, как описан алгоритм в Вики.
Разумеется, это побуквенное расстояние никакого смысла не имеет. Вот расстояние между слогами или иными пра-лексемами в должной многомерной метрике - это было бы то, что нужно :)
P.S. Пример следует понимать как учебный, на самом деле в PHP, начиная с версии 4.0.1 есть стандартная функция levenshtein
26.06.2013, 23:23 [11868 просмотров]