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

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

Форум программистов > Perl: Общие вопросы > Как определить похожие фразы?

Автор: Suppir 22.9.2011, 10:49

Есть ряд фраз. Необходимо найти похожие фразы, которые стоят рядом друг с другом.
Я выбрал их вручную и выделил жирным шрифтом. Можно ли сделать подобное с помощью Perl? Какие алгоритмы можете подсказать.

обращение с отходами потребления
органы управления в области садоводства
оформление прав собственности на землю
оценка земель садоводческих объединений
право на ведение садоводства
предоставление земли для ведения садоводства
предоставление земли для садоводства
предоставление земля для ведения личного подсобного хозяйства
предприятие развития Московского региона
строительные нормы и правила СНиП
программы развития садоводства
программы по развитию садоводства
фонды проката

Автор: Suppir 22.9.2011, 12:42

Подумал, может быть следующим способом:

1) исключаем все союзы и предлоги (и, а, но, по, не, для и т.п.), знаки препинания, переводим в нижний регистр
2) разбиваем фразу на массив слов ('предоставление', 'земли', 'ведения', 'садоводства')
3) теперь хорошо бы привести все элементы массива в именительный падеж
4) потом проверяем количество совпадающих слов между каждыми соседними фразами

Автор: alezzz 22.9.2011, 13:04

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

Код


my @pr = qw(а и у в на не при до или из за из-за с для по);

while (my $line=<DATA>){
    my @words = split /\s+/, $line;
    foreach my $w (0..$#words){
        foreach (@pr){
            if ($words[$w] eq $_){
                undef $words[$w];
            }
        }
        print soundex($words[$w]) . " " if $words[$w];
    }
    print "\n";
}

sub soundex
{
    my $word = shift || $_; 
    $word =~ tr/А-Я/а-я/;       
 
    my $fl = substr $word, 0, 1;
    $word  = substr $word, 1;
 
    $word =~ tr/бпфвгхджшщчзсцрктнмлmйуеъыаоэяиью/11111112222333455667/ds;
    $word = "$fl$word";
    #return $word;                                              # Измененый 
    return substr($word, 0, 4)."0" x (4 - length($word));       # Классический
}

__DATA__
обращение с отходами потребления
органы управления в области садоводства
оформление прав собственности на землю
оценка земель садоводческих объединений
право на ведение садоводства
предоставление земли для ведения садоводства
предоставление земли для садоводства
предоставление земля для ведения личного подсобного хозяйства
предприятие развития Московского региона
строительные нормы и правила СНиП
программы развития садоводства
программы по развитию садоводства
фонды проката

Удаляю все предлоги (или почти все, может забыл что-то) и кодирую слова, в результате получается такое:

Код


о142 о516 п541 
о416 у141 о173 с135 
о146 п410 с135 з670 
о365 з670 с123 о160 
п410 в160 с135 
п413 з670 в160 с135 
п413 з670 с135 
п413 з670 в160 л261 п131 х351 
п414 р315 м351 р160 
с545 н460 п417 с610 
п414 р315 с135 
п414 р315 с135 
ф610 п450

Видно что строки:
программы развития садоводства
программы по развитию садоводства
одинаковы, а вот строки:
предоставление земли для ведения садоводства
предоставление земли для садоводства
немного отличаются, но можно посчитать процент совпадения.

Вобщем вот такая заготовка, если нравится то модернезируйте ее на свое усмотрение.

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

Автор: Suppir 22.9.2011, 13:52

Спасибо, попробую!

Автор: Suppir 22.9.2011, 14:49

