Блог Игоря Шевченко

Cуммаризация с помощью TextRank 20 июня 2013

В марте интернеты бурно обсуждали покупку компанией «Yahoo!» сервиса «Summly». Купленное у семнадцатилетнего стартапера за тридцать миллионов долларов приложение для айфона показывает новости, автоматически создавая для них краткое изложение (саммари, если не по-русски).

Оценивая величину поднявшегося шума по поводу этой покупки и основателя сервиса Ника Д'Алоизио, который стал после неё одним из самых молодых «самодельных» миллионеров, говорили, что только пиар окупил бы вложения «Яху!». Но и сам суммаризатор как сервис кажется перспективным. Вполне соответствует тенденциям: распространяются мобильные устройства, с которых можно выходить в интернет, но сложно читать длинные статьи. Да и вообще длинные тексты читают всё реже. Наконец, есть смысл заняться технологиями автоматической суммаризации, потому что их еще есть куда улучшать.

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

Например, можно преобразовывать текст в граф. Тогда для определения самых важных вершин можно использовать алгоритмы ссылочного ранжирования вроде PageRank, который когда-то лег в основу Гугла. По связям между вершинами графа PageRank назначает каждой из них рейтинг, учитывая две вещи:

1) количество ребер, которые идут из других вершин,

2) рейтинг этих ребер.

Получается, что одни вершины «рекомендуют» другие, а сила рекомендации вычисляется рекурсивно на основе рейтингов вершин. При анализе текста вершинами могут быть или отдельные термины, или целые предложения. Первый вариант может применяться, если из текста надо извлечь ключевые слова. Для создания саммари лучше брать предложения полностью.

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

Этот алгоритм, который называется TextRank, предложила в этой статье Рада Михальча (надеюсь, правильно транскрибировал). Статья довольно понятная, сам алгоритм несложный. Его можно реализовать на питоне примерно в тридцать строк, используя библиотеки nltk для работы с естественным языком и networkx для графов.

Примерно так.

from nltk.tokenize import sent_tokenize

sentences = sent_tokenize(text)

Разбиваем текст на предложения с помощью токенизатора из nltk.

from nltk.tokenize import RegexpTokenizer
from nltk.stem.snowball import RussianStemmer

tokenizer = RegexpTokenizer(r'\w+')
lmtzr = RussianStemmer()
words = [set(lmtzr.stem(word) for word in tokenizer.tokenize(sentence.lower()))
         for sentence in sentences]

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

from itertools import combinations

pairs = combinations(range(len(sentences)), 2)
scores = [(i, j, similarity(words[i], words[j])) for i, j in pairs]

Для каждой пары предложений вычислим их похожесть.

def similarity(s1, s2):
    if not len(s1) or not len(s2):
        return 0.0
    return len(s1.intersection(s2))/(1.0 * (len(s1) + len(s2)))

В качестве меры похожести возьмем отношение количества одинаковых слов в предложениях к суммарной длине предложений. Кажется, это называется коэффициентом Сёренсена.

scores = filter(lambda x: x[2], scores)

Уберем пары, у которых нет ничего общего (похожесть равна нулю).

import networkx as nx

g = nx.Graph()
g.add_weighted_edges_from(scores)

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

pr = nx.pagerank(g)

Посчитаем пейджранки в этом графе.

result = sorted(((i, pr[i], s) for i, s in enumerate(sentences) if i in pr), 
                key=lambda x: pr[x[0]], reverse=True)

Результатом будет список предложений, отсортированный по их пейджранку.

Полностью код выглядит так:

from itertools import combinations
from nltk.tokenize import sent_tokenize, RegexpTokenizer
from nltk.stem.snowball import RussianStemmer
import networkx as nx

def similarity(s1, s2):
    if not len(s1) or not len(s2):
        return 0.0
    return len(s1.intersection(s2))/(1.0 * (len(s1) + len(s2)))

