...

суббота, 13 декабря 2014 г.

Google Chrome пометит HTTP-сайты как небезопасные


сегодня в 17:32


Разработчики веб-браузера Google Chrome обещают пометить веб-сайты, которые используют простое HTTP-подключение с клиентом как небезопасные и предлагают всем другим веб-приложениям (User Agent) сделать то же самое. Таким образом, пользователям хотят дать понять, что это простое подключение не обеспечивает необходимого уровня безопасности при передачи данных. Предполагается, что теперь сам браузер будет различать типы безопасности подключения к серверу для уведомления об этом клиента: безопасное (Secure), сомнительное (Dubious) и небезопасное (Non-secure).



We, the Chrome Security Team, propose that user agents (UAs) gradually change their UX to display non-secure origins as affirmatively non-secure. We intend to devise and begin deploying a transition plan for Chrome in 2015.





Веб-подключения разделяются на три типа:


  • Безопасное (Secure): подключение по HTTPS или localhost.

  • Сомнительное (Dubious): подключение по HTTPS, но c т. н. mixed resources (содержит в теле веб-страницы ссылки на небезопасные ресурсы), а также HTTPS с ошибками в TLS.

  • Небезопасное (Non-secure): подключение через нарушенный (невалидный) HTTPS или простой HTTP.




Для других вендоров веб-приложений (т. н. User Agent vendors) предлагается схема, по которой сайт можно отнести к тому или иному типу и поэтапно реализовать это в продукте см. здесь.




1174


4





Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.


This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Want something else to read? How about 'Grievous Censorship' By The Guardian: Israel, Gaza And The Termination Of Nafeez Ahmed's Blog


Дайджест интересных материалов о создании контента, маркетинге и Growth Hacking #5


сегодня в 12:00




Похожие публикации



Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.


This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Want something else to read? How about 'Grievous Censorship' By The Guardian: Israel, Gaza And The Termination Of Nafeez Ahmed's Blog


Об удобной навигации и отладке C++ кода в Vim

CPU vs GPU. Distance field

Привет всем. Я уже однажды писал про Distance Field, и приводил реализацию «эвристическим» кодом дающую неплохую скорость: http://ift.tt/1b79Uab

Зачем он нужен?




DField можно применять:


  • Для значительного повышения качества шрифтов

  • Для эффектов например горения контура. Один из эффектов я приводил в своей предыдущей статье

  • Для эффекта «metaballs» но в 2д и для любых сложных шейпов. (возможно я когда-нибудь приведу пример реализации этого эффекта)

  • А в данный момент DField мне нужен для качественного сглаживания углов и удаления мелких деталей.




И если в первых двух случаях мы можем заранее вычислить DField, то для других эффектов нам нужно просчитывать его в реальном времени.

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

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


Chamfer классика на CPU




Сегодня я хотел бы обратить внимание на классический способ рассчета DField. Поиграться можно тут (исходный код в git-е). У алгоритма есть неустоявшееся название: chamfer distance algoritm. Этот способ уже описывал RPG в своем топике

Однако там нет объяснений почему и как работает этот код. Почему возникают погрешности, какие они, и как их уменьшить.

Под капотом у Chamfer.




Итак, у нас есть монохромное изображение, от которого мы хотим построить Distance Field. Это белая точка на черном фоне:



Начнем строить DField. Для этого сначала заполним наше будущее изображение +бесконечностью для пустот, и нулями для объекта. Как-то так:



Затем начинаем бежать по изображению (слева направо и сверху вниз), и для каждого пикселя проверять его соседей. Возьмем в соседнем пикселе значение, прибавим к этому значение расстояние до соседа. Для пикселей справа и слева это расстояние = 1. Для пикселей по диагонали sqrt(1*1+1*1)=sqrt(2). Запишем в наш пиксель минимальное значение между текущим, и только что вычисленным у соседа. После того как сделаем это для всех соседей — переходим к следующему пикселю. У нас вышла такая картина:



Поскольку мы бежали слева направо и сверху вниз — расстояния накапливались от предыдущих расчетов, и пиксели отмеченные красными стрелками автоматически посчитались «верно». Теперь если мы пробежим в обратном направлении (справа налево, снизу вверх) — то заполнится недостающая часть карты.

Итак, основная идея — использовать уже просчитанное раннее расстояние. Для этого нам не нужно проверять всех соседей. Достаточно проверить пиксели, по которым мы уже пробежали:



Красным — отмечены пиксели соседей для первого прохода (направо, вниз). Синим — для второго (налево, вверх).

Первый проход даст нам красивый шлейф в одну сторону:



Второй даст в другую, а поскольку мы будем записывать только минимальное значение в обоих случаях — то в сумме оно будет выглядеть вот так:



Сложность алгоритма O(2*W*H*5)

Теперь поговорим о точности. На текущем изображении не видно проблем, но если вы попробуете построить контур (как в этой статье) — то результат будет не самым правдоподобным. Посмотрим на distance%16 контур:



Красными стрелками я отметил ярко выраженную октогональность изображения. Почему же так происходит? А все просто, ведь наш результат накапливается, и накапливается он неправильно:



Наше расстояние будет вычислено по красной линии: 1+sqrt(2), в то время как правильно его будет вычислить по синей линии: sqrt(2*2+1*1)=sqrt(3). Если мы будем в расчетах брать не только соседей, но и соседей соседей:



результат конечно будет лучше. Но вычислительные сложности возрастают с O(2*W*H*5) до O(2*W*H*13). Но есть и хорошие новости, мы можем выбросить часть соседей, никак не повлияв на результат:



Дело в том, что выброшенные соседи имеют кратное расстояние и лежат на одном луче. А значит мы их можем выбросить, ибо значение от ближайших будет корректно накапливаться. Матрицу соседей я буду называть ядром. В первом случае у нас было ядро 3х3. Сейчас ядро 5х5. Давайте посмотрим на результат:



Наша октогональность стала заметно «круглее». (К слову, в фотошопе для слоев есть эффект Outer glow с параметром precise. У меня результат в точности совпал после прохода ядром 5х5. Похоже они используют именно этот алгоритм для данного эффекта.)

Сложность для оптимизированного 5x5 = O(2*W*H*9)

Можно дальше продолжать повышать и повышать размер ядра, качество будет расти, но один неприятный эффект мы так и не сможем побороть. Вот изображение для ядра 13*13:



На изображении присутствуют ступенчатые градиенты. Они все так же связаны с пресловутой погрешностью, и чтобы окончательно избавиться от них нам пришлось бы создать ядро размером в две ширины изображения, т.к. диагональ со сторонами (Много;1) может покрыть только ядро размером 2*Много+1. (с этими погрешностями борятся различные модификации CDA, один из вариантов — хранить в пикселе вектор до ближайшего, но я в статье их затрагивать не буду).

Итак суммарно, плюсы алгоритма:




  • Неограниченный Distance Field (что это такое мы поймем когда разберемся с алгоритмом на GPU).

  • Линейная сложность, и высокая скорость для маленьких ядер.

  • Простота реализации.




Минусы:




  • Плохая точность (особенно для маленьких ядер)

  • Зависимость от предыдущих вычислений (никаких вам SIMD)




GPU в бой.




К сожалению, я не нашел никаких популярных алгоритмов, ложащихся на многопоточную архитектуру GPU. То ли руки у меня не те, то ли гугл зажал. Поэтому я поделюсь с вами своим «велосипедом». Благо он простой. Поиграться можно здесь, исходники лежат в git. Для игры потребуется видеокарточка, поддерживающая OpenGL3 и Rect текстуры.

Итак, допустим нам важно рассчитать Distance Field в радиусе 40 пикселей. Первым проходом мы считаем только вертикальную дистанцию от 40 соседей сверху и от 40 соседей снизу для каждого пикселя. Записываем минимальное значение (если заполненых соседей нет — записываем максимальное значение, 40). Получаем вот такую картину:



После этого делаем второй проход по горизонтали. Точно так же 40 соседей слева, 40 соседей справа. Зная расстояния до соседа, + расстояние по вертикали у соседа — мы легко считаем гипотенузу:



в результат записываем минимальную гипотенузу. После второго прохода нас ждет красивая и правильно построенная картинка:



Сложность алгоритма O(2*W*H*(2*D+1)), где W и H — размеры изображения, а D — расстояние distance field. Distance field у нас получается нормализованным (в изображении не будет значений больше D).

Точность вычислений отличная, т.к. погрешности не накапливаются:



В приложении к статье есть три режима: GL_R8, GL_R16, GL_R32F

Если включить GL_R8 и покрутить дистацию, то можно заметить скачущие погрешности. Дело тут вот в чем. Для промежуточного вертикального DField-а текстура для хранения имеет размер 8бит на пиксель. Поскольку я нормализую дистанцию на диапазон [0;1], то возникают погрешности. Нужно либо хранить не нормализованную дистанцию (но тогда для восьмибитной текстуры она будет ограничена 255 пикселями), либо повышать разрядность текстуры. Для текстуры R16-эти погрешности меньше, а для R32F эти погрешности вообще «отстуствуют», т.к. это float текстура. Учитывайте это, если захотите реализовать подобный distance field.

Итак, плюсы:




  • Абсолютная точность

  • Отлично ложится на SIMD.

  • Простота реализации

  • Данные сразу лежат на GPU!




Минусы




  • Ограниченная дистанция. Мы должны знать, какая дистанция нам нужна заранее.

  • Сложность алгоритма зависит от дистанции

  • Данные на GPU (это может потребовать дополнительно время на получение, если мы планируем дальше работать с этими данными на CPU)


Выводы?




У меня в домашнем компьютере стоит GF450. Для изображения Hello world и DField = 500 пикселей мой GPU умудряется делать 20 кадров в секунду, что примерно равно 50мс на кадр. Все это с отличным качеством и простым прозрачным кодом. На CPU ядром 3х3 Distance field рассчитывается около 100мс. 5х5 около 200мс. Даже если ускорить, оптимизируя под CPU в 4 раза (что очень круто), то я получу качество заметно хуже за то же время. Используйте GPU, если алгоритмы это позволяют ;)

Ссылки по теме:





  1. http://ift.tt/1qFp7Zs — Собственно примеры к статье. Бинарники и исходники.

  2. http://ift.tt/1uwAu1f — отличный разбор как Chamfer алгоритма, так и его модификаций. Сравнение погрешности и времени выполнения.

  3. http://ift.tt/1pMhom0 — Применение DField в рендере шрифтов. Пожалуй самая известная статья.

  4. http://ift.tt/PfOwXH — вышеупомянутая статья от RPG. Хорошо показывает применение DField.


This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Want something else to read? How about 'Grievous Censorship' By The Guardian: Israel, Gaza And The Termination Of Nafeez Ahmed's Blog


Выразительный JavaScript: Формы и поля форм

Содержание


I shall this very day, at Doctor’s feast,

My bounden service duly pay thee.

But one thing!—For insurance’ sake, I pray thee,

Grant me a line or two, at least.

Mephistopheles, in Goethe's Faust


Формы были кратко представлены в предыдущей главе в качестве способа передачи информации, введённой пользователем, через HTTP. Они были разработаны в вебе до появления JavaScript, с тем расчётом, что взаимодействие с сервером происходит при переходе на другую страницу.


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



Поля




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

Много типов полей ввода используют тег . Его атрибут type используется для выбора стиля поля. Вот несколько распространённых типов:


text текстовое поле на одну строку

password то же, что текст, но прячет ввод

checkbox переключатель вкл/выкл

radio часть поля с возможностью выбора из нескольких вариантов

file позволяет пользователю выбрать файл на его компьютере


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


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


(text)



(password)



(checkbox)





(radio)



(file)




Интерфейс JavaScript для таких элементов разнится в зависимости от типа. Мы рассмотрим каждый из них чуть позже.


У текстовых полей на несколько строк есть свой тег
, и он использует текст внутри этих тегов вместо использования атрибута value.








А тег


Когда значение поля изменяется, запускается событие “change”.


Фокус




В отличие от большинства элементов документа HTML, поля форм могут получать фокус ввода клавиатуры. При щелчке или выборе их другим способом они становятся активными, т.е. главными приёмниками клавиатурного ввода.

Если в документе есть текстовое поле, то набираемый текст появится в нём, только если поле имеет фокус ввода. Другие поля по-разному реагируют на клавиатуру. К примеру,


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


Атрибут size тега = 0


Файловое поле




Файловое поле изначально было предназначено для закачивания файлов с компьютера через форму. В современных браузерах они также позволяют читать файлы из JavaScript. Поле работает как охранник для файлов. Скрипт не может просто взять и открыть файл с компьютера пользователя, но если тот выбрал файл в этом поле, браузер разрешает скрипту начать чтение файла.

Файловое поле обычно выглядит как кнопка с надписью вроде «Выберите файл», с информацией про выбранный файл рядом с ней.







Свойство files элемента – массивоподобный объект (не настоящий массив), содержащий список выбранных файлов. Изначально он пуст. У элемента нет простого свойства file, потому что пользователь может выбрать несколько файлов за раз при включённом атрибуте multiple.


У объектов в свойстве files есть свойства имя (имя файла), размер (размер файла в байтах), и тип (тип файла в смысле media type — text/plain или image/jpeg).


Чего у него нет, так это свойства, содержащего содержимое файла. Чтобы получить содержимое, приходиться постараться. Так как чтение файла с диска занимает длительное время, интерфейс должен быть асинхронным, чтобы документ не замирал. Конструктор FileReader можно представлять себе, как конструктор XMLHttpRequest, только для файлов.







Чтение файла происходит при помощи создания объекта FileReader, регистрации события “load” для него, и вызова его метода readAsText с передачей тому файла. По окончанию загрузки в свойстве result сохраняется содержимое файла.


Пример использует Array.prototype.forEach для прохода по массиву, так как в обычном цикле было бы неудобно получать нужные объекты file и reader от обработчика событий. Переменные были бы общими для всех итераций цикла.


У FileReaders также есть событие “error”, когда чтение файла не получается. Объект error будет сохранён в свойстве error. Если вы не хотите забивать голову ещё одной неудобной асинхронной схемой, вы можете обернуть её в обещание (см. главу 17):



function readFile(file) {
return new Promise(function(succeed, fail) {
var reader = new FileReader();
reader.addEventListener("load", function() {
succeed(reader.result);
});
reader.addEventListener("error", function() {
fail(reader.error);
});
reader.readAsText(file);
});
}


Возможно читать только часть файла, вызывая slice и передавая результат (т.н. объект blob) объекту reader.


Хранение данных на стороне клиента




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

Когда такому приложению нужно сохранять информацию между сессиями, переменные JavaScript использовать не получится – их значения выбрасываются каждый раз при закрытии страницы. Можно было бы настроить сервер, подсоединить его к интернету и тогда приложение хранило бы ваши данные там. Это мы разберём в главе 20. Но это добавляет вам работы и сложности. Иногда достаточно хранить данные в своём браузере. Но как?


Можно хранить строковые данные так, что они переживут перезагрузку страниц — для этого надо положить их в объект localStorage. Он разрешает хранить строковые данные под именами (которые тоже являются строками), как в этом примере:



localStorage.setItem("username", "marijn");
console.log(localStorage.getItem("username"));
// → marijn
localStorage.removeItem("username");


Переменная в localStorage хранится, пока её не перезапишут, удаляется при помощи removeItem или очисткой локального хранилища пользователем.


У сайтов с разных доменов – разные отделения в этом хранилище. То есть, данные, сохранённые с вебсайта в localStorage, могут быть прочтены или перезаписаны только скриптами с этого же сайта.


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


Следующий код реализует простую программу для ведения заметок. Она хранит заметки в виде объекта, ассоциируя заголовки с содержимым. Он кодируется в JSON и хранится в localStorage. Пользователь может выбрать записку через поле


Скрипт инициализирует переменную notes значением из localStorage, а если его там нет – простым объектом с одной записью «что купить». Попытка прочесть отсутствующее поле из localStorage вернёт null. Передав null в JSON.parse, мы получим null обратно. Поэтому для значения по умолчанию можно использовать оператор ||.


Когда данные в note меняются (добавляется новая запись или меняется текущая), для обновления хранимого поля вызывается функция saveToStorage. Если б мы рассчитывали, что у нас будут храниться тысячи записей, это было бы слишком накладно, и нам пришлось бы придумать более сложную процедуру для хранения – например, своё поле для каждой записи.


Когда пользователь добавляет запись, код должен обновить текстовое поле, хотя у поля и есть обработчик “change”. Это нужно потому, что событие “change” происходит, только когда пользователь меняет значение поля, а не когда это делает скрипт.


Есть ещё один похожий на localStorage объект под названием sessionStorage. Разница между ними в том, что содержимое sessionStorage забывается по окончанию сессии, что для большинства браузеров означает момент закрытия.


Итог




HTML предоставляет множество различных типов полей формы – текстовые, галочки, множественного выбора, выбора файла.

Из JavaScript можно получать значение и манипулировать этими полями. По изменению они запускают событие “change”, по вводу с клавиатуры – “input”, и ещё много разных клавиатурных событий. Они помогают нам отловить момент, когда пользователь взаимодействует с полем ввода. Свойства вроде value (для текстовых полей и select) или checked (для галочек и радиокнопок) используются для чтения и записи содержимого полей.


При передаче формы происходит событие “submit”. Обработчик JavaScript затем может вызвать preventDefault этого события, чтобы остановить передачу данных. Элементы формы не обязаны быть заключены в теги


.

Когда пользователь выбрал файл с жёсткого диска через поле выбора файла, интерфейс FileReader позволит нам добраться до содержимого файла из программы JavaScript.


Объекты localStorage и sessionStorage можно использовать для хранения информации таким способом, который переживёт перезагрузку страницы. Первый сохраняет данные навсегда (ну или пока пользователь специально не сотрёт их), а второй – до закрытия браузера.


Упражнения




Верстак JavaScript



Сделайте интерфейс, позволяющий писать и исполнять кусочки кода JavaScript.

Сделайте кнопку рядом с









Автодополнение



Дополните текстовое поле так, что при вводе текста под ним появлялся бы список вариантов. У вас есть массив возможных вариантов, и показывать нужно те из них, которые начинаются с вводимого текста. Когда пользователь щёлкает по предложенному варианту, он меняет содержимое поля на него.











Игра «Жизнь» Конвея



Это простая симуляция жизни на прямоугольной решётке, каждый элемент которой живой или нет. Каждое поколение (шаг игры) применяются следующие правила:

— каждая живая клетка, количество соседей которой меньше двух или больше трёх, погибает

— каждая живая клетка, у которой от двух до трёх соседей, живёт до следующего хода

— каждая мёртвая клетка, у которой есть ровно три соседа, оживает


Соседи клетки – это все соседние с ней клетки по горизонтали, вертикали и диагонали, всего 8 штук.


Обратите внимание, что правила применяются ко всей решётке одновременно, а не к каждой из клеток по очереди. То есть, подсчёт количества соседей происходит в один момент перед следующим шагом, и изменения, происходящие на соседних клетках, не влияют на новое состояние клетки.


Реализуйте игру, используя любые подходящие структуры. Используйте Math.random для создания случайных начальных популяций. Выводите поле как решётку из галочек с кнопкой «перейти на следующий шаг». Когда пользователь включает или выключает галочки, эти изменения нужно учитывать при подсчёте следующего поколения.







This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Want something else to read? How about 'Grievous Censorship' By The Guardian: Israel, Gaza And The Termination Of Nafeez Ahmed's Blog





Поиск наилучшей последовательности просмотра списка 250 лучших фильмов с помощью языка Wolfram Language (Mathematica)




Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь (архив, ~76 МБ).

Введение




Некоторое время назад, если быть точным — 515 дней, вышел пост Маттиаса Одисио (Matthias Odisio) под названием “Random and Optimal Mathematica Walks on IMDb’s Top Films” (Случайные и оптимальные блуждания Mathematica по списку 250 лучших фильмов по версии IMDB). В нем рассказывается о том, каким образом можно получить оптимальную последовательность просмотра фильмов из соответствующего списка, основанную на близости жанров фильмов и близости постеров фильмов с точки зрения цвета.



In[1]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_2.png


Out[1]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_3.png


Идея этого поста показалась мне довольно интересной, но мне захотелось её существенно расширить и углубить, следуя нескольким идеям:



  • Построить более совершенную функцию, оценивающую близость фильмов, так как мне кажется, что построение функции расстояния между фильмами на основе близости постеров фильмов по использующимся в них цветам и жанрам фильмов не достаточно объективно. Мне представляется разумным построить функцию расстояния между фильмами на основе нескольких факторов: жанров фильма, описания фильма, актерского состава, режиссера(-ов), года производства, сценариста(-ов) и пр.





  • В статье Маттиаса использовались лишь данные Wolfram|Alpha, что, безусловно, упрощает задачу и компактизирует код. Мне же хочется рассказать о том, как можно использовать в расчетах данные, взятые откуда угодно, например, полученные с помощью веб-парсинга со страниц Википедии, подгруженные из текстовых баз данных и т. п.




Я не буду рассказывать в этой статье о том, как построить оптимальную последовательность просмотра списка 250 лучших фильмов КиноПоиска по той причине, что просто не хочется иметь проблем с условиями использования данного ресурса, которые довольно четко говорят (см. п. 6), что просто взять их список фильмов и произвести его анализ без их согласия не получится. При этом применить алгоритмы, которые я приведу ниже для этого списка довольно просто. Также мне хотелось бы отметить, что во время моей работы с одной из отечественных кинокомпаний для их нужд на языке Wolfram Language был написан парсер, который подгружал информацию о фильмах с сайта КиноПоиск (юридическая сторона вопроса была улажена) для последующего автоматического формирования рекламного буклета о нескольких тысячах фильмов, права на которые принадлежали этой компании. Ниже вы можете видеть пример одной такой полностью автоматически созданной страницы буклета (приведена неокончательная версия, ввиду NDA).
Пример страницы
Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_4.png




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

Импорт данных с сайта Википедии




Для начала, подгрузим символьное представление HTML кода страницы Википедии “250 лучших фильмов по версии IMDb” (в документе отобразим при этом лишь часть результата с помощью функции Short):

In[2]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_5.gif


Out[3]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_6.png


Теперь выделим ссылки на фильмы, приведенные на странице в таблице:


In[4]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_7.png


Out[4]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_8.png


Создадим функцию, которая подгрузит и сохранит символьное представление HTML кода страниц каждого из фильмов:


In[5]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_9.gif


Вспомогательные функции




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

  • Функция для удаления HTML-оберток, оставляющая только данные:




In[8]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_10.png



  • Функция, которая определяет, может ли быть некоторая строка словом на русском языке (т. е. состоит из букв русского алфавита или дефиса):




In[9]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_11.png


In[10]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_12.gif



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




In[12]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_13.png


In[13]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_14.gif



  • Функция, преобразующая (в строке) заглавные буквы русского алфавита в прописные:




In[15]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_15.png


In[16]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_16.png



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




In[17]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_17.png


Out[17]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_18.png



  • Обработаем данные словаря, составив на его основе список слов русского языка (russianWords) и список правил замены форм слов русского языка в их стандартную форму (russianWordsStandardForm):




In[18]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_19.png


В словаре содержится 2 645 347 слов:


In[19]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_20.gif


Out[19]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_21.png


Out[20]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_22.png



  • Создадим функцию, которая проверяет, содержится ли слово в словаре, а также функцию, преобразующую русское слово в его стандартную форму:




In[21]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_23.png


In[22]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_24.png


Примеры работы функций:


In[23]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_25.png


Out[23]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_26.png


In[24]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_27.png


Out[24]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_28.png



  • Создадим функцию, которая будет устанавливать, является ли слово прилагательным:




In[25]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_29.png


In[26]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_30.png


Обработка данных




Теперь можно обработать данные каждого из фильмов. При этом на выходе в переменной filmsData будет храниться база данных информации о фильмах, построенная на основе функции Association, что позволит нам очень легко обращаться к данным.

In[27]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_31.png


In[29]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_32.gif


Пример обращения к сформированной базе по номеру фильма:


In[31]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_33.png


Out[31]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_34.png


Пример обращения с запросом о режиссёре и годе выхода каждого из фильмов:


In[32]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_35.png


Out[32]//Short=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_36.png


Немного статистики на основе данных




Для начала, просто сформируем коллаж из постеров всех фильмов:

In[33]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_37.png


Out[33]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_38.png


Построим распределение количества фильмов в зависимости от года:


In[34]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_39.png


Out[34]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_40.png


Построим распределение фильмов по их продолжительности:


In[35]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_41.png


Out[35]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_42.png


Построим распределение фильмов по их продолжительности и году выпуска:


In[36]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_43.png


Out[36]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_44.png


Первые 10 актеров по количеству фильмов, в которых они сыграли:


In[37]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_45.png


Out[37]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_46.png


Первые 10 режиссёров по количеству фильмов, которые они сняли:


In[38]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_47.png


Out[38]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_48.png


Первые 10 сценаристов по количеству фильмов, сценарий к которым они написали:


In[39]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_49.png


Out[39]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_50.png


Первые 10 композиторов по количеству фильмов, музыку к которым они написали:


In[40]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_51.png


Out[40]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_52.png


Первые 10 стран по количеству фильмов, которые были в них сняты:


In[41]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_53.png


Out[41]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_54.png


Первые 10 жанров по количеству фильмов, которые к ним относятся:


In[42]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_55.png


Out[42]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_56.png


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


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_57.png


Функция, определяющая расстояние между фильмами




Для определения меры различия двух списков объектов мы будем использовать обобщение коэффициента (меры) Чекановского-Съёренсена:

In[43]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_58.gif


Пример:


In[45]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_59.png


Out[45]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_60.png


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


In[46]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_61.png


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


In[47]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_62.png


Out[47]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_63.png


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


In[48]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_64.gif


Выберем для дальнейшей работы те фильмы, для которых известна хоть какая-то информация (ввиду того, что для нескольких фильмов их страницы Википедии пусты):


In[62]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_65.png


Вычислим все меры близости (расстояния) между фильмами:


In[63]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_66.png


Анализ связей между фильмами




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

In[64]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_67.png


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


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_68.png


In[65]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_69.png


Out[65]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_70.png


In[66]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_71.png


Out[66]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_72.png


In[67]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_73.png


Out[67]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_74.png


In[68]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_75.png


Out[68]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_76.png


In[69]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_77.png


Out[69]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_78.png


In[70]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_79.png


Out[70]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_80.png


In[71]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_81.png


Out[71]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_82.png


In[72]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_83.png


Out[72]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_84.png


Построение оптимальной последовательности просмотра фильмов




Мы проделали довольно большую работу и теперь, наконец, можем построить оптимальную последовательность просмотра фильмов:

In[73]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_85.png


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


In[74]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_86.png


Таблица оптимальной последовательности просмотра фильмов из списка 250 лучших фильмов по версии IMDb
Out[74]=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_87.png






Также, можно отобразить её в виде плаката из постеров (последовательность просмотра фильмов при этом будет слева направо, сверху вниз):

In[75]:=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_88.png


Out[75]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_89.png


Мы может также рассмотреть оптимальные последовательности по отдельным критериям:


Последовательность просмотра на основе описания фильма
In[76]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_90.png


Out[76]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_91.png






Последовательность просмотра на основе жанра фильма
In[77]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_92.png


Out[77]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_93.png






Последовательность просмотра на основе актерского состава фильма
In[78]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_94.png


Out[78]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_95.png






Последовательность просмотра на основе режиссёра фильма
In[79]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_96.png


Out[79]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_97.png






Последовательность просмотра на основе сценаристов фильма
In[80]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_98.png


Out[80]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_99.png






Последовательность просмотра на основе композиторов фильма
In[82]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_102.png


Out[82]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_103.png






Последовательность просмотра на основе длительности фильма
In[83]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_104.png


Out[83]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_105.png






Последовательность просмотра на основе постера фильма
In[84]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_106.png


Out[84]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_107.png






Последовательность просмотра на основе страны производства фильма
In[85]:=

Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_108.png


Out[85]=


Poisk-posledovatelnosti-prosmotra-spiska-250-luchshih-filmov-Wolfram-Language-Mathematica_109.png






Заключение




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

Ресурсы для изучения Wolfram Language (Mathematica) на русском языке: http://ift.tt/12b2HEP


This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Want something else to read? How about 'Grievous Censorship' By The Guardian: Israel, Gaza And The Termination Of Nafeez Ahmed's Blog