БлогNot. Длина строки в Юникоде и расстояние между строками

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

Длина строки в Юникоде и расстояние между строками

Совсем некогда написать даже пару мелочей, которые хочу скинуть сюда, пишу ту, что удалось сейчас доделать.

Изначальный вопрос был распространённым - как на 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


теги: php программирование форматы алгоритм числа

комментарии (0)

26.06.2013, 23:23; рейтинг: 8037

  в началопоиск по блогунаписать авторустатистика

Наверх Яндекс.Метрика
© PerS
вход