def textrank(text):
    sentences = sent_tokenize(text)
    tokenizer = RegexpTokenizer(r'\w+')
    lmtzr = RussianStemmer()
    words = [set(lmtzr.stem(word) for word in tokenizer.tokenize(sentence.lower()))
             for sentence in sentences]

    pairs = combinations(range(len(sentences)), 2)
    scores = [(i, j, similarity(words[i], words[j])) for i, j in pairs]
    scores = filter(lambda x: x[2], scores)

    g = nx.Graph()
    g.add_weighted_edges_from(scores)
    pr = nx.pagerank(g)

    return sorted(((i, pr[i], s) for i, s in enumerate(sentences) if i in pr),
                  key=lambda x: pr[x[0]], reverse=True)

def extract(text, n=5):
    tr = textrank(text)
    top_n = sorted(tr[:n])
    return ' '.join(x[2] for x in top_n)

Сразу же можно предложить несколько изменений:

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

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

Вот, например, сюжет фильма «Иван Васильевич меняет профессию» из Википедии, ужатый до пяти предложений:

В присутствии управдома Ивана Васильевича Бунши Шурик испытывает машину на небольшой мощности, и стена между квартирами Шурика и Шпака исчезает. Увидев пришельцев и приняв их за демонов, Феофан убегает за стражей, а Иван Грозный пугается чёрной кошки и убегает в квартиру Шурика. На обеде Иван Васильевич Бунша заигрывает с миловидной Марфой Васильевной (супругой Ивана Грозного) и приходит в состояние алкогольного опьянения. Но, наконец, срабатывает починенная Шуриком машина времени и Иван Васильевич Бунша с Жоржем Милославским вбегают в свой XX век. Воспользовавшись суматохой, из машины «Скорой помощи» выбегает Иван Грозный и бежит в квартиру к Шурику, который снова запускает свою машину.

Хорошо работает c новостями. Так выглядит саммари новости «В Москве и Белгороде разрешили правый поворот на „красный“»:

Российская Госавтоинспекция запустила эксперимент, в рамках которого поворот направо на запрещающий сигнал светофора будет разрешен на некоторых перекрестках Москвы и Белгорода. В Москве эксперимент был запущен в 13:00 на шести перекрестках. На светофорах на перекрестках, участвующих в эксперименте, установлен представленный ранее знак в виде зеленой стрелки, указывающей направо. Перед въездом на перекрестки также расположены щиты, сообщающие о проведении эксперимента. Инициатива о разрешении поворота направо на «красный» была впервые предложена в 2011 году.

6 комментариев

Конспект курса по сонграйтингу 7 мая 2013

В марте на Курсере начался курс по сонграйтингу, который вёл Пэт Паттисон, профессор музыкального колледжа Беркли. До этого я проходил только технические курсы, это был первый чуть более гуманитарный курс, на который я записался.

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

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

Донни и Донна

Курс начинается с очень эмоциональной истории о том, как невеста парня по имени Донни внезапно сообщает ему, что она должна уехать от него в Марракеш. Донни выскакивает из-за стола, за которым он сидел, и начинает петь. С помощью песни он должен выразить свою позицию, передать какое-то сообщение — «Ох, это грустно», «Я буду ждать», «Ну и ладно» или что-то еще. Так мы подходим к тому, что для любой песни нужно продумать подобный бэкграунд, ответив на три вопроса:

  1. Кто говорит?
  2. Кому он или она это говорит?
  3. По какой причине?

Три блока

Три блока — это крутая идея, которую можно применить не только для написания песен.

Три блока

Предположим, у нас есть какая-то мысль, которую мы хотим высказать в песне. При этом одна из задач писателя — не дать слушателю заскучать. Поэтому нельзя вываливать всю свою идею в первом же куплете, а потом повторять её остаток песни. Нужно раскрывать мысль постепенно, начав издалека в первом куплете, добавив деталей во втором и окончательно оформив мысль в третьем. Это и есть те три блока, нарисованные на картинке: первый маленький, второй чуть побольше, потому что он должен содержать в себе первый блок и дополнения к нему, и третий — самый большой.

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

Или вот еще.

Шесть друзей

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

  1. Кто?
  2. Что?
  3. Когда?
  4. Где?
  5. Почему?
  6. Как?

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

Просодия

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

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

  1. Количество строк.
  2. Длины строк.
  3. Схема рифмовки.
  4. Тип рифм.
  5. Ритм строк.

Количество строк

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

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

Длины строк

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

