попандер

четверг, 10 декабря 2015 г.

Система поиска сходства шаблонизированных строк

Автоматизированная поисковая система (АПС) — система, состоящая из персонала и комплекса средств автоматизации его деятельности, реализующая информационную технологию выполнения установленных функций [1].
Основная цель любой поисковой системы — поиск информации, удовлетворяющей запросу пользователя. Необходимо в результате поиска ничего не потерять, то есть найти все документы, относящиеся к запросу, и не найти ничего лишнего.
Примерами АПС являются системы поиска Google, Яндекс, Rambler, системы поиска плагиата. В основном данные системы рассчитаны на поиск файлов, документов, хранящихся в их базах данных. Кроме того, такие системы не раскрывают свои алгоритмы работы.

Проблема поиска сходства также встает при работе сайта частных объявлений. Жизнеспособность такого сайта зависит от количества размещенных на них объявлений. Поэтому, чтобы привлечь клиентов, вводится услуга бесплатных
объявлений. Данные объявления можно подавать неограниченное количество с одного аккаунта сроком на двадцать восемь дней. Сообщения на вершине списка обладают большей популярностью, поэтому для продвижения своей услуги некоторые пользователи подают свое объявление в разные промежутки времени, удерживая его выше других. Это вредит как другим пользователям (по запросу они могут получить много одинаковых записей, что оттолкнет их к конкурентам), так и сайту (при потере клиентов он утратит свою жизнеспособность).

Поэтому поставлен вопрос о поиске дублирующихся объявлений, которые подаются на сайт частных объявлений.
Дублирующееся объявление — это не только копия ранее поданного, но и объявление, отличающееся от исходного од-
ним-двумя неключевыми словами. Данная задача преследует цель не заполнения базы данных повторяющейся инфор-
мацией, и предоставление пользователям, которые ищут какую-либо услугу, разные объявления.
Решением на поставленный вопрос не может быть ни одна из приведенных выше АПС, так как, во-первых, об-
ласть поиска каждой из них — своя база данных; во-вторых, алгоритмы работы скрыты и защищены; в-третьих, необ-
ходим поиск по строке, а не по тексту (то есть в данном случае имеют место разные параметры критериев поиска таких,
как полнота, точность); в-четвертых, в случае поиска дублирующихся объявлений работа ведется с шаблонизирован-
ными строками, что, несомненно, необходимо использовать.
Поэтому целью исследования является определение и разработка механизма поиска сходства шаблонизированных
строк, в основу работы которого заложены алгоритмы нечеткого поиска дубликатов
Для достижения поставленной цели были поставлены и решены следующие задачи:
1. Анализ существующих систем поиска
2. Анализ алгоритмов определения строк-дубликатов
3. Определение алгоритмов, подходящих для работы с шаблонизированными строками
4. Определение методов работы с алгоритмами
5. Построение автоматизированной системы поиска
Несмотря на повсеместное использование АПС, для локальной задачи поиска сходства строк решения не найдено:
системы поиска плагиата — почти все являются платными продуктами со скрытым программным кодом, а такие обще-
доступные системы, как Google или Яндекс, сложно применить к частной задаче. И, конечно, алгоритм работы ни одна
из широко используемых систем не разглашает.
Далее сформируем список алгоритмов нечеткого поиска, которые могут быть использованы в поиске строк-дубли-
катов: алгоритм шинглов и алгоритм Вагнера-Фишера.
Алгоритм шинглов — алгоритм, разработанный для поиска копий и дубликатов рассматриваемого текста в веб-до-
кументе, мощный инструмент, призванный бороться с проявлениями плагиата в интернете.
Уди Манбер в 1994 г. первым в мире выразил идею поиска дубликатов, а в 1997 г. Андрей Бродер оптимизировал
и довел её до логического завершения, дав имя данной системе — «алгоритм шинглов».
Этапы, которые проходит текст, подвергшийся сравнению:
— канонизация текста;
— разбиение на шинглы;
— вычисление хэшей шинглов;
— случайная выборка 84 значений контрольных сумм;
— сравнение, определение результата.
Канонизация текста приводит оригинальный текст к единой нормальной форме. Текст очищается от предлогов, со-
юзов, знаков препинания, HTML тегов, и прочего не нужного «мусора», который не должен участвовать в сравнении.
В большинстве случаев так же предлагается удалять из текста прилагательные, так как они не несут смысловой на-
грузки.
Шинглы (англ. чешуйки) — выделенные в тексте подпоследовательности слов. Необходимо из сравниваемых тек-
стов выделить подпоследовательности слов, идущих друг за другом по 10 штук (длина шингла). Выборка происходит
внахлест, а не встык. Таким образом, разбивая текст на подпоследовательности, получается набор шинглов в количе-
стве равному количеству слов минус длина шингла плюс один (кол_во_слов — длина_шингла + 1).
Принцип алгоритма шинглов заключается в сравнении случайной выборки контрольных сумм шинглов (подпоследо-
вательностей) двух текстов между собой.
Проблема алгоритма заключается в количестве сравнений, ведь это напрямую отражается на производительности.
Увеличение количества шинглов для сравнения характеризуется экспоненциальным ростом операций, что критически
отразится на производительности [2].
Алгоритм Вагнера-Фишера использует одну из наиболее часто применяемых метрик — расстояние Левенштейна.
Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками
в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа,
удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую [3].
Впервые задачу упомянул в 1965 году советский математик Владимир Иосифович Левенштейн при изучении после-
довательностей 0–1. Впоследствии более общую задачу для произвольного алфавита связали с его именем. Большой
вклад в изучение вопроса внес Дэн Гасфилд.
Расстояние Левенштейна и его обобщения активно применяется:
— для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом
распознавании отсканированного текста или речи).
— для сравнения текстовых файлов утилитой diff и ей подобным.....

Агеева Светлана Полиектовна, магистрант
Вологодский государственный технический университет



Комментариев нет:

Отправить комментарий