Допустим нам надо определить Page Rank страниц на заданном сайте.

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

  1. Собрать все страницы с соотв. сайта, а точнее ссылки "откуда" - "куда" (перелинковка)
  2. Для уменьшения потребления памяти передавать лучше не полные урлы перелинковки, а id урлов страниц.
  3. Подготовить необходимо файл csv

 

Некоторые объяснения:

В моей задаче необходимо было посчитать PageRank для 1 млн страниц. Один из методов подсчёта PageRank - составление матрицы перелинковки и нахождение собственного вектора этой матрицы (мы будем брать один вектор с действительными числами, остальные с комплексными значениями, этот вектор и будет списком значений ранга страниц), собственные же значения отбрасываются, т.к. это просто множитель для ранга, его можно отбросить или же выбрать нормированным, как вес, перетекающий между страницами.

Итак, получается, что матрица будет размером 1e6*1e6 (миллион строк на миллион столбцов) = 1e12 - 1 триллион ячеек с цифрами, всё это не поместишь в память ПК при очевидной реализации матрицы и не поместишь в процессорное время (не дождёшься результата) при очевидной реализации нахождения собственных векторов (СВ) и собственных значений (СЗ).

Но есть один большой плюс - большинство ячеек в матрице будут нулями и только около 10-15 млн ячеек будут единицами (при инициализации), поэтому есть интуитивное предположение, что нам можно не хранить значения всех ячеек и выполнять операции не со всеми ячейками, а только с ненулевыми; и это предоставляет как раз python библиотека scipy в модуле sparse.

 

Также в программе реализована возможность задать "внешние ссылки" на сайт - а именно с помощью вектора F.

# -*- coding: utf-8 -*-
from scipy.sparse import csc_matrix, linalg
import scipy
import csv
import json
import math
import urlparse
import re
import time


def get_steps(k):
    steps = []
    s = int(math.log(k)/math.log(2))
    sm = 2**s
    steps.append(s)
    while sm < k:
        s = int(math.log(k - sm)/math.log(2))
        steps.append(s)
        sm += 2**s
    return steps


def _clean(url):
    obj = urlparse.urlparse(url)
    if obj.scheme.lower() == scheme.lower() and \
            obj.netloc.lower().replace('www.', '') == domain.lower():
        if obj.query:
            ret = '{0}?{1}'.format(obj.path, obj.query)
        else:
            ret = obj.path
    else:
        ret = url
    return ret


img_pattern = re.compile(r'(?i)\.png|jpg|xls|rar|zip|djvu|jpeg$')


def _filter(from_page_id, to_page_id):
    if 'plus.google' in to_page_id:
        return True
    if to_page_id.startswith('/ios?'):
        return True
    if from_page_id.startswith('/ios?'):
        return True
    if to_page_id.startswith('/android?'):
        return True
    if from_page_id.startswith('/android?'):
        return True
    if not from_page_id:
        return True
    if not to_page_id:
        return True
    if from_page_id == to_page_id:
        return True
    if img_pattern.findall(to_page_id):
        return True
    if '#' in to_page_id:
        return True
    if '#' in from_page_id:
        return True
    if to_page_id.startswith('mailto:'):
        return True
    return False


scheme = 'HTTPS'
domain = 'kontrolnaya-rabota.ru'
filename = 'site_data.csv'

page_id_key = 'url'
from_page_id_key = 'from_{0}'.format(page_id_key)
to_page_id_key = 'to_{0}'.format(page_id_key)

csv_file = file(filename)

to_file = file('result.csv', 'w')

reader = csv.reader(csv_file, delimiter='\t')

page_ids = set()

print_limiter = 10000000


print 'Step unique pages'

csv_file.seek(0)
c = 0
for item in reader:
    if len(item) < 2:
        continue
    from_page_id, to_page_id = item[:2]
    c += 1
    from_page_id = _clean(from_page_id)
    to_page_id = _clean(to_page_id)
    if to_page_id.startswith('?'):
        to_page_id = urlparse.urlparse(from_page_id).path + to_page_id
    if _filter(from_page_id, to_page_id):
        continue
    if c and c % print_limiter == 0:
        print c / print_limiter
    page_ids.add(from_page_id)
    page_ids.add(to_page_id)