Схема рифмовки

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

Менее стабильный вариант — это строфа со схемой ABAB. Здесь завершенность ощущается уже меньше и только после четвертой строки.

И самый нестабильный вариант — ABBA. После него никакой завершенности уже не чувствуется. Хочется добавить еще две строки и получить ABBABB или хотя бы ABBACC, чтобы создать равновесие, которого нет.

Тип рифмы

Есть несколько типов рифмы, различающиеся по степени стабильности. Рассмотрим их в порядке от более стабильных к менее стабильным.

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

Следующий вид рифм, который лектор называет «семейными рифмами», основывается на группировании согласных звуков.

Согласные звуки можно разделить на группы по способу их образования. Взрывные согласные создаются за счёт того, что поток воздуха из легких во рту блокируется смычкой, а потом смычка резко размыкается. Этой смычкой могут быть губы ([p]), передняя часть языка ([t]), задняя часть языка ([k]). Звуки [p], [t] и [k] создаются без участия голосовых связок. Поэтому они называются глухими. Если при их образовании задействовать голосовые связки, то получатся соответственно звонкие [b], [d] и [g].

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

Другие группы согласных звуков: фрикативные, образующиеся за счёт того, что артикуляторы подходят близко друг к другу, но не смыкаются полностью (например, [s], [z], [v], [f]); носовые, которые производятся с движением воздуха через нос, а не через рот (например, [m], [n]).

Семейная рифма

Боковые звуки (вроде [l] и [r]) тоже образуются родственно, но сами звуки не настолько похожи, чтобы один из них можно было использовать в рифме вместо другого.

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

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

Согласная рифма — это самая слабая звуковая связь, воспринимаемая еще нестабильнее. В слогах, рифмующихся так, совпадают только согласные на конце. Как в friend и wind в этой песне.

Ритм

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

Работа над песней

Наконец, разобравшись со всеми этими вещами, лектор рассказывает о том, как вообще организовать творческий процесс. Он предлагает, определившись с идеей и заголовком песни, создать «рабочий лист», который будет помогать в работе над ней. Методом «рабочего листа» для поиска идей в процессе написания пользуется, например, американский композитор Стивен Сондхайм. (А кроме того, в фильме «Восьмая миля» с Эминемом в какой-то момент видно, что он тоже составляет такой лист.)

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

Таким образом, происходит просто случайный поиск идей, мозговой штурм с применением словаря рифм. Суть использования именно его в том, что идеи сразу будут иметь фонетическую связь. Не нужно будет думать: «Ага, у меня есть две строки, как бы мне теперь их прицепить одну к другой?»

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

4 комментария

Cейчас мы будем скрейпить весь интернет питоном 15 апреля 2013

Почти весь технический контент русскоязычного интернета публикуется либо в маленьких блогах, где его почти никто не видит, либо пишется специально для «Хабрахабра», который посещают уже миллионы человек в день. В англоязычном интернете работает «средний» вариант. Существуют социальные новостные сайты вроде реддита с разделом /r/programming или Hacker News, куда одни пользователи отправляют ссылки на интересные материалы, а другие плюсуют, минусуют, обсуждают. Любой может опубликовать что-то у себя в блоге, а потом разместить ссылку на свой пост там, чтобы привлечь читателей и комментаторов.

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

С тем самым Hacker News оказалось еще сложнее. Хотя контент там часто попадается интересный, непонятно, как за ним следить. Даже ритуала никакого не придумать. Постов много, списков лучшего за какой-то период нет. Только определяемое по неизвестной формуле лучшее на данный момент. Так что единственный вариант — постоянно вспоминать и заходить на сайт. Мне это не очень нравилось. Подумав и вдохновившись многочисленными статьями из серии «сейчас мы будем скрейпить весь интернет питоном», я решил написать штуку, которая поможет мне.

