Как проранжировать список в питоне
Перейти к содержимому

Как проранжировать список в питоне

  • автор:

Реализация поискового движка с ранжированием на Python (Часть 3)

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

Ранжирование результатов запросов

Заключительным шагом в построении поискового движка является создание системы для ранжирования документов по их релевантности к запросу. Это наиболее сложная часть, поскольку она не имеет прямого технического решения: она требует творчества и вашего собственного взгляда. В этой мы реализуем TF-IDF ранжирование (от англ. TF — term frequency (частота слова) и IDF — inverse document frequency (обратная частота документа)), которое является одним из простейших способов сортировки наших документов. В этой части не будет никакого кода, но вы можете изучить финальную версию движка на GitHub. Мы только изучим теорию TF-IDF, а его реализация довольно проста, причем большая часть работы делается во время построения индекса.

Так что, термин «частота» является первой частью нашей систему ранжирования? Ну, это именно то, что приходит на ум, когда вы его слышите: количество раз, которое встречается каждое слово в конкретном документе. Термин частота, как метрика, не учитывает запрос: он предполагает, что документ — это просто амбивалентный набор маркеров, и точное представление о нём можно получить всего лишь пересчитав, сколько раз каждый маркер (слово) встречается. Это не совсем точное предположение, но оно широко используется в области классификации документов. Формально, он больше известен как модель “мешок слов”.

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

Но подождите! Есть, в настоящее время, большой недостаток в нашей модели. Рассмотрим эти два документа: «Путь они едят торт» и «Пусть они едят тор. Путь они едят торт». Они одинаковы, если не считать того, что второй — просто повторяющийся первый, но их векторное представление очень различно: [1, 1, 1, 1] по сравнению с [2, 2, 2, 2]. Чтобы решить эту проблему, мы превращаем каждый вектор в единичный вектор путем деления его величины (рассчитывается путем извлечения квадратного корня из суммы квадратов каждой записи в векторе), “нормализуем” его. Это превратит наши предыдущие векторы в [½, ½, ½, ½] и [½, ½, ½, ½], делая их такими, какими мы и намерены.

Однако, этого ещё не до достаточно. Частота слова является фатальным недостатком (это гармония для любой греческой трагедии). Этот недостаток заключается в том, что «мешок» рассматривает каждый термин как в равной степени важные в представлении документов. Но это не так: слово “и” говорит нам намного меньше о документе, чем слова “Шекспир” или “хламидиоз”. Но слово «и» встречается гораздо чаще, чем слово “хламидиоз” (по крайней мере в документах, которые читал я), что создаёт ложное подобие сходства между документами (поскольку почти все они содержат слово «и»).

Чтобы избежать этого мы должны кое-что добавить в нашу систему ранжирования: обратную частоту документа. Определим частоту, с которой слово встречается в документе, как Dt, а t — как частоту, с которой слово встречается во всех проиндексированных документах. Тогда, если у нас есть K документов, то обратная частота документа (Lt) этого слова будет отношением K к Dt: общее количество документов, делённое на количество документов, в которых встречается это слово.

Есть ещё один, последний нюанс: это корректирует слишком сильно. Если у нас есть 10 документов (K = 10) и одно слово встречается в этих документах 10 раз, а другое слово всего 1 раз, то получается, что второе слово в 10 раз важнее первого. Линейное поведение этой функции является слишком радикальным, и будет искусственно снижать сходство из-за слишком сильной корректировки. Чтобы исправить это, мы просто добавим функцию натурального логарифма, которая будет «выравнивать» нашу функцию, делая её коррекцию более плавной. Теперь наша функция выглядит так: в наборе из K документов, для некоторого слова t, Lt = ln(K/Dt), где Dt — это частота документа слова t, а ln — это функция натурального логарифма.

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

Теперь, чтобы объединить термины частота слова (в документе) и обратная частота документа в одну метрику мы можем их просто перемножить. То есть, вес каждого маркера (слова, термина) в нашем наборе документов определяется как Tt×Lt: частота, с которой встречается слово в документе и обратная частота документа.

