Простой паук

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

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

Библиотека urllib2

Библиотека urllib2, входящая в дистрибутив Python, предназначена для скачивания страниц. От вас требуется только указать URL. В этом разделе мы воспользуемся ею, чтобы скачать страницы для последующего индексирования. Чтобы посмотреть, как она работает, запустите интерпретатор Python и введите следующие команды: >> import urllib2

>> c=urllib2.urlopen(‘http://kiwitobes.com/wiki/Programming_language.html’) >> contents=c.read( ) >> print contents[0:50]

‘<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Trans’ Для того чтобы сохранить HTML-код страницы в строке, вам нужно лишь создать соединение и прочитать содержимое страницы.

Код паука

Программируя паука, мы будем пользоваться библиотекой Beautiful Soup,; она строит структурированное представление веб-страниц. Эта библиотека очень терпимо относится к некорректной HTML-разметке, что весьма полезно при построении паука, поскольку никогда не знаешь, с чем придется столкнуться. Дополнительную информацию о загрузке и установке библиотеки Beautiful Soup см. в приложении A.

С помощью библиотек urllib2 и Beautiful Soup можно построить паука, который принимает на входе список подлежащих индексированию URL и, переползая по ссылкам, находит другие страницы. Начнем с добавления в файл searchengine.py таких предложений:

import urllib2

from BeautifulSoup import *

from urlparse import urljoin

# Создать список игнорируемых слов

ignorewords=set([‘the’,’of’,’to’,’and’,’a’,’in’,’is’,’it’])

Теперь можно написать код главной функции паука. Пока она ничего не сохраняет, а просто печатает посещаемые URL, демонстрируя, что какие-то действия выполняются. Добавьте следующий код в конец файла (поместив его в класс crawler):

def crawl(self,pages,depth=2): for i in range(depth): newpages=set( ) for page in pages: try:

c=urllib2.urlopen(page) except:

print "Не могу открыть %%s" %% page continue soup=BeautifulSoup(c.read( )) self.addtoindex(page,soup)

links=soup(‘a’) for link in links: if (‘href’ in dict(link.attrs)): url=urljoin(page,link[‘href’]) if url.find(        )!=-1: continue

url=url.split(‘#’)[0] # удалить часть URL после знака # if url[0:4]==’http’ and not self.isindexed(url):

newpages.add(url) linkText=self.gettextonly(link) self.addlinkref(page,url,linkText)

self.dbcommit( )

pages=newpages

Эта функция в цикле обходит список страниц, вызывая для каждой функцию addtoindex (пока что она всего лишь печатает URL, но в следующем разделе мы это исправим). Далее с помощью библиотеки Beautiful Soup она получает все ссылки на данной странице и добавляет их URL в список newpages. В конце цикла newpages присваивается pages, и процесс повторяется.

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

Вы можете протестировать функцию, введя следующие команды в интерпретаторе (дожидаться завершения необязательно; когда надоест, можете нажать сочетание клавиш CtrL+C):

>> import searchengine

>> pagelist=[‘http://kiwitobes.com/wiki/Perl.html’] >> crawler=searchengine.crawler(”) >> crawler.crawl(pagelist)

Индексируется http://kiwitobes.com/wiki/Perl.html

Не могу открыть http://kiwitobes.com/wiki/Module_%28programming%29.html Индексируется http://kiwitobes.com/wiki/Open_Directory_Project.html Индексируется http://kiwitobes.com/wiki/Common_Gateway_Interface.html

Вероятно, вы заметили, что некоторые страницы повторяются. В коде имеется заглушка для функции isindexed, которая вызывается перед добавлением страницы в список newpages и проверяет, была ли страница недавно проиндексирована. Это позволяет в любой момент «натравливать» паука на любой список URL, не опасаясь, что будет проделана ненужная работа.

Построение индекса

Наш следующий шаг – подготовка базы данных для хранения полнотекстового индекса. Я уже говорил, что такой индекс представляет собой список слов, с каждым из которых ассоциировано множество документов, где это слово встречается, и место вхождения слова в документ. В данном примере мы анализируем только текст на странице, игнорируя все нетекстовые элементы. Кроме того, индексируются только сами слова, а все знаки препинания удаляются. Такой метод выделения слов несовершенен, но для построения простой поисковой машины сойдет. Поскольку рассмотрение различных баз данных и конфигурирования СУБД выходит за рамки данной книги, я покажу лишь, как хранить индекс в базе данных SQLite. SQLite – это встраиваемая СУБД, которую очень легко настроить, причем вся база данных хранится в одном файле. Поскольку запросы формулируются на языке SQL, будет нетрудно перенести код примеров на другую СУБД. Реализация на Python называется pysqlite, а скачать ее можно со страницы http://initd.org/ tracker/pysqlite.

Имеется инсталлятор для Windows и инструкции по установке на другие операционные системы. В приложении A приведена дополнительная информация по получению и установке pysqlite. После установки SQLite добавьте следующую строку в файл search- engine.py:

from pysqlite2 import dbapi2 as sqlite Необходимо также изменить методы __init__, __del__ и dbcommit, добавив код открытия и закрытия базы данных:

def _ init__ (self,dbname):

self.con=sqlite.connect(dbname)

def __del__(self): self.con.close( )

def dbcommit(self): self.con.commit( )

Создание схемы

Подождите запускать программу – нужно сначала подготовить базу данных. Схема простого индекса состоит из пяти таблиц. Первая (urllist) – это список проиндексированных URL. Вторая (wordlist) – список слов, а третья (wordlocation) – список мест вхождения слов в документы. В оставшихся двух таблицах хранятся ссылки между документами. В таблице link хранятся идентификаторы двух URL, связанных ссылкой, а в таблице linkwords есть два столбца – wordid и linkid – для хранения слов, составляющих ссылку. Вся схема изображена на рис. 4.1.

Рис. 4.1. Схема базы данных поисковой машины

В каждой таблице SQLite по умолчанию имеется поле rowid, поэтому явно задавать ключевые поля необязательно. Для создания базы данных добавьте в класс crawler в файле searchengine.py следующую функцию:

def createindextables(self):

self.con.execute(‘create table urllist(url)’) self.con.execute(‘create table wordlist(word)’)

self.con.execute(‘create table wordlocation(urlid,wordid,location)’) self.con.execute(‘create table link(fromid integer,toid integer)’) self.con.execute(‘create table linkwords(wordid,linkid)’) self.con.execute(‘create index wordidx on wordlist(word)’) self.con.execute(‘create index urlidx on urllist(url)’) self.con.execute(‘create index wordurlidx on wordlocation(wordid)’) self.con.execute(‘create index urltoidx on link(toid)’) self.con.execute(‘create index urlfromidx on link(fromid)’) self.dbcommit( )

Эта функция создает все нужные нам таблицы, а также ряд индексов, ускоряющих поиск. Индексы необходимы, потому что набор данных может быть очень велик. Введите в интерпретаторе следующие команды для создания базы данных searchindex.db: >> reload(searchengine)

>> crawler=searchengine.crawler(‘searchindex.db’) >> crawler.createindextables( )

Позже вы добавим в базу еще одну таблицу для хранения метрики ранжирования на основе указывающих на страницу внешних ссылок.

Выделение слов на странице

Файлы, загруженные из Сети, обычно представлены в формате HTML и потому содержат много тегов, атрибутов и прочей информации, которую индексировать не нужно. Стало быть, для начала нужно выделить те части страницы, которые содержат текст. Для этого можно поискать в «супе» текстовые узлы и взять их содержимое. Добавьте следующий код в функции gettextonly: def gettextonly(self,soup): v=soup.string if v==None: c=soup.contents resulttext=” for t in c: subtext=self.gettextonly(t) resulttext+=subtext+’\n’ return resulttext else:

return v.strip( )

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

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

def separatewords(self,text): splitter=re.compile(‘\\W*’)

return [s.lower( ) for s in splitter.split(text) if s!=”] Поскольку эта функция считает разделителями все символы, кроме букв и цифр, то с выделением английских слов особых проблем не будет, но такие термины, как C++, она обрабатывает неправильно (впрочем, со словом python справляется благополучно). Можете попробовать улучшить регулярное выражение, чтобы оно точнее выделяло слова.

Еще одна возможность улучшения – удалять из слов суффиксы, воспользовавшись алгоритмом выделения основы. Например, слово indexing при этом превращается в index, поэтому человек, который ищет слово index, получит также документы, содержащие слово indexing. Чтобы реализовать этот подход, необходимо выделять основы при индексировании документов и на этапе начальной обработки запроса. Реализация такого алгоритма на Python имеется в библиотеке Porter Stemmer по адресу http://www.tartarus.org/~martin/ PorterStemmer/index.html.

Добавление в индекс

Теперь мы готовы написать код метода addtoindex. Он вызывает две функции, написанные в предыдущем разделе, чтобы получить список слов на странице. Затем эта страница и все найденные на ней слова добавляются в индекс и создаются ссылки между словами и их вхождениями в документ. В нашем примере адресом вхождения будет считаться номер слова в списке слов. Вот код метода addtoindex: def addtoindex(self,url,soup): if self.isindexed(url): return print ‘Индексируется ‘+url

#    Получить список слов text=self.gettextonly(soup) words=self.separatewords(text)

#    Получить идентификатор URL urlid=self.getentryid(‘urllist’,’url’,url)

#    Связать каждое слово с этим URL for i in range(len(words)):

word=words[i]

if word in ignorewords: continue wordid=self.getentryid(‘wordlist’,’word’,word)

self.con.execute("insert into wordlocation(urlid,wordid,location) \ values (%d,%d,%d)" % (urlid,wordid,i))

Необходимо также написать код вспомогательной функции getentryid. От нее требуется лишь одно – вернуть идентификатор записи. Если такой записи еще нет, она создается и возвращается ее идентификатор:

def getentryid(self,table,field,value,createnew=True): cur=self.con.execute(

"select rowid from %s where %s=’%s’" % (table,field,value)) res=cur.fetchone( ) if res==None:

cur=self.con.execute(

"insert into %s (%s) values (‘%s’)" % (table,field,value)) return cur.lastrowid else:

return res[0]

И наконец необходимо написать код функции isindexed, которая определяет, есть ли указанная страница в базе данных и, если да, ассоциированы ли с ней какие-нибудь слова:

def isindexed(self,url): u=self.con.execute \

("select rowid from urllist where url=’%s’" % url).fetchone( ) if u!=None: # Проверяем, что страница посещалась v=self.con.execute(

‘select * from wordlocation where urlid=%%d’ % u[0]).fetchone( ) if v!=None: return True return False

Теперь можно снова запустить паука и дать ему возможность проиндексировать страницы по-настоящему. Это можно сделать в интерактивном сеансе:

>> reload(searchengine)

>> crawler=searchengine.crawler(‘searchindex.db’) >> pages= \

.. [‘http://kiwitobes.com/wiki/Categorical_list_of_prog ramming_languages.html’] >> crawler.crawl(pages)

Скорее всего, паук будет работать долго. Я предлагаю не дожидаться, пока он закончит, а загрузить готовую базу данных searchindex.db по адресу http://kiwitobes.com/db/searchindex.db и сохранить ее в одной папке с программой.

Если вы хотите удостовериться, что паук отработал правильно, проверьте записи, добавленные для какого-нибудь слова, сделав запрос к базе:

>> [row for row in crawler.con.execute(

.. ‘select rowid from wordlocation where wordid=1’)]

[( 1,), (46,), (330,), (232,), (406,), (271,), (192,),…

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

Запросы

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

поисковой машины, которая выполняет поиск. Сначала создайте в файле searchengine.py новый класс, который будет использоваться для поиска:

class searcher: def __init__(self,dbname):

self.con=sqlite.connect(dbname)

def __del__(self): self.con.close( )

Таблица wordlocation обеспечивает простой способ связать слова с документами, так что мы можем легко найти, какие страницы содержат данное слово. Однако поисковая машина была бы довольно слабой, если бы не позволяла задавать запросы с несколькими словами. Чтобы исправить это упущение, нам понадобится функция, которая принимает строку запроса, разбивает ее на слова и строит SQL-запрос для поиска URL тех документов, в которые входят все указанные слова. Добавьте следующую функцию в класс searcher:

def getmatchrows(self,q):

#       Строки для построения запроса fieldlist=’w0.urlid’ tablelist=”

clauselist=” wordids=[]

#       Разбить поисковый запрос на слова по пробелам words=q.split(‘ ‘)

tablenumber=0

for word in words: # Получить идентификатор слова wordrow=self.con.execute(

"select rowid from wordlist where word=’%s’" % word).fetchone( ) if wordrow!=None: wordid=wordrow[0] wordids.append(wordid) if tablenumber>0: tablelist+=’,’ clauselist+=’ and ‘

clauselist+=’w%d.urlid=w%d.urlid and ‘ % (tablenumber-1,tablenumber) fieldlist+=’,w%d.location’ % tablenumber tablelist+=’wordlocation w%%d’ % tablenumber clauselist+=’w%d.wordid=%d’ % (tablenumber,wordid) tablenumber+=1

#       Создание запроса из отдельных частей

fullquery=’select %s from %s where %s’ % (fieldlist,tablelist,clauselist)

cur=self.con.execute(fullquery)

rows=[row for row in cur]

return rows,wordids

Рис. 4.2. Соединение таблиц, выполняемое функцией getmatchrows

Таким образом, для двух слов с идентификаторами 10 и 17 формируется следующий SQL-запрос:

select w0.urlid,w0.location,w1.location from wordlocation w0,wordlocation w1 where w0.urlid=w1.urlid and w0.wordid=10 and w1.wordid=17

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

>> reload(searchengine)

>> e=searchengine.searcher(‘searchindex.db’) >> e.getmatchrows(‘functional programming’)

На первый взгляд функция довольно сложна, но, по существу, она просто создает по одной ссылке на таблицу wordlocation для каждого слова и выполняет соединение таблиц по идентификаторам URL (рис. 4.2).

([(1, 327, 23), (1, 327, 162), (1, 327, 243), (1, 327, 261), (1, 327, 269), (1, 327, 436), (1, 327, 953),..

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100