Этой штукой был скрейпер, который каким-то образом должен с HN некоторое количество лучших постов за вчерашний день и создавать RSS-поток, чтобы я без лишних действий мог получать его себе в ленту. При этом хотелось делать всё культурно, не напрягая, в первую очередь, сам сайт количеством запросов или чем-то еще. Уже не помню где, но видел, как Пол Грэм, создатель сайта, негативно отзывался о ботах, которые грузят не только первую страницу списка постов, но и следующие по ссылке «More», хотя в robots.txt написано так не делать. Я так делать не и стал, хотя это и исключало самый первый логичный вариант: заходить в раз день, загружать пару десятков страниц со списком постов за день, извлекать из них лучшие и публиковать. Можно было на странице с новыми постами только собирать список всех постов за день, а перед публикацией заходить непосредственно в эти посты и получать число голосов за них. Но в том же самом robots.txt установлено требование не делать запросы чаще, чем раз в 30 секунд. Так на загрузку всех постов за день может уйти часов восемь, а то и больше. Такой вариант тоже не подходит хотя бы потому, что за это время число голосов на первых загруженных страницах уже успеет измениться, появятся новые посты, в общем, результат получится неконсистентным.

Я сделал так: с некоторой периодичностью бот получает список постов, которые сейчас находятся на главной странице. Это тоже логично: много ссылок за день и не нужно, а топ-10, например, уж точно побывает на главной. Запросы я решил делать раз в полчаса, потому что, опять же, даже если какой-то пост успеет появиться на главной и снова пропасть в течение получаса, то он нас скорее всего интересовать и не будет.

Следующая часть веб-скрейпинга после загрузки — это разбор полученной страницы и выделение нужной информации. В данном случае нужная — это ссылка, заголовок, количество очков и идентификатор каждого поста. Несмотря на то, что сайт в духе старой школы свёрстан таблицами, трудностей с этим не было, если не считать пару внезапно обнаруженных фич. Например, оказалось, что на HN в списке могут быть рекламные ссылки, за которые голосовать нельзя, и очков у них нет. Другая неожиданность — если ссылка ведёт на pdf-файл, то этот файл загружается еще и на сервис scribd, а заголовок содержит уже две ссылки (исходную и на скрибд). Эту вещь я обнаружил далеко не сразу, и она меня заставила какое-то время поразбираться — а почему же ссылки, которые хранятся у меня для некоторых постов, не соответствуют ссылкам, которые в этих постах на самом деле.

Для парсинга я сначала использовал библиотеку Beautiful Soup. Потом вспомнил, что в обсуждении каждой из того самого множества статей про скрейпинг на питоне обязательно кто-то говорит, что lxml работает быстрее, чем Beautiful Soup (а еще всегда кто-то должен сказать: «А я использую для этого Scrapy»). Переделал на lxml, сравнил скорость: действительно, быстрее. В 90 раз. Поэтому оставил вариант на lxml, хотя временные затраты на парсинг в любом случае меньше, чем на скачивание страницы по сети.

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

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

За время публикации у меня отвечает cron, который регулярно запускает две самодельные команды для manage.py: одну для загрузки информации с сайта, другую для публикации подборки. Это время я назначил на 23:00 UTC. Это пять утра по челябинскому времени. Пять часов — это отличное время. С одной стороны, ссылки с утра уже успеют появиться в ленте, чтобы их можно было посмотреть по дороге или в университете. С другой, это уже достаточно поздно, чтобы засидевшись вечером не «дождаться» внезапного появления подборки в ленте. Для меня, по крайней мере, это время удобно. А в том, что кто-то еще будет пользоваться этой штукой, я не очень уверен.

http://igorshevchenko.ru/hnews/

2 комментария

Дыхание ветра 22 января 2013

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

Года два назад я копался в контркультурных книжках. Ну, вы знаете, такие с оранжевыми обложками. Там я нашел русский перевод романа Кэндзи Сиратори. Сиратори — нойзовый музыкант, который пишет (по крайней мере, раньше писал) больше сотни альбомов в год. В романе «Кровь электрическая» он использовал тот же подход, что и в музыке. Выглядит текст так:

Кровь электрическая

В предисловии переводчик объясняет, в чем дело:

Текст Сиратори является жестоким миксом четырёх языков: английского, латыни, японского и C++.

Действительно, микс получился довольно жестоким, и в тексте кровь, кишки, хаос и шум вместо нормальной, структурированной программы на правильном С++. Даже на перл не очень похоже.

Дальше переводчик рассказывает о значении элементов С++, использованных Сиратори:

