Здравствуйте Гость ( Вход | Регистрация ) | Выслать повторно письмо для активации |
Max |
Отправлено: Jul 16 2008, 02:18 AM
|
Команда ЭйсВэб Группа: Admin Сообщений: 989 Пользователь №: 44 Регистрация: 13-September 06 |
Шинглы - алгоритм шинглов (shingles) - обнаружение нечетких копий и дубликатов текстов (шингл - чешуйка)
Илья Сегалович из Яндекса о шинглах (отрывок из статьи) Рост базы, кроме технических проблем с дисками и серверами, ограничивается логическими: необходимостью адекватно реагировать на мусор, повторы и т.п. Не могу удержаться, чтобы не описать остроумный алгоритм, применяемый в современных поисковых системах для того, чтобы исключить «очень похожие документы». Происхождение копий документов в Интернете может быть различным. Один и тот же документ на одном и том же сервере может отличаться по техническим причинам: быть представлен в разных кодировках и форматах; может содержать переменные вставки – рекламу или текущую дату. Широкий класс документов в вебе активно копируется и редактируется – ленты новостных агентств, документация и юридические документы, прейскуранты магазинов, ответы на часто задаваемые вопросы и т.д. Популярные типы изменений: корректура, реорганизация, ревизия, реферирование, раскрытие темы и т.д. Наконец, публикации могут быть скопированы с нарушением авторских прав и изменены злонамеренно с целью затруднить их обнаружение. Кроме того, индексация поисковыми машинами страниц, генерируемых из баз данных, порождает еще один распространенных класс внешне мало отличающихся документов: анкеты, форумы, страницы товаров в электронных магазинах Очевидно, что с полными повторами проблем особых нет, достаточно сохранять в индексе контрольную сумму текста и игнорировать все остальные тексты с такой же контрольной суммой. Однако этот метод не работает для выявления хотя бы чуть-чуть измененных документов. Для решения этой задачи Udi Manber (Уди Манбер) (автор известной программы приближенного прямого поиска agrep) в 1994 году предложил идею [manber1994], а Andrei Broder (Андрей Бродер) в 1997 [broder] придумал название и довел до ума алгоритм «шинглов» (от слова shingles, «черепички, чешуйки»). Вот его примерное описание. Для каждого десятисловия текста рассчитывается контрольная сумма (шингл). Десятисловия идут внахлест, с перекрытием, так, чтобы ни одно не пропало. А затем из всего множества контрольных сумм (очевидно, что их столько же, сколько слов в документе минус 9) отбираются только те, которые делятся на, скажем, 25. Поскольку значения контрольных сумм распределены равномерно, критерий выборки никак не привязан к особенностям текста. Ясно, что повтор даже одного десятисловия – весомый признак дублирования, если же их много, скажем, больше половины, то с определенной (несложно оценить вероятность) уверенностью можно утверждать: копия найдена! Ведь один совпавший шингл в выборке соответствует примерно 25 совпавшим десятисловиям в полном тексте! Очевидно, что так можно определять процент перекрытия текстов, выявлять все его источники и т.п. Этот изящный алгоритм воплотил давнюю мечту доцентов: отныне мучительный вопрос «у кого студент списывал этот курсовик» можно считать решенным! Легко оценить долю плагиата в любой статье. Чтобы у читателя не создалось впечатление, что информационный поиск исключительно западная наука, упомяну про альтернативный алгоритм определения почти-дубликатов, придуманый и воплощенный у нас в Яндексе. В нем используется тот факт, что большинство поисковых систем уже обладают индексом в виде инвертировнного файла (или инвертировнным индексом) и этот факт удобно использовать в процедуре нахождения почти-дубликатов. -------------------- IXBB.RU - бесплатный хостинг форумов Альтернативный бесплатный софт! - аналог офиса, корела, ftp клиент Сапа бот ищет тебя! |
Vader |
Отправлено: Jul 16 2008, 09:34 PM
|
Команда ЭйсВэб Группа: Super moderator Сообщений: 745 Пользователь №: 1047 Регистрация: 22-July 07 |
Max, ты угадываешь мои мысли. Только сейчас на серче это читал.
-------------------- Бесплатный хостинг на базе DirectAdmin и Cpanel. --- Единственный разумный способ жить в этом мире — это жить без правил. © Джокер |
Splash |
Отправлено: Jul 17 2008, 11:22 AM
|
Команда ЭйсВэб Группа: Super moderator Сообщений: 1167 Пользователь №: 675 Регистрация: 29-April 07 |
Аналогично)))
-------------------- Забавные поздравления в стихах и прозе |
Роман |
Отправлено: Jul 17 2008, 06:50 PM
|
Команда ЭйсВэб Группа: Members Сообщений: 896 Пользователь №: 1160 Регистрация: 25-September 07 |
знаем уже
|