Ruby loves PageRank

Довел до ума обещанный PageRank на Ruby. Забрать можно из моего гит репозитория. Если дадут приглашение на GitHub, то будет и SVN зеркало. Код закомментирован, примеры использования в тестах. Тесты и идея взяты из этой статьи.

В кратце можно описать алгоритм так:

1. Пусть у нас есть n страниц, на каждой из которых I_j ссылок. Мы хотим оценить некую "важность" страницы, с помощью которой можно было бы сказать, какая страница "авторитетнее", на основе количества ссылок на эту статью и "важности" страниц, с которых ведут ссылки. Важность и обзовем словом PageRank.
2. Предположим, что если страница j ссылается на страницу i, то она отдает ей 1/|I_j| своей "важности".
3. Составляем матрицу ссылок следующим образом: в клетке S_i,j стоит число 1/|I_j|, если на j-ой странице есть ссылка на i-ую, 0 в противном случае.
4. У нас получается квадратная матрица, в которой по диагонали стоят нули, а сумма всех чисел в столбце равняется единице.
5. Чтобы посчитать "важность" каждой страницы необходимо найти собственный вектор V полученой матрицы H, соответствующий собственному значению 1. V_i — важность страницы i. Для этого воспользуемся простейшим итерационным методом.
6. В данном решении возникают проблемы, типа висячей страницы, которая не ссылается ни на какие другие. Такая страница перетягивает на себя всю "важность" страниц, которые на нее ссылаются. Для этого мы интерпретируем H в вероятностном аспекте, о чем говорится в статье. Также в ней рассматриваются другие проблемы. Для понимания процесса рекомендую с ней ознакомится.

Комментарии и дополнения к коду приветствуются.

autotest

Если вы пишете для своего кода на Ruby тесты либо спеки, то вам непременно пригодится autotest из гема ZenTest. Эта утилита запускается из корня проекта и следит за изменениями в тестах/спеках. Если таковые имеются, то она запускает только эти измененные файлы. За счет этого достигается скорость тестирования (прогонять переиодически кучу тестов — не быстрое занятие), и мы всегда знаем, когда у нас что-то сломалось.

Для этой утилиты существует плагин RedGreen, который подсвечивает зеленым или красным результаты прогона тестов, дабы одного взгляда хватило, чтобы увидеть ситуацию. Однако этот плагин не работает при тестирвоании спек, так как у них отличается формат вывода сообщения об ошибках. Если поместить следующий код в файл .autotest в вашем корневом каталоге или в каталоге с проектом, откуда запускаем тесты, то все будет работать как хочется.

  module Autotest::RedGreen
    BAR = "=" * 80

    Autotest.add_hook :ran_command do |at|
      # was     if at.results.last =~ /^.* (\d+) failures, (\d+) errors$/
      # changed because if we have pendings, output will look like "5 examples, 1 failure, 2 pending"
      # and this condition will not work
      if at.results.last =~ /^.* ((\d+) failures?|(\d+) errors?)/
        code = ($2 != "0" or (not $3.nil? && $3 != "0")) ? 31 : 32
        puts "\e[#{code}m#{BAR}\e[0m\n\n"
      end
    end
  end

Updated Hemingway theme for Mephisto

Original port of Hemingway theme for Wordpress was out of date with latest mephisto liquid variables. So I've fixed this, also added templates for search, tags pages, added search field, changed base font size. Grab my version here.

TextMate PIR Bundle

A bundle for my favorite text editor TextMate which help to work with PIR programming language from Parrot VM. Include language grammar for syntax highlighting and some code snippets. You can grab it here using Subversion. If you use it, please write me about you experience (e-mail in bundle info.plist, rot13 encoded), or mail you patches, I'll submit them to repo.

Расширение для моего любимого редактора текста TextMate, дабы работать с языком PIR для программирования виртуальной машины Parrot. Добавляет редактору умение подсвечивать код PIR, а также несколько простых сниппетов, типа заготовки для if'а. Брать здесь с помощью Subversion. Если будете его использовать, напишите мне на мыло плиз (в файле info.plist, закодировано с помощью rot13, в расширении Mail есть функция для его раскодирвоания). Также можете слать мне патчи, проверю и внесу в репозиторий, если он будет полезен.