Имееются следующие элементы массива:

Аварийно-спасательная служба

Аварийно-спасательные службы

Спасатель

дисциплина труда спасателей

задачи аварийно-спасательных служб

заявка на предоставления субсидии

заявка на предоставления субсидий


...

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

Каким образом это можно реализовать, не прибегая к морфологическому анализу и сторонним библиотекам?


Это сообщение отредактировал(а) Suppir - 1.2.2010, 13:33

Возможно, устроит расстояние Левенштейна?

Да, то что нужно.

Вот алгоритм:

sub levenshtein($$){
  my @A=split //, lc shift;
  my @B=split //, lc shift;
  my @W=(0..@B);
  my ($i, $j, $cur, $next);
  for $i (0..$#A){
        $cur=$i+1;
        for $j (0..$#B){
                $next=min(
                        $W[$j+1]+1,
                        $cur+1,
                        ($A[$i] ne $B[$j])+$W[$j]
                );
                $W[$j]=$cur;
                $cur=$next;
        }
        $W[@B]=$next;
  }
  return $next;
}
 
sub min($$$){
  if ($_[0] < $_[2]){ pop @_; } else { shift @_; }
  return $_[0] < $_[1]? $_[0]:$_[1];
}

print levenshtein("Аварийно-спасательная служба","Аварийно-спасательные службы"); <>



Напечатает "3". Т.е. в этих строках три разных символа. Но если у меня несколько тысяч строк, то получается, что каждую строку нужно сравнивать с каждой строкой. Довольно долгий перебор получится.

Ну во первых, на сколько я понял, этот алгоритм считает не просто кол-во различных символов, а 


Во вторых надо все таки определить, как понимать похожесть строк, как вариант, можно использовать следующий алгоритм с применением ф-и Левенштейна:

Я думаю так:

если есть массив из элементов
1
2
3
4
5

то не обязательно делать перебор "все со всеми". Можно взять 1 в массив. Потом 2 и сравнить с 1. Потом 3 и сравнить с 2 и 1. И так далее. В общем, спасибо за советы!

Как одна из мер -- если длины строк сильно различаются, то проверять index'ом вхождение меньшей в бОльшую и бросать.

попробуйте по первым нескольким символам слов сравнивать, например

"заявка на предоставления субсидии" => "занапрсу"

"заявочки на предоставления субсидий" => "занапрсу"

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

mvsgt, очень часто бывает, что ошибка состоит в том, что два слова "склеены":

заявка на предоставления субсидии
заявка напредоставления субсидии

Так что по началам слов здесь искать затруднительно. 


amg, "если длины строк сильно различаются, то проверять index'ом вхождение меньшей в бОльшую и бросать." - отличная идея, спасибо. 

p.s. Оказывается, всего ключей более 100 тыс.!