page_ids = list(page_ids)


print 'Step fill nums'

page_nums = {}
for num, page_id in enumerate(page_ids):
    page_nums[page_id] = num


print 'Step create links'

csv_file.seek(0)
link_nums = set()
c = 0
for item in reader:
    if len(item) < 2:
        continue
    from_page_id, to_page_id = item[:2]
    c += 1
    from_page_id = _clean(from_page_id)
    to_page_id = _clean(to_page_id)
    if to_page_id.startswith('?'):
        to_page_id = urlparse.urlparse(from_page_id).path + to_page_id
    if _filter(from_page_id, to_page_id):
        continue
    if c and c % print_limiter == 0:
        print c / print_limiter
    from_num = page_nums[from_page_id]
    to_num = page_nums[to_page_id]
    link_nums.add((from_num, to_num))

link_nums = list(link_nums)


links_count = len(link_nums)
matrix_data = [1] * links_count
print 'links_count: ', links_count


pages_count = len(page_ids)
print 'pages_count: ', pages_count

print 'Step fill graph'

row = []
col = []
indptr = []
indices = []
for from_num, to_num in sorted(link_nums):
    row.append(to_num)
    col.append(from_num)
    indptr.append(from_num + to_num)
    indices.append(from_num)

row = scipy.array(row, dtype=scipy.int64)
col = scipy.array(col, dtype=scipy.int64)

f_matrix_data = scipy.array([100]*pages_count, dtype=scipy.int64)
f_row = scipy.array(range(pages_count), dtype=scipy.int64)

index_page_num = page_nums['/']

f_col = scipy.array([index_page_num]*pages_count, dtype=scipy.int64)

indptr = list(set(indptr))

indptr = scipy.array(indptr, dtype=scipy.int64)
indices = scipy.array(indices, dtype=scipy.int64)


print 'Step calc pr'

A = csc_matrix(
    (matrix_data, (row, col)),
    shape=(pages_count, pages_count),
    dtype='d',
)

F = csc_matrix(
    (f_matrix_data,
         (f_row, f_col),
    ),
    shape=A.shape,
    dtype='d',
)

AF = A# + F

e = csc_matrix(
    ([1]*pages_count,
        (range(pages_count), [0]*pages_count),
    ),
    shape=(pages_count, 1),
    dtype=scipy.float64,
)

eT = csc_matrix(
    ([1]*pages_count,
        ([0]*pages_count, range(pages_count)),
    ),
    shape=(1, pages_count),
    dtype=scipy.float64,
)

print e.todense()

print A.todense()

print eT.todense()

k = pages_count

steps = get_steps(k)

print 'steps', steps

del page_ids
del link_nums

Ak = A.copy()

n = max(steps)
lst_A = []
for num in range(1, n + 1):
    print 'power A to %s: %s' % (n, num)
    Ak = Ak*Ak/2**(2*num + math.log(num))
    if num in steps:
        lst_A.append(Ak.copy())

Afull = 5e2*lst_A[0]
prev_num = steps[0]
for i in range(1, len(lst_A)):
    Ak = lst_A[i]
    num = steps[i]
    print 'product A: %s*%s' % (prev_num, num)
    Afull = Ak*Afull/2**(2*num + math.log(num))
    prev_num = num

pagerank_vs = (Afull*e)/scipy.float32((eT*Afull*e)[0, 0])

_, pseudo_prs = linalg.eigs(AF, k=1, which='LR')

pagerank_vs = list(pseudo_prs[:, 0])

# pagerank_vs = list(pagerank_vs.todense())
pagerank_vs = map(float, pagerank_vs)

sum_pr = sum(pagerank_vs)
pagerank_vs = map(lambda el: el*pages_count/sum_pr, pagerank_vs)


print 'Step view'

reverted_page_nums = {v: k for k, v in page_nums.iteritems()}

for page_num, pagerank in enumerate(pagerank_vs):
    page_id = reverted_page_nums[page_num]
    try:
        text = page_id.encode('utf-8', 'encode') + '\t' + str(pagerank).replace('.', ',') + '\n'
    except:
        continue
    to_file.write(text)

to_file.close()