![Архитектура Google
The Anatomy of a Large-Scale Hypertextual Web Search
Engine [Brin, Page, 1998]](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-6-320.jpg)
![– Регулярное выражение извлечения URL
URL_PATTERN = "^(https?://)?(www)?.?
([a-z0-9-_&+-]+(?:.[a-z0-9-_&
+-]+){1,3})(?::(d+))?((?:/[a-z0-9-_
&+-.%]+)+/?)?(?:?([a-z0-9-_&
+-%.;=]+))?”;](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-14-320.jpg)
![• Прямой просмотр всей коллекции документов –
дорогостоящая операция. Не имеет смысла, когда
корпус документов 102 и более.
• Структура данных позволяющая ускорить скорость
поиска по корпусу документов.
• Позволяет по каждому слову найти все документы и
позиции, в которых они встречаются.
• Структура
<termID, cf =
[ docID => pos1,
docID => pos2, pos3 ]>, <termID, cf..](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-19-320.jpg)
![Токенизация
Обычно, поисковые системы выделяют слова в
тексте как последовательность символов [a-zа-я].
Минусы?](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-22-320.jpg)
![Токенизация
Обычно, поисковые системы выделяют слова в
тексте как последовательность символов [a-zа-я].
Минусы?
– Термины: C#, C++
– Специфические названия: 1+1
– Даты: 2015/01/10](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-23-320.jpg)
![Решение
Обрезать окончание слова (привести к наиболее
близкому значению инфинитива)
ponies => ponie
[Одесса, одесский, одесское] => [одесс, одесск,
одесск]](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-29-320.jpg)
![Алгоритм поиска
1. Разбить поисковый запрос на лемы (termID)
2. Получить в индексе документы (docID),
содержащие все лемы (termID).
3. Отсортировать документы по критериям (зачем
показывать документ, где существует всего одно
вхождения слова [в том случае, если есть
варианты лучше]?).](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-34-320.jpg)
![Поиск в индексе
<7:рецепт, 5 = [ 107; 200; 320 ... ]>,
<109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...>
7:рецепт и 109:пирог - { }](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-35-320.jpg)
![Поиск в индексе
<7:рецепт, 5 = [ 107; 200; 320 ... ]>,
<109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...>
7:рецепт и 109:пирог - { }](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-36-320.jpg)
![Поиск в индексе
<7:рецепт, 5 = [ 107; 200; 320 ... ]>,
<109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...>
7:рецепт и 109:пирог - { }](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-37-320.jpg)
![Поиск в индексе
<7:рецепт, 5 = [ 107; 200; 320 ... ]>,
<109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...>
7:рецепт и 109:пирог - { }](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-38-320.jpg)
![Поиск в индексе
<7:рецепт, 5 = [ 107; 200; 320 ... ]>,
<109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...>
7:рецепт и 109:пирог - { 107; }](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-39-320.jpg)
![Поиск в индексе
<7:рецепт, 5 = [ 107; 200; 320 ... ]>,
<109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...>
7:рецепт и 109:пирог - { 107; }](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-40-320.jpg)
![Поиск в индексе
<7:рецепт, 5 = [ 107; 200; 320 ... ]>,
<109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...>
7:рецепт и 109:пирог - { 107; }](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-41-320.jpg)
![Поиск в индексе
<7:рецепт, 5 = [ 107; 200; 320 ... ]>,
<109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...>
7:рецепт и 109:пирог - { 107; 320 }](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-42-320.jpg)
![Поиск в индексе
<7:рецепт, 5 = [ 107; 200; 320 ... ]>,
<109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...>
7:рецепт и 109:пирог - { 107; 320 ... }](https://image.slidesharecdn.com/random-150525143201-lva1-app6891/85/-43-320.jpg)
диплом
- 1. Разработка поисковой машины для индексации гипертекстовый документов глобальной сети Интернет Ложковой Г.В.
- 2. Поисковая машина • Набор программно-аппаратных компонентов с интерфейсом, предоставляющим возможность поиска информации. • Веб-поисковая машина ведет поиск информации в гипертекстовых документах, размещенных в глобальной сети Интернет. А это более ≈1012 документов.
- 3. • Любая поисковая система состоит из трех компонентов: поискового робота, поискового индекса и обработчика пользовательских запросов (интерфейс). • Главный секрет коммерческих поисковых систем – формула ранжирования (соответсвия документа поисковому запросу).
- 5. Анализ существующих поисковых машин сложен тем, что внутренняя структура всех поисковых систем является коммерческой тайной.
- 6. Архитектура Google The Anatomy of a Large-Scale Hypertextual Web Search Engine [Brin, Page, 1998]
- 9. Цель Обойти документы, скачать и проанализировать. В случае обнаружения новой ссылки при анализе сайта, она попадает в список веб-адресов робота.
- 10. Требования • Высокая скорость скачивания документов. • Работать постоянно. • Контроль частоты обращения к документам, чтобы исключить возможность блокировки IP адреса сервера поисковой машины, либо создать дополнительную нагрузку на веб-сервер. • Обработка исключительных ситуаций: возможность возобновлять работу с минимальными потерями данных, после незапланированного отключения.
- 11. Алгоритм работы 1. Получить следующий документ для обхода. 2. Закачать документ. 3. Найти все ссылки (href). 4. Отфильтровать список ссылок(уже просмотренна, :javascript, :mailto…). 5. Добавить новые ссылки в очередь обхода. 6. Перейти к следующему документу.
- 12. Извлечение URL Хоть на первый взгляд процесс извлечения URL из документа кажется простым, но он осложнен особенностями оформления HTML документов. URL может быть описан как HTTP://www.Example.com/ или так http://www.example.com/a%c2%b1b http://www.example.com/%7Eusername/ http://www.example.com:80/bar.html http://www.example.com/../a/b/../c/./d.html http://208.77.188.166/ http://www.example.com/foo//bar.html /about example.com/#about ../our-company.html https://news.example.com/green-dresses-for- every-day-155672.html category/health/070223/html/category/ business/070302/html/category/community/ 070413/html/FAQ.htm /diplom/prez.pp
- 13. Нормализация URL Процесс, при котором URL приводится к единообразному виду, чтобы определить эквивалентность двух синтаксически различных URL-адресов • Перевести в нижний регистр. • Добавление конечного слеша /. • Удаление сегмента точек .././page.php. • Удаление стандартных главного индекса (index.html, default.aspx). • Удаление #, :mailto, :javascript.
- 14. – Регулярное выражение извлечения URL URL_PATTERN = "^(https?://)?(www)?.? ([a-z0-9-_&+-]+(?:.[a-z0-9-_& +-]+){1,3})(?::(d+))?((?:/[a-z0-9-_ &+-.%]+)+/?)?(?:?([a-z0-9-_& +-%.;=]+))?”;
- 15. Реализация • Две очереди: главных страниц, внутренних страниц. • ≈ 1600 одновременно работающих потоков. • HTTP/HTTPS GET запрос к серверам для получения документа. • Регулярное выражения для получения URL на странице.
- 16. Очереди обхода Доменов содержит главные страницы сайтов Цель найти как можно больше сайтов Страниц содержит внутренние страницы сайтов Цель получить как можно больше информации
- 17. Выводы Данные поискового робота: 1. Список ссылок, которые надо посетить. 2. Данные, скачанных документов (тела документов) с мета-информацией. 3. Веб-граф.
- 18. Поисковый индекс
- 19. • Прямой просмотр всей коллекции документов – дорогостоящая операция. Не имеет смысла, когда корпус документов 102 и более. • Структура данных позволяющая ускорить скорость поиска по корпусу документов. • Позволяет по каждому слову найти все документы и позиции, в которых они встречаются. • Структура <termID, cf = [ docID => pos1, docID => pos2, pos3 ]>, <termID, cf..
- 20. Структура данных интуитивно знакомая каждому
- 21. Индексация 1. Получить текст документа. 2. Разделить на слова (Токенизация). 3. Удалить стоп-слова. 4. Привести к нормальной форме (Нормализация). 5. Назначить каждому слову termID. 6. Связать termID с docID. 7. Сохранить позиции вхождений в документе.
- 22. Токенизация Обычно, поисковые системы выделяют слова в тексте как последовательность символов [a-zа-я]. Минусы?
- 23. Токенизация Обычно, поисковые системы выделяют слова в тексте как последовательность символов [a-zа-я]. Минусы? – Термины: C#, C++ – Специфические названия: 1+1 – Даты: 2015/01/10
- 24. Токенизация Допустим, что слово – это последовательность любых UNICODE символов между популярными разделителями (перевод строки, пробел, точка, запятая…)
- 25. Плюсы решения Не требуется отдельно выделять из текста номера телефонов, даты, термины.
- 26. Минусы решения В индексе много последовательностей символов, не принадлежащих к естественным языкам – больше требуемой памяти для обработки.
- 27. Минусы решения В индексе много последовательностей символов, не принадлежащих к естественным языкам – больше требуемой памяти для обработки. Плюс? Можно искать и по ним.
- 28. Нормализация При поиске требуется учитывать как можно больше возможных форм слова, как идентичные. красная = красное = красные Например, красивые розы = красивая роза
- 29. Решение Обрезать окончание слова (привести к наиболее близкому значению инфинитива) ponies => ponie [Одесса, одесский, одесское] => [одесс, одесск, одесск]
- 30. (ist|an|ian|ean|ism|er|or|ee|eer|ant|ent|ar|ard|ier|ment| ade|hood|cy|acy|age|ing|ence|ance|ion|1on|i1on|a1on|sion| al|dom|ness|ty|ity|ancy|ency|ry|ics|ess|e3e|ese|ie|let|th| ture|ure|lure|sure|ssure|ty|ity|sis|ed) (ий|ии|ия|ов|ей|ев|иев|ию|ам|ям|иям|ом|ем|ием|ами| ями|иями|ии|ах|ях|ях|иях|ый|ая|ое|ые|ого|ой|ого|ых| ому|ой|ую|ым|ыми|ом|ых|ий|яя|ее|ие|ей|его|их|ей|им| ими|ем|их|ист|изм|ась|ись|чик|онный) (а|е|ё|и|о|у|ы|э|ю|я|ь|ъ) (а|i|у|ею|я|и|евi|овi|ом|ову|ям|iв|ях|еш|ємо|єте|є|єш| iмо|ять|ите|имо|iте|iмо|ик|йної|ійні|ії|н|ури|||||||||)
- 31. Стоп-слова Как поступать с высокочастотными словами? но|та|до|вы|да|из|ты|от|не 1. Присутствуют в каждом документе. 2. Не имеют смыслового веса (кроме запросов - цитат). 3. “Можно” не учитывать.
- 32. Поиск
- 33. Поиск Поиск в интернете состоит из двух больших частей: 1. Подготовка поискового индекса (Индексация). 2. Поиск ответа на конкретный запрос в индексе.
- 34. Алгоритм поиска 1. Разбить поисковый запрос на лемы (termID) 2. Получить в индексе документы (docID), содержащие все лемы (termID). 3. Отсортировать документы по критериям (зачем показывать документ, где существует всего одно вхождения слова [в том случае, если есть варианты лучше]?).
- 35. Поиск в индексе <7:рецепт, 5 = [ 107; 200; 320 ... ]>, <109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...> 7:рецепт и 109:пирог - { }
- 36. Поиск в индексе <7:рецепт, 5 = [ 107; 200; 320 ... ]>, <109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...> 7:рецепт и 109:пирог - { }
- 37. Поиск в индексе <7:рецепт, 5 = [ 107; 200; 320 ... ]>, <109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...> 7:рецепт и 109:пирог - { }
- 38. Поиск в индексе <7:рецепт, 5 = [ 107; 200; 320 ... ]>, <109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...> 7:рецепт и 109:пирог - { }
- 39. Поиск в индексе <7:рецепт, 5 = [ 107; 200; 320 ... ]>, <109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...> 7:рецепт и 109:пирог - { 107; }
- 40. Поиск в индексе <7:рецепт, 5 = [ 107; 200; 320 ... ]>, <109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...> 7:рецепт и 109:пирог - { 107; }
- 41. Поиск в индексе <7:рецепт, 5 = [ 107; 200; 320 ... ]>, <109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...> 7:рецепт и 109:пирог - { 107; }
- 42. Поиск в индексе <7:рецепт, 5 = [ 107; 200; 320 ... ]>, <109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...> 7:рецепт и 109:пирог - { 107; 320 }
- 43. Поиск в индексе <7:рецепт, 5 = [ 107; 200; 320 ... ]>, <109:пирог, 16 = [ 68; 80; 107; 190; 202; 320 ...> 7:рецепт и 109:пирог - { 107; 320 ... }
- 44. Ранжирование Характеристики влияющие на позицию в списке? • Наличие слов в документе. • Частота слов. • Наличие в заголовке. • Расположение в документе (позиция в тексте). • Близость слов друг к другу (расстояние между словами запроса в документах).
- 45. Частота слов в документе TF (term frequency — частота слова) — отношение числа вхождения слова к количеству всех слов документа. Чем чаще входит слово в документ — тем оно важнее для данного документа. IDF (inverse document frequency — обратная документная частота) — инверсия частоты, с которой слово встречается во всех документах. То есть если данное слово встречается практически в каждом документе, то оно общеупотребимо и менее важно для поиска.
- 46. Выводы • Полнофункциональная поисковая система – это сложно… но интересно. • Ядро поисковой машины – обратный индекс + и алгоритмы его сжатия и построения • От качества работы поискового робота зависит количество доступных документов в поиске