В марте интернеты бурно обсуждали покупку компанией «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 году.