В продолжение статьи С чего начинается поисковик, или несколько мыслей про crawler
В предыдущей статье я немного порассказал про эксперименты с интенсивностью загрузки и работой Crawler’а, в общих чертах опишу DataFlow проекта до построения индекса, чтобы было понятно о чем я пишу. Каждый шаг я постараюсь описать подробно в соответствующей статье
Итак, скачанная страница первым делом попадает на выделение ссылок. Новые ссылки с текущего сайта попадают в локальную очередь для загрузки в текущей сессии, а на все другие сайты добавляются в общую очередь Crawler’а. В этой очереди содержаться только главные страницы сайтов.
После сбора достаточного количества страниц одного сайта запускается анализатор, выделяются паттерны, присутствующие на большинстве страниц сайта, и они вырезаются.
На выходе получаем тексты страниц без всего лишнего и сгруппированные по сайтам.
Все готовые страницы одного сайта складываю в каталог, который попадает к индексатору. Индексатор создает маленькую версию «прямого» индекса, состоящего из нескольких (10-1000) сайтов подготовленных на предыдущем этапе – парсит HTML, сопоставляет слова, упаковывает, считает метрики пословные. Прямой индекс – это таблица где по ID документа я могу получить список слов и всю информацию об их вхождениях в документ. Также к нему прикладываются БД слов (построенная из этого маленького количества документов) и ссылок (все еще не добавленные в общий индекс и потому еще не имеющие ID). Ссылки идут к модулю пересчета PR (в информации у ссылок участвуют слова и их веса), остальное на обновление обратного индекса. Объем кусочка, который индексатор подготовил, обычно 100-300Mb за час. И это без текстов страниц.
Подсчетом PR и различных метрик занимается отдельный модуль. Самое забавное что для подсчета PR удобнее хранить ссылки как строки, а не как ID т.к. далеко не все ссылки попадут в конечный индекс – забивать структуру хранения ссылок лишней информацией довольно глупо. Из-за этой особенности проще написать эту часть на Perl или подобном языке, который быстро работает со строками, либо придется организовать систему хранения большого кол-ва строк на структурном языке.
На выходе индексатора получаем упакованный кусок прямого индекса. Но нам надо построить обратный индекс, чтобы можно было быстро искать. Обратный индекс это таблица, в которой каждому слову сопоставлен отсортированный по релевантности или PR (как у гугла) список документов в которых это слово есть. Понятно, что просто так взять прямой индекс и перегнать его в обратный займет годы когда база вырастет, поэтому все время инкрементально обратный индекс и пара десятков кусков прямого индекса подготовленного на предыдущей стадии объединяются, а потом сортируются. Технически это происходит одновременно – отсортированная вставка в отсортированный список. Тут много моментов как устроить БД чтобы она это выдержала, как сделать чтобы не надо было каждый раз файлы на сотню гигов копировать туда сюда, как поместить в память необходимый кусок и тд.
Предварительно готовятся БД слов, метрик и всего прочего, так же инкрементально соединяя предыдущую версию с новой информацией. ID слов в мелком прямом индексе на ходу заменяются на те, которые соответствуют полной версии БД, и остальная информация аналогично.
При построении обратного индекса также дополняется отдельная БД хранящая Url страниц — это отдельная большая структура, слишком много записей надо хранить и иметь быстрый доступ по ID, доступ для последовательного чтения в рамках одного сайта, быстро проверять существование ссылки, в описании структур БД я раскрою этот вопрос.
На этапе перестроения обратного индекса нужны данные о PR, метриках страниц и всему прочему, что помогает сортировать результаты. На самом деле надо иметь только первые пару сотен тысяч результатов гарантировано отсортированными – если дело и дойдет до остальных – то это будет уже работа функции ранжирования.
Построенный обратный индекс уже можно использовать для поиска – выбираем списки слов из запроса, ищем пересечение – считаем коэффициенты, дистанцию между найденными словами, ну и сортируем исходя из функции ранжирования.
Еще немного из морфологии – сначала на основе морфологического словаря Зализняка выбираем наибольшую основу, отрезаем окончание, подставляем 1-ю словарную форму. Весь этот процесс собран в дерево для быстрого разбора по буквам, в конечных листьях содержатся варианты окончаний. Бежим по слову, параллельно спуская по дереву исходя из встреченной буквы, пока не дойдем до самого нижнего возможного листа – там, исходя из окончаний, подставляем нормализованное.
Если же нормальной формы не нашлось, то применяем стемминг – исходя из текстов книг скачанных с lib.ru, я построил таблицу частоты встречаемости окончаний, ищем наиболее встречаемое из подходящих (тоже деревом) и заменяем на нормальную форму. Стемминг хорошо работает, если слова не было в языке еще лет 5-10 назад – легко разберет «краулеры» в «краулер»
Полное содержание и список моих статей по поисковой машине будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
В предыдущей статье я немного порассказал про эксперименты с интенсивностью загрузки и работой Crawler’а, в общих чертах опишу DataFlow проекта до построения индекса, чтобы было понятно о чем я пишу. Каждый шаг я постараюсь описать подробно в соответствующей статье
Итак, скачанная страница первым делом попадает на выделение ссылок. Новые ссылки с текущего сайта попадают в локальную очередь для загрузки в текущей сессии, а на все другие сайты добавляются в общую очередь Crawler’а. В этой очереди содержаться только главные страницы сайтов.
После сбора достаточного количества страниц одного сайта запускается анализатор, выделяются паттерны, присутствующие на большинстве страниц сайта, и они вырезаются.
На выходе получаем тексты страниц без всего лишнего и сгруппированные по сайтам.
Все готовые страницы одного сайта складываю в каталог, который попадает к индексатору. Индексатор создает маленькую версию «прямого» индекса, состоящего из нескольких (10-1000) сайтов подготовленных на предыдущем этапе – парсит HTML, сопоставляет слова, упаковывает, считает метрики пословные. Прямой индекс – это таблица где по ID документа я могу получить список слов и всю информацию об их вхождениях в документ. Также к нему прикладываются БД слов (построенная из этого маленького количества документов) и ссылок (все еще не добавленные в общий индекс и потому еще не имеющие ID). Ссылки идут к модулю пересчета PR (в информации у ссылок участвуют слова и их веса), остальное на обновление обратного индекса. Объем кусочка, который индексатор подготовил, обычно 100-300Mb за час. И это без текстов страниц.
Подсчетом PR и различных метрик занимается отдельный модуль. Самое забавное что для подсчета PR удобнее хранить ссылки как строки, а не как ID т.к. далеко не все ссылки попадут в конечный индекс – забивать структуру хранения ссылок лишней информацией довольно глупо. Из-за этой особенности проще написать эту часть на Perl или подобном языке, который быстро работает со строками, либо придется организовать систему хранения большого кол-ва строк на структурном языке.
На выходе индексатора получаем упакованный кусок прямого индекса. Но нам надо построить обратный индекс, чтобы можно было быстро искать. Обратный индекс это таблица, в которой каждому слову сопоставлен отсортированный по релевантности или PR (как у гугла) список документов в которых это слово есть. Понятно, что просто так взять прямой индекс и перегнать его в обратный займет годы когда база вырастет, поэтому все время инкрементально обратный индекс и пара десятков кусков прямого индекса подготовленного на предыдущей стадии объединяются, а потом сортируются. Технически это происходит одновременно – отсортированная вставка в отсортированный список. Тут много моментов как устроить БД чтобы она это выдержала, как сделать чтобы не надо было каждый раз файлы на сотню гигов копировать туда сюда, как поместить в память необходимый кусок и тд.
Предварительно готовятся БД слов, метрик и всего прочего, так же инкрементально соединяя предыдущую версию с новой информацией. ID слов в мелком прямом индексе на ходу заменяются на те, которые соответствуют полной версии БД, и остальная информация аналогично.
При построении обратного индекса также дополняется отдельная БД хранящая Url страниц — это отдельная большая структура, слишком много записей надо хранить и иметь быстрый доступ по ID, доступ для последовательного чтения в рамках одного сайта, быстро проверять существование ссылки, в описании структур БД я раскрою этот вопрос.
На этапе перестроения обратного индекса нужны данные о PR, метриках страниц и всему прочему, что помогает сортировать результаты. На самом деле надо иметь только первые пару сотен тысяч результатов гарантировано отсортированными – если дело и дойдет до остальных – то это будет уже работа функции ранжирования.
Построенный обратный индекс уже можно использовать для поиска – выбираем списки слов из запроса, ищем пересечение – считаем коэффициенты, дистанцию между найденными словами, ну и сортируем исходя из функции ранжирования.
Еще немного из морфологии – сначала на основе морфологического словаря Зализняка выбираем наибольшую основу, отрезаем окончание, подставляем 1-ю словарную форму. Весь этот процесс собран в дерево для быстрого разбора по буквам, в конечных листьях содержатся варианты окончаний. Бежим по слову, параллельно спуская по дереву исходя из встреченной буквы, пока не дойдем до самого нижнего возможного листа – там, исходя из окончаний, подставляем нормализованное.
Если же нормальной формы не нашлось, то применяем стемминг – исходя из текстов книг скачанных с lib.ru, я построил таблицу частоты встречаемости окончаний, ищем наиболее встречаемое из подходящих (тоже деревом) и заменяем на нормальную форму. Стемминг хорошо работает, если слова не было в языке еще лет 5-10 назад – легко разберет «краулеры» в «краулер»
Полное содержание и список моих статей по поисковой машине будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
