КА и обкачка сайтов

Конечные автоматы

Конечный автомат – это выдуманное вычислительное устройство, состоящее из:

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

Нарисуем для примера автомат, который узнаёт предложение на языке Ook.

digraph {
  rankdir="LR";
  node [fontsize=10];
  edge [fontsize=10];
  S [color="darkgreen", label="between words *"];
  S -> S [label="space"];
  S -> S [label="tab"];
  S -> S [label="newline"];
  S -> "seen O" [label="O"];
  "seen O" -> "seen Oo" [label="o"];
  "seen Oo" -> "seen Ook" [label="k"];
  "seen Ook" -> S [label="."];
  "seen Ook" -> S [label="?"];
  "seen Ook" -> S [label="!"];
}

Зелёным выделено начальное состояние, звёздочкой помечены допустимые конечные состояния.

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

   1 def ook(text):
   2     state = "between words"
   3     for character in text:
   4         if state == "between words" and character == " ":
   5             state = "between words"
   6         elif state == "between words" and character == "\t":
   7             state = "between words"
   8         elif state == "between words" and character == "\n":
   9             state = "between words"
  10         elif state == "between words" and character == "O":
  11             state = "seen O"
  12         elif state == "seen O" and character == "o":
  13             state = "seen Oo"
  14         elif state == "seen Oo" and character == "k":
  15             state = "seen Ook"
  16         elif state == "seen Ook" and character == "?":
  17             state = "between words"
  18         elif state == "seen Ook" and character == "!":
  19             state = "between words"
  20         elif state == "seen Ook" and character == ".":
  21             state = "between words"
  22         else:
  23             return False
  24     if state in ["between words"]:
  25         return True
  26     else:
  27         return False

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

Последние четыре строки лучше переписать так:

   1     return (state in ["between words"])

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

   1 ook_fsm = {
   2     ("between words", " "): "between words",
   3     ("between words", "\t"): "between words",
   4     ("between words", "\n"): "between words",
   5     ("between words", "O"): "seen O",
   6     ("seen O", "o"): "seen Oo",
   7     ("seen Oo", "k"): "seen Ook",
   8     ("seen Ook", "?"): "between words",
   9     ("seen Ook", "!"): "between words",
  10     ("seen Ook", "."): "between words",
  11 }
  12 
  13 def ook(text):
  14     state = "between words"
  15     for character in text:
  16         if (state, character) not in ook_fsm:
  17             return False
  18         state = ook_fsm[state, character]
  19     return state in ["between words"]

Последний штрих: давайте вынесем всё описание автомата в словарь.

   1 ook_fsm = {
   2     "initial state": "between words",
   3     "final states": ["between words"],
   4 
   5     ("between words", " "): "between words",
   6     ("between words", "\t"): "between words",
   7     ("between words", "\n"): "between words",
   8     ("between words", "O"): "seen O",
   9     ("seen O", "o"): "seen Oo",
  10     ("seen Oo", "k"): "seen Ook",
  11     ("seen Ook", "?"): "between words",
  12     ("seen Ook", "!"): "between words",
  13     ("seen Ook", "."): "between words",
  14 }
  15 
  16 def fsm(text, fsm):
  17     state = fsm["initial state"]
  18     for character in text:
  19         if (state, character) not in fsm:
  20             return False
  21         state = fsm[state, character]
  22     return (state in fsm["final states"])

Добывание данных из сети

Добывание данных из сети в питоне устроено очень просто. Есть модуль urllib, который позволяет нам "открыть" сайт так же, как мы открывали файл¹:

   1 import urllib
   2 
   3 infile = urllib.urlopen("http://kingjamesprogramming.tumblr.com/")
   4 raw_text = infile.read()
   5 text = raw_text.decode("utf-8")
   6 infile.close()

Одно важное замечание: urllib ничего не пытается делать с кодировками и возвращает нам байтовую строку. Нам нужно самостоятельно её расшифровать.

Откуда узнать кодировку?

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

Ещё более простой ответ: сейчас большинство сайтов использует кодировку utf-8, поэтому можно использовать её, и задаваться вопросами только если она не работает.

Два слова о чистке данных из сети

Если мы теперь скажем print text, мы увидим кучу абракадабры. Большинство данных в сети лежит в форматах: html, css, js. При этом в форматах css и js обычно лежат украшательства, а полезные данные лежат в формате html.

Формат html устроен следующим образом: в нём пишется обычный текст, а некоторые части текста выделены парой тэгов, которые говорят, как эта часть текста (от открывающего тэга до закрывающего тэга) будет выглядеть. Тэги выглядят как набор правил в угловых скобках, открывающие выглядят как <имятэга параметры>, закрывающий как </имятэга>. Например, если в тексте есть выделенное жирным слово, то это выглядит так: посреди предложения <b>жирное</b> слово.

Подробнее с форматом html мы будем разбираться когда будем учиться делать свои веб-страницы. Пока что нас интересует только как из html получать содержательный текст. Простейшая идея: убрать из текста все тэги:

   1 import re
   2 print re.sub(r'<[^>]*>', '', text)

Стало лучше, но осталась куча мусора. Есть тэги, внутри которых лежит только служебная информация, например, тэги <style> и <script>:

   1 cleaner_text = re.sub(r'<(style|script) .*</\1>', '', text)
   2 print re.sub(r'<[^>]*>', '', cleaner_text)

Другие тэги, например <p>, разделяют абзацы, и их наоборот хотелось бы выделить (заменить на пару переносов строки, например).

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

robots.txt

В интернете существуют правила хорошего тона.

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

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

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

Sitemap: http://kingjamesprogramming.tumblr.com/sitemap1.xml

User-agent: *
Disallow: /private
Disallow: /random
Disallow: /day
Crawl-delay: 1

Слово "user-agent" обозначает программу, которая скачивает сайт. Обычно вы смотрите сайт с помощью мозиллы, хрома, оперы или эксплорера, и в этом случае у вас user-agent будет либо Mozilla, либо Chrome, либо Opera, либо Explorer². Когда вы качаете сайт с помощью urllib, у вас user-agent будет называться "urllib".

Дальше есть правила вида "разрешить" и "запретить", в которых указывается адрес после домена.

* в лбюом месте здесь обозначает любое количество любых символов.

По счастью, нам не нужно разбирать этот файл, за нас это умеет делать питон. В нём есть модуль robotparser, которому единственное нужно знать: какой файл robots.txt использовать:

   1 import robotparser
   2 robots = robotparser.RobotFileParser("http://kingjamesprogramming.tumblr.com/robots.txt")
   3 robot.read()
   4 print robots.can_fetch("urllib", "http://kingjamesprogramming.tumblr.com/private/stuff")

Понятно, что мы можем один раз скачать robots.txt, и кучу раз потом им пользоваться, чтобы проверять, что можно, а что нельзя качать:

   1 import urllib
   2 import robotparser
   3 
   4 sites = [...]
   5 domain = "..."
   6 
   7 robots = robotoparser.RobotFileParser(domain + "/robots.txt")
   8 robots.read()
   9 for site in sites:
  10     if robots.can_fetch(site):
  11         file = urllib.urlopen(site)
  12         print file.read()

С robotparser есть одна печаль: он не умеет реагировать на "Crawl-delay", т.е. втыкать задержки в выкачку. Поэтому полезно посмотреть в robots.txt нужного вам сайта глазами, и если там указана задержка, воткнуть перед закачкой соответствующий time.sleep().