Теперь, если у нас есть набор из K документов и все эти документы имеют общее число N уникальных терминов, то наши документы будут представлены как вектора, каждый длинны N, где значение каждой записи (которое соответствует термину) равно частоте, с которой термин встречается в документе, умноженной на обратную частоту документа для этого термина в наборе документов. Каждый вектор будет иметь значение 0 для терминов, не встречающихся в документе (помните, что наши вектора представляют все уникальные термины во всём наборе документов). Обратная частота документа никогда не будет равна 0, потому что это уровень сбора метрик.

Теперь мы сделаем то же самое и для запросов: мы будем представлять его в виде вектора в N-мерном пространстве, как и документы, и вычислять TF-IDF для каждого термина в запросе. Очевидно, это будет более редким (разбросанным), чем в документах.

Небольшое отступление. Попробуем рассчитать показатель подобия между запросом и его результирующем множеством, и ранжировать документы в результирующем множестве за счёт этого. Есть множество различных подходов к этому, но я буду использовать здесь то, что называется коэффициентом Отиаи (cosine similarity), который по сути просто берет скалярное произведение запроса и вектора документа в результирующем множестве и делит это на произведение величин этих двух векторов, который возвращает косинус угла между этими векторами (я мог неправильно объяснить формулу «на словах», поэтому, если вам интересно, можете прочитать статью на Википедии и этот вопрос на StackOverflow для уточнения). Это особенно полезный показатель, так как он не берёт во внимание величины двух векторов при вычислении сходства (в отличие, скажем, Евклидова расстояния), что весьма важно, когда у вас есть один очень разреженный вектор (запрос), и другой значительно менее разреженный вектор (наш документ).

  1. Во-первых нужно заранее рассчитать значение TF и IDF для каждого термина, и построить вектор длинны N для каждого документа, используя произведение TF на IDF в качестве записи.
  2. Затем, мы вычисляем запрос, и получить в результате набор соответствующих документов (с использованием ранее описанной методики).
  3. После этого мы вычисляем вектор запроса, который также имеет длину N и использует произведение TF×IDF в качестве каждой из этих записей.
  4. Затем, мы рассчитываем схожесть запроса и каждого документа в результирующем множестве (через коэффициент Отиаи), и получить балл для каждого документа.
  5. Мы сортируем документы по этому баллу.
Заключение

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

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

Как ни крути, это конец статьи. Если у вас есть какие-либо отзывы или вопросы, вы можете оставить комментарий к оригинальной статье или написать автору на электронную почту/facebook/любую другую новомодную социальную сеть, которую используют ваши дети в настоящее время.

  • поисковые технологии
  • поисковый движок
  • поисковые алгоритмы
  • google
  • перевод

Метод List.sort в Python

Из этого урока вы узнаете о методе сортировки списка Python. Вы увидите, как использовать его со списками с помощью примеров.

Синтаксис, используемый в следующем разделе, предназначен для Python 3. Вы можете изменить его на любые другие версии Python.

Метод sort выполняет сортировку элементов списка в восходящем или нисходящем направлении. Его синтаксис выглядит следующим образом:

List_name.sort(key = …, reverse = . )

Когда метод sort() вызывается без аргументов, по умолчанию он сортируется в порядке возрастания. У него нет возвращаемого значения.

Он просто возвращается к следующей строке, не возвращая никакого вывода.

Обратите внимание, что это не связано со встроенной функцией sorted(). Метод sort изменяет старый список, тогда как sorted() создает новую отсортированную последовательность.

Как работает метод sort

Когда мы вызываем этот метод без аргументов, он перебирает элементы списка в цикле и переставляет их в порядке возрастания.

Если в качестве аргумента указать «reverse = true», список будет отсортирован в порядке убывания.

Основной параметр — это шаги, которые должен пройти метод при сортировке списка элементов. Значение, данное ключу, может быть функцией или простым вычислением и т.д.