Попробовал. Soundex конкретно для моего случая мало подходит :( много лишних совпадений получается.

Автор: ginnie 22.9.2011, 14:54

Suppir, я попробовал два модуля с CPAN: String::Similarity и String::Trigram

код

Код


#! /usr/bin/perl

use strict;
use warnings;

use String::Similarity;
use String::Trigram;

my @strings;
push(@strings, 'обращение с отходами потребления');
push(@strings, 'органы управления в области садоводства');
push(@strings, 'оформление прав собственности на землю');
push(@strings, 'оценка земель садоводческих объединений');
push(@strings, 'право на ведение садоводства');
push(@strings, 'предоставление земли для ведения садоводства');
push(@strings, 'предоставление земли для садоводства');
push(@strings, 'предоставление земля для ведения личного подсобного хозяйства');
push(@strings, 'предприятие развития Московского региона');
push(@strings, 'строительные нормы и правила СНиП');
push(@strings, 'программы развития садоводства');
push(@strings, 'программы по развитию садоводства');
push(@strings, 'фонды проката');

my $prev_string = '';

for my $string (@strings) {
    unless ($prev_string) {
        $prev_string = $string;
        next;
    }
    my $similarity = String::Similarity::similarity($prev_string, $string);
    my $similatiry_trigram = String::Trigram::compare($prev_string, $string);
    warn sprintf('%s : %s %.3f %.3f', $prev_string, $string, $similarity, $similatiry_trigram), $/;
    $prev_string = $string;
}

результат

Код


обращение с отходами потребления : органы управления в области садоводства 0.394 0.087
органы управления в области садоводства : оформление прав собственности на землю 0.468 0.110
оформление прав собственности на землю : оценка земель садоводческих объединений 0.364 0.066
оценка земель садоводческих объединений : право на ведение садоводства 0.448 0.109
право на ведение садоводства : предоставление земли для ведения садоводства 0.667 0.382
предоставление земли для ведения садоводства : предоставление земли для садоводства 0.900 0.826
предоставление земли для садоводства : предоставление земля для ведения личного подсобного хозяйства 0.660 0.365
предоставление земля для ведения личного подсобного хозяйства : предприятие развития Московского региона 0.436 0.094
предприятие развития Московского региона : строительные нормы и правила СНиП 0.301 0.013
строительные нормы и правила СНиП : программы развития садоводства 0.349 0.031
программы развития садоводства : программы по развитию садоводства 0.921 0.718
программы по развитию садоводства : фонды проката 0.348 0.087

может поможет

Автор: Suppir 22.9.2011, 15:03

Сейчас потестю smile

Автор: ginnie 22.9.2011, 15:22

До кучи еще можно расстояние Левенштейна определить (Text::LevenshteinXS):

Код


обращение с отходами потребления : органы управления в области садоводства 0.394 0.087 29
органы управления в области садоводства : оформление прав собственности на землю 0.468 0.110 29
оформление прав собственности на землю : оценка земель садоводческих объединений 0.364 0.066 33
оценка земель садоводческих объединений : право на ведение садоводства 0.448 0.109 29
право на ведение садоводства : предоставление земли для ведения садоводства 0.667 0.382 20
предоставление земли для ведения садоводства : предоставление земли для садоводства 0.900 0.826 8
предоставление земли для садоводства : предоставление земля для ведения личного подсобного хозяйства 0.660 0.365 29
предоставление земля для ведения личного подсобного хозяйства : предприятие развития Московского региона 0.436 0.094 42
предприятие развития Московского региона : строительные нормы и правила СНиП 0.301 0.013 33
строительные нормы и правила СНиП : программы развития садоводства 0.349 0.031 27
программы развития садоводства : программы по развитию садоводства 0.921 0.718 4
программы по развитию садоводства : фонды проката 0.348 0.087 25

Автор: Suppir 22.9.2011, 15:52

Расстояния Левенштейна иногда использую. С помощью него хорошо искать опечатки (разницу в 1-3 буквы), вроде:

программы по развитию садоводства
программы но развитию садоводства

Но при этом невозможно применять в таких случаях:
программы по развитию садоводства
программы по развитию частного садоводства

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

Добавлено @ 16:00
Сейчас передо мной стоит следующая частная задача.

Есть два массива:

@a = ('мама', 'мыла', 'раму');
@b = ('мама', 'помыла', 'раму');

Необходимо подсчитать степень соответствия между двумя массивами. При этом нужно учитывать:
1) количество одинаковых слов <разделить на> общее количество слов //это легко, сам могу smile

2) правильность порядка слов в массивах //это не получается smile

Подскажите, плиз

Автор: ginnie 22.9.2011, 16:10

А что такое "правильность порядка слов в массивах"?

Автор: KSURi 22.9.2011, 16:12

Все эти модули оперируют на уровне символов или их последовательнстей, что в данном случае не очень полезно.

Наиболее очевидным вариантом кажется уже предложенный алгоритм:
убрать стоп-слова, нормализовать (в т.ч. словоформы), отсортировать (?), сравнить.

Автор: Suppir 22.9.2011, 16:20

А что такое "правильность порядка слов в массивах"?

Вот что:

Если
@a = ('мама', 'мыла', 'раму');
@b = ('мама', 'помыла', 'раму');
то здесь повторяются "мама" и "раму". Они занимают одинаковые позиции (0 и 2 элемент массива).

Если
@a = ('мама', 'мыла', 'раму');
@b = ('помыла', 'мама', 'раму');
то здесь повторяются "мама" и "раму". НО здесь только слово "раму" занимает одинаковую позицию.
Поэтому степень совпадения двух массивов должна быть меньшей, чем в первом случае.

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

@a = ('сегодня', 'мама', 'мыла', 'раму');
@b = ('мама', 'мыла', 'раму');

По первой проверке имеем всего лишь одно лишнее слово "сегодня". Но из-за того, что это слово "сдвинуло" всю цепочку, по второй проверке (на правильность порядка) мы получим полное несоответствие (1 != 0, 2 != 1, 3 != 2). Поэтому перед второй проверкой нужно исключать слова, у которых нет соответствий.

