Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Как определить схожесть текстов? 
:(
    Опции темы
maxim1000
Дата 21.11.2006, 21:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110



Цитата(SoWa @  21.11.2006,  19:04 Найти цитируемый пост)
Хм. Как без словарика можно определить такую структуру?

не, то я говорил как раз в продолжение мысли о словарике

Цитата(SoWa @  21.11.2006,  19:04 Найти цитируемый пост)
Это легко. Слово встретил незнакомое- выдаст запрос- это что: существительное, глагол, наречие, др...

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

Цитата(SoWa @  21.11.2006,  19:04 Найти цитируемый пост)
Для начала и это прокатит. Но уж совсем не оптимизировано.

ну... рановато оптимизировать...
как при ускорении оптимизация должна отталкиваться от профайлера, так и здесь хорошо бы строить развитие на основании экспериментальных данных

Цитата(podval @  21.11.2006,  19:05 Найти цитируемый пост)
Превед велосипедистам!

smile
хобби такое вот - велосипедизм
во всех областях специалистом не станешь, а мозги разминки требуют smile


--------------------
qqq
PM WWW   Вверх
podval
Дата 22.11.2006, 10:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62



Цитата(sergejzr @  21.11.2006,  20:53 Найти цитируемый пост)
Цитата(podval @  21.11.2006,  19:05 )
У тебя подход, судя по задаче, должен быть похожим.


ИМХО не совсем похож.. Кластеризация и классификация текстов это слишком круто здесь.  Хотя статья интересная.
Но тут текстов не так много и функции дискриминации попроще 


Серж, ты именно здачу классификации и решил. 
Кстати, зачот smile
PM WWW ICQ   Вверх
sergejzr
Дата 22.11.2006, 13:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 4
Всего: 360



Цитата(podval @  22.11.2006,  09:20 Найти цитируемый пост)
Серж, ты именно здачу классификации и решил. 

Почти smile там были авторы - центроиды по которым собственно тексты и классифицировались. А тут почти тоже самое, только центроидов для сравнения нет.


--------------------
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
Levenson
Дата 28.11.2006, 20:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 28
Регистрация: 17.9.2006

Репутация: нет
Всего: нет



Релевантность (англ. relevant) — степень соответствия запроса и найденного, уместность результата.
Основным методом для оценки релевантности является TF-IDF–метод, который используется в большинстве поисковых систем.
Вот ссылочка: http://ru.wikipedia.org/wiki/TF-IDF 

PM MAIL   Вверх
sergejzr
Дата 28.11.2006, 21:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 4
Всего: 360



Levenson, ну это релевантность документа к слову. Честно, ума не приложу, как её применить для сравнения документов. разве только каждое слово сравнивать. И потом, схема расчитана на относительную релевантность. Т.е зависит от самих документов в группе и их количества.
К примеру два текста, не совпадающие на одно слово, будут считаться похожими, если в группе всего три документа и третий ещё больше отличается от тех двух.


--------------------
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
SID_M
Дата 6.12.2006, 20:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 195
Регистрация: 11.2.2005
Где: Россия, г. Москва

Репутация: нет
Всего: нет



Цитата(sergejzr @  28.11.2006,  21:55 Найти цитируемый пост)
 Честно, ума не приложу, как её применить для сравнения документов

Ты отчасти прав... сравнивать каждое слово, только по-умному.

Я бы сделал так: 
1) написал бы морфологический анализатор на словарной базе (словари уже готовы и бесплатны) для того чтобы по любому слову определять его начальную форму. Для начала рассматривал бы только существительные.

2) для каждого документа системы составил бы карту частоты встречаемости, используя подход "TF-IDF". Как показала практика в тексте достаточно большого размера слов, которые являются существительными не так уж и много.

3)далее я уже сравнивал бы такие карты для различных текстов

Кстати, в чем проблема?
Цитата(sergejzr @  28.11.2006,  21:55 Найти цитируемый пост)
 два текста, не совпадающие на одно слово, будут считаться похожими, если в группе всего три документа и третий ещё больше отличается от тех двух

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

--------------------
Если тебе не дано летать, то хотя бы ползай с гордо поднятой головой.
PM MAIL ICQ Skype GTalk   Вверх
sergejzr
Дата 6.12.2006, 20:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 4
Всего: 360



Цитата(SID_M @  6.12.2006,  19:05 Найти цитируемый пост)
Они и так будут считаться похожими. Мож я не понял, чего ты хочешь сказать...

Нет, я конечно же совсем не то и не так хотел сказать  smile  smile  smile  smile Спасибо за то, что заметил smile Это предложение наверное осталось случайно. можно его не считать.

Имелось ввиду, что идея IDF в том, что если слово в документе встречается часто, а во всей группе - редко, то релевантность документа (по отношению к этому слову) будет расчитана как высокая. Таким образом она будет скакать в зависимости от количества документов.


--------------------
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
SID_M
Дата 7.12.2006, 18:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 195
Регистрация: 11.2.2005
Где: Россия, г. Москва

Репутация: нет
Всего: нет



