Pi-code

Миф о продуктивности Python-а

2011-03-13T16:47:00.002+03:00

Последние 2-3 года моя основная работа связана с Perl-ом и каждая попытка написать на Python-е что-нибудь "для души" заканчивается раздражением. Спотыкаешься там, где, казалось бы, никаких "коряг" быть не должно. Так произошло и в эти выходные.

Мне понадобилось написать программку, которая разбирает access.log и раскладывает его поля по таблицам базы данных SQLite. Вполне тривиальная задачка, кто только ей ни занимался.

Сам парсер не представляет из себя ничего сложного. Вот пример строки лог-файла:


89.179.242.83 - - [06/Mar/2011:07:09:48 +0000] "GET /themes/_pebble/handheld.css HTTP/1.1" 200 1020 "http://www.lunarium.ru/2011/02/19/1298158440000.html" "Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_6_6; ru-ru) AppleWebKit/533.19.4 (KHTML, like Gecko) Version/5.0.3 Safari/533.19.4"

А вот регулярное выражение, которое прекрасно с ней справляется (я позаимствовал его из Johen's blog :


parts = [
    r'(?P\S+)',       # host %h
    r'\S+',                 # indent %l (unused)
    r'(?P\S+)',       # user %u
    r'\[(?P.+)\]',    # time %t
    r'"(?P.+)"',   # request "%r"
    r'(?P[0-9]+)',  # status %>s
    r'(?P\S+)',       # size %b (careful, can be '-')
    r'"(?P.*)"',   # referer "%{Referer}i"
    r'"(?P.*)"',     # user agent "%{User-agent}i"
]
pattern = re.compile(r'\s+'.join(parts)+r'\s*\Z')

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


Berkana:~ sergey$ ping 3232235777
PING 3232235777 (192.168.1.1): 56 data bytes
64 bytes from 192.168.1.1: icmp_seq=0 ttl=255 time=6.288 ms

В Python-овской бибиотеке urllib имеется функция inet_aton, возвращающая упакованное бинарное значение, которое может потребоваться при обмене данными с низкоуровневыми С-библиотеками. Из него можно получить целочисленное значение, для этого его надо распаковать, используя стандартный модуль struct. Беда в том, что документация к inet_aton немногословна и мне понадобилось немало времени, чтобы понять, с какими ключами вызывать функцию struct.unpack для получения нужного результата.


import socket
import struct
struct.unpack('!L', socket.inet_aton(ip))

, где ip представляет собой строку типа: '192.168.1.1'.

Обратная операция:

 socket.inet_ntoa(struct.pack('!L', i))

, где i представляет собой целое число.

Я в курсе, что можно плюнуть на библиотеки и поступить по-простому:


a << 24 | b << 16 | c << 8 | d

, где a, b, c, d — части Ip-адреса. Но не стал этого делать из принципа, дабы не плодить сущности.

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


http://go.mail.ru/search?q=%E4%EE%EB%E3%EE%F2%E0%20%E4%ED%FF%20%ED%E0%20%EC%E0%F0%F2%202011%E3%EE%E4%E0&rch=e&num=10&sf=90%22

Тарабарщина со знаками процентов в данном случае — ни что иное как фраза "долгота дня на март 2011года". Разумеется, хранить удобнее читаемый текст. В Perl-е, чтобы расшифровать закодированную таким методом строку, достаточно импортировать модуль URI::Escape и вызвать его функцию uri_unescape(). В Python-е для этой же цели служат urllib.unquote() и urllib.unquote_plus().


>>> import urllib
>>> url = "http://go.mail.ru/search?q=%E4%EE%EB%E3%EE%F2%E0%20%E4%ED%FF%20%ED%E0%20%EC%E0%F0%F2%202011%E3%EE%E4%E0&rch=e&num=10&sf=90"
>>> unquoted_url = urllib.unquote_plus(url)
>>> unquoted_url
'http://go.mail.ru/search?q=\xe4\xee\xeb\xe3\xee\xf2\xe0 \xe4\xed\xff \xed\xe0 \xec\xe0\xf0\xf2 2011\xe3\xee\xe4\xe0&rch=e&num=10&sf=90'

Поскольку SQLite работает с UTF-8, полученное значение необходимо перевести в unicode.


>>> unicode(unquoted_url)
Traceback (most recent call last):
File "", line 1, in 
UnicodeDecodeError: 'ascii' codec can't decode byte 0xe4 in position 27: ordinal not in range(128)

Что случилось? А дело в том, что функция unicode не знает кодировку исходной строки. Раз запрос исходил из mail.ru, наверняка тут русская windows-кодировка. Так и есть!


>>> unicode(unquoted_url, encoding='cp1251')
u'http://go.mail.ru/search?q=\u0434\u043e\u043b\u0433\u043e\u0442\u0430 \u0434\u043d\u044f \u043d\u0430 \u043c\u0430\u0440\u0442 2011\u0433\u043e\u0434\u0430&rch=e&num=10&sf=90'

Ну, а как быть с другими кодировками? ...Вспоминаю, что для угадывания кодировки текста существует питоновский модуль chardet. Он считается достаточно надежным, однако для моей цели явно не подходит — уж слишком часто промахивается. Видимо потому, что исходный текст слишком короток. Пришлось написать вот такой костыль:


def decode_referer(url):
    refurl = urllib.unquote_plus(url)
    try:
       refurl = unicode(refurl)
    except UnicodeDecodeError:
       logger.warn("Could not decode string: '%s'. Trying cp1251..." % refurl)
       try:
           refurl = unicode(refurl, encoding='cp1251')
           logger.info('Success.')
       except

UnicodeDecodeError:

            logger.warn("Could not decode string. Trying to guess encoding...")
           enc = chardet.detect(refurl)['encoding']
           logger.warn('Detected %s' % enc)
           try:
               refurl = unicode(refurl, encoding=enc)
               logger.info('Success.')
           except UnicodeDecodeError:
               logger.error('Could not decode string. Will store it as is')
    return refurl

...И кто придумал миф о продуктивности Python-а?

Ленивая дата

2010-11-19T14:02:00.013+03:00

Календарные функции, представленные в предыдущей заметке, работают, исходя из наивного предположения, что на вход поступают правильные данные. В каких-то случаях ничего плохого не произойдет. К примеру, при вычислении юлианской даты на 29 февраля 1975г (в феврале 1975 было 28 дней), результат будет таким же как для 1 марта:

$ perl julian.pl 1975 2 29
JD: 2442472.500000
JD at 0h: 2442471.500000
Fri

$ perl julian.pl 1975 3 1
JD: 2442472.500000
JD at 0h: 2442471.500000
Fri

Хорошим такое API никак не назовешь. Самое время задуматься над созданием удобного для использования класса.

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

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

Julian->new(date => \%ymd, djd => $scalar)

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

new_from_date(year => $scalar, month => $scalar, day => $scalar)

```
new_from_djd($djd)
```

Как правило, я стараюсь не использовать модуль Params::Validate, который создан как раз для проверки входных параметров -- уж больно велики накладные расходы, да и ни к чему превращать динамический язык в подобие Java. Но тут как раз тот случай, когда без него не обойтись.

Начнем с более простого метода new_from_djd.

...
use Params::Validate qw/:all/;
use Readonly;
Readonly our $DJD_TO_JD => 2415020;

...

sub new_from_djd {
 my $class = shift;

 validate_pos(
    @_,
    {
        type => SCALAR,
        regex => qr/^[-+]?0*(\d+|(?:\d*\।\d+))$/, 
        callbacks => {
            'djd range' => sub{ $_[0] >= -$DJD_TO_JD }
        }
    }
 );

 bless {
     _djd  => shift,
     _date => undef,
 }, $class
}
...

Поскольку параметры здесь не именованные, а позиционные, для валидации данных используется метод validate_pos из пакета Params::Validate. Имя класса предварительно убрано из списка аргументов ( @_ ). Проверка производится по трем критериям:

```
type => SCALAR
```
аргумент должен быть скаляром
```
qr/^[-+]?0*(\d+|(?:\d*\.\d+))$/
```
аргумент должен быть целым или десятичным числом, с любым количеством ведущих нулей и с необязательным ведущим "плюсом" или "минусом"
```
'djd range' => sub{ $_[0] >= -$DJD_TO_JD }
```
число не должно быть меньше нулевой стандартной юлианской даты (напомню, что видоизмененная юлианская дата, которую мы используем, больше стандартной на 2415020 суток. Функции обратного вызова (callbacks) -- "тяжелая артиллерия" пакет Params::Validate. Внутри них можно осуществлять любые проверки. На входе всегда два параметра: проверяемый аргумент и ссылка на все аргументы (хэш или массив).

В конце мы "благословляем" (bless) новорожденный экземпляр с инициализированным атрибутом djd и пустой (до поры до времени) календарной датой.

Второй метод-фабрика сложнее:


...
use Params::Validate qw/:all/;
use Readonly;

Readonly our $DJD_TO_JD     => 2415020;
Readonly our $MIN_YEAR      => -4713;
Readonly our $MAX_YEAR      =>  4713;

...

sub new_from_date {
 my $class = shift;

 my %args = validate(
     @_,
     {
         year  => {
             type      => SCALAR,
             regex     => qr/^[\-+]?\d{1,4}$/,
             callbacks => {
                 'year range'    => sub{
                     $MIN_YEAR <= $_[0] && $MAX_YEAR >= $_[0]
                 },
                 'non-zero year' => sub{ 0 != $_[0] }
             }
         },

         month  => {
             type      => SCALAR,
             regex     => qr/^0*([1-9]|(1[0-2]))$/,
         },

         day    => {
             type      => SCALAR,
             regex     => qr/^0*([1-9]|([0-2]\d)|(3[0,1]))(\।\d+)?$/,
             callbacks => {
                    'day range' => sub{
                        my ($d, $arg) = @_;
                        $d >= 1 &&
                        $d < _days_per_month($arg->{year}, $arg->{month}) + 1;
                    }
             }
         },
     }
 );


 bless {
     _djd  => undef,
     _date => \%args,
 }, $class
}
...

Здесь аргументы именованные, поэтому для их валидации используется метод validate.

год проверяется по четырем критериям:
1. тип аргумента -- скаляр
2. аргумент -- положительное или отрицательное целое число
3. диапазон: от 4713г. до н.э до 4713г. н.э.
4. ноль не допускается

У месяца тип должен должен быть скаляром, а диапазон (1-12) проверяется регулярным выражением
```
qr/^0*([1-9]|(1[0-2]))$/
```
Проверка числа самая сложная.
1. тип аргумента -- скаляр.
2. при помощи регулярного выражения проверяем, что это число, возможно, с десятичными долями; при этом целая часть не выходит за рамки диапазона 1-31.
3. При окончательной проверке диапазона вызывается внешняя функция _days_per_month (см. ниже)

В конце мы "благословляем" (bless) новорожденный экземпляр с сохраненными в хэше годом, номером месяца и числом.

Сколько дней в месяце?

Количество дней во всех месяцах, кроме февраля, в григорианском календаре неизменно.
Чтобы узнать число дней в феврале, надо определить, является ли год високосным. Если да -- то 29, если нет -- то 28. Для определения "високосности" функция _leap_year. Год в григориансмком календаре является високосным, если он кратен 4 и при этом не кратен 100, либо кратен 400 (в отличие от "старого стиля", где високосным считался каждый четвертый год).

# является ли год високосным?
sub _leap_year {
  my $y = shift;
  return 1 if $y % 400 == 0;
  return 0 if $y % 100 == 0;
  return 1 if $y %   4 == 0;
  return 0;
}

# количество дней в месяце
sub _days_per_month {
  my ($y, $m) = @_;
  return _leap_year($y) ? 29 : 28 if $m == 2; # февраль
  return 30 if grep{ $m == $_ } (4, 6, 9, 11); # апрель, июнь, сентябрь, ноябрь
  return 31; # остальные месяцы
}

Ленивые вычисления

Два getter-а: djd и date служат для получения юлианской и календарной даты. Если либо одно либо другое не определено (undef), оно вычисляется и сохраняется как аттрибут объекта.

sub djd {
  my $self = shift;
  $self->{_djd} = _date2djd(%{$self->{_date}})
      unless defined $self->{_djd};
  $self->{_djd}
}

sub date {
  my $self = shift;
  $self->{_date} = _djd2date($self->{_djd})
      unless defined $self->{_date};
  $self->{_date}
}

Функции _date2djd и _djd2date, которые заняты вычислениями, уже описаны в предыдущей заметке. Здесь я только добавил к их названиям нижнее подчеркивания в качестве рекомендации не использовать их снаружи.

Юлианские даты

2010-11-10T16:00:00.038+03:00

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

Непрерывный счет дней

Одним из широко известных решений этой проблемы стало так называемое "время Unix", измеряемое количеством секунд, прошедших от полуночи 1 января 1970 года. Прикладные языки программирования предоставляют собственные библиотечные средства. Помнится, в Delphi был тип TDateTime, который хранил даты и время в виде десятичных чисел; целая часть представляла количество дней, прошедших с полуночи 30 декабря 1899 года, а дробная часть -- время суток (стандарт OLE Automation). Базы данных, где проблема расчета времени весьма актуальна, делают это по-своему. Например, TIMESTAMP в MySQL 5.1 отсчитывается от 0ч 1 января 1000 года. Python умеет работать с датами в диапазоне от 1 до 9999 г.г. н.э. В языке Java... впрочем, довольно подробностей. Если нас интересуют события космического масштаба, как-то: восходы и заходы, равноденствия и солнцестояния, фазы Луны, координаты планет, наконец, интервалы времени, не ограничивающиеся нашей эрой -- ни одно из этих средств не подойдет. Что понадобится -- так это юлианские даты, система непрерывного счета времени, которую используют астрономы.

За точку отсчета астрономы приняли средний гринвичский полдень 1 января 4713 г. до н.э. Очередная юлианская дата начинается в 12ч00м UT, что на полсуток расходится с началом гражданских суток. Целая часть числа представляет собой число суток, дробная -- доли суток, прошедшие от полудня. Например, 6ч 17 февраля 1985 года соответствует юлианской дате 2446113.75.

Проблемы с точностью

В эпоху первых персональных компьютеров и программируемых калькуляторов возникали проблемы с точностью. В некоторых системах на хранение вещественных чисел отводилось всего 4 байта (то же самое, что сегодняшнее float), что ограничивало точность 6-7 цифрами. Между тем, юлианские даты часто представлены 11-12 цифрами. Скажем, 11ч. 17 августа 1938 года = JD 2429127.9583

Смещение точки отсчета

Можно принять за точку отсчета вместо даты, отстоящей от нас на 6 тысячелетий, момент поближе. Питер Даффетт-Смит в книге "Astronomy With Your Personal Computer" (Cambridge University Press, 1986) предлагает использовать 12ч GMT 31 декабря 1899 года, т.е. ближайший полдень до начала XXв. Вычисления в рамках ближайших столетий становятся точнее, поскольку на хранение переменных потребуется меньше памяти. Даты до этого момента отрицательные. Чтобы перейти от такой даты (назовем ее вслед за Даффетт-Смитом DJD) к стандартной юлианской (JD), надо прибавить к первой 2415020.

Современное восьмибайтное представление вещественных чисел (double), дает точность до 16 цифр, так что проблема, о которой идет речь, больше неактуальна, однако я намерен следовать методу из книги Даффетт-Смита. Тем более, что момент 12ч UT 31 декабря 1989 года взят не с потолка. Забегая вперед, скажу, что во множестве астрономических расчетов используется время в юлианских столетиях, прошедшее именно от этой даты (T). Формула такова:

T = (JD - 2415020) / 36525

Здесь JD -- юлианская дата. То же самое, что DJD / 36525. Делитель, как нетрудно догадаться, представляет собой количество суток в условном юлианском столетии.

Между прочим, класс DateTime из одноименного пакета Perl содержит метод jd, выдающий стандартную юлианскую дату. В базе SQLite имеется функция для ее получения.

От календаря к юлианской дате

Алгоритм пересчета календарной даты в юлианскую суров и непригляден. Его реализации на любых языках программирования
выглядят примерно одинаково. Ниже представлен ее вариант на языке Perl.


sub date2djd {
    my %args = @_;
    my $d = $args{date};
    my $m = $args{month};
    my $y = $args{year};
 
    $y++ if $y < 0;
    if ($m < 3) {
        $m += 12;
        $y--
    }
    my $b;
    if (after_gregorian($y, $m, $d)) {
        my $a = floor($y / 100);
        $b = 2 - $a + floor($a / 4);
    }
    else {
        $b = 0
    }
    my $f = 365.25 * $y;
    my $c = floor( $y < 0 ? $f - 0.75 : $f ) - 694025;
    my $e = floor(30.6001 * ($m + 1));
    return $b + $c + $e + $d - 0.5
}

На входе у нее именованные аргументы:

year -- номер года, отрицательный для годов до н.э. Нулевое значение недопустимо, т.е. за -1 следует +1 вместо 0.
month - номер месяца (1-12)
day -- день месяца с долями суток. Например, 07ч 40м первого числа будет соответствовать 1 + (7 + 40 / 60.0) / 24.0

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

Календарная дата относится к пролептическому григорианскому календарю. Так называется григорианский
календарь, который используется для обозначения дат, предшествовавших его введению. А применен он был впервые 15 октября 1582 года. Вспомогательная функция after_gregorian как раз и помогает определить, приходится ли заданная дата на период до или после календарной реформы


sub after_gregorian {
    my ($y, $m, $d) = @_;
    return 0 if $y < 1582;
    return 1 if $y > 1582;
    return 0 if $m < 10;
    return 1 if $m > 10;
    return 0 if $d <= 15;
    return 1;
}

Использовать эту функцию самостоятельно, вне пролептического календаря, не имеет смысла, потому что григорианское летоисчисление не было принято везде одновременно. Наша страна перешла на "новый стиль" в 1918 году.

От юлианской даты к календарю

А вот как выглядит обратная функция, переводящая юлианскую дату в календарную.


sub djd2date {
    my $djd = shift;

    my $d = $djd + 0.5;
    my ($f, $i) = modf($d);

    if ($i > -115860) {
        my $a = floor($i / 36524.25 + 9.9835726e-1) + 14;
        $i += 1 + $a - floor($a / 4);
    }
    my $b = floor($i / 365.25 + 8.02601e-1);
    my $c = $i - floor(365.25 * $b + 7.50001e-1) + 416;
    my $g = floor($c / 30.6001);
    my $dy = $c - floor(30.6001 * $g) + $f;
    my $mn = $g - ($g > 13.5 ? 13 : 1);
    my $yr = $b + ($mn < 2.5 ? 1900 : 1899 );
    $yr-- if $yr < 1;

    return {year => $yr, month => $mn, day => $dy}
}

На входе DJD -- число юлианских дней от начала XX века. На выходе -- хэш того же вида, что и на входе date2jd.

День недели

Система юлианских дней позволяет довольно просто вычислить день недели. Для этого достаточно:

Взять юлианскую дату на начало календарных суток (0ч UT).
Прибавить к ней 1.5.
Найти остаток от деления результата на 7

0 будет соответствовать воскресенью, 1 -- понедельнику, 2 -- вторнику и так до 6 -- субботы.

Добавим две новые функции:

jd_midnight для вычисления юлианской даты на календарную полночь, исходя из заданной юлианской даты
weekday для вычисления дня недели по юлианской дате на начало суток.


#!/usr/bin/perl -w
use strict;
use warnings;
use POSIX qw/modf floor/;
use Readonly;

Readonly our $DJD_TO_JD => 2415020;
Readonly our @WEEKDAYS => qw/Sun Mon Tue Wed Thi Fri Sat/;

....

sub jd_midnight {
    my $j = shift;
    my $f = floor($j);
    return $f + (abs($j - $f) > 0.5 ? 0.5 : -0.5);
}

sub weekday {
    my $j = shift;
    my $j0 = jd_midnight($j);
    return ($j0 + 1.5) % 7
}


if (@ARGV < 3) {
    print "Usage: perl julian.pl YEAR MONTH DAY";
    exit(0)
}

my $djd = date2djd(year => $ARGV[0], month => $ARGV[1], day => $ARGV[2]);
my $j = $djd + $DJD_TO_JD;
printf "JD: %f\n", $j;
my $j0 = jd_midnight($j);
printf "JD at 0h: %f\n", $j0;
my $w = weekday($j);
print $WEEKDAYS[$w], "\n";

На месте многоточий в скрипте должны фигурировать функции date2djd и after_gregorian.
Важно: на входе jd_midnight и weekday стандартная юлианская дата, а не DJD. Иначе пришлось бы возиться с отрицательными значениями.

Пример: в какой день недели был запущен первый советский спутник? Известно, что это произошло 4 октября 1957 года 19ч28м34с UT.
Третьим аргументом (день) будет:((34 / 60 + 28) / 60 + 19) / 24 + 4 = 4.8115

$ perl julian.pl 1957 10 4.8115
JD: 2436116.311500
JD at 0h: 2436115.500000
Fri

Пятница, все правильно.

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

Perl и рекурсия: ура!

2010-11-09T02:14:00.013+03:00

В прошлой заметке выяснилось, что в Python-е рекурсия работает медленнее, чем for-цикл, а тот, в свою очередь -- медленнее, чем while. С циклами все понятно, while всегда быстрее. Что же касается рекурсии, то мне стало любопытно: специфична ли ее низкая производительность для Python-а или это везде так. И я решил ту же задачку -- получение из десятичного числа градусов, минут и секунд -- на Perl-е. Правда, ограничившись двумя

функциями: рекурсивной и циклом-while. Было интересно, насколько сильно здесь рекурсия отстает от цикла.

Результат удивил: рекурсия оказалась эффективнее.


Benchmark: timing 1000000 iterations of Recursive, While-loop...
Recursive: 136.521 wallclock secs (119.61 usr +  0.64 sys = 120.25 CPU) @ 8316.01/s (n=1000000)
While-loop: 142.86 wallclock secs (123.91 usr +  0.66 sys = 124.57 CPU) @ 8027.61/s (n=1000000)

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

Вот скрипт целиком:

Python и рекурсия? Увы...

2010-11-08T15:25:00.014+03:00

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

Полагаем, что x = исходное число.
Находим целую (i) и дробную (f) часть x.
Целую часть сохраняем как градусы, минуты или секунды.
Если найдены три числа, конец.
Полагаем x = f * 60 и возвращаемся к шагу 2.

Понятно, что эти вычисления производятся в цикле, однако подробности организации цикла пока не важны.

Как быть с отрицательными числами? В этом случае алгоритм немного усложняется:

Полагаем, что x = исходное число.
Находим целую (i) и дробную (f) часть от абсолютного значения x.
Если x положительное, переходим к шагу 5.
Если i не равно 0, полагаем i = -i. В противном случае, f = -f
Целую часть сохраняем как градусы, минуты или секунды.
Если найдены три числа, конец.
Полагаем x = f * 60 и возвращаемся к шагу 2.

Теперь при отрицательном исходном числе, первое значащее число будет отрицательным. Так,

11.75 -> 11:45:0
-11.75 -> -11:45:0
-0.75 -> 0:-45:0

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

Полагаем, что x = исходное число.
Если при текущем повторении вычисляются секунды, сохраняем x как секунды и выходим из цикла.
Находим целую (i) и дробную (f) часть от абсолютного значения x.
Если x положительное, переходим к шагу 6
Если i не равно 0, полагаем i = -i. В противном случае, f = -f
Целую часть сохраняем как градусы или минуты.
Полагаем x = f * 60 и возвращаемся к шагу 2.

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

рекурсивно;
при помощи циклов: for и while;
с использованием генераторов.

Начнем с рекурсии.

Функция возвращает кортеж из шестидесятиричных значений: (градусы, минуты, секунды). Именованный параметр num_vals указывает на то, сколько значений необходимо вернуть. Если секунды не нужны, num_vals=2.

Рассмотрим альтернативные способы. Чтобы не повторять один и тот же код, вынесем общую часть в отдельную функцию:

Функция, делающая то же самое при помощи for-цикла, выглядит менее изящно:

А вот вариант с циклом while:

На очереди -- генераторы. Первый из них использует for, второй -- while

Какая из функций работает быстрее всех? Для измерения я воспользовался стандартным методом Timer.timeit, которая по умолчанию запускает заданный код миллион раз. Получилось вот что:

Benchmarking X -> D,M,S

465 сек.: 'while'-цикл
600 сек.: 'while'-генератор
768 сек.: 'for'-цикл
544 сек.: 'for'-генератор
995 сек.: рекурсия

Увы, самый изящный, на мой взгляд, способ оказался самым медленным! А выиграла самая примитивная функция -- даже не генераторы.

Входной билет на собеседование

2010-02-19T12:47:00.011+03:00

Письмо, полученное сегодня утром, показалось мне знакомым. Так и есть! В 2008 году та же "ведущая игровая компания" уже искала Perl программистов. Требования к кандидатам и условия работы стандартные. Далее шла неуклюжая формулировка:

"Решением о дальнейшем сотрудничестве являются:
Успешно выполненное тестовое задание;
Положительные результаты собеседования."

Тестовое задание прилагалось -- даже не одно, а два.

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

Допустим, веб-приложение я напишу за вечер. Хотя нет, вечера не хватит, учитывая необходимость дублировать CGI. Хоть в условиях и сказано, что можно ограничиться GET-запросами (а POST, мол, является дополнительным плюсом), у меня рука не поднимется передавать логин и пароль пользователя так, чтобы они были видны в адресной строке браузера. Так что, если в пятницу вечером я сяду, то закончу в субботу часикам к четырем. На второе задание уйдет как минимум полдня.

И в том и другом случае особого ума не требуется, это рутина. Но рутина трудоёмкая. А на выходные у меня уже имеются кое-какие планы. Во-первых, мы с Мариной собирались на концерт, в кои-то веки. Во-вторых, детям при моей занятости недостает внимания. Позавчера сижу в офисе, Марина звонит, жалуется: "...Два сапога -- пара, только что поругались и принялись кидаться друг в друга едой". В-третьих, есть пара собственных проектов, на которые катастрофически не хватает времени. Так что, увольте. Выходные -- слишком высокая цена для входного билета на собеседование.

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

Он мечтает попасть в эту компанию. Мне самому ни разу не приходилось слышать о компании "Адептус". Но, наверное, я не в теме. Ясно, что существует она не меньше двух лет, причем -- кризисных, хороший признак. Может, программисты валят туда толпами и они выбирают лишь тех, кто готов на все лишь бы получить там место.
Нет выбора. С работы уволили, деньги кончились, больше никуда не берут.

Больше ничего не приходит в голову.

PS. Кто-то метко сказал: "тестовое задание я готов выполнить за тестовую зарплату".

Краулер своими руками. Часть 12

2009-01-30T12:23:00.005+03:00

Как работает базовая аутентификация

Наряду с аутентификацией при помощи формы, существует и более простая -- так наз. "базовая аутентификация":

При первой попытке зайти на сайт сервер проверяет, если среди заголовков запроса поле 'Authorization'. Если нет или там содержится неверное значение, возвращается ошибка 401.
Браузер открывает всплывающее окошко для ввода имени пользователя логин и пароля
Пользователь вводит имя и пароль, нажимает OK и браузер делает повторный запрос, вставив в заголовок запроса: Authorization: Basic данные.
Сервер проверяет логин с паролем и если все в порядке, возвращает запрошенную страницу с кодом 200.

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

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

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

Базовая аутентификация и urllib2

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

HTTPPasswordMgr
HTTPBasicAuthHandler

Первый позволяет задавать имя пользователя и пароль, второй добавляется в набор handler-ов (обработчиков запроса) для специализированного экземпляра OpenDirector (см. подробности).

Простейший вариант HTTPPasswordMgr

class KnownPasswordMgr(HTTPPasswordMgr):
 """
 Хранит заранее заданную пару логин/пароль
 """
 def __init__(self, username, password):
     HTTPPasswordMgr.__init__(self)
     self.username = username
     self.password = password

 def find_user_password(self, realm, authuri):
     """
     Возвращает заранее известную пару значений
     """
     retval = HTTPPasswordMgr.find_user_password(self, realm, authuri)
     if not (retval[0] or retval[1]):
         return (self.username, self.password)
  
     return retval

Этот класс рассчитан на использование одной единственной пары имя/пароль.

HTTPBasicAuthHandler

В конструктор класса UserAgent добавим необязательный параметр: credentials. Если он присутствует, к набору handler-ов будет добавлен HTTPBasicAuthHandler.

class UserAgent(object):
 """
 Краулер.

 Именованные аргументы конструктора и значения по умолчанию:
   agentname -- имя ('Test/1.0')
   email -- адрес разработчика (пустая строка)
   hdrs -- словарь HTTP-заголовков (DEFAULT_HEADERS)
   ignore_robots -- True, если следует игнорировать robots.txt (False)

   credentials -- словарь с ключами 'логин' и 'пароль', если нужна
                  базовая аутентификация (None).
 """

 def __init__(self,
              agentname=DEFAULT_AGENTNAME,
              email=DEFAULT_EMAIL,
              hdrs=None,
              ignore_robots=False,
              credentials=None):
  
     if not hdrs:
         hdrs = {}
     self.agentname = agentname
     self.email = email

     self.cookies_handler = SessionCookieHandler()
     handlers = [ self.cookies_handler, ]
     if not ignore_robots:
         handlers.append(RobotsHTTPHandler(self.agentname))
      
     if credentials:
         handlers.append(
             HTTPBasicAuthHandler(KnownPasswordMgr(**credentials))
         )
      
     self.opener = urllib2.build_opener(*handlers)

     # переопределение заголовков по умолчанию
     headers = copy(DEFAULT_HEADERS)
     headers.update(hdrs)     
     op_headers = [ (k, v) for k, v in headers.iteritems() ]
     op_headers.append(('User-Agent', self.agentname))
     # если email не задан, HTTP-заголовок 'From' не нужен
     if self.email:
         op_headers.append(('From', self.email))
  
     self.opener.addheaders = op_headers

Вот, собственно, и все. TestCase для новой функции может выглядеть так:

class TestAuth(unittest.TestCase):
 def setUp(self):
     self.crawler = crawler.UserAgent(
         agentname='Mozilla/4.0 (compatible; MSIE 5.5; Windows NT)',
         ignore_robots=True,
         credentials = dict(username='ЛОГИН', password='ПАРОЛЬ')
     )

 def _on_success(self, *args):
     self.assertTrue(1)

 def _on_failure(self, url, err):
     self.fail('Authentication failed: %s' % err) 
  
 def test_authentication(self):
     self.crawler.visit('АДРЕС САЙТА',
                        on_success=self._on_success,
                        on_failure=self._on_failure )

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

Краулер своими руками. Часть 11

2009-01-26T22:31:00.016+03:00

Лень как двигатель прогресса

В последнее время я пристрастился к порталу "Кинокопилка", откуда можно скачивать фильмы. Я захожу в разделы интересующих меня жанров, чтобы узнать, не появилось ли там что-нибудь интересное. Не все же время программы писать! Еще есть онлайн-библиотека технической литературы. Рассылка приходит раз в месяц, а новые книги появляются ежедневно. В отличие от "Кинокопилки", этот сайт предоставляет RSS-канал. Но среди первых заголовков, которые я вижу через программу просмотра каналов, далеко не всегда фигурируют книги по моей специальности. Так что, все равно приходится идти на сайт.

Если добавить еще пяток ежедневно просматриваемых сайтов, то процедура становится уже несколько утомительной. А кому-то необходимо отслеживать информацию, меняющуюся каждый час: наблюдать за финансовыми событиями, наличием свободных мест и объявлений... Вот почему пользуются спросом так называемые "скраперы".

Скрапер

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

Типичный сценарий

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

Нельзя ли пропустить первый шаг, сразу отправляя на сервер логин и пароль? Иногда можно, но чаще -- нет, по двум причинам:

В ходе авторизации сервер может проверить наличие кода анонимной сессии. А код этот можно получить только если вначале открыть страницу сайта (читай: сделать GET-запрос). У анонимной сессии тоже имеется код, только сервер не связывает его с базой данных зарегистрированных пользователей.
Многие сайты, помимо логина и пароля, проверяют еще и заголовок HTTP-запроса "Referer", ожидая увидеть там адрес страницы авторизации (а то ходят тут всякие...).

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

Авторизация средствами urllib2

Кодом сессии клиент и сервер обычно обмениваются через механизм cookie, о котором шла речь в предыдущей заметке. Поэтому при использовании Python-библиотеки urllib2 в первую очередь надо позаботиться о том, чтобы в экземпляр OpenDirector был включен HTTPCookieProcessor. В заметке, посвященной cookies, использовался
экземпляр стандартного HTTPCookieProcessor-а. Он работает out of the box. Но если требуется расширенная функциональность -- к примеру, возможность сохранять полученные коды авторизации в файле, удобнее определить класс-наследник:

Поддержка cookies

import cookielib
from urllib2 import HTTPCookieProcessor
COOKIEFILE = '...' # путь к файлу, где хранятся cookies
class SessionCookieHandler(HTTPCookieProcessor):
  """
  Загружает и сохраняет куки.
  """
  def __init__(self):
      cjar = cookielib.LWPCookieJar()
      if os.path.isfile(COOKIEFILE):
          cjar.load(COOKIEFILE)
  
      HTTPCookieProcessor.__init__(self, cjar)

  def save_cookies(self):
      """ Сохранение кук"""
      self.cookiejar.save(COOKIEFILE)

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

self.cookies_handler = SessionCookieHandler()
handlers = [
  self.cookieshandler,
  # другие нестандартные handler-ы
]
self.opener = urllib2.build_opener(*handlers)

POST-запрос

Класс urllib.Request имеет второй аргумент -- data. При непустом значении предполагается, что там содержатся параметры POST-запроса, которые выглядят примерно так: param1=value1&param2=value2... Для создания такой строки используется функция из "соседнего" пакета urllib:

import urllib # не путать с urllib2!
data = urllib.urlencode({'param1':'param1', 'param2':'value2',})

ESCAPE-последовательности и кирилица

Не проще ли создать строку параметров запроса руками? Нет, потому что функция urlencode при необходимости конвертирует строки в ESCAPE-последовательности.

from urllib import urlencode
urlencode({'name':'sergey krushinsky'})
'name=sergey+krushinsky'

Тонкость работы urlencode с кириллицей в том, что уникодные и байтовые строки возвращают разные результаты.

from urllib import urlencode, unquote
s1 = urlencode({'name':'вася'})
s2 = urlencode({'name':u'вася'})
print unquote(s1).encode('1251')
name=РІР°СЃСЏ
print unquote(s2).encode('1251')
name=вася

Запрос будет выглядеть так:

req = urllib2.Request(url, post_data)
handle = self.opener.open(req, None, TIMEOUT)
...
self.self.cookies_handler.save_cookies()

Скрапер как "конечный автомат"

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

#!/usr/bin/python
# -*- coding:  utf8 -*-
#########################################################################
# Scrapper
# author: Sergey Krushinsky
# created: 2009-01-25
#########################################################################
from crawler import UserAgent
from parsers import extract_text
import urllib
import logging
logging.basicConfig(
  level=logging.DEBUG,
  format='%(asctime)s %(levelname)-8s %(message)s',
  datefmt='%Y-%m-%d %H:%M:%S',
)


class Scrapper(object):
  """
  Пример авторизации на сайте 'www.kinokopilka.ru'
  через POST-форму.
  """
  def __init__(self):
      self.crawler = UserAgent(
          #agentname='Mozilla/5.0 (Windows; U; Windows NT 5.1; ru; rv:1.9.0.5) Gecko/2008120122 Firefox/3.0.5',
          ignore_robots=True
      )
    
      # страница с формой
      self.signin_url = 'http://www.kinokopilka.ru/account/signin'
      # адрес, куда отправляется POST-запрос
      self.login_url = 'http://www.kinokopilka.ru/account/login'
      # адрес, куда сервер должен перенаправить клиента
      # после авторизации
      self.expected_redirect = 'http://www.kinokopilka.ru/movies'

      self.form = {
          'login': 'ЛОГИН',
          'password': 'ПАРОЛЬ',
          'remember': 'true',
          'commit_login': 'Войти', # кнопка
      }
    
      # исходное стостояние "конечного автомата"
      # по мере выполнения задач, значением становится очередное
      # состояние.
      self.state = 'signin'
       
       
  def error(self):
      """
      Состояние ошибки. Прекращает выполнение.
      """
      logging.debug('Error state')
      self.state = None

  def completed(self):
      """
      Состояние успешного завершения действий.
      Прекращает выполнение.
      """      
      logging.debug('Completed')
      # TODO: на практике, должно включаться следующее состояние,
      # которое выполняет что-то полезное -- например, поиск
      # новых фильмов
      self.state = None
    
  def login(self):
      """
      Логин при помощи формы
      """
      def _handle_success(url, data, info):
          if (url != self.expected_redirect):
              logging.error('Expected redirect to %s. Got: %s' % \
                        (self.expected_redirect, url))
              self.state = 'error'
          else:
              text = extract_text(data)
              # print 'text: %s' % text
              # В случае успешной авторизации на странице будет приветствие:
              # "Здравствуйте, имя_пользователя", где имя пользователя
              # совпадает со значением 'login' в форме.
              if text.find(self.form['login']) > -1:
                  self.state = 'completed'
              else:
                  logging.debug('No greeting text found')
                  self.state = 'error'
             
      def _handle_failure(url, err):
          logging.error("Could not login: %s: %s" % (url, err))  
          self.state = 'error'
        
      data = urllib.urlencode(self.form)
      self.crawler.visit(self.login_url,
                         on_success=_handle_success,
                         on_failure=_handle_failure,
                         post_data=data) 
      
  def signin(self):
      """
      Получение страницы с формой и всех cookies.
      """
      def _handle_failure(url, err):
          logging.error("Could not signin: %s: %s" % (url, err))
          self.state = 'error'
    
      def _handle_success(url, data, info):
          self.state = 'login'

      self.crawler.visit(self.signin_url,
                         on_success=_handle_success,
                         on_failure=_handle_failure)

  def run(self):
      """
      Главный метод "конечного автомата".
      """
      while self.state:
          logging.info('-' * 50)
          logging.info("Entering '%s' state" % self.state)
          logging.info('-' * 50)
          # поиск функции, чье название соответствует состоянию.
          fn = getattr(self, self.state)
          fn()

if __name__ == '__main__':
  Scrapper().run()

***

Должен признаться, что используя Perl и библиотеку WWW::Mechanize, я написал быстрее, чем за час, скрипт, который делает то же самое. На отладку скрапера, чей код приведен выше, пришлось потратить изрядное количество времени... не буду говорить, сколько, чтобы меня не заподозрили в непрофессионализме. При том, что для краулера имеется набор функциональных тестов. Строчек кода в питоновской версии значительно больше. ...Эй, кто там восхвалял продуктивность Питона?

Другое дело, что в Perl-версии использовалась специализированная библиотека. Справедливости ради, надо отметить, что и в Python-е имеется ее аналог под названием mechanize. Она состоит из довольно большого количества классов, которые встраиваются в urlllib2, расширяя ее возможности, а иногда подменяют существующие там классы. Но если документацию к WWW::Mechanize достаточно бегло просмотреть в течение ровно пяти минут, чтобы начать писать что-то полезное, то с этим хозяйством предстоит разбираться долго. Когда-нибудь я это обязательно сделаю. А пока лучше посмотрю фильм, полученное с "Кинокопилки"...

Краулер своими руками. Часть 10

2009-01-16T00:11:00.007+03:00

Ярлычки на чемодане

В некоторых случаях взаимодействие клиента с сервером невозможно без обмена порциями данных, получивших поэтическое имя cookies -- "печенье". Сценарий таков:

При первом обращении к серверу клиент приходит с пустыми руками. Сервер "видит" это и передает ему HTTP-заголовок "Set-Cookie:данные". В данных может быть уникальный идентификатор или какие-то настройки -- скажем, языковые.
Клиент запоминает эти данные и при повторном обращении снова возвращает их серверу через заголовок "Cookie:данные".
Сервер читает заголовок "Cookie" и распознает клиента.

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

***
OpenDirector, который используется в библиотеке urllib2 по умолчанию, не работает с Cookie. В наборе готовых handler-ов имеется HTTPCookieProcessor, но если не подключить его руками, он не будет задействован. Подключить его можно таким образом:

import cookielib
COOKIEFILE = '...' # путь к файлу, где хранятся cookies

cookie_jar = cookielib.LWPCookieJar()
# загрузить сохраненные cookies, если файл существует
if os.path.isfile(COOKIEFILE):
  cookie_jar.load(COOKIEFILE)

cookie_processor = urllib2.HTTPCookieProcessor(cookie_jar)
opener = urllib2.build_opener(cookie_processor, другие handler-ы)

Теперь библиотека urllib2 будет автоматически читать и передавать назад данные, полученные через cookies.
После выполнения запроса надо сохранить полученные cookies:

req = urllib2.Request(url, None)
...
handle = self.opener.open(req, None, TIMEOUT)
cookie_jar.save(COOKIEFILE)

Все эти операции легко включить в класс UserAgent.

Библиотека cookielib появилась в Python 2.4. До этого использовался класс ClientCookie. О том, как сделать работу с cookies независимой от версий питона, подробно рассказано в статье cookielib and ClientCookie на www.voidspace.org.uk.

Краулер своими руками. Часть 9

2009-01-13T11:13:00.012+03:00

Пора заняться усовершенствованием краулера.

Сжатие контента

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

Клиент должен отправить в запросе заголовок Accept-encoding: алгоритм сжатия(например, gzip).
Если сервер умеет сжимать страницу указанным алгоритмом, он это сделает и вернет заголовок Content-Encoding: алгоритм сжатия.
Клиент проверяет заголовок Content-Encoding и если там указано сжатие, распаковывает данные.

До недавних пор распаковывать налету сжатый контент средствами питоновских библиотек было непросто. Xah Lee даже использовал официальную документацию к модулю gzip как пример неудачной документации. У меня год-два назад не получалось распаковывать сжатый web-контент, как ни старался. Но, видимо, в текущей версии недоработки были исправлены. Сейчас простой рецепт приведен в Dive Into Python.

Метод visit, добавленный в класс UserAgent, представляет собой обертку вокруг open:

...
from StringIO import StringIO
import gzip

class UserAgent(object):
 ...

 def open(self, url, add_headers=None):
     """
     Возвращает file-like object, полученный с заданного адреса.
     В случае ошибки возвращает HTTPError, URLError или IOError.
     """
     logging.info('Opening %s...' % url)
     req = urllib2.Request(url, None)
     if add_headers:
         for k, v in add_headers.iteritems():
             req.add_header(k, v)
     handle = self.opener.open(req, None, TIMEOUT)

     return handle

 def gunzip(self, stream):
     gz = gzip.GzipFile(fileobj=stream)
     return StringIO(gz.read())

 def visit(self, url, add_headers={}, on_success=None, on_failure=None):
     """
     Возвращает последний пройденный URL, объект StringIO и info, полученные
     с заданного адреса через callback-метод on_success.
     В случае ошибки вызывает метод on_failure, передавая туда исклчение.
  
     Фактически, это обертка вокруг open. Важное отличие в том, что
     этот метод автоматически разворачивает сжатый контент.
     """
     add_headers.update({'Accept-encoding': 'gzip'})
     try:
         r = self.open(url, add_headers)
         s = StringIO(r.read())
         info = r.info()
         if info.get('Content-Encoding') == 'gzip':
             logging.debug('Gzipped content received')
             stream = self.gunzip(s)
         else:
             stream = s
         stream.seek(0)
         on_success(r.geturl(), stream, info)
     except Exception, e:
         on_failure(url, e)

старый метод open принимает дополнительные заголовки.
новый метод visit читает данные и "заворачивает" их в StringIO
результат возвращается в callback-функции on_success и on_failure.

Почему используются callback-функции?

В случае успешного запроса, могут понадобиться три результата:

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

Можно, конечно, вернуть список результатов, но по-моему, это не очень красиво и удобно с точки зрения поддержки. Нехорошо когда функция возвращает больше одного значения. И не всегда будут нужны сразу три результата. В последнем случае callback-функция может быть объявлена без указания лишних аргументов:

def handle_success(*args):
ctype = args[2].get('Content-Type')
...

Мне это больше нравится, чем:

results = visit(аргументы)
ctype = results[2].get('Content-Type')

Впрочем, дело вкуса...

Старый метод open теперь снаружи практически не нужен.

Краулер своими руками. Часть 8

2009-01-10T12:16:00.012+03:00

Извлечение текста из HTML

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

Поскольку парсер возвращает DOM-дерево (точнее minidom), для извлечения текста применяется тривиальный рекурсивный обход узлов:

from html5lib import treebuilders

IGNORED_ELEMENTS = ('script')

...

def build_dom(fileobj):
 """
 Читает fileobj и возвращает дерево minidom.
 """
 #HTMLSanitizer дает странные результаты
 #parser = html5lib.HTMLParser(tree=treebuilders.getTreeBuilder('dom'),
 #                             tokenizer=sanitizer.HTMLSanitizer)
 parser = html5lib.HTMLParser(tree=treebuilders.getTreeBuilder('dom'))
 return parser.parse(fileobj)


def extract_text(fileobj):
 """
 Извлекает текст из HTML-страницы. Результат в кодировке utf-8.
 fileobj -- файло-подобный объект.
 """
 def visit(node):
     if node.nodeType == node.TEXT_NODE:
         return node.data.strip()
     elif node.nodeType == node.ELEMENT_NODE \
          and not node.tagName in IGNORED_ELEMENTS \
          and node.hasChildNodes():

         resulttext = ''
         for child in node.childNodes:
             subtext = visit(child)
             if subtext:
                 resulttext = '%s %s' % (resulttext, subtext)
         return resulttext
     return None

 dom = build_dom(fileobj)

 text = visit(dom.getElementsByTagName('body')[0])
 dom.unlink()
 return text

DOM-дерево получается тем же способом, что и при извлечении ссылок. Поэтому я вынес парсинг в отдельную функцию 'build_dom'. Только от Sanitizer-а пришлось отказаться (см. закомментированные строки) -- с ним в результат, помимо чистого текста попадали HTML-теги, уж не знаю, почему.
Поиск начинается с содержимого элемента 'body'.
Если текущий узел -- текстовый (node.TEXT_NODE), возвращается его содержимое.
Если текущий узел -- элемент (node.ELEMENT_NODE), имеющий потомков и не относящийся к числу игнорируемых элементов, потомки проверяются один за другим. Текст, добытый из каждой дочерней ветки, добавляется через пробел к уже собранному тексту.

Получается одна длинная строка.
Вот простейший тест:

class TestTextExtractor(unittest.TestCase):
 def setUp(self):
     self.user_agent = crawler.UserAgent()

 def test_utf8_source(self):
     page_url = 'http://krushinsky.blogspot.com/'
     fileobj = self.user_agent.open(page_url)
     txt = extract_text(fileobj)
     print txt
     self.assertTrue(txt, 'No text was extracted from %s' % page_url)

Результаты выглядят неплохо:

Фото -субъектив четверг, Декабрь 18, 2008 Вторая Табачная Экспедиция Утром отправился в экспедицию за табаком. Шла метель, дороги стали скользкими. Я впервые познакомился с заносами. Ехал предельно осторожно, на поворотах замедлялся и страховался ногами...

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

Краулер своими руками. Часть 7

2009-01-09T12:00:00.010+03:00

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

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

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

HEAD-запрос

Сделать HEAD-запрос в Python-е проще всего средствами httplib. Библиотека urllib2 это тоже позволяет, но придется писать много лишнего кода. Функция, представленная ниже, возвращает код ответа на HTTP-запрос или 0, если соединение не состоялось. Этого достаточно, чтобы узнать, жива ли страница.

from urlparse import urlparse
import httplib

def request_head(url):
parts = urlparse(url)
conn = None
try:
 conn = httplib.HTTPConnection(parts.netloc)
 conn.request('HEAD', parts.path, parts.params)
 return conn.getresponse().status
except:
 return 0
finally:
 if conn:
     conn.close()

И методы, использующие эти запросы:

# если при попытке открыть ссылку возвращается один из этих кодов,
# ссылка считается неработающей
BAD_CODES = (301, 303, 307, 404, 410, 500, 501, 502, 503, 504)

for link in links_iterator(response, is_http_link ):
 status = passed.setdefault(
     link,
     request_head(link)
 )               
                
 if not status or status in BAD_CODES:
     print '%s --> %s: %s ' % (url, hostname, status)
...

Выглядит неплохо. Но не работает. Корневая страница открывается, как положено, из нее извлекаются новые ссылки. После чего скрипт благополучно завершает свою работу. Обхода вглубь не происходит.

Проблема в том, что после парсинга страницы внутри callback-метода test_links из файло-подобного объекта (file-like object), который возвращает метод opener.open(), уже невозможно ничего прочесть. Первая идея, приходящая в голову: применить метод файла seek(0), чтобы вернуться в начало. Однако, вызов response.seek(0) ни к чему ни приводит, хотя Python не ругается, как непременно сделала бы Java.

Утка или не утка?

В динамических языках любят идиому: "Если нечто ходит, как утка -- значит, это утка". Именно так устроено в питоне все, что называется "file-like object", в том числе, результат urllib2.Request.open(). Однако, метод seek не работает. Если задуматься, нет ничего удивительного в том, что сокет работает иначе, чем файл. Другой вопрос: хорошо это или плохо когда нечто, что называется уткой, ходит, как положено утке, но отказывается нести яйца -- не лучше бы ее тогда назвать как-то иначе? Эта тема уже обсужалась в списке рассылки python-bugs-list. Там же был предложен рецепт: как все-таки заставить файло-подобный объект одноразового использования перематываться. Для этого достаточно прочесть данные из потока и "завернуть" их в StringIO, чтобы получить своего рода виртуальный файл.

import StringIO

response = self.open(url)
data = StringIO.StringIO(response.read())

Большая стирка

Теперь seek работает, но вместе с response исчезли и его дополнительные методы, такие как info() и geturl(). Заголовки HTTP-ответа, которые можно было получить через response.info(), уже недоступны вне traverse, поскольку в функцию обратного вызова on_success передается другой объект -- StringIO. Придется изменить функцию обратного вызова, добавив туда новый аргумент:

on_success(url, response.info(), data)

В модуль parsers.py тоже надо внести изменения. Поскольку теперь мы не можем получить базовый адрес для преобразования относительных адресов в абсолютные, используя response.geturl(), придется передавать этот адрес как аргумент:

def links_iterator(base, response, link_filter=None):
 """
 Итератор по ссылкам, найденным в документе.
 Аргументы:
 base     -- URL страницы, с которой делается запрос
 response -- поток ввода
 filter   -- функция, которая может быть использована для
             отбора нужных ссылок. На входе: url, на выходе
             True, если проверка прошла, иначе -- False
 Если параметр 'filter' не задан, итератор возвращает
 все найденные ссылки.
 """
 ...

Новая версия UserAgent.traverse() выглядит так:

def traverse(self, start_url, links_filter=None, on_success=None, on_failure=None):
 """
 Обход сети.

 start_url    -- исходный адрес
 links_filter -- функция для оценки очередной ссылки, полученной со
                 страницы. При результате False не включается в очередь.
 on_success   -- callback-функция, которая вызывается при успешном
                 открытии страницы с аргументами (url, response)
 on_failure   -- callback-функция, которая вызывается в случае неудачи
                 с аргументами: (url, exception)
 """
 queue = [ start_url ]
 passed = set()
 last_url = None
 while queue:
     logging.debug('Queue size: %d, Passed: %d ' % \
                   (len(queue), len(passed)) )
     url = queue.pop(0)
     try:
         if last_url:
             r = self.open(url, {'Referer': last_url})
         else:
             r = self.open(url)
         data = StringIO(r.read())
         logging.debug('Success')
         if on_success:
             on_success(url, r.info(), data)
         # извлекаем со страницы новые ссылки и добавляем их в очередь
         data.seek(0)
         new_links = [
             u for u in links_iterator(
                 url,
                 data,
                 lambda u: False if (u in passed or u in queue) \
                                 else links_filter(u)
             )
         ]             
         queue.extend(new_links)
         logging.debug('Added %d new links' % len(new_links))
   
     except Exception, ex:
         logging.warn('Failure: %s' % ex)
         if on_failure:
             on_failure(url, ex)
     finally:
         last_url = url
         passed.add(url)
  
 logging.debug('Crawling completed. %d pages passed' % len(passed))

Помимо "заворачивания" результата self.open в StringIO и изменения API callback-функции on_success, есть и другие улучшения:

В очередной запрос, начиная со второго, добавляется заголовок 'Referer' для имитации поведения браузера. Некорые сайты проверяют его.
При извлечении ссылок со страницы вначале проверяется, не пройден ли уже адрес и нет ли его в очереди заданий и только потом, если эти условия выполняются, вызывается функция link_filter. Раньше проверка происходила в другом порядке. Поскольку неизвестно заранее, сколько ресурсов потребуются на фильтрацию, лучше сразу отсекать лишнее и не дергать link_filter лишний раз.
Добавился блок finally.

Краулер своими руками. Часть 6

2009-01-05T13:30:00.008+03:00

Нормализация ссылок

Присмотревшись к логам, я заметил странные адреса, например:

INFO Opening http://pi-code.blogspot.com/2008/12/\"http://pi-code.blogspot.com/\"

Дешевый способ преобразовывать относительные адреса в абсолютные:

u = urlparse.urldefrag( # удаление фрагмента
 urlparse.urljoin(base, tag['href'], allow_fragments=False)
)[0].encode('ascii')

явно ненадежен. Пришлось писать новый вариант:

def normalize_url(base, url):
 """
 Нормализация URL. Используется для преобразования относительных адресов
 в абсолютные.

 base -- домен (напр. 'taxonomist.tripod.com'), вторая часть результата
         urlparse.urlsplit result
 url  -- исходный URL, может быть относительным.
 """
 parts = urlparse.urlsplit(url)
 defaults = ('http', base, '/', parts[3], parts[4])
 norm = [ p if p else defaults[i]
         for i, p in enumerate(parts) ]
 url = urlparse.urlunsplit(norm)
 url = urlparse.urldefrag(url)[0] # удаление фрагмента
 url = url.encode('ascii') # перекодировка из уникода в ascii
 return url


def links_iterator(response, link_filter=None):
 """
 Итератор по ссылкам, найденным в документе.
 Аргументы:
 response -- file-like object, возвращаемый
             при открытии страницы библиотекой urllib2
 filter   -- функция, которая может быть использована для
             отбора нужных ссылок. На входе: url, на выходе
             True, если проверка прошла, иначе -- False
 Если параметр 'filter' не задан, итератор возвращает
 все найденные ссылки.
 """
 if not link_filter:
     link_filter = lambda x: True
 base = response.geturl()

 parser = html5lib.HTMLParser(
     tree=treebuilders.getTreeBuilder('dom'),
     tokenizer=sanitizer.HTMLSanitizer)
 dom = parser.parse(response)
 for elem in dom.getElementsByTagName('a'):
     if elem.hasAttribute('href'):
         href = elem.getAttribute('href')
         u = normalize_url(base, href)
         if link_filter(u):
             yield u

 dom.unlink()

Теперь относительные адреса стали преобразовываться в абсолютные по-человечески.

"Минздрав предупреждает"

Еще один неприятный момент: при импорте html5lib Python 2.6 выдавал DeprecationWarning:

C:\Python26\lib\site-packages\html5lib-0.11.1-py2.6.egg\html5lib\
inputstream.py:367:DeprecationWarning: object.__init__() takes no parameters

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

from html5lib import treebuilders, sanitizer
import warnings
warnings.simplefilter("ignore",DeprecationWarning)

Краулер своими руками. Часть 5

2009-01-04T16:38:00.009+03:00

В 2007 году, когда я писал краулера на Питоне для поискового проекта, именно отсутствие надежного HTML-парсера заставила меня пересесть на Perl. Ни SGMLParser ни HTMLParser из стандартных библиотек не в состоянии справиться со страницами, выходящими за рамки академического гипертекста. Альтернативная библиотека BeautifulSoup, вроде бы хорошо себя зарекомендовавшая, оказалась, как выяснилось в предыдущей заметке, ненадежной.

Прежде чем ставить вердикт, что Python -- неподходящий инструмент для написания простейшего краулера, дадим шанс еще одной библиотеке: html5lib. Прежде всего, добавим в модуль test_parsers новый тест:

class TestLinks(unittest.TestCase):
 ...
 def test_blogspot(self):
     page_url = 'http://krushinsky.blogspot.com/'
     fileobj = self.user_agent.open(page_url)
     test_link = 'http://krushinsky.blogspot.com/2007_12_01_archive.html'
  
     links = [ u for u in links_iterator(fileobj, lambda u: u == test_link) ]
     self.assertTrue(len(links), "Link '%s' is absent" % test_link) 
 ...

Первой версии функции links_iterator не удавалось пройти этот тест, поскольку парсер BeautifulSoup не справлялся со страницей гугловского блога.

Альтернативная версия links_iterator опирается на парсер из библиотеки html5lib.

import urlparse
import html5lib
from html5lib import treebuilders, sanitizer

def links_iterator(response, link_filter=None):
   """
   Итератор по ссылкам, найденным в документе.
   Аргументы:
   response -- file-like object, возвращаемый
               при открытии страницы библиотекой urllib2
   filter   -- функция, которая может быть использована для
               отбора нужных ссылок. На входе: url, на выходе
               True, если проверка прошла, иначе -- False
   Если параметр 'filter' не задан, итератор возвращает
   все найденные ссылки.
   """
   if not link_filter:
       link_filter = lambda x: True
   base = response.geturl()
  
   parser = html5lib.HTMLParser(
       tree=treebuilders.getTreeBuilder('dom'),
       tokenizer=sanitizer.HTMLSanitizer)
   dom = parser.parse(response)
   for elem in dom.getElementsByTagName('a'):
       if elem.hasAttribute('href'):
           href = elem.getAttribute('href')
           u = urlparse.urldefrag( # удаление фрагмента
               urlparse.urljoin(base, href, allow_fragments=False)
           )[0].encode('ascii')
           if link_filter(u):
               yield u  

   dom.unlink()

html5lib.HTMLParser способен возвращать разного типа деревья: minidom, elementTree и даже злополучный BeautifulSoup. Я начал с minidom-а как с простейшего варианта. Поэтому в конструкторе парсера присутствует аргумент: tree=treebuilders.getTreeBuilder('dom').
Второй аргумент: tokenizer=sanitizer.HTMLSanitizer предписывает использовать стандартный класс для очистки HTML от двусмысленных элементов и CSS-объявлений.
Чтобы получить все теги "a" применяется стандартный методы DOM: getElementsByTagName.

Тест test_blogspot выполняется. Ура! Удаляем BeautifulSoup, работаем с html5lib и продолжаем писать краулер на Питоне.

Отмечу только, что установка html5lib версии 0.11.1 из исходных кодов не проходит гладко -- по крайней мере, в среде Windows. Стандартная команда python setup.py install не перенесла библиотечные файлы в директорию site-packages, а оставила их там, где лежали исходники. Пришлось копировать их вручную.

Краулер своими руками. Часть 4

2009-01-04T09:57:00.013+03:00

Обход сети

Ниже представлен метод краулера (UserAgent) traverse, позволяющий обходить сеть.

def traverse(self, start_url, links_filter=None, on_success=None, on_failure=None):
  """
  Обход сети.

  start_url    -- исходный адрес
  links_filter -- функция для оценки очередной ссылки, полученной со
                  страницы. При результате False не включается в очередь.
  on_success   -- callback-функция, которая вызывается при успешном
                  открытии страницы с аргументами (url, response)
  on_failure   -- callback-функция, которая вызывается в случае неудачи
                  с аргументами: (url, exception)
  """
  queue = [ start_url ]
  passed = set()
  last_url = None
  while queue:
      logging.debug('Queue size: %d, Passed: %d ' % \
                    (len(queue), len(passed)) )
      url = queue.pop(0)
      try:
          if last_url:
              response = self.open(url, {'Referer': last_url})
          else:
              response = self.open(url)
          if on_success:
              on_success(url, response)
          logging.debug('Success')
          # извлекаем со страницы новые ссылки и добавляем их в очередь
          new_links = [
              u for u in links_iterator(response, links_filter)
                if not u in passed and not u in queue ]              
          queue.extend(new_links)
      except Exception, ex:
          logging.warn('Failure: %s' % ex)
          if on_failure:
              on_failure(url, ex)
      last_url = url
      passed.add(url)
  logging.debug('Crawling completed.')

Задания снимаются из "головы" очереди (queue). Сперва туда помещается исходный адрес. Затем она пополняется ссылками, извлеченными с очередной страницы.
Открыв очередную страницу, краулер вызывает callback-функцию on_success, передавая туда адрес, а также файло-подобный (file-like) объект, из которого можно прочесть ее содержание. Если открыть страницу не удается, вызывается другой метод обратного вызова: on_error.
Из текущей страницы извлекаются ссылки и помещаются в конец очереди заданий. Для их отбора применяется внешняя функция links_filter. Как и было обещано в предыдущей части, сам UserAgent не принимает решений относительно дальнейшего маршрута. Кроме того, выражение list comprehension построено таким образом, что игнорируются как пройденные ссылки, так и те, что уже имеются в очереди (...if not u in passed and not u in queue).
Обход завершается когда заданий не остается.

В набор тестов TestUserAgent добавляется новая функция:

def test_traverse(self):
  """
  Проверяет функцию обхода сети.
  """
  page_url = 'http://pi-code.blogspot.com'
  hostname = urlsplit(page_url).hostname

  def is_valid_link(u):
      url_parts = urlsplit(u)
      return False if url_parts.hostname != hostname \
             else False if url_parts[0] != 'http' \
                  else True
    
  passed = [] # успешно пройденные адреса
  errors = [] # адреса, которые не удалось пройти

  def on_success(url, response):
      passed.append(url)
    
  def on_failure(url, error):
      errors.append(url)

  self.crawler.traverse(
      page_url,
      links_filter=is_valid_link,
      on_success=on_success,
      on_failure=on_failure)

  self.assert_(passed > 1, 'No nodes were passed')  

Почему не генератор?

Я предпочел более традиционный подход с функциями обратного вызова. Можно было бы сделать traverse генератором по образцу стандартной функции для обхода директорий os.walk. Но тогда было бы сложнее с обработкой ошибок. Если в генераторе возникнет исключение, цикл остановится. Как сообщить "наверх" о том, что страницу не удалось открыть, не останавливая паука?

В os.walk для обработки ошибок может быть использована callback-функция onerror. Если она не задана в качестве аргумента, ошибки игнорируются. Но это довольно некрасиво с точки зрения архитектуры. Любой генератор -- своего рода callback наизнанку, альтернатива функциям обратного вызова. Одновременное их использование явно избыточно.

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

Проверка ссылок

Пора сделать что-нибудь полезное. Попробуем приспособить краулер для решения довольно распространенной задачи: проверки "мертвых" внутренних ссылок на сайте.

Игнорирование robots.txt

Для тестирования сайта учитывать ограничения robots.txt ни к чему. В конструктор класса UserAgent стоит добавить необязательный параметр ignore_robots со значением False по умолчанию. При значении True, opener будет создаваться без RobotsHTTPHandler (cм. "Краулер своими руками, часть 2"):

class UserAgent(object):
def __init__(self,
            agentname=DEFAULT_AGENTNAME,
            email=DEFAULT_EMAIL,
            new_headers=None,
            ignore_robots=False):

   ...
   if ignore_robots:
       self.opener = urllib2.build_opener()
   else:
       self.opener = urllib2.build_opener(
           RobotsHTTPHandler(self.agentname))
   ...

Любопытно, что попытка использовать метод self.opener.add_handler(RobotsHTTPHandler) ни к чему ни приводит.

Скрипт для проверки "мертвых" ссылок совсем короткий:

#!/usr/bin/python
# -*- coding: cp1251 -*-
#########################################################################
# Tool for testing site links
# author: Sergey Krushinsky
# created: 2008-12-28
#########################################################################

from urlparse import urlunparse, urlsplit
from crawler import UserAgent
import logging
logging.basicConfig(
  level=logging.DEBUG,
  format='%(asctime)s %(levelname)-8s %(message)s',
  datefmt='%Y-%m-%d %H:%M:%S',
  filename='%s.log' % __name__,
  filemode='w'
)

# имитируем браузер
AGENT_NAME = "Mozilla/5.0 (Windows; U; Windows NT 5.1; ru; rv:1.9.0.5) Gecko/2008120122 Firefox/3.0.5"

def is_valid_link(u, hostname):
  """
  Фильтрация ссылок.
  """
  logging.debug("Validating link: '%s'" % u)
  url_parts = urlsplit(u)
  return False if url_parts.hostname != hostname \
         else False if url_parts[0] != 'http' \
              else True

def main(hostname):
  """
  Обход хоста с целью проверки на наличие мертвых ссылок.
  """
  def on_failure(url, error):
      """Вывод ошибки"""
      print "%s: %s" % (url, error)

  ua = UserAgent(agentname=AGENT_NAME, ignore_robots=True)
  root = urlunparse(('http', hostname, '/', '', '', ''))
  ua.traverse(
      root,
      links_filter=lambda u: is_valid_link(u, hostname),
      on_failure=on_failure)


if __name__ == '__main__':
  import sys
  if len(sys.argv) < 2:       
      print 'Usage: python deadlinks.py HOSTNAME'       
      sys.exit(1)      
  main(sys.argv[1])

Первым делом я напустил этот скрипт на собственный блог krushinsky.blogspot.com. И очень удивился когда увидел, что краулер прошел всего 7 страниц -- это в блоге, который ведется с лета 2007 года. В число ссылок, извлеченных со страницы, не попала ни одна архивная.

Как выяснилось в ходе тестов, часть ссылок BeautifulSoup просто молча игнорировал! Когда я попытался вместо того, чтобы использовать SoupStrainer (см. часть 3), парсить весь HTML, а потом методом find_all искать нужные теги, как описано в документации, парсер просто начал умирать. Гугловский шаблон оказался ему не по зубам.

Краулер своими руками. Часть 3

2008-12-31T14:32:00.011+03:00

Диспетчер и исполнитель

UserAgent из предыдущей части не обладает интеллектом, его роль сводится к тому, чтобы открыть web-страницу, читать которую будет кто-то другой. Задания он тоже получает извне. Нетрудно добавить функцию, которая будет получать не один адрес, а список. Но принципиально это ничего не изменит. Гораздо интереснее будет, если программа сможет самостоятельно прокладывать свой маршрут через web-узлы, извлекая очередную порцию "пищи" с каждой пройденной страницы.

Cам UserAgent не должен этого делать. Во-первых, существует много ситуаций, с которыми он не в состоянии справиться Сайты, где страницы генерируются динамически, могут предоставлять почти бесконечное число потенциальных маршрутов. Взять к примеру календарики, где каждый месяц и год -- ссылки на соседние месяц и год. Там можно застрять навсегда. Мало того, бывают специально созданные "паучьи ловушки". Так что, нужен механизм, наделенный эвристикой для оценки перспективности того или иного маршрута. Ходить куда попало, по всем подряд адресам нельзя.

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

Извлечение ссылок

Поскольку задач, связанных с разбором текста, предстоит решить немало, я создал в корне приложения отдельный модуль под названием parsers.py, куда поместил функцию-итератор links_iterator.
Чтобы она работала, необходимо установить популярную среди питонистов библиотеку для разбора HTML под названием BeautifulSoup.

import urlparse
from BeautifulSoup import SoupStrainer, BeautifulSoup
import logging

def links_iterator(response, link_filter=None):
   """lm
   Итератор по ссылкам, найденным в документе.
   Аргументы:
   response -- file-like object, возвращаемый
               при открытии страницы библиотекой urllib2
   filter   -- функция, которая может быть использована для
               отбора нужных ссылок. На входе: url, на выходе
               True, если проверка прошла, иначе -- False
   Если параметр 'filter' не задан, итератор возвращает
   все найденные ссылки.
   """
   if not link_filter:
       link_filter = lambda x: True
   base = response.geturl()
   link_tags = SoupStrainer('a')
   for tag in BeautifulSoup(response, parseOnlyThese=link_tags):
       if ('href' in dict(tag.attrs)):
           u = urlparse.urldefrag( # удаление фрагмента
               urlparse.urljoin(base, tag['href'], allow_fragments=False)
           )[0].encode('ascii')
           if link_filter(u):
               yield u

Обычно при работе с BeautifulSoup (как и с большинством других подобных библиотек) необходимо получить из исходного документа (в нашем случае HTML) дерево, из которого потом извлекаются узлы. Но для нашей задачи есть более простой способ: вместо того, чтобы заставлять парсер строить все дерево, сразу же сказать, какого типа узлы нас интересуют. Делается это через объект SoupStrainer.

Unicode, возвращаемый парсером, не подходит. Если передать уникодную строку методу RobotParser.can_fetch() возникнет KeyError (это известная недоработка, см. http://bugs.python.org/issue1712522). Поэтому на последнем этапе строка перекодируется в ascii.

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

Ниже представлены тесты, позволяющие "обкатать" API и проверить, все ли правильно работает.

import unittest
from urlparse import urlsplit

parent_dir = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
src_dir = os.path.join(parent_dir, 'src')
sys.path.append(src_dir)

import crawler
from parsers import links_iterator

class TestLinks(unittest.TestCase):
def setUp(self):
  self.user_agent = crawler.UserAgent()
  self.urls = (
      'http://www.google.com',
      'http://spintongues.msk.ru/',
      'http://www.crummy.com/software/BeautifulSoup/documentation.html',
      'http://pi-code.blogspot.com',
      'http://krushinsky.blogspot.com'
  )

def test_alllinks(self):
  """
  Общая проверка.
  """
  links = []
  for page_url in self.urls:
      fileobj = self.user_agent.open(page_url)
      links.extend([ u for u in links_iterator(fileobj) ])

  self.assertTrue(links, 'No links from %d pages' % len(self.urls))

def test_inbound_links(self):
  """
  Проверка фильтра.
  Удается ли извлечь только внутренние ссылки?
  """
  outbound = [] # список внешних ссылок, должен остаться пустым
  for page_url in self.urls:
      hostname = urlsplit(page_url).hostname
      fileobj = self.user_agent.open(page_url)

      def is_inbound(u):
          # является ли ссылка внутренней?
          h = urlsplit(u)[1]
          return h == hostname

      links = [ u for u in links_iterator(fileobj, is_inbound) ]
      # если среди результатов имеются внешние ссылки, они помещаются
      # в массив outbound
      outbound.extend(
          [ u for u in links if urlsplit(u).hostname != hostname ]
      )
      for link in links:
          print link

  self.assertFalse(outbound, 'Unexpected outbound links: %s' % outbound)


def test_outbound_links(self):
  """
  То же самое, что test_inbound_links, но тут отбираются только внешние
  ссылки.
  """
  inbound = [] # список внутренних ссылок, должен остаться пустым
  for page_url in self.urls:
      hostname = urlsplit(page_url).hostname
      fileobj = self.user_agent.open(page_url)

      def is_outbound(u):
          # является ли ссылка внешней?
          h = urlsplit(u).hostname
          return h == hostname

      links = [ u for u in links_iterator(fileobj, is_outbound) ]
      inbound.extend(
          [ u for u in links if urlsplit(u).hostname != hostname ]
      )
      for link in links:
          print link

  self.assertFalse(inbound, 'Unexpected inbound links: %s' % inbound)


if __name__ == '__main__':
  module = __import__(__name__)
  suite = unittest.TestLoader().loadTestsFromModule(__import__(__name__))
  unittest.TextTestRunner(verbosity=2).run(suite)

Краулер своими руками. Часть 2

2008-12-29T11:30:00.021+03:00

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

Обучение агента

Python предлагает много средств, позволяющих соорудить web-агента.

socket -- низкоуровневый API к базовым сетевым службам операционной системы;
httplib -- библиотека более высокого уровня, которую используют сейчас главным обазом в случаях, когда нужно или хочется полностью все контролировать;
urllib -- высокоуровневая библиотека, позволяющая быстро получить результат, но не очень гибкая;
urllib2 -- современный Java-образный фреймворк, главный недостаток которого -- плохая документированность при некоторой запутанности;

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

Вот что получилось

#!/usr/bin/python
# -*- coding: cp1251 -*-
#########################################################################
# Main UserAgent class
# author: Sergey Krushinsky
# created: 2008-12-28
#########################################################################
import sys


import urllib2
from copy import copy
from robotparser import RobotFileParser
from urlparse import urlunsplit, urlsplit

# Конфигурация по умолчанию
# TODO: вынести в конфигурационный файл
TIMEOUT = 5 # максимальное время ожидания ответа в секундах

# HTTP-заголовки, которые используются по умолчанию и могут быть
# переопределены в конструкторе UserAgent
DEFAULT_HEADERS = {
'Accept'           : 'text/html, text/plain',
'Accept-Charset'   : 'windows-1251, koi8-r, UTF-8, iso-8859-1, US-ASCII',
'Content-Language' : 'ru,en',
}
# Имя для HTTP-заголовка 'User-Agent' и проверки robots.txt
DEFAULT_AGENTNAME = 'Test/1.0'
# email автора; при пустом значении не используется
DEFAULT_EMAIL = ''


class RobotsHTTPHandler(urllib2.HTTPHandler):
"""
Класс, который передается специализированному экземпляру
OpenDirector.
Прежде, чем произвести запрос, проверяет, нет ли запрета
на посещение ресурса файлом robots.txt.

Аргументы:
agentname -- имя краулера
"""
# TODO: кэшировать один раз полученные данные, чтобы при повторных
#       запросах к одному хосту не делать лишних запросов.
def __init__(self, agentname, *args, **kwargs):
 urllib2.HTTPHandler.__init__(self, *args, **kwargs)
 self.agentname = agentname

def http_open(self, request):
 """
 перегрузка родительского метода. Если в корне сервера
 имеется robots.txt c запретом на посещение заданного
 ресурса, генерируется исключение RuntimeError.

 request -- экземпляр urllib2.Request
 """
 url = request.get_full_url()
 host = urlsplit(url)[1]
 robots_url = urlunsplit(('http', host, '/robots.txt', '', ''))
 rp = RobotFileParser(robots_url)
 rp.read()
 if not rp.can_fetch(self.agentname, url):
     # запрещено
     raise RuntimeError('Forbidden by robots.txt')
 # не запрещено, вызываем функцию
 return urllib2.HTTPHandler.http_open(self, request)

class UserAgent(object):
"""
Краулер.

Именованные аргументы конструктора и значения по умолчанию:
name -- имя ('Test/1.0')
email -- адрес разработчика (пустая строка)
headers -- словарь HTTP-заголовков (DEFAULT_HEADERS)
"""
def __init__(self,
          agentname=DEFAULT_AGENTNAME,
          email=DEFAULT_EMAIL,
          new_headers={}):

 self.agentname = agentname
 self.email = email 
 # для соединений будет использоваться OpenDirector,
 # лояльный к robots.txt.
 self.opener = urllib2.build_opener(
     RobotsHTTPHandler(self.agentname),
 )
 # переопределение заголовков по умолчанию
 headers = copy(DEFAULT_HEADERS)
 headers.update(new_headers) 
 opener_headers = [ (k, v) for k, v in headers.iteritems() ]
 opener_headers.append(('User-Agent', self.agentname))
 # если email не задан, HTTP-заголовок 'From' не нужен
 if self.email:
     opener_headers.append(('From', self.email))

 self.opener.addheaders = opener_headers

def open(self, url):
 """
 Возвращает file-like object, полученный с заданного адреса.
 В случае ошибки возвращает HTTPError, URLError или IOError.
 """
 return self.opener.open(url, None, TIMEOUT)

Новый директор

Ключом к использованию urllib2 является класс OpenDirector, отвечающий за всю последовательность операций по открытию страницы. Требуется что-нибудь не совсем стандартное? Назначьте нового директора.

За каждую операцию, управляемую "директором", отвечает отдельный исполнитель -- handler. За обработку редиректов -- HTTPRedirectHandler, за коммуникацию через proxy -- ProxyHandler, за открытие защищенного соединения -- HTTPSHandler и т.д. Существует иерархия handler-ов. Некоторые используются по умолчанию, другие можно при желании подключить к директору, третьи придется доработать. Вся эта бюрократическая структура сильно напоминает то, что делается в библиотеках языка Java.

OpenDirector удобно создавать вспомогательным методом build_opener(набор handler-ов). После этого можно вызвать метод urllib2.install_opener(), чтобы новый директор применялся в библиотеке по умолчанию (тогда urllib2.Request.open() будет использовать только его). Однако, в этом случае есть риск неприятных побочных эффектов. Что, если понадобится одновременно запустить два краулера с разными конфигурациями?

Правила вежливости

В нашем случае требуется handler, который прежде, чем открывает страницу, проверяет, не запрещено ли ее посещение файлом robots.txt (если таковой имеется). Этой цели служит класс RobotsHTTPHandler -- наследник стандартного urllib2.HTTPHandler.

если robots.txt найден, он проверяется при помощи стандатного класса RobotFileParser. В случае запрета генерируется RuntimeError. В противном случае страница открывается стандартным родительским методом
если robots.txt не найден, страница открывается стандартным родительским методом.

Тут есть одна тонкость, не освещенная в документации. RobotsFileParser может быть создан конструктором без аргументов. Задать адрес файла robots.txt позволяет метод set_url(). Например, set_url('http://yandex.ru/robots.txt'). Такое API склоняет к мысли, что можно один раз создать экземпляр RobotsParser, а потом использовать его для разных хостов. Как выяснилось, это не работает. Попробуйте:

>>> rp = RobotFileParser()
>>> rp.set_url('http://spintongues.msk.ru/robots.txt')
>>> rp.read()
>>> rp.can_fetch('Test/1.0', 'http://spintongues.msk.ru/kafka2.html')
True
>>> rp.set_url('http://yandex.ru/robots.txt')
>>> rp.read()
>>> rp.can_fetch('Test/1.0', 'http://yandex.ru/')
True
>>> rp = rp = RobotFileParser('http://yandex.ru/robots.txt')
>>> rp.read()
>>> rp.can_fetch('Test/1.0', 'http://yandex.ru/')
False
>>>

В первый раз -- когда был задан и прочтен robots.url с Яндекса, метод can_fetch вернул True. Во второй раз -- после создания нового экземпляра с тем же яндексовским адресом -- False.

Поэтому приходится при каждом новом запросе создавать новый экземпляр RobotsFileParser, что увы, не способствует производительности. Зато тест 'test_robotrules' проходит.

Редиректы

Вначале я думал, что нужно будет создавать еще и собственный обработчик перенаправлений -- в духе примера из "Dive Into Python" -- чтобы ограничить максимальное число редиректов, скажем, до 7. В документации к urllib2 об этом ничего не сказано. Как выяснилось, в классе HTTPredirectHandler это уже предусмотрено: имеется недокументированный атрибут max_redirections со значением 10. Ну, пускай будет столько...

Заголовки

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

Заголовок 'From' в примере пустой. Я не хочу помещать туда собственный почтовый адрес. Но любой вежливый краулер обязан предоставлять email создателя, куда возмущенный веб-мастер мог бы отправить гневное послание. А еще лучше -- адрес домашней страницы с подробной информацией о краулере, исходным кодом и подарками. Краулеры, не предоставляющие такой информации, обычно попадают в разряд подозрительных.

Первое испытание

В предыдущей части приведен код unittest-ов. Результат тестов -- на картинке вверху страницы.

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

if __name__ == '__main__':
   # вызов из консоли
   if len(sys.argv) < 2:
       print "Usage: python crawler.py URL"
       sys.exit(1)
      
   import socket # требуется исключительно длч отлавливания socket.error
  
   ua = UserAgent()
   try:
       resp = ua.open(sys.argv[1])
   except RuntimeError, e:
       # ошибка в ходе выполнения, в т.ч. запрет в robots.txt
       sys.stderr.write('Error: %s\n' % e)
       sys.exit(4)
  
   except urllib2.HTTPError, e:
       # сервер вернул код ошибки
       sys.stderr.write('Error: %s\n' % e)
       sys.stderr.write('Server error document:\n')
       sys.stderr.write(e.read())
       sys.exit(2)
   except urllib2.URLError, e:
       # другие ошибки
       sys.stderr.write('Error: %s\n' % e)
       sys.exit(3)

   # чтение данных
   bytes_read = long()
   while 1:
       try:
           data = resp.read(1024)
       except socket.error, e:
           sys.stderr.write('Error reading data: %s' % e)
           sys.exit(5)

       if not len(data):
           break
       bytes_read += len(data)
      
   # проверка длины полученных данных; работает только если
   # в ответном заголовке присутствует поле 'Content-Length'       
   content_length = long(resp.info().get('Content-Length', 0))           
   if content_length and (bytes_read != content_length):
       print "Expected %d bytes, but read %d bytes" % \
             (content_length, bytes_read)
       sys.exit(6)
      
   # все в порядке; выводим данные
   sys.stdout.write(data)   

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

(Продолжение следует...)

Краулер своими руками. Часть 1

2008-12-29T01:17:00.023+03:00

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

Бумажный кораблик

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

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

import urllib
tmpfile, headers = urllib.urlretrieve('http://www.python.org/')

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

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

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

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

Вот предварительные требования к программе:

Переносимость. Модуль должен работать одинаково из под разных операционных систем и по возможности ограничиваться стандартными библиотеками.
Компактность. Очень не хочется городить очередной фреймворк, который к концу проекта будет провисать под собственным весом. Достаточно того, что urllib2 -- скорее не библиотека, а Java-образный фреймворк.
Вежливость. Вежливыми принято называть краулеры, лояльные к 'robots.txt'. Так называется специальный файл, где веб-мастера объявляют правила поведения пауков на сайте. Скажем: таком-то краулеру не ходить в раздел '/news', никому не ходить в /weather/... Пример можно увидеть прямо через браузер: http://tv.yandex.ru/robots.txt .

Задача краулера -- попытаться открыть страницу, после чего либо сообщить "наверх" об ошибке либо вернуть полученные данные и как можно быстрее двигаться дальше. Он не должен заниматься ничем посторонним. Сохранение данных, извлечение текста из HTML, прокладывание дальнейшего маршрута и даже проверка заголовков ответа -- все это не его дело.

Начнем, как водится, с конца

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

python crawler.py URL

В ответ краулер должен вернуть содержание документа либо выдать сообщение об ошибке и прекратить работу с кодом выхода больше нуля.

Какого рода могут быть ошибки? Их можно свести к нескольким категориям:

Соединение не состоялось. Например, кошка поиграла с сетевым кабелем и сети не стало. Или вместо http:// задано реез://. Или сервер долго не отвечает.
Соединение состоялось, но посещение страницы запрещено robots.txt
Соединение состоялось, но сервер вместо запрошенных данных вернул код ошибки (401 -- "требуется авторизация", 404 -- "документ не найден", 500 -- "внутренняя ошибка" и т.д ).
Вместо целой страницы пришла только ее часть

Сразу же установим несколько ограничений -- по крайней мере, для первой версии краулера:

используется только HTTP-протокол
интересны только html -документы и простой текст

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

#!/usr/bin/python
# -*- coding utf8 -*-
#########################################################################
# UserAgent tests
# author: Sergey Krushinsky
# created: 2008-12-28
#########################################################################
import sys, os
import urllib2
import unittest
import crawler

class TestUserAgent(unittest.TestCase):
   def setUp(self):
       self.crawler = crawler.UserAgent()
 
   def tearDown(self):
       pass

   def test_default_agentname(self):
       """
       Если имя не задано в конструкторе, он должно соответствовать
       имени по умолчанию.
       """      
       msg = "Default agent name should be '%s', not '%s'" % \
           (crawler.DEFAULT_AGENTNAME, self.crawler.agentname)
       self.assertEqual(self.crawler.agentname, crawler.DEFAULT_AGENTNAME, msg)

   def test_custom_agentname(self):
       """
       Если имя задано в конструкторе, оно должно таким и быть.
       """
       name = 'Other Test/2.0'
       c = crawler.UserAgent(agentname=name)
       self.assertEqual(
           c.agentname,
           name,
           "Custom agent name should be '%s', not '%s'" % \
           (name, c.agentname))

   def test_htmlget(self):
       """
       Краулер открывает заданный ресурс и в заголовке ответа возвращается
       text/html.
       """
       resp = self.crawler.open('http://spintongues.msk.ru/kafka2.html')
       ctype = resp.info().get('Content-Type')
       # В заголовке может быть что-нибудь вроде 'text/html; charset=windows-1251',
       # поэтому обычное сравнение не подходит.
       self.assert_(ctype.find('text/html') != -1, 'Not text/html')

   def test_urlerror(self):
       """
       Если задан неверный адрес, должны генерироваться ошибка IOError.
       """
       self.assertRaises(IOError, self.crawler.open, 'http://foo/bar/buz/a765')
             
   def test_robotrules(self):
       """
       Если выяснилось, что robots.txt запрещает посещение адреса,
       должно генерироваться исключение.
       """
       # Яндекс, как известно, не любит пауков
       self.assertRaises(
           RuntimeError,
           self.crawler.open,
           'http://yandex.ru/')
 

if __name__ == '__main__':
   suite = unittest.TestLoader().loadTestsFromTestCase(TestUserAgent)
   unittest.TextTestRunner(verbosity=2).run(suite)

Пояснения к тестам:

существует пакет по имени crawler и в нем -- класс UserAgent. Почему 'UserAgent', а не 'Crawler' или 'Spider'? Потому что последние два имени скорее ассоциируются с обходом сети. Позже мы решим и эту задачу.
Экземпляр может быть создан без аргументов либо с аргументом 'agentname'. Это имя включается в заголовки HTTP-запроса, а кроме того, используется при анализе robots.txt.
Основной рабочий метод -- open(адрес). Почему не 'get'?-- потому что сам UserAgent не читает содержание страницы, он открывает ее, возвращая 'file-like object', проверять и обрабатывать который будет уже кто-то другой.
При попытке открыть страницу с несуществующего адреса, выбрасывается исключение IOError.
Если пауку вход запрещен, генерируется RuntimeError.

(продолжение следует)

Меняющаяся карта

2008-12-24T22:04:00.003+03:00

Никогда, никогда больше не буду писать код без тестов!-- пообещал я себе сегодня утром после того, как исправил мерзкую ошибку.

Мерзость ее заключалась в том, что появлялась она время от времени. Да, я замечал, что изредка breadcrumbs -- так называется маршрут к текущей странице ('вы здесь...') на веб-портале не появлялся, но винил в этом браузер, memcached, скомпилированные Django-шаблоны -- все, что угодно, только не свой модуль, который отвечает за построение breadcrumbs.

Модуль работает следующим образом:

Из YAML-файла читается карта сайта. В результате получается дерево. Это происходит один раз, при старте Django-приложения
При выводе очередной страницы вызывается функция 'search' с текущим адресом в качестве аргумента. Она ищет в дереве узел, соответствующий заданному адресу.
Если узел найден, то в шаблон возвращается маршрут к нему. Каждый пункт маршрута содержит адрес и заголовок. В результате получается что-то вроде: "Вы здесь: Главная/Сообщения/Непрочитанные".

В любом веб-приложении имеется множество динамических адресов. В Django особенно любят дурачить пользователей и краулеры красивыми псевдо-статическими адресами. Если для доступа к событию в каком-нибудь календарике используется URL /calendar/2008/12/24/, это отнюдь не означает, что выдаваемый документ хранится на сервере в соответствующей структуре каталогов. Фреймворк знает из своей конфигурации, что последние три сегмента являются параметрами функции, отвечающей за обработку запросов по адресу /calendar.

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

YAML получился примерно такой:

--- # Карта сайта
url   : /
title : Главная
nodes :
 - url   : accounts/
   title : Пользователи
   nodes :
 - url   : accounts/{USER_ID}/
 - url   : accounts/{USER_NAME}/
 - url   : blog/
   title : Блог
   nodes :
  - url   : blog/{ENTRY_ID}/
  - url   : blog/add/
           title : Новая запись
...

Наряду со статическими адресами (например: "/", "accounts/"), здесь присутствуют и динамические. Когда функция, отвечающая за обход дерева, встречает узел accounts/{USER_ID}/ и проверяет, соответствует ли этому узлу текущий адрес account/1111/, она говорит: "Ага, это то что мне надо!"

Чтобы найти маршрут для breadcrumbs, достаточно пройти от найденного узла к вершине дерева. Получится:

/ - "Главная"
/accounts - "Пользователи "
/accounts/1111 - ...

...Стоп. Нельзя писать в breadcrumbs id пользователя, это некрасиво и не информативно. Надо заменить его именем. Значит, на последнем этапе, прежде чем возвращать результат, следует пройтись по цепочке и где надо, преобразовать id в названия.

Вот как выглядела основная функция search до того, как я исправил ту самую ошибку, с которой начал эту заметку:

 def translate(node, goal):
     """
     Преобразует узел node карты в структуру, пригодную для использования.
     Если в адресе имеются шаблоны, они заменяется динамическими данными     
     (например: {USER_ID} --> 1111
     Если существует правило замены заголовка, то node получает атрибут
     'title' с новым значением.

     node -- узел карты сайта
     goal -- текущий URL
     """
     ...

 def search(url):
     """
     Поиск адреса в карте сайта.
     Аргументы:
       url -- искомый адрес (строка)
     Возвращает:
       True, маршрут -- если адрес найден
       False, пустой список -- если адрес не найден.

     Маршрут -- это список узлов, каждый из которых представлен словарем
     c теми же ключами, что заданы в конфигурационном файле.
     """
     path = [] # маршрут
     url = normalize_url(url) # приводит искомый URL к правильному виду
  
     # рекурсивный обход дерева
     if visit(SITE_MAP, url, path):
         # узел найден
         return True, map(
             lambda node: translate(node, url), path)
     else:
         # неудача
         return False, []

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

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

import unittest

class TestCase(unittest.TestCase):
def setUp(self):
self.urls = (
    # адреса, про которые заранее известно,
    # что они прописаны в карте сайта
    ...
)

def test_search_results(self):
"""
Прогоняем через search self.urls;
Если хотя бы один не найден, тест провален.
"""
print 'Searching %d entries' % len(self.urls)
search_all = ((url, search(url)[0])
   for url in self.urls)
negative = [ url for url, result in search_all if not result ]
msg = 'Some urls were not found: %s' % ', '.join(negative)
self.assertEqual(len(negative), 0, msg)

Один узел почему-то не находился. Это был динамический маршрут (из серии .../{ШАБЛОН}). Как ни странно, с другим узлом, попадающим в тот же шаблон, все было в порядке. Сколько я ни вчитывался, никаких опечаток, пробелов -- ничего этого не было.

Я добавил в тест функцию, которая искала этот единственный проблематичный узел:

def test_idpattern(self):
 print 'Id pattern'
 url = u'/accounts/2227/'
 result, path = search(url)
 self.assertEqual(result, True, "URL '%s' not found" % url)

Тест прекрасно отрабатывал.

Наконец, я понял, в чем дело. Я попался на типичное питоновское 'gotcha'.

На вход функции "visit" подается исходное дерево, полученное YAML-парсером:

visit(SITE_MAP, url, path)

Время жизни этого дерева совпадает со временем жизни приложения -- а Django-приложения, в отличие от CGI, живут долго. В ходе очередного поиска используется одно и то же дерево.

Когда 'visit ' возвращает маршрут, оно берет его из исходного SITE_MAP. Причем возвращается не копия, а ссылка. Perl, между прочим, вернул бы копию, там операция присвоения работает иначе:

my %a = (a => 'foo', b => 'bar');
my %b = %a;
$b{'a'} = 'buz';

printf "Original: %s\n", $a{'a'};
printf "Copy: %s\n", $b{'a'};
Original: foo
Copy: buz

На вход функции 'translate' подавался все тот же узел (точнее, ссылка на него) и преобразовывала она его же. Из-за этого преобразования и возникала ошибка. После благополучного нахождения узла /accounts/1/, шаблон /accounts/{USER_ID} переставал существовать, "{USER_ID}" заменялось на "1". Не удивительно, что другой адрес такого же типа: accounts/2227 уже не имел шансов. Это все равно, что пытаться ориентироваться по карте, которая по мере твоего продвижения сама меняется.

Чтобы поправить ошибку, достаточно было отредактировать одну-единственную строчку в функции 'search':

from copy import copy

# рекурсивный обход дерева
if visit(SITE_MAP, url, path):
 # узел найден
 return True, map(   
     lambda node: translate(copy(node), url), path)
...

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

Как разбить текст на слова

2008-12-19T20:57:00.000+03:00

"Practical Text Mining With Perl" -- заметки на полях

Как часто нужные книги попадают в руки когда они уже не так актуальны! Вот первое, что я подумал, открыв "Practical Text Mining With Perl" (Roger Bilisoly, Wiley & Sons, 2008). А не повод ли это вернуться к старым увлечениям?

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

@tokens = split(/\s+/, $line);
foreach $tk (@tokens) {
    if ( $x =- /(\w+)/ ) {
        # $1 содержит слово
    }
}

Но результат будет немного неожиданным.

Внутренняя пунктуация

От слова "инженер-программист" останется лишь "инженер". От английского "o'clock" -- "o". Издатель O'Reilly не узнает своей фамилии... Шаблон \w+ набирает буквы, цифры и нижнее подчеркивание (_). Как только в тексте встречается другой символ, дверца (круглая скобка) закрывается. Слово закончилось.

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

$x =~ /(([a-zA-Z']+-)*[a-zA-Z']+)/

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

Включение апострофа в квадратные скобки -- не лучшее решение, потому что теперь словом может считаться, например: '-'-'-'-'-'-'-'-'-'-'-'-'-'-' . И разве бывают слова, где за апострофом следует дефис? Не лучше ли принять, что разделителем составных слов может быть либо дефис либо апостроф?

$x =~ /(([a-zA-Z]+[-']))*[a-zA-Z]+'?)/

Второй очевидный недостаток: диапазон a-zA-Z не оставляет никакого шанса не только цифрам, но и кириллическим символам. Одно из решений -- использовать уникодные расширения регулярных выражений:

$x =~ /(([[:alpha:]]+['-])*[[:alpha:]]+'?)/

Разумеется, придется позаботиться о том, чтобы текст был в кодировке utf-8.

***
Всегда ли имеет смысл считать составное слово чем-то отдельным? Вот ряд примеров:

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

Определить, является ли составное слово отдельной смысловой единицей или нет, способен исключительно носитель языка. Иногда ответ зависит от контекста ("красно-коричневый").

Автор "Practical Text Mining With Perl" считает, что проще все же не разбивать составные слова, и я с ним согласен. Некоторое количество лишних словообразований в лексиконе не так вредно с точки зрения анализа смысла, как дробление. Что останется от понятия "mother-in-law" (свекровь) -- пишет Bilisoly -- если разбить его на "mother", "in" и "law" ("мать", "в", "закон")?

Тире

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

s/--/ -- /g

Скрипт

Ниже код программы, адаптированный к русскому языку. В качестве аргументов задается имя исходного файла и файла с результатом (списком слов). Предполагается, что исходный файл в Windows-кодировке. При другой кодировке следует отредактировать строчку:

use open ':encoding(cp1251)';

###############################################
# split_words.pl
# Usage: perl split_words.pl FROM_FILE TO_FILE
###############################################
use strict;
use warnings;
use open ':encoding(cp1251)';

open (my $I, '<', $ARGV[0]) or die $!; 
open (my $O, '>', $ARGV[1]) or die $!;
while (<$I>) {
    chomp;
    s/--/ -- /g;
    my @words = split /\s+/;
    foreach my $w (@words) {
        print $O "$1\n"
            if $w =~ /(([[:alpha:]]+['-])*[[:alpha:]]+'?)/ )
    }
}
close $O;
close $I;

Python-версия

А вот версия для Питона:

#!/usr/bin/python
# -*- coding: utf-8 -*-
#
# from __future__ import with_statement # Python2.5
import sys
import re

pattern = re.compile("(([\w]+[-'])*[\w']+'?)", re.U)
with open(sys.argv[1]) as f:
  for line in f:
      line = unicode(line, 'cp1251')
      line = line.replace('--', ' -- ')
      for token in line.split():
          m = pattern.match(token)
          if m:
              print m.group()

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

Везде свои тонкости

Локализованная версия испытывалась на русском переводе рассказа Эдгара По "Сердце-обличитель". В книге "Text Mining With Perl" с этой же целью используется оригинал: "Tell-Tale Heart". А что если мы обрабатываем текст, по которому не прошелся корректор? Авторы блог-постов, например, часто забывают поставить пробел после точки в конце предложения или после запятой. Предположение, что слова всегда разделены пробелами, может оказаться неверным.

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

@tokens = split(/\W+/, $line);

Это работает, но к сожалению, все составные слова будут разбиты.

На Питоне:

splitter = re.compile(r'\W*', re.U)
words = [ s for s in splitter.split(text) if s ]

А вот более интересный пример из книги "An Introduction to Language Processing with Perl and Prolog" (Pierre M. Nugues, Springer, 2006):

$text = <>;
while ($line = <>) {
    $text .= $line;
}
$text =~ tr/a-zåàâäæçéèêëîïôöoeùûüßAZÅÀÂÄÆÇÉÈÊËÎÏÔÖOEÙÛÜ’()\-,.?!:;/\n/cs;
$text =~ s/([,.?!:;()’\-])/\n$1\n/g;
$text =~ s/\n+/\n/g;
print $text;

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

Если символ не является ни буквой ни знаком пунктуации, он заменяется символом новой строки
Каждый знаки пунктуации помещается на отдельную строку
Повторяющиеся символы новой строки заменяются одним

Чтобы адаптировать этот код к кириллице, придется дополнить длинную цепочку не-ASCII символов, переданных оператору tr. К сожалению, этот оператор не понимает уникодных расширений. Впрочем, того же результата можно добиться более привычным оператором замены (s///).

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

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

Спасибо тебе, Мишка!

2007-11-20T13:08:00.000+03:00

В книге "Mastering Perl" есть глава "Философия борьбы с неразрешимыми проблемами от Брайена ди Фоя". Один из рецептов звучит так: "А пытались ли вы поговорить об этом с Мишкой?"

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

Я вспомнил этот совет когда ломал голову над тестовым заданием следующего содержания:

Есть две таблицы:
table1 (table1_id integer, name varchar(255)),
table2 (table2_id integer, table1_id integer, alias varchar(255))

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

У меня сложные отношения с SQL. Периодически в него погружаюсь и решаю довольно сложные задачи. Но стоит полгода не позаниматься -- все забывается чуть ли не начисто. (Нечто подобное, но еще в большей степени происходит с XSLT). Ясно было, что надо использовать GROUP и MAX, но как объединить все это в один запрос?...

Я прокрался в спальню, к детской кроватке. У пятилетнего Степы есть несколько медведей, в том числе два белых брата Кнут и Олаф Хаммундсены. Интуиция подсказывала, что для моих целей подойдет Винни-Пух. Через пять минут я четко и с расстановкой объяснял ему, в чем проблема. А через 10 минут решение было готово. Вот оно:

SELECT table1_id FROM table2
GROUP BY table1_id
HAVING COUNT(*) =
(
SELECT MAX(table2_count)
FROM (
SELECT COUNT(*) AS table2_count
FROM table2
GROUP BY table1_id
) AS inner_table
);

Ответ находится в 3 этапа:

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

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

CGI::Application и AJAX

2007-11-20T01:58:00.000+03:00

В выходные решил попрактиковаться с CGI::Application, библиотекой JQuery и AJAX, потому что за год погружения в краулеры/парсеры подзабыл, как пишутся CGI-приложения. Получился вот такой словарик онлайн.

Больше всего времени угрохал на то, чтобы разобраться, как передавать клиенту в ответ на асинхронный запрос данные в JSON-формате -- то есть ни HTML ни XML, а JavaScript. Соответственно, content-type в заголовке HTTP-ответа должен быть "text/javascript". Между тем, фреймворк CGI::Application предполагает, что каждый "run-mode" возвращает HTML.
Вот как выглядит решение:

$self->header_type('none');
print "Content-Type: text/javascript; charset=utf-8\n\n";
return objToJson($self->_get_dictionaries() );

$self->header_type(none) "сообщает" фреймворку: не заботься о HTTP-заголовках.
затем мы выводим свой собственный, нестандартный заголовок
метод $self->_get_dictionaries() возвращает структуру данных, которая преобразуется в JSON-формат функцией objToJson из CPAN-библиотеки JSON

На стороне клиента:

function resetDictionaries() {
 $.getJSON('/cgi-bin/words.cgi',
           {rm: 'update_dicts',
            dicttype: document.SearchForm.DictType.value
           },
           function(data) {
             populateCombo('#Dict', data);
           });    
}

Эта функция вызывается когда пользователь меняет категорию словаря в верхнем выпадающем списке.

методом JQuery getJSON мы отправляем на сервер асинхронный запрос
ответные данные -- те самые, которые были упакованы методом objToJson -- приходят в анонимную callback-функцию. Ее аргумент data преставляет собой готовый к использованию JavaScript-объект. Функция populateCombo (которая здесь не приводится) динамически меняет содержание выпадающего списка словарей.

Разобраться с JQuery мне, помимо официальной документации, помогла статья на RSDN: JQuery -- Javascript нового поколения.

List Comprehension средствами Perl

2007-11-14T22:46:00.000+03:00

Решая один из вопросов теста, понял, как средствами Perl сделать подобие питоновского 'list comprehension'.

Задача: имеется строка запроса вида: 'param1=foo&param2=bar...'
Необходимо получить хэш: (param1 => 'foo', param2=>'bar'...)

Прямолинейное решение:

sub query2hash {
my  $query = shift;
my @arr;
foreach (split  /&/, $query) {
    push @arr, split /=/, $_;
}
@arr;
}

Каждому, кто знаком с "list comprehension" в языке Python, столь многословная инициализация массива @arr покажется каменным веком. Выполнив на Python-е:

query = 'param1=foo&param2=bar&param3=zoo'
arr = [ pair.split('=') for pair in query.split('&') ]

мы получим список списков:

[['param1', 'foo'], ['param2', 'bar'], ['param3', 'zoo']]

Можно ли написать на Perl столь же лаконичную конструкцию?...
Проще простого:

sub query2hash {
 map { split /=/ } split /&/, shift;
}

Всего строчка! Более того, в Python-е предстоит еще повозиться, чтобы преобразовать список списков в словарь. А тут мы получаем хэш даром. Достаточно присвоить список, возвращаемый функцией, хэш-переменной:

my %params
  = query2hash( 'param1=foo&param2=bar&param3=zoo' );

См также:

Функциональное программироване на Питоне -- статья из Wikipedia
List Comprehension -- о List Comprehension c примерами на разных языках программирования

Уверенные знания и большие плюсы

2007-11-14T20:48:00.000+03:00

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

Тестовое задание состояло из вопросов по Perl, SQL и Unix. Я отдавал себе отчет, что 24 вопроса -- многовато для первого знакомства. Но работа обещала быть интересной (сбор информации, анализ текста -- близко к поисковым задачам, которыми я занимался почти год). К тому же, хотелось освежить память по SQL. Вот почему я посвятил этому тесту целый выходной.

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

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

Позапрошлым летом я пытался устроиться в Гугл. После, наверное, месячного молчания оттуда ответили, что у них, к сожалению, нет подходящей для меня вакансии в Москве. И ни слова о 8-клеточных пятнашках, которые я вполне корректно решил методом "A-Star" -- таково было тестовое задание.

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