31 дек. 2008 г.

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

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

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)

29 дек. 2008 г.

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

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


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

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


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

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

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

С другой стороны, современные языки программирования предоставляют готовые библиотеки, позволяющие свести задачу скачивания документа к одной строчке кода. Например, на Питоне:
import urllib
tmpfile, headers = urllib.urlretrieve('http://www.python.org/')
Это работает и выглядит весьма заманчиво. Можно даже, следуя примеру из книги Т.Сегарана "Программируем коллективный разум" ("Символ-плюс", 2008), написать "обертку" вокруг этой строчки, которая позволит идти вглубь и вширь, по ссылкам, добытых с каждой загружаемой страницы. Если запустить такой краулер на ночь, то к утру вас могут ожидать один или несколько неприятных сюрпризов из серии:
  • многие документы обрываются в самом начале;
  • неоправданно большое количество сообщений об ошибках, в том числе с ресурсов, которые прекрасно видны через браузер;
  • диск заполнен мусором: вместо текстов пришли какие-то бинарные файлы из каких-то неприкаянных потоков;
  • краулер всю ночь провисел в ожидании ответа от какого-то хоста;
  • компьютер впал в ступор после того как процесс скушал все доступные ресурсы;
  • ваш IP-адрес заблокирован и помещен в черные списки веб-мастеров, потому что краулер ходит куда не положено и делает запросы с частотой дятла;
Это все равно, что пустить в Москву-реку бумажный кораблик, надеясь, что рано или поздно он попадет в Каспийское море.

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

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


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

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

Какого рода могут быть ошибки? Их можно свести к нескольким категориям:
  1. Соединение не состоялось. Например, кошка поиграла с сетевым кабелем и сети не стало. Или вместо http:// задано реез://. Или сервер долго не отвечает.
  2. Соединение состоялось, но посещение страницы запрещено robots.txt
  3. Соединение состоялось, но сервер вместо запрошенных данных вернул код ошибки (401 -- "требуется авторизация", 404 -- "документ не найден", 500 -- "внутренняя ошибка" и т.д ).
  4. Вместо целой страницы пришла только ее часть
Сразу же установим несколько ограничений -- по крайней мере, для первой версии краулера:
  1. используется только HTTP-протокол
  2. интересны только 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.


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

24 дек. 2008 г.

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

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

Мерзость ее заключалась в том, что появлялась она время от времени. Да, я замечал, что изредка 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)
...
Не знаю, через сколько времени была бы обнаружена причина изредка появляющихся ошибок в веб-приложении, если бы не тест.

19 дек. 2008 г.

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

"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;
Здесь вместо того, чтобы обрабатывать строчку за строчкой, все прочитанные из файла строки, наоборот, сливаются в один текст. Затем:
  1. Если символ не является ни буквой ни знаком пунктуации, он заменяется символом новой строки
  2. Каждый знаки пунктуации помещается на отдельную строку
  3. Повторяющиеся символы новой строки заменяются одним
Чтобы адаптировать этот код к кириллице, придется дополнить длинную цепочку не-ASCII символов, переданных оператору tr. К сожалению, этот оператор не понимает уникодных расширений. Впрочем, того же результата можно добиться более привычным оператором замены (s///).

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

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