Автор: alezzz 22.9.2011, 17:22

http://search.cpan.org/~jkeenan/List-Compare-0.37/lib/List/Compare.pm

Автор: ginnie 22.9.2011, 17:31

KSURi, как ты предлагаешь модифицированные строки сравнить?

Автор: KSURi 22.9.2011, 18:59

Модифицированные это в смысле разные словоформы? Если да, то я упомнул, что их надо нормализовать — лемматизировать.
Иначе не понятно, что имелось в виду.

Автор: ginnie 22.9.2011, 19:03

Цитата

убрать стоп-слова, нормализовать (в т.ч. словоформы), отсортировать (?), сравнить

интересует последний этап, как?

если не сложно, покажи на примере

право на ведение садоводства
предоставление земли для ведения садоводства
предоставление земли для садоводства

Автор: KSURi 22.9.2011, 20:07

Выкидываем стоп-слова, нормализуем, получаем:
право ведение садоводство
предоставление земля ведение садоводство
предоставление земля садоводство

Получаем степень похожести (совпадения / кол-во слов):
право ведение садоводство <=> предоставление земля ведение садоводство: 0.14
предоставление земля ведение садоводство <=> предоставление земля садоводство: 0.42
предоставление земля садоводство <=> право ведение садоводство: 0.16

Автор: alezzz 22.9.2011, 20:44

KSURi, а у меня вопрос по нормализации, каким образом делается? словарем?

Автор: KSURi 22.9.2011, 21:15

В том числе и словарем, да. На основе словаря можно сделать предсказание слов, которых в словаре нет.

Автор: alezzz 22.9.2011, 21:40

Цитата(KSURi @ 22.9.2011, 21:15

)

В том числе и словарем, да.

но все-же больше интересуют алгоритмы, есть такие?

Автор: KSURi 22.9.2011, 23:04

http://download.yandex.ru/company/iseg-las-vegas.pdf

Автор: ginnie 23.9.2011, 00:40

alezzz, кроме статьи Сегаловича на ночь почитайте еще http://www.aot.ru/docs/Nozhov/chapter2.pdf Игоря Ножова "Морфологическая и синтаксическая обработка текста (модели и программы)" smile

Там вроде бы про бессловарный морфологический анализатор написано.

Автор: Suppir 23.9.2011, 07:07

Я для себя определили следующий алгоритм сравнения:

предоставление земли для ведения садоводства
предоставление земли для садоводства

1) убираем частицы, союзы, знаки, препинания. Дефисы меняем на пробелы. Ё на е. Переводим все в нижний регистр

предоставление земли ведения садоводства
предоставление земли садоводства

2) разбиваем строку на массив слов

3) убираем окончания буквы [уеыаоэяиюй], которые идут в конце слова

предоставлен земл веден садоводств
предоставлен земл садоводств

4) теперь сравниваем соседние массивы слов по следующем алгоритму

4.1) считаем общее количество совпадающих слов в двух массивах. Делим на общее количество слов в массивах.
Совпадает 6 слов из 7. Получили точность 86%

4.2) исключаем слова, которые не получили совпадений:

предоставлен земл садоводств
предоставлен земл садоводств

(исключили "веден")

4.3) сопоставляем одинаковые слова и их позиции в массиве. Все позиции совпадают (0 = 0, 1 = 1, 2 = 2).
Значит, точность расстановки слов = 100%

Считаем среднюю точность совпадения: (86 + 100) / 2 = 93 %

-----------------------------------------

Попробуем другие строки:

право на ведение садоводства
предоставление земли для ведения садоводства

преобразовываем:

прав веден садоводств
предоставлен земл веден садоводств

По первой проверке получаем точность совпадения 4 / 7 = 57 %

Исключаем не совпадающие слова для второй проверки

веден садоводств
веден садоводств

точность расстановки опять 100%

Средняя точность = 78 %

--------------------------

Теперь пробуем мало похожие строки

оценка земель садоводческих объединений
право на ведение садоводства

Преобразуем:

оценк земель садоводческ объединен
прав веден садоводств

Точность по первой проверке = 0%
Точность по второй проверке = 0%

Хотя, конечно, нам стоило получше преобразовать слова "садоводческих" и "садоводства". Тогда бы получили точность 13%

Добавлено через 1 минуту и 6 секунд
Осталось накидать Perl-код )

Автор: alezzz 23.9.2011, 10:18

KSURi, ginnie, спасибо, попробую осилить, интересуют именно методы без словаря.

Автор: ginnie 23.9.2011, 10:46

Suppir, можно для удаления окончаний (и суффиксов) использовать стеммер Портера Lingua::Stem::Ru.