У меня есть набор строк, в которых встречаются опечатки и небольшие вариации написания. Я хотел бы выделить кластеры, для приведения их содержимого впоследствии к одному виду.
В каждой строке от 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