Сортировка списка чисел в порядке возрастания
Natural_numbers = [1,4,23,3,2,1,0,9,7] Natural_numbers.sort() print(Natural_numbers) # [0, 1, 1, 2, 3, 4, 7, 9, 23]
Сортировка списка чисел в порядке убывания
Natural_numbers = [1,23,4,25,22,3,4,5,9,7,5] Natural_numbers.sort(reverse = True) print(Natural_numbers) # [25, 23, 22, 9, 7, 5, 5, 4, 4, 3, 1]
Сортировка списка строк в порядке возрастания
Fruits = ["Apple", "Banana", "Tomato", "Grapes"] Fruits.sort() print(Fruits) # ['Apple', 'Banana', 'Grapes', 'Tomato']
Сортировка списка строк по убыванию
Fruits = ["Apple", "Banana", "Tomato", "Grapes"] Fruits.sort(reverse = True) print(Fruits) # ['Tomato', 'Grapes', 'Banana', 'Apple']
Сортировка списка с помощью функции (по возрастанию)
# Сортируем на основе 2-го элемента def keyFunc(item): return item[1] # Неупорядоченный список unordered = [('b', 'b'), ('c', 'd'), ('d', 'a'), ('a', 'c')] # Сортировка списка с помощью ключа unordered.sort(key=keyFunc) # Вывести отсортированный список print('Ordered list:', unordered)
Ordered list: [('d', 'a'), ('b', 'b'), ('a', 'c'), ('c', 'd')]
Сортировка списка с помощью функции (по убыванию)
def keyFunc(item): return item[1] unordered = [('b', 'b'), ('c', 'd'), ('d', 'a'), ('a', 'c')] unordered.sort(key=keyFunc, reverse = True) print('Ordered list:', unordered)
Ordered list: [('c', 'd'), ('a', 'c'), ('b', 'b'), ('d', 'a')]

Сортировка словаря по значению и/или ключу в Python

Сортировка словарей производится при помощи встроенной функцией sorted() и происходит немного сложнее чем сортировка списков или кортежей.

Сортировка словаря по ключу.

Функция sorted() работает со всеми объектами, которые поддерживают итерирование. Словарь, в свою очередь при итерировании, выдает только ключи, но нам необходимо получить исходный отсортированный словарь, а не только отсортированные ключи. Следовательно из словаря необходимо получить итерацию [(key, val), (key, val), . ] , затем отсортировать ее по значению key и преобразовать обратно в словарь.

Список кортежей (key, val) можно получить методом словаря dict.items() .

>>> d = 'b': 9, 'a': 3, 'c': 7> # получаем итерацию кортежей `(key, val)` >>> d.items() # dict_items([('b', 9), ('a', 3), ('c', 7)]) # то что нужно 

Так как значение key стоит первым, то и ключ для сортировки укажем как lambda x: x[0] , где x — это кортеж (key, val)

# исходный словарь >>> d = 'b': 9, 'a': 3, 'c': 7> # собственно сама сортировка >>> sorted_tuple = sorted(d.items(), key=lambda x: x[0]) # получили отсортированный список кортежей, # отсортированных по первому значению >>> sorted_tuple # [('a', 3), ('b', 9), ('c', 7)] # преобразовываем обратно в словарь dict(sorted_tuple) #

Сортировка словаря по значению.

Применяя методику сортировки описанную выше, можно легко догадаться как сортировать словарь по значению. Для этого просто укажем в качестве ключа сортировки индекс значения словаря в полученном списке кортежей: lambda x: x[1] , где x — это кортеж (key, val)

>>> d = 'b': 9, 'a': 3, 'c': 7> >>> sorted_tuple = sorted(d.items(), key=lambda x: x[1]) >>> sorted_tuple # [('a', 3), ('c', 7), ('b', 9)] # преобразовываем обратно в словарь >>> dict(sorted_tuple) #

Для получения ключа сортировки из dict.items() , так же можно использовать функцию operator.itemgetter() :

>>> d = 'b': 9, 'a': 3, 'c': 7> >>> import operator >>> sorted_tuple = sorted(d.items(), key=operator.itemgetter(1)) >>> sorted_tuple # [('a', 3), ('c', 7), ('b', 9)] >>> dict(sorted_tuple) #
  • ОБЗОРНАЯ СТРАНИЦА РАЗДЕЛА
  • Представления словарей dict.keys, dict.values и dict.items
  • Исходный словарь для представления dictview.mapping
  • Получение списка ключей словаря list(dict)
  • Количество элементов в словаре len(dict)
  • Доступ к значению словаря по ключу dict[key]
  • Добавление/изменение значения словаря по ключу key
  • Удаление значения словаря по ключу
  • Проверка наличия/отсутствия ключа key в словаре dict
  • Проверка наличия/отсутствия значения value в словаре Python
  • Проверка наличия/отсутствия пары (key, value) в словаре dict
  • Итерирование по ключам и значениям словаря Python
  • Метод dict.clear(). Очистить словарь
  • Метод dict.copy(), копия словаря
  • Метод dict.fromkeys(), словарь с ключами по умолчанию
  • Метод dict.get(), значение по умолчанию если ключа нет
  • Метод dict.items(), список кортежей
  • Метод dict.keys(), список ключей словаря
  • Метод dict.values(), список значений словаря
  • Метод dict.pop()
  • Метод dict.popitem(), получить пару ключ/значение
  • Метод dict.setdefault(), получает/вставляет значение ключа
  • Метод dict.update(), обновление/дополнение словаря
  • Объединение двух словарей в новый словарь Python
  • Сортировка словаря по значению и/или ключу
  • Обратный порядок/реверс словаря reversed(dict)
  • Генератор словаря и его использование
  • Фильтр словаря по ключам и/или значениям
  • Словарь как фабрика функций

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

Дай 10 !)

воскресенье, 5 октября 2014 г.

Поиск и ранжирование

Сегодня мы рассмотрим систему полнотекстового поиска, она позволяют искать слова в большом наборе документов и сортируют результаты поиска по релевантности найденных документов запросу. Алгоритмы полнотекстового поиска относятся к числу важнейших среди алгоритмов коллективного разума. Новые идеи в этой области помогли сколотить целые состояния. Широко распространено мнение, что своей быстрой эволюцией от академического проекта к самой популярной поисковой машине в мире система Google обязана прежде всего алгоритму ранжирования страниц PageRank.

Что такое поисковая машина

Итак, давайте же создадим здоровую конкуренцию мировым поисковикам!) Статья так же будет полезна начинающим SEO специалистам, т.к. покажет некоторые величины, которые могут влиять на позиции вашего сайта в поиске.

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

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

Ну и последний шаг – это, конечно, возврат ранжированного списка документов в ответ на запрос. Имея индекс, найти документы, содержащие заданные слова, сравнительно несложно; хитрость заключается в том, как отсортировать результаты. Можно придумать огромное количество метрик, и недостатков в них.

Итак, для данной задачи нам потребуется DB (PostgreSQL) и Python (библиотека Grab). А за источник индексирования, новостную ленту rambler’а.

Все функции, описаные ниже, у меня являются методами классов, с такой инициализацией:

class Indexer: def __init__(self): self.conn = psycopg2.connect("dbname='postgres' user='postgres' password='120789' host='localhost'") self.cur = self.conn.cursor() self.cur.execute("set search_path to 'rambler_search'") self.grab = Grab() def __del__(self): self.conn.close() def dbcommit(self): self.conn.commit()

Код паука

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

Эта функция в цикле обходит список страниц, вызывая для каждой функцию addtoindex. Далее она получает все ссылки на данной странице и добавляет их URL в список newpages. В конце цикла newpages присваивается pages, и процесс повторяется.

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

# Начинаем со списка страниц для индексации # опускаемся в глубину на 2 уровня def crawl(self, pages, depth=2): rambler_news_href_pattern = re.compile(r'(^http:\/\/news\.rambler\.ru\/[\d]+)') for i in range(depth): newpages=<> for page in pages: try: self.grab.go(page) except: print "Could not open %s" % page continue try: article_text = '' # текст статьи for paragraph in self.grab.tree.xpath("//p[contains(@class, 'b-article__paragraph')]"): article_text += paragraph.text_content() self.addtoindex(page, article_text) # записываем в базу текст статьи с индексацией links = self.grab.tree.xpath("//a") for link in links: if ('href' in link.attrib): url = urljoin(page, link.attrib['href']).split('#')[0]# делаем полную ссылку и удаляем часть за # если она есть match = rambler_news_href_pattern.findall(url) if match: url = match[0] if url[0:4] == 'http' and not self.isindexed(url): newpages[url] = 1 linkText = link.text_content() # текст ссылки self.addlinkref(page, url, linkText) # записываем в базу текст ссылки с индексацией self.dbcommit() except Exception, e: print "Could not parse page %s" % page, e pages = newpages

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

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

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

Подождите запускать программу – нужно сначала подготовить базу данных. Схема простого индекса состоит из пяти таблиц. Первая (url_list) – это список проиндексированных URL. Вторая (word_list) – список слов, а третья (word_location) – список мест вхождения слов в документы. В оставшихся двух таблицах хранятся ссылки между документами. В таблице link хранятся идентификаторы двух URL, связанных ссылкой, а в таблице link_words есть два столбца – word_id и link_id – для хранения слов, составляющих ссылку. Вся схема изображена на рисунке ниже. Код запросов приводить не буду, должны ведь и вы поработать)))

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

Для решения данной задачи, воспользуемся простейшей функцией. Мы не будем вводить стоп слова, которые не нужно индексировать, а просто введем ограничение на длину слова в 3 символа, тем самым убрав предлоги и другой мусор (хоть и пострадают всякие мелкие слова, типа «мир», «тир», «пир»).

def getwords(html): words = [] for split_str in html.split(): t = re.split("[\s;:\-_*\". ()'&#«»]", split_str) words += [a.lower() for a in t if a != '' and len(a) > 3] return words

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

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

def addtoindex(self, url, text): if self.isindexed(url): return # если уже индексирована - пропускаем print 'Indexing %s' % url # Получаем слова из текста words = getwords(text) # Получаем id url'а url_id = self.getentryid('url_list', 'url', url) # Связываем слова с этим урлом for i, word in enumerate(words): # пронумеруем слова word_id = self.getentryid('word_list', 'word', word) self.cur.execute("insert into word_location(url_id, word_id, location) values (%d, %d, %d)" % (url_id, word_id, i)) self.dbcommit()

Хорошо, теперь нужно описать функцию getentryid — возвращающую id записи из бд и isindexed — проверяющую, не индексировали ли мы эту страницу раньше.

# Узнаем id записи в БД, если нет # иначе записываем и возвращаем новый def getentryid(self, table, field, value, createnew=True): self.cur.execute("select id from %s where %s = '%s'" % (table, field, value)) cur = self.cur.fetchone() if not cur: # print (table, field, value) self.cur.execute("insert into %s (%s) values ('%s') returning %s.id" % (table, field, value, table)) cur = self.cur.fetchone() self.dbcommit() return cur[0] else: return cur[0] # Возвращаем True, если посещали страницу def isindexed(self, url): self.cur.execute("select id from url_list where url = '%s'" % url) u = self.cur.fetchone() if u: # Проверяем, что паук посещал страницу self.cur.execute("select count(1) from word_location where url_id = %d" % u[0]) v = self.cur.fetchone() if v[0]: return True return False

Последняя функция, необходимая нам для начала индексирования — это addlinkref. Как следует из ее названия, она заносит ссылки и слова из которых они состоят к нам в БД.

def addlinkref(self, urlFrom, urlTo, linkText): words = getwords(linkText) from_id = self.getentryid('url_list', 'url', urlFrom) to_id = self.getentryid('url_list', 'url', urlTo) if from_id == to_id: return self.cur.execute("insert into link(from_id, to_id) values (%d, %d) returning link.id" % (from_id, to_id)) link_id = self.cur.fetchone()[0] for word in words: word_id = self.getentryid('word_list', 'word', word) self.cur.execute("insert into link_words(link_id, word_id) values (%d, %d)" % (link_id, word_id))

Ну что же, на этом этапе мы можем запустить паука и создать базу данных)

Запросы

Теперь, когда у нас есть материал, с которым можно работать, необходимо написать сам поисковик. Начнем мы с малого, грубого поиска, по абсолютному вхождению фразы в новость.

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

def get_match_rows(self, query): select_query_add = [] join_query_add = [] where_query_add = [] main_search_query = """ SELECT wl0.url_id, %s FROM word_location wl0 %s WHERE %s """ query_words = getwords(query) query_word_ids = [] for query_word in query_words: self.cur.execute("select id from word_list where word = '%s'" % query_word) query_word_id = self.cur.fetchone() if query_word_id: query_word_ids.append(query_word_id[0]) if query_word_ids: for position, query_word_id in enumerate(query_word_ids): if position: join_query_add.append('JOIN word_location wl%d ON wl%d.url_id = wl%d.url_id' % (position, position-1, position)) select_query_add.append('wl%d.location' % position) where_query_add.append('wl%d.word_id = %d' % (position, query_word_id)) main_search_query = main_search_query % (', '.join(select_query_add), ' '.join(join_query_add), ' and '.join(where_query_add)) self.cur.execute(main_search_query) search_results = self.cur.fetchall() return search_results, query_word_ids

Данная функция всего лишь создает строгий JOIN, типа такого:

SELECT wl0.url_id, wl0.location, wl1.location FROM word_location wl0 JOIN word_location wl1 ON wl0.url_id = wl1.url_id WHERE wl0.word_id = 2734 and wl1.word_id = 2698

В результате, получаем список кортежей и список с id слов. Каждый кортеж — это сто список вида (id новости, позиция 1го слова, позиция 2го слова. )

Ранжирование по содержимому

Итак, худо-бедно, но мы научились искать по индексу. Однако возвращаем мы их в том порядке, в котором они посещались пауком. Чтобы решить эту проблему, необходимо как-то присвоить страницам ранг относительно данного запроса и уметь возвращать их в порядке убывания рангов.

  • Частота слов

Количество вхождений в документ слова, указанного в запросе, помогает определить степень релевантности документа.

Основная тема документа, скорее всего, раскрывается ближе к его началу.

Если в запросе несколько слов, то они должны встречаться в документе рядом.

Самые первые поисковые машины (кстати rambler.ru) часто работали только с подобными метриками и тем не менее давали пристойные результаты. Давайте добавим следующие методы:

# Функция, которая взвешивает результаты def get_scored_list(self, rows, word_ids): total_scores = if rows: # Список весовых функций weight_functions = [ ] for (weight, scores) in weight_functions: for url in total_scores: total_scores[url] += weight * scores[url] return total_scores # Возвращает полный урл по id def get_url_name(self, url_id): self.cur.execute("select url from url_list where % url_id) return self.cur.fetchone()[0] # Основная функция поиска def search(self, search_sentence): search_results, word_ids = self.get_match_rows(search_sentence) scores = self.get_scored_list(search_results, word_ids) ranked_scores = [(score, url) for (url, score) in scores.items()] ranked_scores.sort() ranked_scores.reverse() for (score, url_id) in ranked_scores[0:10]: print '%f\t%s' % (score, self.get_url_name(url_id)) return word_ids, [r[1] for r in ranked_scores[0:10]]

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

Функция нормализации

Все рассматриваемые ниже функции ранжирования возвращают словарь, в котором ключом является идентификатор URL, а значением – числовой ранг. Иногда лучшим считается больший ранг, иногда – меньший. Чтобы сравнивать результаты, получаемые разными методами, необходимо как-то нормализовать их, то есть привести к одному и тому же диапазону и направлению.
Функция нормализации принимает на входе словарь идентификаторов и рангов и возвращает новый словарь, в котором идентификаторы те же самые, а ранг находится в диапазоне от 0 до 1. Ранги масштабируются по близости к наилучшему результату, которому всегда припи- сывается ранг 1. От вас требуется лишь передать функции список рангов и указать, какой ранг лучше – меньший или больший:

def normalize_scores(self, scores, smallIsBetter=0): vsmall = 0.00001 # Avoid division by zero errors if smallIsBetter: minscore = min(scores.values()) return else: maxscore = max(scores.values()) if maxscore == 0: maxscore = vsmall return return scores

Отлично! Пора заняться весовыми функциями, для которых мы и придумали эту нормализацию.

Весовые функции

Частота слов

Метрика, основанная на частоте слов, ранжирует страницу исходя из того, сколько раз в ней встречаются слова, упомянутые в запросе. Если я выполняю поиск по слову python, то в начале списка скорее получу страницу, где это слово встречается много раз, а не страницу о музыканте, который где-то в конце упомянул, что у него дома живет питон.

def frequency_score(self, rows): counts = for row in rows: counts[row[0]] += 1 return self.normalize_scores(counts)

Чтобы активировать ранжирование документов по частоте слов, измените строку функции get_scored_list, где определяется список weight_functions, следующим образом:

weight_functions = [(1.0,self.frequency_score(rows))]

Запустите поиск снова и радуйтесь!)

Расположение в документе

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

def location_score(self, rows): locations = <> for row in rows: loc = sum(row[1:]) if locations.has_key(row[0]): if loc < locations[row[0]]: locations[row[0]] = loc else: locations[row[0]] = loc return self.normalizescores(locations, smallIsBetter=1)

Расстояние между словами

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

def distance_score(self, rows): mindistance = <> # Если только 1 слово, любой документ выигрывает if len(rows[0]) mindistance = <> for row in rows: dist = sum([abs(row[i]-row[i-1]) for i in xrange(2, len(row))]) if mindistance.has_key(row[0]): if dist < mindistance[row[0]]: mindistance[row[0]] = dist else: mindistance[row[0]] = dist return self.normalize_scores(mindistance, smallIsBetter=1)

Использование внешних ссылок на сайт

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

Простой подсчет ссылок

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

def inbound_link_score(self, rows): unique_urls = inbound_count = <> for url_id in unique_urls: self.cur.execute('select count(*) from link where to_id = %d' % url_id) inbound_count[url_id] = self.cur.fetchone()[0] return self.normalize_scores(inbound_count)

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

Алгоритм PageRank

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

Теоретически алгоритм PageRank (названный по фамилии одного из его изобретателей Лари Пейджа (Larry Page)) рассчитывает вероятность того, что человек, случайно переходящий по ссылкам, доберется до некоторой страницы. Чем больше ссылок ведет на данную страницу с других популярных страниц, тем выше вероятность, что экспериментатор чисто случайно наткнется на нее. Разумеется, если пользователь будет щелкать по ссылкам бесконечно долго, то в конце концов он посетит каждую страницу, но большинство людей в какой-то момент останавливаются. Чтобы учесть это, в алгоритм PageRank введен коэффициент затухания 0,85, означающий, что пользователь продолжит переходить по ссылкам, имеющимся на текущей странице, с вероятностью 0,85.

Давайте рассмотрим пример:

Вычисление PageRank страницы A

Каждая из страниц B, C и D ссылается на A, и для них ранг уже вычис- лен. На странице B есть ссылки еще на три страницы, а на странице C – на четыре. D ссылается только на A. Чтобы вычислить ранг A, берем ранги (PR) каждой ссылающейся на A страницы, делим их на общее число ссылок на этой странице, складываем получившиеся значения, затем умножаем результат на коэффициент затухания 0,85 и добавляем минимальную величину 0,15. Вот как производится вычисление PR(A):

PR(A) = 0,15 + 0,85 × (PR(B)/ссылки(B) + PR(C)/ссылки(C) + + PR(D)/ссылки(D))
= 0,15 + 0,85 × (0,5/4 + 0,7/5 + 0,2/1) = 0,15 + 0,85 × (0,125 + 0,14 + 0,2)
= 0,15 + 0,85 × 0,465
= 0,54525

Обратите внимание, что D дает больший вклад в ранг A, чем B или C, хотя ее собственный ранг меньше. Это вызвано тем, что D ссылается только на A и, значит, привносит в результат свой ранг целиком.

Несложно, да? Увы, имеется тут небольшая ловушка – в данном при- мере для всех страниц, ссылающихся на A, уже вычислен ранг. Но невозможно вычислить ранг страницы, пока неизвестны ранги ссылающихся на нее страниц, а эти ранги можно вычислить, только зная ранги страницы, которые ссылаются на них. Так как же вычислить значение PageRank для множества страниц, ранги которых еще неизвестны?

Решение состоит в том, чтобы присвоить всем страницам произвольный начальный ранг (в программе ниже взято значение 1,0, но на самом деле точная величина несущественна) и провести несколько итераций. После каждой итерации ранг каждой страницы будет все ближе к истинному значению PageRank, как бы сходиться к некоему пределу, который и есть действительный PR. Количество необходимых итераций зависит от числа страниц.

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

# Вычисляем PageRank страниц def calculate_page_rank(self, iterations=20): START_PR = 1 self.cur.execute('update url_list set page_rank = %d' % START_PR) self.db_commit() for i in range(iterations): print "Iteration %d" % (i) self.cur.execute('select id from url_list') for url_id, in self.cur.fetchall(): # Конечный PR зависит от START_PR и этого базового pr pr = 0.15 self.cur.execute('select distinct from_id from link where to_id = %d' % url_id) # Перебираем все страницы, ссылающиеся на данную for linker, in self.cur.fetchall(): # Получаем PR ссылающейся страницы self.cur.execute('select page_rank from url_list where % linker) linking_pr = self.cur.fetchone()[0] # Получаем общее количество ссылок на ссылающейся странице self.cur.execute('select count(*) from link where from_id = %d' % linker) linking_count = self.cur.fetchone()[0] pr += 0.85 * (linking_pr/linking_count) self.cur.execute('update url_list set page_rank = %f where % (pr, url_id)) self.db_commit()

Итак, запустили - вычислили, пора написать весовую функцию, использующую данную величину.

def page_rank_score(self, rows): page_ranks = for row in rows: self.cur.execute('select page_rank from url_list where % row[0]) page_ranks[row[0]] = self.cur.fetchone()[0] return self.normalize_scores(page_ranks)

Использование текста ссылки

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

def link_text_score(self, rows, word_ids): link_scores = word_ids_string = ','.join(map(str, word_ids)) url_ids_string = ','.join(set([str(row[0]) for row in rows])) self.cur.execute(''' select sum(u_l.page_rank), l.to_id from link l join link_words l_w on l.id = l_w.link_id join url_list u_l on u_l.id = l.from_id where word_id IN (%s) and l.to_id IN (%s) group by l.to_id''' % (word_ids_string, url_ids_string)) for sum_pr_url_from, url_id in self.cur.fetchall(): link_scores['url_id'] = sum_pr_url_from return self.normalize_scores(link_scores)

Функция выбирает ссылки со словами поиска, которые ведут на новости, в которых они употребляются. Суммирует их PageRank's и возвращет этот навесок.

Вывод в продолжение

Поздравляю, вот мы и написали своего поискового робота!

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

Стоит заметить, что таких метрик может быть целая уйма (учет жирности написания слов, кол-во времени проведенного на странице и т.д.)! Не зря поисковики и их браузеры, так пристально следят за нашими действиями). Так что и Вы, придумывайте и улучшайте качество поиска! А в следующей статье, мы попробуем его немного поучить.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *