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


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


Это сообщение отредактировал(а) Suppir - 22.9.2011, 10:49

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

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

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

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

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

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

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

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

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

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

код



результат



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

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

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



Это сообщение отредактировал(а) ginnie - 22.9.2011, 15:23

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

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


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

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





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

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

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

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

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


Это сообщение отредактировал(а) Suppir - 22.9.2011, 16:00

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

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

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

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

Вот что:

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

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

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

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

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



Это сообщение отредактировал(а) Suppir - 22.9.2011, 16:26

List::Compare

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

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

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

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

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

Это сообщение отредактировал(а) ginnie - 22.9.2011, 19:06

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

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

Это сообщение отредактировал(а) KSURi - 22.9.2011, 20:09

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

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

Это сообщение отредактировал(а) KSURi - 22.9.2011, 21:17

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

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

alezzz, кроме статьи Сегаловича на ночь почитайте еще часть диссертации Игоря Ножова "Морфологическая и синтаксическая обработка текста (модели и программы)"   Там вроде бы про бессловарный морфологический анализатор написано.

Это сообщение отредактировал(а) ginnie - 23.9.2011, 00:42

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


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

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-код )

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

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