Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: Общие вопросы > Найти в массиве похожие элементы

Автор: Suppir 1.2.2010, 13:29

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

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

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

Спасатель

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

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

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

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

...

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

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

Автор: DurRandir 1.2.2010, 15:37

Возможно, устроит http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D1%82%D0%B0%D0%BD%D1%86%D0%B8%D1%8F_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0?

Автор: Suppir 1.2.2010, 15:46

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

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

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". Т.е. в этих строках три разных символа. Но если у меня несколько тысяч строк, то получается, что каждую строку нужно сравнивать с каждой строкой. Довольно долгий перебор получится.

Автор: klem4 1.2.2010, 16:45

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

Цитата

мера разницы двух последовательностей символов (строк) относительно минимального количества операций вставки, удаления и замены, необходимых для перевода одной строки в другую.

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

Код


while (кол-во строк > 0)
{
   берем 1-ю строку;
  добавляем строку в новую(пустую) группу
  идем по остальным строкам:
  {
      разница между первой и текущей просматриваемой нас устраивает? -> да: добавляем эту строку в ГРУППУ похожих на первую и удаляем ее из массива
  }
  удаляем первую строку из массива
}

Автор: Suppir 2.2.2010, 09:13

Я думаю так:

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

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

Автор: amg 3.2.2010, 15:49

Цитата(Suppir @ 1.2.2010, 15:46

)

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

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

Автор: mvsgt 3.2.2010, 16:55

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

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

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

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

Автор: Suppir 4.2.2010, 10:25

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

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

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

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

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