Алтайский Краевой Инновационный Банк Данных
Министерство экономического развития Алтайского края
Управление инновационного развития и кластерной политики 
Алтайский Центр
Кластерного Развития
Инновации

Разработка новых структур данных и алгоритмов для задач быстрого сравнения текстов

Отношение к критическим технологиям:
Технологии производства программного обеспечения


Контактная информация

ФИО пользователя
Дягилев Вадим Викторович


Почтовый адрес
, Малахова, 97-263


ФИО руководителя проекта:
Цхай Александр Андреевич


Аннотация проекта

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


Современное состояние исследований в данной области науки, сравнение ожидаемых результатов с мировым
Классический фильтр Блума - это вероятностная структура данных, позволяющая проводить быструю проверку вхождения элемента во множество. При этой проверке, скорость сравнения достигается за счет появления управляемой вероятности ложноположительного результата. Использование фильтров Блума для сравнения текстов - относительно новая задача. Она требует некоторой предварительной обработки текста, которая бы задала критерий схожести. После предобработки тексты помещаются в фильтр Блума и производится анализ вхождения нового документа в данное множество. Однако, прямое использование фильтров Блума затруднено проблемой их масштабирования, если мощность множества сравниваемых документов - неизвестна заранее. Различные модификации фильтров, разработанные в мире к настоящему моменту, хотя и решают проблему масштабирования, требуют многоступенчатой проверки и дополнительного расхода памяти. Второй недостаток классических фильтров заключается в том, что во многих задачах недостаточно знать, что фрагменты проверяемого документа просто встречаются в библиотеке, состоящей из миллионов документов. Во многих случаях требуется определить: какие именно фрагменты совпадают. В 2011 году в одной из зарубежных публикаций для решения этой проблемы был предложен матричный фильтр Блума, помещающий каждый документ библиотеки в отдельную бит-строку. Однако, данный подход является ресурсоемким в отношении потребления оперативной памяти. Научная новизна предполагаемой разработки определяется тем, что она предполагает исследование и разработку усовершенствованной модели матричного фильтра Блума, которая позволит решить задачу плотного заполнения строк матрицы. Основная проблема матричного фильтра Блума, нерешенная на данный момент в мире - это эффективное использование строк фильтра с учетом того, что документы, хранящиеся в разных строках, могут существенно отличаться по длине. Опубликованные к настоящему моменту в мировой литературе вариации фильтра Блума имеют недостатки, связанные с неэффективным использованием памяти, либо с отсутствием локализации объекта сравнения. Предлагаемый вариант усовершенствования компактного матричного фильтра Блума является новым и не имеет аналогов в мировых публикациях в области быстрого сравнения символьных последовательностей. Прикладное значение данной структуры и алгоритмов покрывает класс алгоритмов поиска схожих документов и не ограничивается задачами распознавания плагиата. В качестве дополнительных областей можно привести системы, связанные с фильтрованием интернет-трафика, в том числе для систем защиты от внутренних утечек информации. Уровень проекта предполагает получить результаты выше текущего мирового в области поиска схожих текстов. Авторы проекта публикуют работы, в том числе в ведущих мировых журналах, связанных с разработкой прикладных систем распознавания плагиата. Для тестирования алгоритмов предполагается использовать массивы документов, многократно опробованные на международных соревнованиях по распознаванию плагиата.


Новизна подхода в решении обозначенной проблемы
Научная новизна данной разработки определяется тем, что она представляет собой модификацию матричного фильтра Блума, позволяющую решить задачу плотного заполнения строк матрицы. Основная проблема матричного фильтра Блума, нерешенная на данный момент в мировой литературе - это эффективное использование строк фильтра с учетом того, что документы, хранящиеся в разных строках, могут существенно отличаться по длине.


Описание области применения результатов научно-исследовательской работы
Разработка может служить основой для создания прототипа системы обнаружения плагиата, а также для систем, предназначенных для фильтрации трафика, таких как, например, системы класса защиты от утечек информации.


Имеющийся у коллектива научный задел по предлагаемому проекту, полученные ранее результаты, разработ
Участники коллектива имеют значительный опыт работ над теоретическими и прикладными аспектами быстрого сравнения схожих документов. Так в 2008-2009 годах была разработана оригинальная модель быстрого сравнения документов, основанная на усовершенствованном алгоритме Винновинга (Winnowing). На основе этого было выполнено проектирование и успешное внедрение двух проектов в области распознавания документов. В 2009 году один из авторов проекта принимал участие в международных соревнованиях по распознаванию плагиата с лучшим результатом по точности нахождения плагиата и с шестым результатом в общем зачете. В 2010-2012 годах проведен анализ возможности изменения технологии распознавания плагиата, с целью уменьшения количества информации, передаваемой в систему обнаружения плагиата. Такая цель была обоснована необходимостью защиты интеллектуальной собственности в проверяемом документе. В результате была разработана теоретическая модель, подтвержденная экспериментально. Результаты эксперимента опубликованы в ведущих российских и зарубежных изданиях, а также представлены на международных конференциях. Данный научный задел позволяет оценить уровень предлагаемого проекта выше текущего мирового, а также дает возможность реализовать его силами авторского коллектива с гарантией положительного результата исследований.


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


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


Текущая стадия разработки проекта
Научно-исследовательская работа


Патентная чистота научно-технического задела, его защищенность
Имеются патенты


Тип научно-исследовательской работы
Поисковые проблемно-ориентированные исследования


Описание основных ожидаемых научных результатов
- разработка новой вероятностной структуры данных, основанной на понятии фильтра Блума и позволяющей решить проблему резкого увеличения требуемого объема компьютерной памяти при обработке больших массивов документов разной длины; - апробация полученных структур данных и алгоритмов работы с ними на практической задаче распознавания плагиата. В качестве тестовых выборок предполагается использовать массивы данных, используемых на международных соревнованиях по распознаванию плагиата.


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


Срок реализации Проекта (месяцев)
12


Необходимый объем финансирования (тыс. руб.)
150000


Ключевые слова

Информационные технологии/информатика, Моделирование


Графические, презентационные, текстовые и иные материалы к проекту

-