Систему IDF я понял. Просто я предлагаю использовать только TF. А IDF оставить в покое. Т.е. анализировать схожесть текста только на основании словарей. Думаю, что такой подход имеет место быть.

Еще одно предложение: Считать сочетания понятий в предложениях и составлять такие же словари для них. Не секрет, что сочетания слов в тексте точнее характеризует этот текст нежели просто вхождение слов.
--------------------
Если тебе не дано летать, то хотя бы ползай с гордо поднятой головой.
PM MAIL ICQ Skype GTalk   Вверх
sergejzr
Дата 7.12.2006, 18:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 4
Всего: 360



Цитата(SID_M @  7.12.2006,  17:11 Найти цитируемый пост)
Не секрет, что сочетания слов в тексте точнее характеризует этот текст нежели просто вхождение слов. 

TF тоже относителен количеству слов в документе. Нет. ИМХО похожесть так не определишь..

Цитата(SID_M @  7.12.2006,  17:11 Найти цитируемый пост)
Не секрет, что сочетания слов в тексте точнее характеризует этот текст нежели просто вхождение слов. 

Это да, но такой анализатор на 10000 текстах будет буксовать... Хотя можно конечно многое сделать.
Я делал такую систему (как уже писал), но у меня были сочетания определены заранее. (Брал примеры и по ним сравнивал). Дело интересное, но опять же свои нюансы. Надо знать "о чём" документы.

Добавлено @ 18:26 
TF(А,Б) - сколько раз слово ""А находится в документе "Б".


--------------------
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
SID_M
Дата 7.12.2006, 20:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 195
Регистрация: 11.2.2005
Где: Россия, г. Москва

Репутация: нет
Всего: нет



Цитата(sergejzr @  7.12.2006,  18:25 Найти цитируемый пост)
такой анализатор на 10000 текстах будет буксовать

1) Зависит от текстов
2) А никто легкой жизни и не обещал  smile 

Можно конечно сложность алгоритма посчитать, толтко лень как-то...  smile 
--------------------
Если тебе не дано летать, то хотя бы ползай с гордо поднятой головой.
PM MAIL ICQ Skype GTalk   Вверх
Artemios
Дата 9.12.2006, 00:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 1
Всего: 50



Может быть пригодится:
http://company.yandex.ru/articles/spamooborona.html
http://company.yandex.ru/articles/article10.html

Добавлено @ 00:46 
P.S. Ссылки всплыли здесь:
http://forum.vingrad.ru/topic-125971.html
человек решает аналогичную задачу.


--------------------
fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]
PM MAIL   Вверх
kulibinka
Дата 9.12.2006, 12:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4



Ага, я решил аналогичную задачу методом шинглов.
Теперь бьюсь над повышением ее быстродействия.

Кстати, возник вопрос:

Цитата

Я бы упростил схему по стандартному методу, который уже много раз использовал в различных задачах. (Как уже писал в теме про антимат smile )

1) Нормализация текста
2) Сравнение

Теперь надо "развернуть" этото алгоритм по нашей задаче.
1а) Стеммер, в нижний регистр, елиминация всего, кроме слов, выкидываем предлоги итд.
1б)тезаури (маппинг синонимов);
1в) Создание общего вектора
2) Подсчёт дистанции Hamming'a


Не подскажете где можно получить словари синонимов русского языка?
PM MAIL   Вверх
sergejzr
Дата 9.12.2006, 19:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 4
Всего: 360



Цитата(kulibinka @  9.12.2006,  11:50 Найти цитируемый пост)
Не подскажете где можно получить словари синонимов русского языка? 

Скорее всего надо будет писать самому. Стандартные словари мало чего дадут. (т.к у одного и тогоже слова бывает несколько значений.)


--------------------
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
kulibinka
Дата 10.12.2006, 11:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4



Цитата

Скорее всего надо будет писать самому. Стандартные словари мало чего дадут. (т.к у одного и тогоже слова бывает несколько значений.) 


А что такое "стандарнтый словарь"?

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

Но зачем это еще раз делать, если в стандартных словарях типа http://www.trishin.ru/slovar.html это уже давно сделано и подчищено?

Вот и хочется получить результат аналогичный http://www.trishin.ru/slovar.html, но не в виде программы, а в сыром (текстовом) виде для удобства встраивания в свои программы.

Это сообщение отредактировал(а) kulibinka - 10.12.2006, 13:00
PM MAIL   Вверх
sergejzr
Дата 10.12.2006, 16:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 4
Всего: 360



Цитата(kulibinka @  10.12.2006,  10:40 Найти цитируемый пост)
Но зачем это еще раз делать, если в стандартных словарях типа http://www.trishin.ru/slovar.html это уже давно сделано и подчищено?

Я давал пример слова "ягуар". Это может быть машина, а может быть животное. Зависит от типа текста и ещё кучи вещей. 
Цитата(kulibinka @  10.12.2006,  10:40 Найти цитируемый пост)
Я конечно понимаю как перелопатив горы текста правильным скриптом можно самому создать подобие словаря синонимов.

Нет, всё же скриптом не получится.


--------------------
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
Страницы: (4) Все 1 2 [3] 4 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1426 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.