// – конец блока

/ – разделитель уровней (мой дом/моя квартира/ моя комната) + – сложение

++ – постфиксное приращение (брить++себя – бриться)

‹‹ или ‹‹= – сдвиг влево

›› или ››= – сдвиг вправо

! – логическое отрицание

!= – не равно

== – равно

= – присвоение (витал=сыворотка – витал стал сывороткой)

:: – разрешение области действия

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

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

Оказалось, что думают примерно одно и то же: ужас, кошмар, автора надо отправить на лечение, да и переводчика теперь тоже стоило бы; но были и те, кто смог осилить книгу до конца. Они даже рассказывали свои интерпретации сюжета. Например, менее убедительная версия состоит в том, что текст о киборге, который борется с какой-то корпорацией (там и название ее было, но я не помню).

Более убедительная — что он о машине, которой понадобилось тело. И она каким-то образом попала в морг и стала там пытаться собрать его из отдельных частей. Она приделывает себе новые органы, учится пользоваться ими, исследует работу человеческого тела, изучает физиологические реакции. Заканчивается всё главой «Ликвидация» и словами: «Я вычисляю и взрываюсь::планета эродирует».

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

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

LDA

Здесь в каждой строчке перечислен набор слов с коэффициентами, которые характеризуют каждую тему. Не слишком разнообразно, зато жизненно.

Но на тот момент задача была другой. Я достал свой скрипт, который называется Соня Котлованова. Он был написан, чтобы генерировать тексты с помощью цепей Маркова, в частности, вопросы для ЧГК и твиты для твитера. В этот раз я обучил его на извлеченном из пабликов корпусе и на некоторых настоящих программах на C++. Соня Котлованова сгенерировала мне текст под названием «Дыхание ветра».

Отрывок из него:

осадок всё равно твоя жизнь полна любви <начинали эти отношения, возмущенное лицо, расстается без слез>

надеждами и глазами(партнером ради единственного поцелуя, валяться с кем приятно,

    одиночку шоколадку, утробе кричало дитя, скучает по тебе скучали) {

    образ является реальной силой(встречайте счастье и любовь где, освобождает дорогу кому);

    бросились в их животах образуется целое кладбище из упавших на дно(пожелайти удачи, влюбились ещё в таком удовольствии);

    непроизвольно исказилось(

        хитрые и коварные врачи спрашивают<вумя рукм>::ок будет,

        исполняют женских желаний<представляют каким должно быть столько одежды>::сходящих друг от друга и его считают юным агрессором);

    комбинезоне жарко(бутылкою в руках удержать, лебединую верность,

        лез в вашу секту<пятнадцати минут>::поддавайся а предали,

        думают что у девушки мозга<свадьба или кольцо>::производят на окружающих столь ошеломительного впечатления);

    позвонила сказать (вставать не хотела этих концертов != любящий мужчина найдет в каждом часу && смесью из равных частей оливкового масла и рома != спичечных коробках)

    закалённый характер (граффити нарисую(название фильма, распускается во всей этой боли тебя вернут в день свадьбы))

    тогда кричишь;

    нечеловеческие способности(бороды хотабыча(тренировочных базах, радовали нас))

    ++выгодно вдвойне;

    далёком прошлом

    ++разобравшись с тем мужчиной, ++сильному уступят дорогу;

    животными и людьми является то == девичьи привычки;

}

Как видно, получившийся текст, во-первых, написан на настоящем С++, в котором все символы значат именно то, что указано в стандарте языка, и, во-вторых, посвящен той правде жизни, которую любят ванильные девочки. Это уже хорошо.

Но не менее важно, что с точки зрения процесса мы оказались чуть ли не ближе к идеям Сиратори, чем он сам. Ведь программа, которая копается в исходниках Standard Template Library и постах из контакта, по-всякому препарируя их и пытаясь сконструировать что-то, похожее на живой текст о том, что дорого людям, — это почти что описанная им машина, пустившая по органам нескольких тел свою электрическую кровь.

Только плюсы правильные. И про любовь.

Нет комментариев

Прочтение этого текста позволит вам обрести стиральную машину, микроволновую печь и автомобиль 22 сентября 2012

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

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

