![]() |
|
![]() ![]() ![]() |
|
Sosed |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 52 Регистрация: 18.8.2009 Репутация: нет Всего: 1 |
Доброго времени суток
Такая задача - нужно реализовать программу для проверки текста на уникальность, используя свою базу текстов. В качестве текста выступают письменные работы - курсовые, рефераты, доклады и т.п. Под НЕ уникальностью понимается полное совпадение текста, т.е. обычный копипаст. Учитывая объем анализируемого текста, я никак немогу придумать, что именно брать из текста за метаинформацию, какие-нибудь шинглы были бы идеальны, но если предположить довольно большую БД работ, то процесс сравнения тонны хешей, как мне кажется, затянется на долго, хотя, может мне это действительно кажется? Подсказали, что можно использовать метод корреляции локальных максимумов, используя в качестве характеристики объема текста кол-во различных пробелов, запятых и других знаков препинания на фиксированный блок текста. Т.е. в итоге мы получим два ряда чисел, локальных максимумов, которые впоследствии сравниваются. Мне кажется при применении этого метода, придется рассматривать документ(реферат etc.) как набор глав, выбирать которые либо по содержанию, либо опять же резать кусками и считать максимумы для каждого такого куска, так как проверяемый текст в большинстве своем может быть уникальным, а какая-либо глава будет добавлена копипастом, отловить ее максимумы на промежутке от начала текста до конца будет невозможно, смешаются с уникальной частью, а в пределах одной главы вполне. Но опять же у меня сомнения по поводу правильности такого подхода. Хотелось бы увидеть комментарии по данному методу, либо какие-либо варианты решения задачи. Спасибо. |
|||
|
||||
VictorTsaregorodtsev |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 274 Регистрация: 28.7.2006 Репутация: 3 Всего: 8 |
Из текстов выкидываются стоп-слова (союзы, предлоги,...), слова нормализуются (окончания приводятся к единственному числу, именительному падежу,...). По корпусу текстов составляется словарь, самые-самые редкоиспользуемые и, возможно, встречающиеся во всех текстах слова отбрасываются из словаря. В словаре останется несколько тысяч слов - это, реально, немного. Если есть набор синонимов - синонимы можно заменять на какое-то одно слово, тем самым еще сократив словарь.
Т.е. всякие способы разбавления текста союзами-предлогами и многие другие способы рерайтинга текста минимизируют свое влияние. Далее каждый отдельный текст или глава текста представляется в виде частотного словаря. Набор частотных словарей (векторов одинаковой длины, совпадающей с числом слов в эталонном словаре) даст базу данных (таблицу), по которой можно будет провести кластерный анализ (если хочется сократить последующее время "боевой работы" системы по классификации каждого нового текста). Каждый новый текст также представляется в виде вектора, т.е. такого же частотного словаря (с использованием нашего эталонного словаря) и для него ищется ближайший к нему вектор-эталон (из входящих в базу эталонных текстов). Можно сначала найти ближайший к новому вектору кластер (если проведена кластеризация эталонных данных), и только внутри ближайшего к тексту кластера сопоставлять новый вектор с векторами из этого кластера. Данные каждого отдельного кластера (вектора) можно дополнить другими компонентами - например, средним числом слов в предложении, если такие признаки будут различаться от кластера к кластеру. Тогда внутри кластера новый текст-вектор будет сравниваться с эталонными векторами с учетом их увеличенной длины, чтобы захватить специфичные для данного кластера признаки. Нашли ближайший к новому вектору эталонный вектор - и вычислить, насколько расстояние между этими векторами превышает некоторый порог (если отличие меньше порога - новый текст совпадает со старым, если больше порога - то это действительно новый текст). Тут надо подумать, простейший способ - это найти минимальное расстояние между парой эталонных векторов (но требует N^2 операций, где N - число эталонных векторов), если, конечно, предполагается, что среди исходных текстов есть только уникальные тексты. В общем, можно придумать разные способы вычисления порога и выбрать такой, который минимизирует число ложных срабатываний на эталонных текстах (чтобы как можно больше эталонных текстов классифицировались как уникальные). В общем, задача довольно тривиальная - приемлемое качество решения будет получено даже без привлечения знаний из лингвистики (единственно будет нужен хороший словарь стоп-слов, хорошие алгоритмы нормализации окончаний, "правильный" для данной темы текстов словарь синонимов). Если написал непонятно - то пусть другие "переводят", либо заказывайте мне такую программу, ибо на подобных задачах я деньги зарабатываю ;) Подобный подход нами опробован в 2001, для авторубрикации выкачиваемых из интернета новостевых, прессрелизных и патентных текстов. Единственно что тогда практически не сделали - это проверку текстов на совпадение в соответствии с предложенным здесь рецептом, т.к. патенты просто не могут быть об одном и том же, а разные новости об одном и том же могли для заказчика нести существенные информации в своих мелочах (соответственно, нельзя было из нескольких новостей оставлять какую-то одну, надо было показывать их все). |
|||
|
||||
Sosed |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 52 Регистрация: 18.8.2009 Репутация: нет Всего: 1 |
Спасибо за ответ, но есть вопросец:
Немогу понять что есть эталонный словарь? Точнее откуда его получить. Вы написали:
т.е. чтобы составить такой словарь нужно проанализировать кучу текстов? Или это просто набор слов? |
|||
|
||||
VictorTsaregorodtsev |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 274 Регистрация: 28.7.2006 Репутация: 3 Всего: 8 |
Это тот перечень слов, который встретился в наборе эталонных текстов. За исключением совсем неинформативных слов (встречающихся во всех этих текстах и встречающихся настолько редко, что эти слова не нужно обращать внимание)
Ведь очевидно, что несмотря на деградацию средней и высшей школы, слова из албанского ;) языка будут довольно редко встречаться в рефератах-курсовых по физике, химии, техническим и многим другим наукам и предметам, а если и встретятся в каком-нибудь тексте - то будут совсем неинформативны для определения оригинальности этого текста (т.к. смысл текста не будет связан со словами из албанского). Поэтому какой-то стандартный готовый словарь общеупотребительных слов русского языка брать не советую - советую адаптировать систему к тому набору текстов, которые изначально взяты за эталон (за оригинальные тексты), и при существенном пополнении набора оригинальных текстов перестраивать словарь. |
|||
|
||||
Sosed |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 52 Регистрация: 18.8.2009 Репутация: нет Всего: 1 |
Эх, где бы еще взять этот набор эталонных текстов) Похоже придется грабить различные онлайн банки рефератов, буду пробывать прогонять, может чего из этого интересное и выйдет, угляжу какие-либо закономерности в словах, а то пока много сомнений)
Если я правильно понял алгоритм, то для каждого нового текста создается вектор размера равного кол-ву слов в словаре. То есть для пополнения словаря нужно будет прогнать всю имеющуюся базу текстов с учетом новых слов, или же лучше сохранять для каждой работы весь частотный словарь, а использовать лишь часть? З.Ы. Такие штуки как слова из албанского или какие-либо редкие технические термины могли бы послужить довольно неплохим фильтром, для сужения кружка "подозреваемых", да и такого рода слова врятли встретятся в словаре, что облегчает их поиск) |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |