81080

ОБЛАКА ТЕГОВ ДЛЯ ПАРАЛЛЕЛЬНОЙ ФИЛЬТРАЦИИ ДАННЫХ

Дипломная

Информатика, кибернетика и программирование

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

Русский

2015-02-19

503.5 KB

2 чел.

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

«Уральский федеральный университет

имени первого Президента России Б.Н. Ельцина»

Институт математики и компьютерных наук

Кафедра высокопроизводительных компьютерных технологий

ОБЛАКА ТЕГОВ ДЛЯ ПАРАЛЛЕЛЬНОЙ ФИЛЬТРАЦИИ ДАННЫХ

Допустить к защите:                                                         Магистерская диссертация

                                                                                           студента VI курса

зав. кафедрой                                                                    Сударикова Романа

высокопроизводительных                                               Олеговича  

компьютерных технологий

доктор физико-математических                                       

наук                                                   

ПОПОВ

ЛЕОНИД ДЕНИСОВИЧ

                                                                                            

                                                                                            

                                                                               

                                                                                            Научный руководитель:

                                                                                            кандидат технических

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

                                                                                            АВЕРБУХ ВЛАДИМИР

                                                                                            ЛАЗАРЕВИЧ

Екатеринбург

2012 г.


[1] Введение

[2]
Теоретическая часть

[2.1] Метафора контекстного облака тегов

[2.2]
Облачные вычисления

[2.3]
Аппликация грубых множеств

[2.4] Разработка модели

[2.4.1] Визуализация

[2.4.2] Модель потока данных

[2.4.3] Итераторы  Ruby

[2.4.4] Фильтрация данных

[2.4.5] Метрики оценки эффективности

[2.5]
Создание прототипа программы

[3]
Список литературы

[4]
ПРИЛОЖЕНИЯ


Вступление

В работе рассматривается метафора визуализации и взаимодействия – контекстное облако тегов, предназначенная для эффективной интерпретации результатов поиска в Интернете. Данная метафора построена на основание формальной модели, включающей два основных утверждения: во-первых, метафору или модель визуализации надо строить так, чтобы достигался минимум когнитивного расстояния; во-вторых, утверждение об эквивалентности определений функции принадлежности и вычислимой функции. Задание функции принадлежности можно рассматривать, как инструментарий программирования и как метрику оценки эффективности. Реализован вариант контекстного облака тегов, рассматривается дальнейшее развитие, например, в направлении информационной визуализации.

Введение

Современная вычислительная техника позволяет хранить и обрабатывать все большие объемы информации. В результате возникает проблема эффективного доступа и интерпретации этих данных. Одним из решений такой проблемы представляется  метафора контекстного облака тегов. Которая подразумевает такую модель компьютерной визуализации данных, когда результаты “стандартного” поиска масштабируются и интерпретируются после дополнительной обработки с использованием указанной метафоры. Разнообразие определений компьютерной визуализации можно объяснить тем, что данный термин существенно зависит от контекста  его применения. Так визуализацию можно рассматривать как графический алгоритм, как часть цикла прохождения задания, как анализ результатов вычислений, как обратную задачу моделирования, связанную с  восприятием и интерпретацией. Теория визуализации нужна, во-первых, для анализа существующих систем, во-вторых, для обучения новых специалистов и, в-третьих, для быстрого и правильного проектирования новых систем. Особое внимание необходимо уделить эффективности разработки, включая, скорость и простоту проектирования новых систем, и повышение качества сервисов, предоставляемых пользователю. Без модели не возможна формализованная оценка эффективности. “В огромном числе случаев при попытке построить модель какого-либо объекта либо не возможно прямо указать фундаментальные законы, или вариационные принципы, которым он подчиняется, либо с точки зрения наших сегодняшних знаний, вообще нет уверенности в существовании подобных законов, допускающих математическую формулировку. Одним из плодотворных подходов к такого рода объектам является использование аналогий с уже изученными явлениями.” [1]  Визуализация, как объект изучения, несомненно,  плохо формализуема, но необходимость, прежде всего, оценки эффективности диктует построение полумодели или оснований теории визуализации, начиная с декларативных определений и поиска аналогий.  

В области визуализации и супервычислений актуальными являются такие задачи как оценка эффективности: параллельных программ, фильтрации данных, планирования задач, интерфейса, распознавания жестов. Принципиально важно имеет ли решение (модель), например, задача автоматической оценки интерфейса, основанная на не эвристическом подходе. Наличие параллелизма существенно усложняет модель. Так эффективность алгоритма общепринято зависит от количества данных, а эффективность параллельного алгоритма, кроме того, от количества процессоров, наличия ресурсов, схемы распараллеливания. Наличие сложных зависимостей ведет к нелинейности времени (в смысле нарушения принципа суперпозиции) и как следствие к плохой масштабируемости,

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

В работе рассматривается решение задачи построения контекстного облака тегов для результатов поиска с помощью использования парадигмы программы-посредника, которая находится между конечным пользователем и фактической поисковой выдачей. Для реализации был выбран язык Ruby, потому что, кроме простоты реализации клиент-серверной модели, общая постановка предполагает задания функции принадлежности для обрабатываемого множества, что в некоторой степени соответствует применению ассоциативных массивов, так же рассматривалась перспектива развития с применение параллельной “поисковой” системы Hadoop, поддерживающей связку Ruby-Sinatra

Стандартное отображение результатов поиска в  Интернете плохо масштабируется, поэтому попробуем построить другой вид отображения  - контекстное облако тегов. В основе лежит простая идея – для поиска применяется алгоритм MapReduce, поэтому вид отображения выберем аналогичный этому алгоритму. Результаты поиска (нечеткое множество X) представим в виде массива ассоциативных массивов (Рис. 1.1), где центральный элемент массива – строка поиска «параллельная фильтрация данных». Формально задаются две функции принадлежности: ширина контекста (количество слов поиска слева и справа от строки поиска) и  частота встречаемости слова, зависящая от типа документа с расширением pdf, doc, html соответственно отображается градацией цвета R,G,B. Результаты поиска также включают название документа и гиперссылку, которые предполагается отображать через взаимодействие с конкретным словом (ключом).


Рис.1.1

Очевидно, что контекстное облако тегов хорошо масштабируется, но облегчит ли оно интерпретацию результатов поиска? В рамках предполагаемой модели интерпретация должна упроститься, если пользователь, конечно, имеет представление о работе алгоритма MapReduce. Адекватность модели предполагается проверить на основе тестирования, по единственному критерию - помогает ли контекстное облако тегов поиску.


Теоретическая часть 

Теоретическая часть включает разделы:

  •  Метафора контекстного облака тегов;
  •  Облачные вычисления;
  •  Аппликация грубых множеств;
  •  Язык программирования Ruby;

Кратко поясним, почему выбраны именно эти пункты.

Метафора контекстного облака тегов является расширением облака тегов с заданием нескольких функций принадлежности для множества, включающего результаты поиска. Архитектура программы, по сути, - облачные вычисления. В работе рассматривается решение задачи построения контекстного облака тегов для результатов поиска с помощью использования парадигмы программы-посредника, которая находится между конечным пользователем и фактической поисковой выдачей. Этот подход активно применяется в секторе  компьютерной визуализации, в частности для удаленной визуализации. В работе так же рассматривается возможность применения теории грубых множеств для задач визуализации и обработки информации. Задание функций принадлежности для множества можно рассматривать, как способ упорядочения этого множества. Так же очевидно параллель между предыдущим и ассоциативными массивами. Наибольший интерес представляет рассмотрение функций принадлежности грубых множеств, как относительную метрику оценки эффективности. Так построение модели визуализации можно рассматривать, как решения обратной некорректной задачи - нахождения операторов взаимодействия (итераторов) и переходу к задаче минимизации функционала (нахождения оптимального взаимодействия). Язык программирования Ruby интересен с точки зрения языкотворчества. Так рассмотрение итераторов, как “синтаксический сахар” цикла  на наш взгляд не достаточно. С точки зрения функционального программирования итератор – это замыкание цикла. А  с точки зрения параллельного программирования итератор – это цикл с автопараллелизмом. Также особое внимание уделено ассоциативным массивам.

Метафора контекстного облака тегов

“Облако тегов или Облако меток или Облако ключевых слов — визуальное представление списка ярлыков (или категорий). Частота упоминаний, поисков, ссылок в Интернете с определённого сайта неких слов, терминов, имён, отображается в специальной области в виде изображения этих слов в формате гиперссылок. Размер изображения тем больше, чем чаще использовался данный тег (слово, термин или имя)” - цитата из Википедии.

В сфере визуального дизайна облако тегов является подвидом элемента, называющегося взвешенным списком, который использовался в географии при отображении размера названия города в зависимости от его фактической площади. Популярность самого облака тегов пришла в начале XXI века, когда все большее число вебсайтов стало использовать методику проектирования под названием Web 2.0. «Web 2.0 (определение Тима О’Рейли) — методика проектирования систем, которые путём учета сетевых взаимодействий становятся тем лучше, чем больше людей ими пользуются» - цитата из Википедии. Позже облако тегов стало использоваться как один из основных методов визуализации корпусов текста. Одними из самых заметных исследований были разработки  Daniel Steinbock(нужно переводить имя-фамилию на русский?) в Стенфордском университете в 2006 г. (проект TagCrowd) и  исследователем из IBM Jonathan Feinberg в 2008 г. (проект  Wordle). Исследования Steffen Lohmann в 2009 г. выявили следующие закономерности в восприятии пользователем облака тегов[2]:

  •  Размер тега: Слова большего размера сильнее притягивают взгляд пользователя(на что влияет количество букв в слове, размеры соседних слов и позиция тега в облаке)
  •  Сканирование: Пользователи в основном просматривают(сканируют) слова в облаке, нежели читают
  •  Центрирование: Слова в центре облака притягивают большее внимание, чем находящиеся на краях
  •  Позиционирование: Слова, находящиеся в верхнем левом квадранте получают больше внимания(это связано с принципом чтения слева направо)
  •  Исследование: Обычные облака тегов представляют неэффективную помощь, в тех случаях, когда пользователь ищет узкоспециальные слова, которые не могут быть очень большого размера

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

По сути, облако тегов - это популярная в Интернете визуальная метафора, или вид отображения, где упорядоченному списку (например, слов по частоте встречаемости) ставится  в соответствие двухмерное изображение в декартовых координатах, где можно варьировать позиция объекта (слова), его размер, цвет. Не трудно видеть, что это определение можно применить и для других случаев (не текстовых), например, посещаемость сайта (статистической информации ставится в соответствие карта мира, в данном случае возможно применение трехмерного изображения или сферических координат).

Метафора контекстного облака тегов является расширением облака тегов с заданием нескольких функций принадлежности для множества, включающего результаты поиска.  В основе лежит простая идея – для поиска применяется алгоритм MapReduce, поэтому вид отображения выберем аналогичный этому алгоритму.


Облачные вычисления

Облачные вычисления в информатике — это модель обеспечения повсеместного и удобного сетевого доступа по требованию к общему пулу конфигурируемых вычислительных ресурсов (например, сетям передачи данных, серверам, устройствам хранения данных, приложениям и сервисам — как вместе, так и по отдельности), которые могут быть оперативно предоставлены и освобождены с минимальными эксплуатационными затратами и/или обращениями к провайдеру. [3]

Национальным институтом стандартов и технологий США зафиксированы следующие обязательные характеристики облачных вычислений[4]:

  •  Самообслуживание по требованию, потребитель самостоятельно определяет и изменяет вычислительные потребности, такие как серверное время, скорости доступа и обработки данных, объём хранимых данных без взаимодействия с представителем поставщика услуг;
  •  Универсальный доступ по сети, услуги доступны потребителям по сети передачи данных вне зависимости от используемого терминального устройства;
  •  Объединение ресурсов, поставщик услуг объединяет ресурсы для обслуживания большого числа потребителей в единый пул для динамического перераспределения мощностей между потребителями в условиях постоянного изменения спроса на мощности; при этом потребители контролируют только основные параметры услуги (например, объём данных, скорость доступа), но фактическое распределение ресурсов, предоставляемых потребителю, осуществляет поставщик (в некоторых случаях потребители всё-таки могут управлять некоторыми физическими параметрами перераспределения, например, указывать желаемый центр обработки данных из соображений географической близости);
  •  Эластичность, услуги могут быть предоставлены, расширены, сужены в любой момент времени, без дополнительных издержек на взаимодействие с поставщиком, как правило, в автоматическом режиме;
  •  Учёт потребления, поставщик услуг автоматически исчисляет потреблённые ресурсы на определённом уровне абстракции (например, объём хранимых данных, пропускная способность, количество пользователей, количество транзакций), и на основе этих данных оценивает объём предоставленных потребителям услуг.

Модели обслуживания:

  •  Программное обеспечение как услуга (SaaS, англ. Software-as-a-Service) — модель, в которой потребителю предоставляется возможность использования прикладного программного обеспечения провайдера, работающего в облачной инфраструктуре и доступного из различных клиентских устройств или посредством тонкого клиента, например, из браузера (например, веб-почта) или интерфейс программы. Контроль и управление основной физической и виртуальной инфраструктурой облака, в том числе сети, серверов, операционных систем, хранения, или даже индивидуальных возможностей приложения (за исключением ограниченного набора пользовательских настроек конфигурации приложения) осуществляется облачным провайдером.

  •  Платформа как услуга (PaaS, англ. Platform-as-a-Service) — модель, когда потребителю предоставляется возможность использования облачной инфраструктуры для размещения базового программного обеспечения для последующего размещения на нём новых или существующих приложений (собственных, разработанных на заказ или приобретённых тиражируемых приложений). В состав таких платформ входят инструментальные средства создания, тестирования и выполнения прикладного программного обеспечения — системы управления базами данных, связующее программное обеспечение, среды исполнения языков программирования — предоставляемые облачным провайдером. Контроль и управление основной физической и виртуальной инфраструктурой облака, в том числе сети, серверов, операционных систем, хранения осуществляется облачным провайдером, за исключением разработанных или установленных приложений, а также, по возможности, параметров конфигурации среды (платформы).

  •  Инфраструктура как услуга (IaaS, англ. IaaS or Infrastructure-as-a-Service) предоставляется как возможность использования облачной инфраструктуры для самостоятельного управления ресурсами обработки, хранения, сетей и другими фундаментальными вычислительными ресурсами, например, потребитель может устанавливать и запускать произвольное программное обеспечение, которое может включать в себя операционные системы, платформенное и прикладное программное обеспечение. Потребитель может контролировать операционные системы, виртуальные системы хранения данных и установленные приложения, а также ограниченный контроль набора доступных сервисов (например, межсетевой экран, DNS). Контроль и управление основной физической и виртуальной инфраструктурой облака, в том числе сети, серверов, типов используемых операционных систем, систем хранения осуществляется облачным провайдером.

Одной из ветвей развития данной работы рассматривается интеграция разработанной системы с сервером распределенных вычислений Hadoop.

Hadoop — проект фонда Apache Software Foundation, свободно распространяемый набор утилит, библиотек и программный фреймворк для разработки и выполнения распределённых программ, работающих на кластерах из сотен и тысяч узлов. Используется для реализации поисковых и контекстных механизмов многих высоконагруженных веб-сайтов, в том числе, для Yahoo! и Facebook. Разработан в рамках вычислительной парадигмы MapReduce, согласно которой приложение разделяется на большое количество одинаковых элементарных заданий, выполнимых на узлах кластера и естественным образом сводимых в конечный результат.

По состоянию на 2011 год Hadoop состоит из трёх подпроектов:

  •  Hadoop Common, являющееся связующим программным обеспечением — набор инфраструктурных программных библиотек и утилит, используемых для других подпроектов и родственных проектов
  •  HDFS - Hadoop Distributed File System, является распределённой файловой системой
  •  Hadoop MapReduce - фреймворк для реализации MapReduce-вычислений

Разработка была инициирована в начале 2005 году Дугом Каттингом с целью построения программной инфраструктуры распределённых вычислений для проекта Nutch — свободной программной поисковой машины на Java, её идейной основой стала публикация сотрудников Google Джеффри Дина и Санжая Гемавата[5] о вычислительной концепции MapReduce [6]. В январе 2006 года корпорация Yahoo пригласила Каттинга возглавить специально выделенную команду разработки инфраструктуры распределённых вычислений, к этому же моменту относится выделение Hadoop в отдельный проект. В феврале 2008 года Yahoo запустила в продуктивную эксплуатацию кластерную поисковую машину на 10 тыс. процессорных ядер, управляемую средствами Hadoop.В январе 2008 года Hadoop становится проектом верхнего уровня системы проектов Apache Software Foundation. В апреле 2008 года Hadoop побил мировой рекорд производительности в стандартизованном бенчмарке сортировки данных — 1 ТБайт был обработан за 309 сек. на кластере из 910 узлов[7]. В апреле 2010 года корпорация Google предоставила Apache Software Foundation права на использование технологии MapReduce, через три месяца после её защиты в патентном бюро США, тем самым избавив организацию от возможных патентных претензий [7]. Начиная с 2010 года Hadoop неоднократно характеризуется как ключевая технология «Больших Данных», прогнозируется его широкое распространение для массово-параллельной обработки данных, и, наряду с Cloudera, появилась серия технологических стартапов, целиком ориентированных на коммерциализацию Hadoop [8][9].

Рассмотрим каждый подпроект системы Hadoop более подробно. В Hadoop Common входят библиотеки управления файловыми системами, поддерживаемыми Hadoop и сценарии создания необходимой инфраструктуры и управления распределённой обработкой, для удобства выполнения которых создан специализированный упрощённый интерпретатор командной строки, запускаемый из оболочки операционной системы специальной командой. HDFS  — файловая система, предназначенная для хранения файлов больших размеров, поблочно распределённых между узлами вычислительного кластера. Все блоки в HDFS (кроме последнего блока файла) имеют одинаковый размер, и каждый блок может быть размещён на нескольких узлах, размер блока и коэффициент репликации (количество узлов, на которых должен быть размещён каждый блок) определяются в настройках на уровне файла. Благодаря репликации обеспечивается устойчивость распределённой системы к отказам отдельных узлов. Файлы в HDFS могут быть записаны лишь однажды (модификация не поддерживается), а запись в файл в одно время может вести только один процесс. Организация файлов в пространстве имён — традиционная иерархическая: есть корневой каталог, поддерживается вложение каталогов, в одном каталоге могут располагаться и файлы, и другие каталоги. Развёртывание экземпляра HDFS предусматривает наличие центрального узла имён, хранящего метаданные файловой системы и метаинформацию о распределении блоков, и серии узлов данных, непосредственно хранящих блоки файлов. Узел имён отвечает за обработку операций уровня файлов и каталогов — открытие и закрытие файлов, манипуляция с каталогами, узлы данных непосредственно отрабатывают операции по записи и чтению данных. Узел имён и узлы данных снабжаются веб-серверами, отображающими текущий статус узлов и позволяющими просматривать содержимое файловой системы. Административные функции доступны из интерфейса командной строки. Hadoop MapReduce — программный фреймворк для кодирования и выполнения распределённых вычислений в рамках парадигмы MapReduce, а также набор Java-классов и исполняемых утилит для создания пакетных заданий на MapReduce-обработку. Разработчику приложения для Hadoop MapReduce необходимо реализовать базовый обработчик, который на каждом вычислительном узле кластера обеспечит преобразование исходных пар «ключ-значение» в промежуточный набор пар «ключ-значений», и обработчик, сводящий промежуточный набор пар в окончательный, сокращённый набор. Фреймворк передаёт на вход свёртки отсортированные выводы от базовых обработчиков, сведение состоит из трёх фаз — shuffle (тасовка, выделение нужной секции вывода), sort (сортировка, группировка по ключам выводов от распределителей — досортировка, требующаяся в случае, когда разные атомарные обработчики возвращают наборы с одинаковыми ключами, при этом, правила сортировки на этой фазе могут быть заданы программно и использовать какие-либо особенности внутренней структуры ключей) и собственно reduce (усечение) — получения результирующего набора. Для некоторых видов обработки свёртка не требуется, и фреймворк возвращает в этом случае набор отсортированных пар, полученных базовыми обработчиками. В руководстве Hadoop указывается, что приемлемым уровнем параллелизма является использование 10-100 экземпляров базовых обработчиков на узел кластера, а для задач, не требующих значительных затрат процессорного времени — до 300. Hadoop MapReduce позволяет создавать задания как с базовыми обработчиками, так и со свёртками, написанными без использования Java: утилиты Hadoop streaming позволяют использовать в качестве базовых обработчиков и свёрток любой исполняемый файл, работающий со стандартным вводом-выводом операционной системы, есть также SWIG-совместимый прикладной интерфейс программирования Hadoop pipes на C++. Также, в состав дистрибутивов Hadoop входят реализации различных конкретных базовых обработчиков и свёрток, наиболее типично используемых в распределённой обработке.

Архитектура разрабатываемой программы по сути - система облачных(распределенных) вычислений. В работе рассматривается решение задачи построения контекстного облака тегов для результатов поиска с помощью использования парадигмы программы-посредника, которая находится между конечным пользователем и фактической поисковой выдачей. Этот подход активно применяется в секторе  компьютерной визуализации, в частности для удаленной визуализации. К примеру, в работе[5] подобный подход используется для реализации системы удаленной визуализации. Система состоит из трёх уровней: (1) модулей визуализации, (2) сервиса-посредника и (3) интерфейсов пользователя. Каждый модуль визуализации (программа рендеринга) –  это один или несколько процессов, ответственных за загрузку и графическое представление экспериментальных данных определённого типа. Сервис-посредник это серверный процесс, он принимает команды от интерфейса пользователя и направляет их к программам рендеринга. Интерфейсы пользователя – в настоящее время построенные на веб-технологиях – отображают построенные графические представления данных и взаимодействуют с пользователем.[10] Можно утверждать, что подобная модель имеет право на существование и может рассматриваться как система распределенных вычислений.


Аппликация грубых множеств

Рассматривается возможность применения теории грубых множеств для задач визуализации и обработки информации. Задание функций принадлежности для множества можно рассматривать, как способ упорядочения этого множества. Так же очевидно параллель между предыдущим и ассоциативными массивами. Наибольший интерес представляет рассмотрение функций принадлежности грубых множеств, как относительную метрику оценки эффективности. В общем случае, можно рассмотреть нечеткое множество X, где для каждого элемента множества (объекта) задана функция принадлежности X(x)<0,1>.  Функция принадлежности: X(x)<0,1>  задает степень принадлежности элемента множеству, в отличие от классической теории, когда элемент точно принадлежит множеству. Функция принадлежности переводит множество само на себя. Можно рассматривать , как вероятность  принадлежности элемента множеству.

Вопрос об определении алгоритма по существу равносилен вопросу об определении вычислимой функции. Цель - задать функцию принадлежности для любого элемента множества. Этот процесс называется фаззификацией, обратный соответственно называется дефаззификацией. Несмотря на то, что область определения дискретное множество (и, следовательно, можно построить отображение на область определения натуральных чисел для вычислимой функции) функция принадлежности, очевидно, считается непрерывной или кусочно-непрерывной. Здесь необходимо добавить информацию о теории грубых множеств. Теория грубых множеств, так же как и теория нечетких множеств, является один из возможных подходов к неопределенности. Эту теорию можно рассматривать как одно из развитий идеи Фреге о неопределенности, в частности, в данном подходе нечеткость определяется через границу множества, а не через частичную принадлежность, как в теории нечетких множеств. Если знаний о множестве не достаточно для его строгого определения, то граница не равна нулю, иначе стандартное (четкое) множество. Граница, как топологическое понятие – разность между замыканием и внутренностью множества.

Нижняя  аппроксимация:

Верхняя аппроксимация:

Граница:                             

Важное понятие данной теории – гранулярность. Множество представляется в виде совокупности элементарных знаний. Нижняя аппроксимация множества рассматривается как объединение всех гранул, которые полностью содержатся в множестве, а верхняя аппроксимация – как объединение всех гранул, имеющих непустое пересечение с множеством (Рис 1.2).

Рис. 1.2

Функция принадлежности определяется как:  

Это функция принадлежности двум множествам, так как не учитывает границу, если множества не пересекаются =0, если содержится одно в другом =1 (Рис 1.3).

Рис. 1.3

Граница дает дополнительную информацию. Простой пример оценки интерфейса (наивный байесовский подход) – два базисных знака фон и кнопка. Определим (фон)=0, (граница)=1/2, (кнопка)=1. Гранула – пиксель. Можно оценить минимальный размер кнопки через сумму вероятностей попиксельно. Вариант с границами гранулированных множеств легко расширяем. Кнопка в виде круга лучше прямоугольной, так как имеет наименьшую границу. Для трехмерной графики гранула – графический приметив. Определены операции пересечения и объединения. Можно ввести любое количество базисных знаков и функцию принадлежности нескольким знакам (кластеризация).

Грубые множества находят применение при работе с таблицами данных, которые называются также таблицами атрибут-значение, или информационными системами, или таблицами принятия решений (decision tables). Таблица принятия решений (decision table) – это тройка Τ = (U, C, D), где U – это множество объектов, С – это множество атрибутов условий (condition attributes), D – это множество атрибутов решений (decision attributes). Ниже приведен пример подобной таблицы (Таб. 1.1).

U

C

D

Головная боль

Температура

Грипп

U1

да

Нормальная

Нет

U2

да

Высокая

Да

U3

да

Нормальная

Нет

U4

да

очень высокая

Нет

U5

нет

Высокая

Нет

U6

нет

очень высокая

Да

U7

нет

Высокая

Да

U8

нет

очень высокая

Да

Таб. 1.1

Проанализировав таблицу, мы получаем, следующие данные:
U = {U1, U2, U3, U4, U5, U6, U7, U8}
C = {Головная боль, Температура}
D = {Грипп}

Возможные значения атрибутов:
VГоловная боль = {да, нет}
VТемпература = {нормальная, высокая, очень высокая}
VГрипп = {да, нет}

Разбиение множества U в соответствии со значениями атрибута Головная боль имеет вид:

Sда = {1, 2, 3, 4}

Sнет = {5, 6, 7, 8}

S = {{1, 2, 3, 4}, {5, 6, 7, 8}}


Разбиение множества U в соответствии со значениями атрибута Температура имеет вид:

Sнормальная = {1, 3}

Sвысокая = {2, 5, 7}

Sочень высокая = {4, 6}

S = {{1, 3}, {2, 5, 7}, {4, 6}}


Разбиение множества U в соответствии со значениями атрибута решения Грипп имеет вид:

Sда = {2, 6, 7, 8}

Sнет = {1, 3, 4, 5}

S = {{2, 6, 7, 8}, {1, 3, 4, 5}}

Пациент U5 и U7 неразличимы по атрибутам Температура и Головная боль, но при этом U7 оказывается болен гриппом. Из этого следует, что эти два случая будут считаться граничными и не могут быть четко выявлены исходя из доступных знаний. Набор {U2, U6, U8} может считаться нижней аппроксимацией признаков гриппа, верхней аппроксимацией будет набор {U2,U5, U6, U7, U8} и соответственно границей будет {U5, U7}.

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

  1.  Наивный Байесовский
  2.  Индуктивный
  3.  Метод опорных векторов
  4.  Фильтрация

«Наивный» байесовский классификатор. В данном методе предполагается условная независимость признаков друг от друга для данного значения слова. Хотя сама модель основывается на предположениях, параметры вычисляются по тестовым данным. Применительно к разрешению многозначности, признаками обычно являются термины, т.е. контекст рассматривается как «набор слов». Обычно это тысячи двоичных признаков, обозначающих наличие или отсутствие слова в тексте.

Индуктивное построение классификатора для категории  заключается в определении функции принадлежности документа к категории , которая представляет собой степень отношения (от 0 до 1) документа  к категории . Данная функция  имеет различную структуру, в зависимости от классификатора: например, в «наивном» байесовском подходе она определяется с помощью вероятностей, в то время как в методе Роккио  представляется в виде метрики в r-мерном пространстве.

Главная идея метода опорных векторов заключается в том, чтобы отобразить наше первоначальное множество атрибутов в пространство признаков большой размерности, а затем построить в этом пространстве линейное классифицирующее правило («оптимальную гиперплоскость»). Таким образом, мы сможем найти максимальную границу между векторами двух классов. Векторы, задающие эту границу, называются «опорными векторами». Получается, что они могут заменить все обучающее множество экземпляров.

Фильтрация относится к группе методов отбора терминов, которые выбирают из первоначального множества терминов те, которые будут использоваться для индексации документа. В соответствии со значениями определенной числовой функции, которая определяет «важность» термина для классификации, выбираются r` << r терминов, на которых достигаются наибольшие значения данной функции.


Язык программирования Ruby

Ruby – достаточно молодой языков программирования. Вот как описывает Ruby его создатель, японский программист Юкихиро Мацумото (Yukihiro Matsumoto): "Это мощный и динамический объектно-ориентированный язык с открытыми исходниками, который я начал разрабатывать в 1993 году. Ruby работает на многих платформах, включая Linux и многие реализации Unix, MS-DOS, Windows 9x/2000/NT, BeOS и MacOS. Главная цель Ruby - эффективность разработки программ, и пользователи найдут, что программирование на нем эффективно". В Японии Ruby сильно потеснил такие известные языки как Python и Perl и начал распространяться по всему миру. У этого языка очень неплохие шансы стать действительно популярным - ведь он вобрал в себя достоинства других языков, учтя их недостатки. Этот язык, несомненно, является одним из лучших в качестве первого языка программирования, изучаемого студентами и школьниками. Быстрый цикл разработки (редактирование - запуск - редактирование), использование интерпретатора, изначальная объектно-ориентированность языка, нетипизированные переменные, которые не требуют объявления - все это позволяет пользователям сконцентрировать свое внимание на общих принципах программирования. Использование Ruby в различных операционных системах практически ничем не отличается, а результаты выполнения не зависят от используемой ОС. Ruby – интерпретируемый язык. Так как это свойство отрицательно сказывается на производительности, то хочется дать некоторые комментарии. Во-первых, быстрый цикл разработки является важнейшим достоинством, которое перевешивает некоторые недостатки. Во-вторых, хотя Ruby и не является катастрофически медленным, в тех случаях, когда скорость абсолютно необходима, допускается возможность написания части кода на языке C. Наконец, в-третьих, существует большая вероятность того, что когда-нибудь будет написан компилятор с языка Ruby.

Программа на языке Ruby, часто называемая скриптом, есть последовательность инструкций (утверждений, предложений). Каждая инструкция по умолчанию заканчивается концом строки. Если же по каким-либо причинам требуется разместить несколько инструкций на одной строке, то их нужно разделять символом ; (точка с запятой). С другой стороны, иногда инструкция не помещается на одной строке. В этом случае символ \ сигнализирует о том, что ее продолжение располагается в следующей строке.

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

При описании Ruby было отмечено, что он является объектно-ориентированным языком программирования. Это означает что все, с чем работает программа, является объектом, при этом вычисление осуществляется посредством взаимодействия объектов. Каждый объект есть представитель (экземпляр) некоторого класса и его поведение (функциональность) определяется именно им.

В данной работе язык Ruby был использован для разработки кода программы-посредника, отвечающего за обработку результатов поиска перед их выводом на экран пользователя. Использование именно этого языка было обусловлено несколькими факторами:

  •  Быстрый цикл разработки, для проверки модели и первичного тестирования
  •  Удобная работа с ассоциативными массивами, которые используются для реализации функционала принадлежности
  •  Возможность интеграции сервера распределенных вычислений Hadoop


Практическая часть

Практическая часть данной работы состоит из следующих разделов:

  •  Разработка модели
  •  Создание прототипа программы
  •  Тестирование и обзор будущего развития

Разработка модели

Построение модели требует формулировки основных определений. Начнем с определения предметной области. Понятие “Визуальные супервычисления” вводится в работе [11], где указывается, что они касаются инфраструктурных технологий для поддержки визуальных и интерактивных вычислений вообще и визуализации в частности в сложных сетевых вычислительных средах. Одним из способов повышения эффективности разработки – это применение всевозможных конструкторов. В области визуальные супервычислений – это конструктор систем визуализации [12]. Обозначим основные требования к такому конструктору, с кратким пояснением, почему выбраны именно эти спецификации:

  •  Web-интерфейс, глобальная метафора визуализации – мировая паутина;
  •  Идея плавного перехода от off-line визуализации к on-line в параллельных вычислениях по-прежнему актуальна [10];
  •  Возможность применения модели потока данных к графическому конвейеру, в том числе с использованием средств визуального программирования;
  •  Оценка эффективности в рамках формальной модели.
  •  Разнообразие определений визуализации можно объяснить тем, что данный термин существенно зависит от контекста  его применения.

Визуализация

Стоит отметить общую тенденцию рассмотрения компьютерной визуализации, как единого феномена. Если уж феноменология, то разрешите рассматривать сложные определения, для их лучшей структурированности по трем направлением: a. онтология (происхождение определения); b. гносеология (смысл); c. целеполагание, которое дает условие экстремальности на пути формализации.

a. Несомненно, по происхождению, визуализация - графический алгоритм.

b, Визуализация – интерактивный процесс, где ввод, вывод осуществляется в лексикографическом виде. Такое определение мало, чем отличается от расширения понятия графический алгоритм. В тоже время между алгоритмом и визуализацией есть существенные различия, которые выражаются, прежде всего в различие целей. Цель визуализации, как анализ результатов вычислений – это интерпретация.

c. Когнитивное расстояние измеряет усилия пользователя, необходимые для преобразования действий по вводу данных и представлений выводимой информации в операции и объекты прикладной области. Переопределим его таким образом: Когнитивное расстояние – это расстояние между модельными объектами ввода и вывода в рамках ментальной модели пользователя. И так цель можно сформулировать, как нахождение минимума когнитивного расстояния.

Чем плоха командная строка? Вроде соответствует ментальной модели, но минимум не достигается: ввод можно представить в виде командной строки, а вывод вряд ли, вывод обращен к человеку, а не к компьютеру.

Стандартное отображение результатов поиска в  Интернете плохо масштабируется, поэтому попробуем построить другой вид отображения  - контекстное облако тегов. В основе лежит простая идея – для поиска применяется алгоритм MapReduce, поэтому вид отображения выберем аналогичный этому алгоритму, чтобы получить минимума когнитивного расстояния.

Формально цель (нахождение минимума когнитивного расстояния.) можно представить формулой:

S – Смысл, предельное понятие (ментальная модель пользователя). I – Оператор взаимодействия, назовем его итератор (интерпретатор), Модель (визуализации) представлена, как сумма (объединение) знаков (C), Модель строится, как решение некорректной задачи (предполагается, что  S известно), тогда цель можно определить, как нахождение наилучшего приближения для ментальной модели пользователя Мощность оператора /I /=k (дает k решений обратной некорректной задачи). Предлагается формализация визуализации на основе семиотического подхода, где ряд идей пересекаются с теоретическими исследованиями в книге [7]:.

Также возможна аналогия рассмотрения когнитивного расстояния, как границы грубого множества [8], функцию принадлежности которого задает метрику оценки эффективности.

Модель потока данных

Модель потока данных активно применяется в супервычислениях. Схематично ее можно представить в виде (Рис. 2.1), справа выделена вычислительная часть, а слева вид отображения (в обратном порядке соответственно клиент-сервер), стрелочка обозначает правило вывода или замыкание. Данные рассматриваются, как упорядоченные конечные множества X (для каждого множества задана одна или несколько функций принадлежности ) у каждого множества свой поток (нить, процесс), возможно применение фильтрации данных (применение фильтра ) как метод сокращения информации и как метод слияния, объединения, агрегации данных. Конечно, для модели потока данных возможна другая аннотация, рассмотрение с позиций функционального или императивного программирования. Различия в этих стилях, наверное, стоит рассматривать через различия определения алгоритма, соответственно через рекурсивные функции и цепи Маркова.

Рис. 2.1.

Нас интересует утверждение об эквивалентности определений функции принадлежности и вычислимой функции. Задание функции принадлежности можно рассматривать, как инструментарий программирования и как метрику оценки эффективности с точки зрения грубых множеств [13]. Вопрос об определении алгоритма по существу равносилен вопросу об определении вычислимой функции. Вычислимые функции — это множество функций вида, , которые могут быть реализованы на исполнителе машин Тьюринга. Функция принадлежности: X(x)<0,1>  задает степень принадлежности элемента множеству, в отличие от классической теории, когда элемент точно принадлежит множеству, по сути, упорядочивает множество. Функция принадлежности переводит множество само на себя. Если область определения конечное дискретное множество, то можно построить отображение на область определения натуральных чисел для вычислимой функции.

Рис. 2.1 можно рассматривать и как средство визуального программирования, добавив итераторы – возможность взаимодействовать с элементами схемы. Так, нажимая на стрелочку можно задать замыкание (преобразование координат). Такое действие, по сути - итератор (оператор взаимодействия). В рамках человеко-компьютерного взаимодействия термины итератор и интерпретатор можно считать эквивалентными (интерпретация в процессе взаимодействия).

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

Итераторы  Ruby

В Ruby массивы - это объект, являющийся ассоциативным массивом специального вида, где ключ – это индекс элемента или прямоугольные скобки, по ключу [ выдается значение, которое соответствует адресу массива, а по ]  – длина массива. Кроме того, любой элемент массива может быть массивом, такая структура данных хорошо подходит для работы с графами, можно назвать такие массивы деревянными. Плюсом ассоциативных массивов является аппаратное хеширование.

a. Итераторы по происхождению, можно определить, как замыкание цикла (развитие конструкции for/in в этом смысле, Ruby близок к JavaScript).

b. По смыслу итератор – это параллельный цикл, или цикл с векторно-конвейерным  авто параллелизмом. Без циклов жить нельзя на свете, но в ряде случаев их можно заменить итераторами. Поясним этот тезис на простом примере (Рис. 2.2): довольно часто из потока данных нужно убрать лишние строки (шум).


x=("a".."z").to_a

a="a"

x.size.times do |n|

if x[n]==a

   x[n]=nil

end

end

x=x.compact

Рис. 2.2.

Эквивалентный цикл нет смысла приводить, стоит отметить только, что в теле цикла значение переменной цикла увеличивали бы на единицу, т. е. изменялось бы. В итераторе все три значения цикла константы. В примере цикл заменен циклом-итератором и методом compact, которые можно распараллелить. Итераторы можно представить и в форме функционального  программирования I(x,a) - бинарный оператор взаимодействия между x и a.

c. Итак, можно сформулировать цель - сравнение эффективности работы цикла и итератора. Казалось бы, можно померить времена, но абсолютная метрика ничего не даст, так как время нелинейно (в смысле нарушения принципа суперпозиции), на нелинейность влияют и многозадачность, и умные трансляторы, автоматически распараллеливающие циклы, и разная языковая природа этих двух конструкций. Следовательно, необходима относительная метрика в рамках общей модели. Например, через задание функции принадлежности грубого множества, где верхней границей является цикл, а нижней итератор. Рассматриваемый пример можно было реализовать через метод  find_all, затем нам понадобится множественный однопроходный поиск - вводится логический итератор any? и так до бесконечности или есть насыщение?

В Ruby для массивов реализован метод sort (сортировка по возрастанию). Рассмотрим пирамидальную сортировку, где вместо замены элементов (значений), будем менять индексы элементов (ключи). В этом случае пирамида переходит в квадрат и этот квадрат можно распараллелить хоть по строкам, хоть по столбцам, хоть блочно. Вряд ли можно говорить об эквивалентности (морфизме) этих двух алгоритмов, так как “квадратный” алгоритм существенно зависит от схемы распараллеливания. Не трудно выбрать такой “квадратный” алгоритм, который бы соответствовал сортировки методу деления пополам. Кроме того, в “квадратном” алгоритме на одно присваивание значения меньше, пусть оно float, а ключ int – это было существенно во времена роботронов, казалось бы, такой пустяк, а давал ускорение (операция с плавающей запятой была значительно медленнее). Вопрос эффективности спустя годы вновь становится актуальным для экстремальных вычислений.

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

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

Фильтрация данных

a. Графический конвейер включает три этапа обработки информации: фильтрация данных, геометрическая обработка  и растеризация. Фильтрация – это процесс удаления незначащих объектов и атрибутов данных. В этом определение не хватает интерактивности. Рассмотрим визуализацию данных большого объема. Предположим, что не хватает ресурсов для вывода сложного геометрического объекта, можно вывести в интерактивном режиме три проекции, или набор сечений, надеясь, что пользователь сможет интерпретировать эти данные и восстановить объект. Следовательно, фильтр следует рассматривать, как процедуру изменения и восстановления геометрии или информации.

b, Смысловое определение фильтра можно вывести из сравнения фильтрации и хеширования. Фильтр – это любая поэлементная операция над данными, изменяющая их количество. Из этого определения следует, что объединение объектов или слияние баз данных является фильтром. Текстовое сжатие изменяет не количество  данных, а их длину, следовательно, не является фильтром. Аналогично, изменение цвета, вращение, перемещение, увеличения (без изменения уровня детализации) объекта меняют некоторые значения, а не количество, то есть эти операции не являются фильтрами. Для обеспечения векторного (конвейерного) параллелизма нужна возможность применения фильтра к любому элементу множества. Так при реализации фильтра в работе [14] использовались особенности синтаксиса языка Си, позволяющего передавать в качестве параметра функции, реализующей фильтр, ссылку на функцию. Однако при решении подобной задачи можно воспользоваться и другими методами.

с. Цель фильтрации данных – получение необходимой информации с минимальными затратами. Следовательно, операции, которые являются фильтрами надо выполнять параллельно, минимизировать количество передаваемых данных, применять когнитивную визуализацию.

Реализацию фильтров, также как и работу с ассоциативными массивами  можно организовать через задание функции принадлежности, которую можно рассматривать, например, как правило, слияния данных. Для контекстного облака тегов рассмотрим простой фильтр (индуктивное построение): удаляя лишнюю информацию и увеличивая ширину контекста через последовательное обращение к Goggle API можно получить интересующий результат.

Важным вопросом является отличие параллельного фильтра от родительского, последовательного фильтра. Если операция выполняется над распределенными данными, которые не являются тесно связанными, то параллельный фильтр совпадает с последовательным. Например, рассмотрим поиск по ключевому слову в Интернете. Предположим, есть слишком большой текст, который не входит на один жесткий диск, разбив текст на два файла одинаковой длины, его можно поместить на две машины. При таком разбиение большая вероятность того, что некоторое слово будет разделено в два файла, выполняя стандартный поиск это слово не будет найдено. В данном случае решение довольно простое: достаточно одного обмена между файлами или немного увеличив длины файлов хранить это слово целиком в обоих файлах (в последнем случае не нужен дополнительный обмен). Также можно запомнить исключение из правила поиска для разорванного слова. Предположим, возникла необходимость хранить отформатированный текст на 24 колонки в двух файлах по 12 колонок, попробуйте написать эффективный параллельный фильтр поиска. Видно, что при написании параллельного фильтра узким местом является точка или граница разрыва распределенных, связанных данных. Оценкой правильности реализации параллельного фильтра является получение того же результата, что и при выполнении последовательного фильтра. С точки зрения когнитивности визуализации не обязательно сто процентное совпадение результатов, разрывы или возникновение артефактов на границе могут быть не существенны.

В реализованном варианте контекстного облака тегов фильтры пока не используются, но активно применяются технологии закрашивание или категоризация цветом (“brushing”) и линковка. Так ненужный ключ в ассоциативном массиве просто закрашивается белым цветом.

Метрики оценки эффективности

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

В качестве относительной метрики эффективности далее будем рассматривать масштабируемость, которую определим как отношение количества результатов поиска в системе контекстного облака тегов (максимальный размер из ассоциативных массивов или число строк в таблице) к количеству результатов поиска в исходной системе (например, Google). Отметим, что значения данной метрики будет лежать в [0;1], причем  максимальная эффективность будет достигаться на минимальном значении этой метрики. Т.е. если исходная система будет выдавать 7 результатов, а проектируемая – 5, то масштабируемость будет представлять нечеткое число 5/7.


Создание прототипа программы

Целью данной работы является постановка и демонстрация решения задачи построения контекстного облака тегов, как средство эффективной интерпретации информации в больших объемах данных. Система строится с использованием парадигмы программы-посредника, которая находится между конечным пользователем и фактической поисковой выдачей. Для разработки использовался язык Ruby, а так же фреймворк Sinatra. Sinatra —открытый программный каркас написанный на языке Ruby, предназначенный для разработки веб-приложений. Он является альтернативой таким популярным фреймворкам на Ruby как Ruby on Rails и Merb. Фреймворк представляет собой небольшое и гибкое приложение, которое фокусируется на идее быстрого создания веб-приложений на Ruby с минимальными усилиями. Реализация в виде веб-приложения была выбрана в связи с тем, что практически все исследования и разработки в рамках поисковых моделей лежат в поле онлайн, а не оффлайн поиска. Для создания приложения так же использовалась библиотека jQuery, а для тестирования модели была выбрана поисковая система Google, а именно Google Custom Search, на котором были проведены исследования и измерения метрики масштабируемости результатов. Ниже будет представлено описание разработанного прототипа программы.

Основное окно приложения выглядит как обычная поисковая строка, с возможностью выбора  ширины контекста, т.е. количества слов поиска слева и справа от строки поиска (Рис. 2.3).

Рис 2.3

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

search_api = function search_api(){

var search_str = $('[name="gstr"]').val();

$.getJSON('https://www.googleapis.com/customsearch/v1?key=AIzaSyDfe6OsUoujJ3AB5_d6zRBRlh5_ADJmSD4&cx=007625171540799111237:ypbh5mdmvw0&q="'+search_str+'"&fields=searchInformation,items(title,fileFormat,snippet,link)&start='+current_page,function(response){

   if(response&&response.searchInformation){

     if(response.searchInformation.totalResults>0){

       for (var i = 0; i < response.items.length; i++) {

         var item = response.items[i];

         var title = item.title;

         switch(item.fileFormat){

           case 'PDF/Adobe Acrobat':{

             title="[PDF] "+title;

             break;

             }

           case 'Microsoft Word':{

             title="[DOC] "+title;

             break;

             }

           default:{

             break;

             }

         }

         temp_results.push(title.replace(/\r\n/g, "")+"\n"+item.snippet.replace(/\r\n/g, "")+"\n"+item.link.replace(/\r\n/g, ""));

       }

     }

   }

   current_page++;

   if(current_page<=page_num){

     search_api();

   }else{

     $('[name="test" ]').submit();

   }

 });

}

Данный запрос получает информацию с помощью технологии Google Custom Search API, затем формирует из неё корпус текста, на котором в дальнейшем будут осуществляется операции поиска и фильтрации. При этом  количество полученной информации можно регулировать через переменную page_num. Затем, полученные данные передаются программе-посреднику, которая занимается их обработкой. Во время этих действий из текста выделяются контекстные слова, стоящие рядом с поисковыми, определяется формат данных и формируется основная структура, на которой будет производиться все операции по анализу текста. Далее пользователь переходит на следующую страницу, на которой  отображаются найденные документы, а так же контекст поиска (Рис 2.4). При этом в центре контекстного облака тегов находится поисковая фраза, выделенная совокупностью всех цветов, поскольку она содержится во всех найденных документах. Остальные слова раскрашиваются в зависимости от частоты употребления в заданном поисковом контексте в каждом документе.

Рис 2.4

В зависимости от ширины поискового контекста пользователь будет получать различные по размеру контекстные облака тегов (Рис 2.5).

Рис 2.5

Таким образом, пользователь может без труда определить различные результаты поисковой выдачи. Раскраска слов производится в функции form_colors(). Основная часть функции представлена ниже.

maxsol.times do |i|

    maxcol.times do |j|

      color=Array.new(3) {|ii| 0x00}

      if astr[i]&&astr[i][j] != " "

         dst="dst"+k.to_s

         dstt[k]=dst

         max=0;maxl=0

         3.times do |l|

           if word[j].kind_of?(Array)

             if max<word[j][i][l]

                max=word[j][i][l]

                maxl=l

             end

           end

         end

         3.times do |l|

           if word[j].kind_of?(Array)

             if word[j][i][l]>0

                 if l==maxl

                   color[l]=(0xff-word[shcontext[0]][0][l]+word[j][i][l])*mask[l]

                 else

                   color[l]=(0x80+word[j][i][l])*mask[l]

                 end

             else

               #color[l]=0xff

             end

           end

         end

         if(color==[0,0,0])

           color=Array.new(3) {|ii| 0xff}

         end

         new_color="rgb("+color.join(',')+')';

         dcol[k]=new_color

         if !dhash[astr[i][j]].kind_of?(Array) then

           dhash[astr[i][j]]=[]

         end

         dhash[astr[i][j]].push(dst)

         k=k+1

      end

    end

Работа данной функции сводится к определению максимального порядка встречаемости для слов и пропорциональная раскраска. При этом учитывается, что не раскрашенные слова маркируются белым, но при этому всё равно попадают в выдачу. В данном окне пользователь может задать фильтрацию по тем источникам, которые ему необходимы (Рис 2.6), а так же выбрать только интересующие его контекстные слова. Оба этих действия реализованы с помощью ajax-запросов и не требуют перезагрузки всей страницы.  

Рис 2.6

Фильтрация по источнику данных реализована в виде обработчика события нажатия на соответствующую кнопку.

 $('#typebox :checkbox').change(function(){load_results();});

Функция load_results() состоит из двух ajax-запросов, первый из которых запрашивает у программы-посредника список слов, которые встречаются в выбраных типах источников.

$.post('/get_words',{left:$('[name="left"]').val(),right:$('[name="right"]').val(),gstr:$('[name="gstr"]').val(),pdf:($('[name="pdf"]').prop('checked')?'1':'0'),doc:($('[name="doc"]').prop('checked')?'1':'0'),html:($('[name="html"]').prop('checked')?'1':'0')},function(data){

     if(data!='Fail'){

       $('#cloud').html(data);

И при успешном выполнении выводит их на экран.

Обработчик, при получении подобного запроса выполняет следующие действия:

post '/get_words' do

 astr=session[:astr]

 if !astr.kind_of?(Array)

   if form_results()

       astr=session[:astr]

   end

 end

 if astr.kind_of?(Array)

   @astr=astr

   @maxsol=session[:maxsol]

   @maxcol=session[:maxcol]

   @dcol= form_colors()

   @dstt=session[:dstt]

   erb :words, :encoding=>"utf-8"

 else

   "Fail"

 end

end

Как можно заметить, обработчик использует сессии, для того, чтобы не анализировать исходный набор данных постоянно, а хранить результаты анализа в памяти. Функция form_results() как раз отвечает за анализ исходного набора данных, а функция form_colors() выполняет расчет раскраски для каждого слова. Второй запрос совершает запрос к обработчику для получения списка найденных документов и его раскрашивание.

       $.post('/get_results',{left:$('[name="left"]').val(),right:$('[name="right"]').val(),gstr:$('[name="gstr"]').val(),pdf:($('[name="pdf"]').prop('checked')?'1':'0'),doc:($('[name="doc"]').prop('checked')?'1':'0'),html:($('[name="html"]').prop('checked')?'1':'0')},function(data){

         if(data!="Fail"){

           $('#search_results').html(data);

           for(var i in mask){

             if(mask.hasOwnProperty(i)){

               if($('[name="'+i+'"]').prop('checked')=='0'){

                 $('.color_'+mask[i]).hide();

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

При выделении одного конкретного слова – ключа, происходит выделение данного слова и всех остальных слов, встречающихся в документах вместе с исходным, а затем происходит вывод документов, в которых содержатся эти слова (Рис 2.7). На указанном рисунке выделено слово «визуальных», которое содержится в документе вместе со словами «супервичисления», «понятие» и «манаков».

Рис 2.7

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

$.post('/get_context',{word:$.trim($(this).html()),index:$(this).parent().parent().find('td').index($(this).parent()),left:$('[name="left"]').val(),right:$('[name="right"]').val(),gstr:$('[name="gstr"]').val(),pdf:($('[name="pdf"]').prop('checked')?'1':'0'),doc:($('[name="doc"]').prop('checked')?'1':'0'),html:($('[name="html"]').prop('checked')?'1':'0')},function(data){

     if(data.data!='Fail'){

       var words = data.data;

       $('#'+words.join(',#')).css('color','#000000');

       var txt_result = data.result;

       $('#result'+txt_result.join(',#result')).css('color','#000000');

     }},"json");

Для всех полученных идентификаторов выполняется действие перекраски полученных слов и документов в черный цвет. Получение этих идентификаторов реализовано в обработчике с помощью заранее сформированных ассоциативных массивов.

a2_txt = session[:a2_txt]

   word = session[:word]

   k = conhash[index][word_context]

   if(k>=0) then

     temp_word = word[index][k]

     result = []

     i=0

     words_to_mark=[]

     words_count=0

     (temp_word.size).times do |j|

       if(j>=3&&j%2==1) then

         result[i]=temp_word[j]

         i+=1

         a2_txt[temp_word[j]*4+2].size.times do |jj|

           temp_array = a2_txt[temp_word[j]*4+2][jj]

           temp_array.size.times do |word_index|

             if temp_array[word_index]&&temp_array[word_index]!=0 then

               words_to_mark[words_count]= temp_array[word_index]

               words_count+=1

             end

           end

         end

       end

     end

   В результате выполнения этого кода в массиве words_to_mark будут собраны все слова, которые следует раскрасить черным цветом. Затем функция вычисляет уникальные идентификаторы для каждого полученного слова и возвращает их. А массив result в результате будет содержать идентификаторы тех документов, в которых встречаются найденные слова.


Тестирование и перспективы развития

При  тестировании использовалась метрика эффективности, обозначенная как масштабируемость, которая оценивает, как хорошо разработанная модель позволяет уменьшать объемы данных, демонстрируемых пользователю. Так же планируется проведение эмпирических исследования зависимости выбранной метрики от ширины контекста и анализ полученных результатов. В дальнейшем ожидается проведение более массового тестирования для изучения отношения пользователя к измененному поисковому интерфейсу и возможное модифицирование этого интерфейса с учетом полученных замечаний. Предполагается использование сервера Hadoop для реализации и выполнения вычислений в рамках парадигмы MapReduce, что может впоследствии быть использовано для тестирования быстродействия системы на больших объемах данных.


Список литературы

  1.  Самарский А.А., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. - М.: Физматлит, 3993, - 320 с.
  2.  Lohmann, S., Ziegler, J., Tetzlaff, L. Comparison of Tag Cloud Layouts: Task-Related Performance and Visual Exploration, T. Gross et al. (Eds.): INTERACT 2009, Part I, LNCS 5726, pp. 392–404, 2009.
  3.  NIST, 2011, “Cloud computing is a model for enabling ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction”
  4.  NIST, 2011, p. 6
  5.  Dean, Jeffrey and Ghemawat, Sanjay MapReduce: Simplified Data Processing on Large Clusters// OSDI ’04: 6th Symposium on Operating Systems Design and Implementation. — USENIX, 2004. — С. 137-149. — DOI:10.1145/1327452.1327492
  6.  Cutting, Doug Hadoop: a brief history. Yahoo! (24 March 2008) http://research.yahoo.com/files/cutting.pdf
  7.  White, Tom Hadoop: The Definitive Guide. — 2-nd edition. — Sebastopol: O’Reilly Media, 2011. — 600 p. — ISBN 978-1-449-38973-4
  8.  Metz, Cade How Yahoo Spawned Hadoop, the Future of Big Data  (англ.). Wired (18 October 2011)
  9.  Моррисон, Алан и др. Большие Данные: как извлечь из них информацию  (рус.). Технологический прогноз. Ежеквартальный журнал, российское издание, 2010 выпуск 3. PricewaterhouseCoopers (17 декабря 2010)
  10.  Бахтерев М.О., Васёв П.А., Казанцев А.Ю., Манаков Д.В. , Система удалённой визуализации для инженерных и суперкомпьютерных вычислений // Вестник ЮУрГУ. Серия "Математическое моделирование и программирование". 2009. № 17 (150). Вып. 3. С. 4-11
  11.  K. Brodlie, J. Brooke, M. Chen, D. Chisnall, A. Fewings, C. Hughes, N. W. John, M. W. Jones, M. Riding and N. Roard, Visual Supercomputing - Technologies, Applications and Challenges, // Eurographics 2004, STAR Reports, P. 37-68.
  12.  Васёв П.А., Кумков С.С., Шмаков Е.Ю. О создание среды разработки систем научной визуализации // XIII Международный семинар супервычисления м математическое моделиро-вание. Тезисы. Саров. ФГУП «РФЯЦ ВНИИЭФ», 2011, С. 50-51.
  13.  Z.Pawlak, Rough sets, J. Comput. Information Sciences, vol. 11, 1982, P. 341-345
  14.  Manakov D., Mukhachev A., Shinkevich A. Visualization of the Distributed Data of Huge Vol-ume. Assembly, Filtration, Sorting. // Proccedings of the 13-th International Conference on Computer Graphics and Vision Graphicon-2003 Moscow, September 5-10, 2003. P. 198-201.


ПРИЛОЖЕНИЯ

Приложение 1

Файл tag.rb

# coding: utf-8

require 'sinatra'

require 'erb'

require "sinatra/reloader" if development?

use Rack::Session::Pool

def form_results()

 right = Integer(params[:right])

 left = Integer(params[:left])

 mask=[]

 mask[0] = params[:pdf]?Integer(params[:pdf]):0

 mask[1] = params[:doc]?Integer(params[:doc]):0

 mask[2] = params[:html]?Integer(params[:html]):0

 shcontext = [left,0,right]

 tr1 = 'ЁЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ'

 tr2 = 'ёйцукенгшщзхъфывапролджэячсмитьбю'

 sh = params[:gstr].to_s.tr(tr1,tr2)

 

 a2_txt = session[:'a2_txt']

 if !a2_txt.kind_of?(Array)||a2_txt.empty?

   return false

 end

 search_result=Array.new((a2_txt.size/4)) {|ii| 0}

 maxsol=shcontext[0]+shcontext[2]+1

 key =Array.new(maxsol) {|ii| 0}

 word=Array.new(maxsol) {|ii| 0}

 conhash=Array.new(maxsol) {|ii| 0}

 jj=0

 maxcol=0

 conhash.size.times do |i|

   wd=Array.new(1)

   wd[0]=[0,0,0]

   conhash[i] = Hash.new(-1)

   k=0

   if i!=shcontext[0]

    (a2_txt.size/4).times do |j|

     search_result[j]=Hash.new(-1)

     search_result[j]["type"]=a2_txt[j*4]

     search_result[j]["txt"]=a2_txt[j*4+1]

     a2_txt[j*4+2].size.times do |n|

       if a2_txt[j*4+2][n][i-jj]!=0

          if conhash[i][a2_txt[j*4+2][n][i-jj]]==-1

             conhash[i][a2_txt[j*4+2][n][i-jj]]=k

             wd[k]=[0,0,0]

             wd[k][a2_txt[j*4]]+=1

             wd[k]=wd[k]+[j,n]

             k+=1

             wd=wd+[]

          else

             k1=conhash[i][a2_txt[j*4+2][n][i-jj]]

             wd[k1][a2_txt[j*4]]+=1

             wd[k1]=wd[k1]+[j,n]

           end

       end

     end

    end

   else

    conhash[i][sh]=k

    wd[k]=[0,0,0]

    k+=1

    jj=1

   end

   word[i]=wd

   if maxcol<k

      maxcol=k

   end   

 end

 as=Array.new(maxsol) {|ii| " "}

 maxsol.times do |i|

   key[i]=conhash[i].keys

   as[i]=Array.new(maxcol) {|ii| " "}

   maxcol.times do |j|

     if j<key[i].size

         as[i][j]=key[i][j]

     else

        as[i][j]=" "

     end

   end

 end

 astr=as.transpose

 maxsol.times do |i|

   if i!=shcontext[0]

      word[i].size.times do |k|      

        3.times do |j|

          if word[shcontext[0]][0][j]<word[i][k][j]

             word[shcontext[0]][0][j]=word[i][k][j]

          end

        end

      end

   end

 end

 

 session[:search_results]=search_result

 session[:maxsol]=maxsol

 session[:maxcol]=maxcol

 session[:word]=word

 session[:conhash]=conhash

 session[:astr]=astr

 return true

end

def form_colors()

 right = Integer(params[:right])

 left = Integer(params[:left])

 mask=[]

 mask[0] = params[:pdf]?Integer(params[:pdf]):0

 mask[1] = params[:doc]?Integer(params[:doc]):0

 mask[2] = params[:html]?Integer(params[:html]):0

 shcontext = [left,0,right]

 word=session[:word]

 maxsol=session[:maxsol]

 maxcol=session[:maxcol]

 astr=session[:astr]

 k=0

 dstt=[]

 dcol=[]

 dhash = Hash.new("0")

 maxsol.times do |i|

    maxcol.times do |j|

      color=Array.new(3) {|ii| 0x00}

      if astr[i]&&astr[i][j] != " "

         dst="dst"+k.to_s

         dstt[k]=dst

         max=0;maxl=0

         3.times do |l|

           if word[j].kind_of?(Array)

             if max<word[j][i][l]

                max=word[j][i][l]

                maxl=l

             end

           end

         end

         3.times do |l|

           if word[j].kind_of?(Array)

             if word[j][i][l]>0

                 if l==maxl

                   color[l]=(0xff-word[shcontext[0]][0][l]+word[j][i][l])*mask[l]

                 else

                   color[l]=(0x80+word[j][i][l])*mask[l]

                 end

             else

               #color[l]=0xff

             end

           end

         end

         if(color==[0,0,0])

           color=Array.new(3) {|ii| 0xff}

         end

         new_color="rgb("+color.join(',')+')';

         dcol[k]=new_color

         if !dhash[astr[i][j]].kind_of?(Array) then

           dhash[astr[i][j]]=[]

         end

         dhash[astr[i][j]].push(dst)

         k=k+1

      end

    end

  end

 session[:dstt]=dstt

 session[:dhash]=dhash

 return dcol

end

get '/' do

 @maxsol=0

 @maxcol=0

 @astr=[]

 @dstt=[]

 @dcol=[]

 @left=2

 @right=2

 @mask=[1,1,1]

 @search_results=[]

 erb :test, :encoding=>"utf-8"

end

post '/get_words' do

 astr=session[:astr]

 if !astr.kind_of?(Array)

   if form_results()

       astr=session[:astr]

   end

 end

 if astr.kind_of?(Array)

   @astr=astr

   @maxsol=session[:maxsol]

   @maxcol=session[:maxcol]

   @dcol= form_colors()

   @dstt=session[:dstt]

   erb :words, :encoding=>"utf-8"

 else

   "Fail"

 end

end

post '/get_results' do

 mask=[]

 mask[0] = params[:pdf]?Integer(params[:pdf]):0

 mask[1] = params[:doc]?Integer(params[:doc]):0

 mask[2] = params[:html]?Integer(params[:html]):0

 @mask=mask

 search_results=session[:search_results]

 if !search_results.kind_of?(Array)

   if form_results()

       search_results=session[:search_results]

   end

 end

 if search_results.kind_of?(Array)

   @search_results=session[:search_results]

   erb :results, :encoding=>"utf-8"

 else

   "Fail"

 end

end

post '/get_context' do

 mask=[]

 mask[0] = params[:pdf]?Integer(params[:pdf]):0

 mask[1] = params[:doc]?Integer(params[:doc]):0

 mask[2] = params[:html]?Integer(params[:html]):0

 word_context = params[:word].to_s

 index = Integer(params[:index])

 @mask=mask

 conhash=session[:conhash]

 if !conhash.kind_of?(Array)

   if form_results()

       conhash=session[:conhash]

   end

 end

 if conhash.kind_of?(Array)

   a2_txt = session[:a2_txt]

   word = session[:word]

   k = conhash[index][word_context]

   if(k>=0) then

     temp_word = word[index][k]

     result = []

     i=0

     words_to_mark=[]

     words_count=0

     (temp_word.size).times do |j|

       if(j>=3&&j%2==1) then

         result[i]=temp_word[j]

         i+=1

         a2_txt[temp_word[j]*4+2].size.times do |jj|

           temp_array = a2_txt[temp_word[j]*4+2][jj]

           temp_array.size.times do |word_index|

             if temp_array[word_index]&&temp_array[word_index]!=0 then

               words_to_mark[words_count]= temp_array[word_index]

               words_count+=1

             end

           end

         end

       end

     end

     words_to_mark = words_to_mark.uniq

     words_to_mark-=[nil]

     dhash = session[:dhash]

     data=[]

     words_to_mark.size.times do |word_index|

       if(dhash[words_to_mark[word_index]].kind_of?(Array)) then

         data+=dhash[words_to_mark[word_index]]

       else

         data+=[dhash[words_to_mark[word_index]]]

       end

     end

     "{

   \"data\":#{data.to_s},

   \"result\":#{result.to_s}

   }"

   else

     "{\"data\":\"Fail\"}"

   end

 else

   "{\"data\":\"Fail\"}"

 end  

end

post '/test' do

tr1 = 'ЁЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ'

tr2 = 'ёйцукенгшщзхъфывапролджэячсмитьбю'

sh = params[:gstr].to_s.tr(tr1,tr2)

right = Integer(params[:right])

left = Integer(params[:left])

mask=[]

mask[0] = params[:pdf]?Integer(params[:pdf]):0

mask[1] = params[:doc]?Integer(params[:doc]):0

mask[2] = params[:html]?Integer(params[:html]):0

#sh = "ПАРАЛЛЕЛЬНАЯ фильтрация данных".tr(tr1,tr2)

sh1=sh.gsub(/(\S)\s/i){ $1 + "" }

shcontext = [left,0,right]

a_sh = sh.split(" ")

lsh = a_sh.size

shcontext[1] =lsh

a_txt = params[:google_results].scan(/.+/)#.split("\r\n")

j=i=0

a2_txt=[]

while (i<a_txt.size) do

 if j==0

    a=a_txt[i][/[A-Z\[\]]+/]

    if a=="\[PDF\]"

       a2_txt=a2_txt+[0,a_txt[i].sub("\[PDF\]\s","")]

    elsif a=="\[DOC\]"

       a2_txt=a2_txt+[1,a_txt[i].sub("\[DOC\]\s","")]

    else

      a2_txt=a2_txt+[2,a_txt[i]]

    end

 elsif j==1

 b=a_txt[i].tr(tr1,tr2).gsub(sh,sh1).split("...")

 b.size.times do |k|

   b[k]=b[k].scan(/[А-Яа-я]+/)

   ib=-1

   bcon=Array.new(shcontext[0]+shcontext[2]) {|ii| 0}

   b[k].size.times do |n|

     if b[k][n]==sh1

        ib=n

     end

   end

   if ib==-1

      puts "ERROR"

   end

   n=0

   im=0

   m=shcontext[0]-1

   while (n<ib) do

   if m>-1

      if b[k][ib-im-1].size < 3

        im+=1

      else

        bcon[m]=b[k][ib-im-1]

        m-=1

        im+=1

      end

   else

     m=ib

   end

   n+=1

   end

   n=0

   im=0

   m=0

   while (n<b[k].size-ib-1) do

   if m<shcontext[2]

      if b[k][ib+im+1].size < 3

        im+=1

      else

        bcon[shcontext[0]+m]=b[k][ib+im+1]

        m+=1

        im+=1

      end

   else

     n=b[k].size-ib

   end

   n+=1

   end

   b[k]=bcon

 end

 a2_txt=a2_txt+[b]

 elsif j==2

   c=a_txt[i].split(" ")

   a2_txt=a2_txt+[c[0]]

 

 elsif j==3

   c=a_txt[i].split(" ")

   j=-1

   if c[0]!="Дополнительные"  

      i-=1

   end

 end

j+=1

i+=1

end

session[:a2_txt]=a2_txt

@left=left

@right=right

@mask=mask

@search_str=sh

if form_results()

 @maxsol=session[:maxsol]

 @maxcol=session[:maxcol]

 @search_results=session[:search_results]

 @astr=session[:astr]

 @dcol=form_colors()

 @dstt=session[:dstt]

else

 @maxsol=0

 @maxcol=0

 @astr=[]

 @dstt=[]

 @dcol=[]

 @search_results=[]

end

erb :test, :encoding=>"utf-8"

end


Приложение 2

Файл test.erb

<html>

<head>

<meta http-equiv="Content-Type" content="text/html; charset=windows-1251" />

<link rel="stylesheet" type="text/css" href="/style.css" />

<script src="https://www.google.com/jsapi" type="text/javascript"></script>

<script language="javascript" src="/jquery.js"></script>

<script>

var temp_results = new Array();

var mask = new Object();

var page_num;

var current_page=1;

mask['pdf']=0;

mask['doc']=1;

mask['html']=2;

var colors = new Object();

update_colors = function update_colors(){

 for(var i in colors){

   if(colors .hasOwnProperty(i)){

     $('#'+i).css('color',colors[i]);

   }

 }

 $('.color_0').css('color','#ff0000');

 $('.color_1').css('color','#00ff00');

 $('.color_2').css('color','#0000ff');

}

search_api = function search_api(){

 var search_str = $('[name="gstr"]').val();

 $.getJSON('https://www.googleapis.com/customsearch/v1?key=AIzaSyDfe6OsUoujJ3AB5_d6zRBRlh5_ADJmSD4&cx=007625171540799111237:ypbh5mdmvw0&q="'+search_str+'"&fields=searchInformation,items(title,fileFormat,snippet,link)&start='+current_page,function(response){

   if(response&&response.searchInformation){

     if(response.searchInformation.totalResults>0){

       for (var i = 0; i < response.items.length; i++) {

         var item = response.items[i];

         var title = item.title;

         switch(item.fileFormat){

           case 'PDF/Adobe Acrobat':{

             title="[PDF] "+title;

             break;

             }

           case 'Microsoft Word':{

             title="[DOC] "+title;

             break;

             }

           default:{

             break;

             }

         }

         temp_results.push(title.replace(/\r\n/g, "")+"\n"+item.snippet.replace(/\r\n/g, "")+"\n"+item.link.replace(/\r\n/g, ""));

       }

     }

   }

   current_page++;

   if(current_page<=page_num){

     search_api();

   }else{

     $('[name="test" ]').submit();

   }

 });

};

load_results = function load_results(){

 $.post('/get_words',{left:$('[name="left"]').val(),right:$('[name="right"]').val(),gstr:$('[name="gstr"]').val(),

   pdf:($('[name="pdf"]').prop('checked')?'1':'0'),doc:($('[name="doc"]').prop('checked')?'1':'0'),html:($('[name="html"]').prop('checked')?'1':'0')},function(data){

     if(data!='Fail'){

       $('#cloud').html(data);

       $.post('/get_results',{left:$('[name="left"]').val(),right:$('[name="right"]').val(),gstr:$('[name="gstr"]').val(),

       pdf:($('[name="pdf"]').prop('checked')?'1':'0'),doc:($('[name="doc"]').prop('checked')?'1':'0'),html:($('[name="html"]').prop('checked')?'1':'0')},function(data){

         if(data!="Fail"){

           $('#search_results').html(data);

           for(var i in mask){

             if(mask.hasOwnProperty(i)){

               if($('[name="'+i+'"]').prop('checked')=='0'){

                 $('.color_'+mask[i]).hide();

               }

             }

           }

         }else{

           return;

         }

       });

     }else{

       return;

     }

 });

}

$(document).ready(function(){

 $('.word').live('click',function(){

   if($(this).css('color')=='rgb(255, 255, 255)'){

     return;

   }

   update_colors();

   $.post('/get_context',{word:$.trim($(this).html()),index:$(this).parent().parent().find('td').index($(this).parent()),

       left:$('[name="left"]').val(),right:$('[name="right"]').val(),gstr:$('[name="gstr"]').val(),

       pdf:($('[name="pdf"]').prop('checked')?'1':'0'),doc:($('[name="doc"]').prop('checked')?'1':'0'),html:($('[name="html"]').prop('checked')?'1':'0')},function(data){

     if(data.data!='Fail'){

       var words = data.data;

       $('#'+words.join(',#')).css('color','#000000');

       var txt_result = data.result;

       $('#result'+txt_result.join(',#result')).css('color','#000000');

     }

   },"json");

 });

 $('[name="test" ]').submit(function(){

   return true;

   if(!temp_results.length){

     page_num=3;

     current_page=1;

     search_api();

     return false;

   }else{

     $('[name="google_results"]').val(temp_results.join("\n"));

     return true;

   }

   if(!temp_results.length){

     var search_str = $('[name="gstr"]').val();

     $('body').append('<script src="https://www.googleapis.com/customsearch/v1?key=AIzaSyDfe6OsUoujJ3AB5_d6zRBRlh5_ADJmSD4&cx=007625171540799111237:ypbh5mdmvw0&q='+search_str+'&callback=hndlr&fields=searchInformation,items(title,fileFormat,snippet,link)">');

     return false;

     }else{

       $('[name="google_results"]').val(temp_results.join("\n"));

       return true;

     }

 });

 $('#typebox :checkbox').change(function(){

   load_results();

 });

});

</script>

<head>

<body>

<form name="test" method="post" action="/test">

 <div id="search_panel">

  <input name="left" type="text" size="1" maxlength="1" value="<%= @left %>" />

  <input name="gstr" type="text" size="40" value="<%= @search_str %>" />

  <input name="right" type="text" size="1" maxlength="1" value="<%= @right %>" />

  <input type="hidden" name="google_results" />

  <input type="submit" value="Поиск" id="search" />

 </div>

 <div id="typebox">

  <input type="checkbox" name="pdf" value="1" <%= @mask[0]==1?"checked=\"checked\"":''%> id="pdf" /> <label for="pdf"><span id="a1">PDF</span></label>

  <input type="checkbox" name="doc" value="1" <%= @mask[1]==1?"checked=\"checked\"":''%> id="doc" /> <label for="doc"><span id="a2">DOC</span></label>

  <input type="checkbox" name="html" value="1" <%= @mask[2]==1?"checked=\"checked\"":''%> id="html" /> <label for="html"><span id="a3">HTML</span></label>

  <!--<input type="button" name="apply_filter" value="Фильтровать" />-->

 </div>

<div id="cloud">

<table>

<% k=0 %>

<% @maxcol.times do |i| %>

  <tr>

  <% @maxsol.times do |j| %>

    <% if @astr[i][j] != " " %>

       <td><div id=<%= @dstt[k] %>  class="word"> <%= @astr[i][j]%> </div></td>

       <% k=k+1 %>

    <%else%>

       <td> <%= @astr[i][j]%> </td>

    <%end%>

  <%end%>

  </tr>

<%end%>

</table>

</div>

</form>

<div id="search_results" class="results_table">

  <% @search_results.size.times do |i| %>

     <%if @mask[@search_results[i]["type"]]==1%>

       <div id="result<%= i %>" class="result_div color_<%= @search_results[i]["type"] %>"><%= @search_results[i]["txt"] %></div>

     <%end%>

  <%end%>

</div>

<script>

<% @dcol.size.times do |i| %>

   colors["<%= @dstt[i]%>"] = "<%= @dcol[i] %>";

<%end%>

 update_colors();

</script>

</body>

</html>


Приложение 2

Файл words.erb

<table>

<% k=0 %>

<% @maxcol.times do |i| %>

  <tr>

  <% @maxsol.times do |j| %>

    <% if @astr[i][j] != " " %>

       <td><div id=<%= @dstt[k] %> class="word"> <%= @astr[i][j]%> </div></td>

       <% k=k+1 %>

    <%else%>

       <td> <%= @astr[i][j]%> </td>

    <%end%>

  <%end%>

  </tr>

<%end%>

</table>

 

<script>

<% @dcol.size.times do |i| %>

   colors["<%= @dstt[i]%>"] = "<%= @dcol[i] %>";

 <%end%>

 update_colors();

</script>


Приложение 2

Файл results.erb

<% @search_results.size.times do |i| %>

   <%if @mask[@search_results[i]["type"]]==1%>

     <div id="result<%= i %>" class="result_div color_<%= @search_results[i]["type"] %>"><%= @search_results[i]["txt"] %></div>

   <%end%>

<%end%>


Гранулы знаний

Множество объектов

Верхняя аппроксимация

Нижняя аппроксимация

Множество

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

X

R(x)

R(x)

 x

X

X

 x

R(x)

x

EMBED Equation.3     

EMBED Equation.3  

EMBED Equation.3  


 

А также другие работы, которые могут Вас заинтересовать

78611. Рынок труда. Региональные особенности рынка труда в современной России 38.5 KB
  Рынок труда. Региональные особенности рынка труда в современной России. Специфика рынка труда во многом определяется особенностями того товара который на нем представлен. Поэтому на рынке труда продается и покупается не сам труд а услуги труда количество и качество которых зависят от многих факторов уровня профессиональной подготовки работника его квалификации опыта добросовестности и других.
78612. Инфляция: особенности российской инфляции и антиинфляционная деятельность государства 115 KB
  Инфляция: особенности российской инфляции и антиинфляционная деятельность государства. Сущностью инфляции является дисбаланс между совокупным предложением и совокупным спросом в сторону превышения последнего сложившийся одновременно на всех рынках на товарном денежном и рынке ресурсов. Это открытая форма инфляции. Некоторые экономисты полагают что дефицит это антипод открытой инфляции: если отпустить цены то дефицит быстро исчезнет но за это придется заплатить повышением общего уровня цен.
78613. Социальная политика государства 35 KB
  Исходя из приоритета анализа экономики необходимо прежде всего остановиться на регулировании доходов непосредственных Участников хозяйственной деятельности. Дело в том что внутренние механизмы рыночной саморегуляции и распределения доходов не могут быть признаны социально удовлетворительными. Требуется государственное вмешательство с целью корректировки системы распределения и перераспределения доходов в обществе. При этом необходимо сознавать что регулирование доходов отношения найма занятости относятся не только к сфере...
78614. Многообразие форм собственности в рыночной экономике 49.5 KB
  Многообразие форм собственности в рыночной экономике. Так человек обладая собственностью на свою рабочую силу и вступая в отношения найма присваивает заработную плату и тем самым реализует экономическое отношение собственности. Право собственности закрепляет фиксирует и регулирует отношения людей к вещам и в этом смысле оно всегда производно от экономических отношений собственности. Но в то же время оно выступает и предпосылкой экономического присвоения ибо закрепленное право собственности на любые блага открывает путь к экономической...
78615. Конкуренция как условие функционирования рыночной экономики. Виды конкуренции 46 KB
  Конкуренция как условие функционирования рыночной экономики. Конкуренция это соперничество товаропроизводителей за выгодные условия хозяйствования и получение максимальной прибыли. Конкуренция основана на частной собственности и хозяйственной самостоятельности. По форме конкуренция представляет систему норм правил и методов хозяйствования рыночных субъектов.
78616. Основные методы государственного регулирования рыночной экономики 37.5 KB
  Впервые комплексный анализ экономической политики государства был проведен в 1952 г. Согласно Тинбергену вопервых правительственные органы должны выбрать конечные цели экономической политики и сформулировать их что обычно делается в терминах максимизации функции общественного благосостояния. Важнейшая проблема на которой остановился Тинберген соответствие между количеством целей и количеством инструментов при проведении экономической политики. Тинберген сделал вывод что политики могут достичь обеих целей тогда когда количество...
78617. Социальная ориентация рыночной экономики. Формы и методы ее осуществления 39.5 KB
  Нельзя забывать что подавляющая часть общества живет за счет труда. Поэтому в отношении человека как носителя рабочей силы задача заключается в превращении труда в творческую деятельность и более полное использование личностного потенциала. Необходимо постепенное высвобождение человека труда от выполнения исключительно исполнительной функции. В отношении подобного рода производств важное значение имеют новаторские формы организации труда позволяющие преодолеть рутинность монотонность труда и отсутствие его связи с конечными результатами.
78619. Реструктуризация предприятии (производства, управления) 33 KB
  Под ним подразумевается коренная перестройка перепроектирование деловых процессов для достижения радикального скачкообразного улучшения деятельности фирмы. Это позволяет преодолеть негативное воздействие сложившихся хозяйственных догм; пренебрежение действующими системами структурами и процедурами компании и радикальное изменение способов хозяйственной деятельности; приведение к значительным изменениям показателей хозяйственной деятельности на порядок отличающихся от предыдущих. К началу процесса реструктуризации необходимо иметь ее...