Типичная игра там проходит так: игроки видят, из скольких букв состоит слово; пытаются назвать буквы, которые вероятнее всего будут в этом слове (обычно гласные, они же во всех словах есть); затем, когда гласных набирается, на их взгляд, достаточно, пытаются угадать согласные, которые были бы уместны среди того, что уже получено; и наконец, когда открыто достаточно букв, чтобы исключить большинство вариантов, какой-то счастливчик называет слово. Таким образом, у каждого игрока в голове есть какая-то частотная модель русского языка, которой они пользуются, чтобы максимизировать вероятность угадывания. Причем эта модель должна отличаться от той, которой пользовался герой Эдгара По (и, как мне почему-то казалось, герой Артура Конана Дойля в «Пляшущих человечках», но там оказалась своя мистическая технология):

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

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

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

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

Я извлек из словаря Открытого корпуса русского языка все нарицательные существительные, которых вышло примерно 66 тысяч, обработал их и получил такой результат (буквы по убыванию частоты):

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

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

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

Хотя и не очень.

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

Вот, например, по четырехбуквенным словам:

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

И по восьмибуквенным:

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

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

Учитывая эти пять пунктов, можно предложить такую стратегию: игрок, перед тем как назвать букву, выбирает из словаря все слова нужной длины, в которых не встречаются ошибочно названные буквы, а отгаданные стоят на соответствующих местах. Затем он подсчитывает для каждой буквы количество слов, в которых она встречается, и называет ту, для которой это число максимально. Мне кажется, любой участник «Поля чудес» способен проделать это, пока крутится барабан.

Недостатком этого алгоритма является то, что он детерминированный, то есть каждый раз можно предсказать, каким будет следующий ход. В теории игр существует понятие равновесия Нэша — состояния, когда всем участникам игры известны стратегии остальных, но ни один из них не может увеличить своего выигрыша, изменив свою стратегию, если у остальных участников она останется прежней. Если представить, что в «Поле чудес» есть два игрока, один из которых — Якубович, загадывающий слово, а другой — вся тройка, пытающаяся назвать как можно меньше букв, которых в слове нет, причем они побеждают, если отгадают слово, допустив менее какого-то фиксированного числа ошибок; так вот, если представить, то равновесия при использовании этой стратегии нет. Ведущий может подобрать слово, которое не получается отгадать, и каждый раз загадывать его. Немного (но далеко не полностью) приблизить равновесие Нэша можно, если делать выбор более случайно. Например, в какой-то момент посчитали, что буква А встречается в 5 словах, буква О — в 7, а буква Р — в 3. Тогда запускается генератор случайных чисел, с помощью которого с вероятностью 5/15 выбирается А, 7/15 — О и 3/15 — Р. В среднем это должно дать то же самое.

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

  1. Перебрать все 66 тысяч слов с помощью первого детерминированного варианта, чтобы отбросить наиболее легкие. Примерно в трети случаев слова были названы полностью без единой ошибки. В итоге, я оставил те десять тысяч, в которых отгадыватель предположил более трех букв неправильно.
  2. Затем, прогнать каждое слово из оставшихся по 20 раз уже на случайном алгоритме. Тут появилась небольшая проблема с тем, что требовалось определиться, сколько ошибок можно сделать до того, как игрока повесят. Просто отгадывать до конца, а потом посчитать среднее, нельзя: поражение с пороговым числом ошибок и поражение с числом, превышающим его, по сути одинаковы. Оказалось, что единого мнения о количестве деталей на рисунке с висельником, нет. Пришлось прикинуть: столб, перекладина, петля, голова, туловище, правая рука, левая рука, правая нога, левая нога, посиневший язык. Итого десять.
  3. Около четырехсот слов, которые не были отгаданы более, чем в половине случаев, я прогнал уже немного более масштабно: по 100 раз каждое. Топ по числу поражений выглядит так:

ЦАЦКА ЖИЖА ЦЕЖ ЧОХ

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

А перед тем, как начнется рекламная пауза, я хочу передать привет Саше, Саше, Антону, Сереже, Насте, Саше, Оле, Толику, Юле, Анюте, Богдану и всем остальным, кто может меня читать.

1 комментарий
← Раньше Позже →