Метрика на пространстве строк и кластеризация

[cepesh]

У меня есть набор строк, в которых встречаются опечатки и небольшие вариации написания. Я хотел бы выделить кластеры, для приведения их содержимого впоследствии к одному виду.
В каждой строке от 1 до 4-5 слов.

Сейчас применяется вот такой алгоритм. Тут, конечно, нет кластеризации в нормальном понимании, но кандидатов на слияние можно отловить.

  1 <?php
  2         $in = file("publ.txt");
  3         $n = count($in);
  4         for ($i = 0; $i < $n; $i++) {
  5                 $publ[$i] = mb_strtoupper($in[$i], "UTF-8");
  6                 $publ[$i] = preg_replace("/[\s\.,\-\(\)\"\"\'\/]+/", '', $publ[$i]);
  7         }
  8
  9         $delta = 0.1;
 10         for ($i = 0; $i < $n; $i++) {
 11                 $res = '';
 12                 $len = 1.0 * strlen($publ[$i]);
 13                 for ($j = $i + 1; $j < $n; $j++) {
 14                         if (abs($len - strlen($publ[$j])) > 0.25 * $len) {
 15                                 continue;
 16                         }
 17                         $similarity = similar_text($publ[$i], $publ[$j]) / $len;
 18                         if ($similarity >= 1-$delta) {
 19                                 $res .= "<tr><td>" . $in[$j] . "</td><td>" . $similarity . "</td></tr>\n";
 20                         }
 21                 }
 22                 if ($res != '') {
 23                         echo "<h2>" . $in[$i] . "</h2><table border=1>";
 24                         echo $res;
 25                         echo "</table><br><br>";
 26                 }
 27         }
 28 ?>

В строке 17 используется функция similar_text()

Меня интересует, можно ли решать задачу более эффективно? Не в плане скорости, а в плане качества результатов. Существует ли понятие метрики на строках?

Вот тут входные данные: http://lib.mexmat.ru/tmp/publ.txt
Вот тут результат работы: http://lib.mexmat.ru/tmp/publMatch.php

[PAV]

Не разбираясь в приведенном коде, можно сразу заведомо сказать, что первый (и, возможно, единственный) кандидат - это метрика выпадений-вставок-замещений. Мы определяем некоторые допустимые преобразования строк (замены одних символов другими, удаления символов, добавления, перестановки соседних...) Каждому преобразованию может быть приписан вес, который может зависеть от всего, чего угодно: от значений самих символов, их расположения в строке, соседей и т.д. Расстояние между строками - это цепочка преобразований, переводящая одну строку в другую, имеющая минимальный вес. Считается влет динамическим программированием.

[cepesh]

То есть предлагается использовать алгоритм Левенштайна?

[PAV]

Да, но его можно значительно видоизменить. Классическая метрика Левенштейна - это метрика вставок-выпадений, когда вставка и выпадение имеют вес 1. В более общем виде, как я отметил, можно ввести и другие преобразования (как минимум - замены символов) и присвоить им произвольные веса. Ну, например, можно присвоить меньший вес заменам символов, которые расположены на соседних клавишах клавиатуры, а которые далеко друг от друга - больший. Можно также добавить перестановки символов.

Добавлено спустя 13 минут 12 секунд:

cepesh писал(а):

То есть предлагается использовать алгоритм Левенштайна?

А более общо - динамическое программирование. Исключительно мощное и универсальное средство, когда надо сравнивать и сопоставлять упорядоченную последовательность чего-либо.