Поисковик по нашим учебникам

Прошлая глава закончилась вопросом: как ответ на запрос приходит за доли секунды, если страниц в вебе миллиарды? Масштаб у задачи такой: Google пишет, что его индекс охватывает сотни миллиардов страниц и занимает больше ста миллионов гигабайт. Прочитать столько за время, пока вы моргаете, нельзя никакими машинами. Значит, ответ готовят заранее, ещё до того, как вопрос задан. Как это возможно, мы выясним самым надёжным способом — построим поисковик сами.

Искать будем по тому, что под рукой: по учебникам этого сайта. Это сам курс, который вы читаете, и «Царица наук» — курс математики: больше ста двадцати глав, почти семьсот тысяч слов и больше тысячи трёхсот ссылок между главами. Маленький интернет со своими страницами и гиперссылками. Поисковик будет расти версиями, и каждая версия чинит то, на чём споткнулась предыдущая. В конце вы получите работающий поиск, а вопрос номер семь — ответ.

Наш маленький интернет

Тексты глав собраны в песочницу курса скриптом: он прочитал файлы глав, выбросил код и формулы, разрезал каждую главу по разделам и выписал, какая глава на какую ссылается. Это снимок: поисковик знает учебники такими, какими они были в день сборки, и главы, написанные позже, ему неизвестны, пока скрипт не запустят снова. В снимок попала и эта глава — так что поисковик найдёт и сам себя. Большие поисковики живут с той же бедой: их индекс всегда немного отстаёт от веба.

Каждая страница — словарь: адрес id вида cs:hashing или math:eigen, название, ссылка на сайте и разделы с чистым текстом. Граф ссылок — словарь «страница → куда она ссылается», такой же, как граф метро в главе 19.

Паук

Прежде чем искать, поисковик должен узнать, какие страницы вообще существуют. Списка всех страниц веба нет ни у кого. Есть программа-паук (по-английски crawler, «ползун»): она скачивает страницу, вынимает из неё ссылки, ставит их в очередь, скачивает следующую — и так без конца. Это обход в ширину из главы 19, только граф заранее неизвестен и открывается по ходу. Запустим паука по нашим учебникам с двух стартовых страниц — с начала этого курса и с начала «Царицы наук».

Паук, начавший с этого курса, нашёл всё. Паук, начавший с математики, не нашёл ни одной главы этого курса: «Царица наук» на него не ссылается. Страниц, на которые не ведут ссылки, для паука не существует. Поэтому новый сайт добавляют в поисковик вручную или дают ему карту сайта — файл со списком всех адресов. А чтобы паук не обрушил чужой сервер тысячей запросов в секунду, в 1994 году Мартейн Костер предложил файл robots.txt: в корне сайта написано, куда паукам ходить можно и куда нельзя. По воспоминаниям писателя Чарльза Стросса, поводом стал написанный им плохо воспитанный паук, который нечаянно положил сервер Костера.

Версия 0.1: просмотреть всё

Страницы скачаны. Самый прямой поисковик просматривает их все подряд и проверяет, есть ли в тексте строка запроса.

На наших семи мегабайтах перебор работает быстро, за пару миллисекунд: проверку in Python выполняет на языке C. Но время растёт вместе с объёмом текста, и на всём индексе Google один запрос занял бы около года. Хуже того, перебор не понимает слов: на запрос «мир» он нашёл «программирования» и «ортонормированный», где «мир» сидит внутри. А о том, какая из десятков найденных страниц нужна, он не говорит ничего. Следующие версии чинят эти беды по одной, и первой — скорость.

Версия 0.2: указатель в конце книги

Слово в толстом учебнике ищут по предметному указателю в конце: «хеш-таблица — 211, 340, 517». Указатель составили заранее, один раз, и теперь любой поиск — одна строчка в нём. Google описывает свой индекс теми же словами: как указатель в конце книги, где есть строчка для каждого слова, которое встретилось на каждой странице.

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

Запрос из нескольких слов — это пересечение их списков: нужны страницы, где есть все слова. Списки отсортированы, поэтому пересекать их можно двумя пальцами, как в слиянии из главы 21: палец, стоящий на меньшем номере, шагает вперёд, а совпадение записывается в ответ. Шагов на это уходит столько, сколько номеров в двух списках. Начинать выгодно с самого короткого: дальше результат может только уменьшаться. Ответ пришёл за микросекунды, в десятки и сотни раз быстрее перебора, и это время определяется длиной списков, а общее число страниц и слов на него почти не влияет.

Индекс справился со скоростью и заодно, нечаянно, со второй бедой: «мир» теперь ищется как отдельное слово. Зато последние два запроса в ячейке показывают новую. «Сортировка слиянием» нашлась в нескольких главах, а «сортировкой слияния» — только там, где эти две формы стоят в тексте дословно, в том числе в этой самой главе: она тоже лежит в указателе. Для указателя «сортировка» и «сортировкой» — разные слова.

Версия 0.3: слова и их формы

Прежде чем класть текст в указатель, его режут на токены — слова, приведённые к одному виду: строчные буквы, «ё» заменена на «е», знаки препинания отброшены. Это мастерская чистки текста из главы 7; в модуле cs.search этим занята функция tokens. Но в русском у каждого слова десятки форм: «сортировка, сортировки, сортировке, сортировку, сортировкой, сортировок». Английскому поисковику проще: у английского слова форм немного.

Первое решение — отрезать окончания. Программу, которая приводит слово к основе, называют стеммером, от английского stem — «стебель, основа». Самый простой стеммер — список окончаний: отрезать самое длинное подходящее, если от слова останется хотя бы три буквы.

Десяток строк кода, и «сортировка», «сортировки», «сортировкой» сошлись в «сортировк», а все формы «графа» — в «граф». Но и ошибок видно сразу три сорта. «Сортировок» и «деревьев» не сошлись с остальными: в русском гласные бывают беглыми, и окончание тут ни при чём. «Лев» и «льва» не сойдутся никогда по той же причине, а «шёл» и «идти» — вообще разные основы. Это недоклейка. Бывает и переклейка: «мыло», «мыла» и «мыли» стали одним «мыл», хотя мыло и мытьё — разные слова. Без словаря и без смысла фразы этого не различить.

Есть и обратная сторона: слова, которые не помогают искать. «И», «в», «не», «что» — первые строчки закона Ципфа из главы 8 — стоят почти в каждой главе. Их списки вхождений самые длинные, а пользы от них нет. Такие слова называют стоп-словами; раньше поисковики их просто выбрасывали, а сегодня чаще оставляют, но почти не учитывают при ранжировании. Как «почти не учитывать» — первое, что нужно следующей версии.

Версия 0.4: кто первый

Индекс находит быстро, но выдаёт найденное в порядке номеров страниц. На запрос «хеш таблица» пришло больше десятка глав, и глава о хеш-таблицах в этом списке только третья. Нужно правило, по которому для этого запроса одна страница окажется важнее другой.

Первая мысль — считать, сколько раз слово встречается на странице: глава о хеш-таблицах повторяет «хеш» почти сотню раз, а глава о словарях — один раз. Это частота слова, term frequency, tf; чтобы длинные страницы не выигрывали только длиной, её делят на число слов страницы. Ещё в 1958 году Ханс Петер Лун, автор записки о хешировании из главы 16, предлагал выбирать значимые слова документа по частоте и так составлять рефераты автоматически. Но одной частоты мало: «и» встречается чаще «хеша» на любой странице. Нужна вторая половина.

Её в 1972 году нашла Карен Спарк Джонс из Кембриджа: слово тем ценнее для поиска, чем в меньшем числе документов оно встречается. Если слово есть во всех $N$ документах, оно ничего не различает; если в одном — указывает прямо на него. Мерой стала обратная документная частота $\text{idf} = \log \frac{N}{\text{df}}$, где df — число документов со словом. Произведение двух частот называют TF-IDF, а вес страницы для запроса — сумму TF-IDF его слов. Для эксперимента подбросим в коллекцию фальшивую страницу: слово «хеш», повторённое двести раз, и больше ничего.

В таблице idf «и» и даже «число» есть почти везде, и их вес — сотые доли; «хеш» есть меньше чем в каждой пятой главе, а «коллизия» и «Барроуз» — в считаных, и весят они больше всех. Стоп-слова ранжирование выключило само, без всякого списка. Но первая строка выдачи — позор: на первом месте фальшивка. У неё частота «хеша» — сто процентов, и TF-IDF не видит ничего подозрительного. В вебе так и делали: набивали страницу ключевыми словами, часто белым по белому, чтобы человек не видел, а поисковик видел.

Версия 0.5: насыщение

Вторая строка выдачи — исправление. Формулу BM25 вывели Стивен Робертсон, Карен Спарк Джонс и их коллеги для поисковой системы Okapi в Сити-университете Лондона; в нынешнем виде она сложилась в 1990-х. От TF-IDF она отличается двумя поправками. Первая — насыщение: вклад слова растёт с его частотой, но всё медленнее и упирается в потолок $k_1 + 1$. Десятое упоминание добавляет меньше первого, а двухсотое — почти ничего. Вторая — длина: частоту сравнивают со средней длиной страницы, и параметр $b$ решает, насколько строго.

$$\text{BM25} = \sum_{\text{слова запроса}} \text{idf} \cdot \frac{\text{tf} \cdot (k_1 + 1)}{\text{tf} + k_1 \left(1 - b + b \cdot \frac{\text{длина}}{\text{средняя длина}}\right)}, \qquad k_1 \approx 1{,}2, \ b \approx 0{,}75.$$

Фальшивка выбыла: её «хеш» упёрся в потолок, а слов «таблица» и «коллизия» у неё нет вовсе. Насыщение защищает и от честного многословия: страница, где слово встречается сто раз, не в сто раз полезнее той, где оно встречается раз пять. Тридцать лет спустя BM25 по-прежнему считают по умолчанию поисковые библиотеки вроде Lucene и Elasticsearch, а в полнотекстовом поиске SQLite, базы данных из главы 45, есть функция bm25().

Версия 0.6: голосование ссылками

BM25 судит страницу по её собственному тексту. А текст пишет её автор, и он может написать что угодно. Есть ли у страницы свойство, которое автор не может назначить себе сам?

Идея Брина и Пейджа — PageRank — умещается в одну фразу: страница важна, если на неё ссылаются важные страницы. Определение ходит по кругу, но у него есть наглядный смысл. Представьте читателя, который бесконечно бродит по учебникам: на каждой странице он щёлкает по случайной ссылке, а иногда ему надоедает, и он открывает случайную страницу из всех. Чем чаще он оказывается на странице, тем она важнее. В формуле Брина и Пейджа вероятность пойти по ссылке, а не заскучать, обозначена $d$ и названа коэффициентом затухания; по их словам, обычно её берут равной 0,85.

Если читатель гуляет долго, доля времени на каждой странице перестаёт меняться — и эти доли и есть PageRank. Считать их прогулкой долго и неточно. Есть путь короче: раздавать важность. Сначала у всех страниц она одинаковая. На каждом шаге страница отдаёт долю $d$ своей важности поровну тем страницам, на которые ссылается, а оставшиеся $1 - d$ раздаются всем, как прыжки заскучавшего читателя. Повторяем, пока числа не перестанут меняться. Это степенной метод: каждый шаг — умножение вектора важностей на матрицу ссылок, а ответ — её собственный вектор. Почему процесс всегда сходится и к одному и тому же ответу, доказывает глава о собственных векторах в «Царице наук»; нам остаётся посчитать.

Первая шестёрка — сплошь математика: последовательности, простые числа, иррациональность, комбинаторика. На эти главы ссылаются десятки других, и среди них — главы этого курса. А главы курса вместе собрали заметно меньше важности, чем их доля среди страниц: в снимке, по которому написана глава, — около 36 % важности при 52 % страниц. Причина видна в графе: курс CS ссылается на «Царицу наук», а она на курс — ни разу. Важность утекает по ссылкам в одну сторону и обратно не возвращается. Внутри курса наверху «Словарь и телеграф», «Хеш-таблица», «Сколько стоит программа» — на базовые главы ссылаются все последующие.

Сколько шагов понадобится, можно оценить заранее. Расстояние до точного ответа на каждом шаге сокращается по меньшей мере в $1/d$ раз: это и доказывает глава о собственных векторах. При $d = 0{,}85$ оценка обещает точность в миллиардные доли примерно за 130 шагов. На нашем графе хватило меньше, потому что оценка рассчитана на худший случай. Чем ближе $d$ к единице, тем медленнее сходимость, так что от $d$ зависят и смысл рейтинга, и цена его расчёта.

Ферма ссылок

PageRank придумали, чтобы автор не мог назначить своей странице важность сам. Но ссылки тоже можно делать самому. Возьмём главу 4, «Снова и снова», — она в нижней половине рейтинга. Создадим сорок пустых страниц, каждая из которых ссылается на неё, — так называемую ферму ссылок.

Сорок пустых страниц подняли главу из нижней половины таблицы на первое место. Механизм виден в формуле: каждая страница получает свою долю $\frac{1 - d}{N}$ от прыжков заскучавшего читателя, даже если на неё не ссылается никто, — и исправно передаёт её дальше по единственной ссылке. Фальшивая страница стоит почти ничего, а голос у неё есть. Десятилетиями так и продвигали сайты: фермы, сети блогов, ссылки, купленные пачками, комментарии со ссылками под чужими статьями.

Защиту Брин и Пейдж предложили в той же статье 1998 года: прыжки заскучавшего читателя можно направлять на одну страницу или небольшую группу, и тогда, как они писали, обмануть систему намеренно становится «почти невозможно». Последние две строки ячейки показывают, почему. Если читатель прыгает только на оглавления двух курсов, фальшивые страницы не получают ничего: на них не ведёт ни одна ссылка из доверенной части графа, а без входящей важности и раздавать нечего. Ферма потеряла голос: с доверенными прыжками место главы одно и то же, есть ферма или нет. На этой идее выросли и другие защиты — от «доверия», которое растекается от проверенных сайтов, до пометки rel="nofollow": с 2005 года ею помечают ссылки в комментариях и рекламе, чтобы поисковик их не засчитывал. Сегодня PageRank — лишь один из сотен признаков, по которым поисковики ранжируют страницы, и гонка между спамерами и поисковиками продолжается.

Версия 0.7: сборка

Осталось соединить текст и ссылки. Способов много; один из простых — умножить оценку BM25 на PageRank в некоторой степени: $\text{оценка} = \text{BM25} \cdot (N \cdot \text{PR})^{w}$. Множитель $N \cdot \text{PR}$ у средней страницы равен единице, у популярной больше, у глухой меньше, а показатель $w$ решает, насколько ссылки весомее текста: при $w = 0$ их нет вовсе. Модуль cs.search собирает в класс Engine всё, что мы написали: токены, основы, индекс со счётчиками, BM25 и PageRank. Вдобавок он выбирает для каждой найденной страницы раздел, где слов запроса больше всего, и вырезает из него кусок с первым из них — чтобы было видно, почему страница найдена.

Индекс по ста двадцати с лишним главам строится за доли секунды, поиск занимает миллисекунды, и поисковиком уже можно пользоваться. Поисковое поле ниже отправляет запрос на сервер курса, где работает тот же Engine, и показывает выдачу со ссылками прямо на нужный раздел.

Поиграйте с весом ссылок. При большом $w$ наверх лезут популярные главы «Царицы наук», даже если запрос о другом, — PageRank ничего не знает о запросе. При $w = 0$ решает только текст, и короткая страница, где нужные слова мелькнули несколько раз, может обойти главу, целиком посвящённую теме. Промышленные поисковики подбирают такие веса, глядя на поведение людей: на какой результат нажимают, возвращаются ли назад к выдаче. Сегодня это делают машинным обучением, к которому мы придём в главе 63.

Версия 0.8: подсказки

Последний штрих — подсказки, пока вы печатаете. В главе 27 мы собрали бор по словам «Войны и мира» и обещали, что он вернётся в поисковике. Соберём бор по двадцати тысячам самых частых слов учебников, и в каждом узле, где кончается слово, запомним, сколько раз оно встретилось.

Подсказки верные, но однообразные: на «хеш» — пять форм одного слова. Лечится тем же стеммером: из всех слов с одной основой показывать только самое частое. Так и сделано в поле поиска выше. А на «кэ», кроме кэша, вылез Артур Кэли из «Царицы наук» — поисковик ищет по всем учебникам сразу. В больших поисковиках подсказки строят по запросам, которые люди уже набирали, и поддерево целиком не обходят: в каждом узле бора заранее хранят несколько лучших продолжений, чтобы ответить, пока палец ещё над клавишей.

Как это работает на миллиардах

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

Заранее: обход, указатель, PageRank. Паук обходит веб без остановки, указатель перестраивается кусками, а PageRank пересчитывают по всему графу ссылок. Указатель строят сортировкой: из каждой страницы выписывают пары «слово, номер страницы» и сортируют их по слову — в статье 1998 года сортировка указателя занимала около суток на четырёх машинах. Пары, которые не помещаются в память, сортируют по кускам, а готовые куски сливают: слияние двух списков мы видели в главе 21, а слияние многих сразу, кучей, — в задаче «Слить отсортированное» из главы 18.

Во время запроса: несколько строк указателя. Слова запроса ищутся в словаре — хеш-таблице из главы 16 или дереве из главы 46, — а их списки вхождений пересекаются двумя пальцами. Время зависит от длины списков, а не от размера веба. Списки хранятся сжатыми: номера страниц идут по возрастанию, и вместо самих номеров пишут разности между соседними — маленькие числа, которые занимают по байту, а то и меньше. Это приёмы из прошлой главы, и выигрывают от них не одни диски: сжатый указатель помещается в оперативную память, а память, как мы видели в главе 34, в тысячи раз ближе диска.

Тысячи машин сразу. Указатель всего веба не помещается ни в одну машину, поэтому его режут на части по страницам: каждая машина держит указатель своей доли страниц. Запрос рассылается всем частям одновременно, каждая находит у себя лучшие десять, и ответы сливаются — кучей из главы 18, которая выбирает лучшие из лучших. Каждая часть к тому же размножена на несколько машин: одна сломалась — отвечает соседняя, как в главе 44.

Ранжирование в два прохода. Дешёвая формула вроде нашей — BM25 и PageRank — быстро отбирает несколько тысяч кандидатов, и только их пересортировывает дорогая модель с сотнями признаков. А частые запросы и вовсе не считаются заново: ответ на «погода» лежит в кэше.

Поисковик ищет заранее, до того как вопрос задан. Паук обходит веб по ссылкам и скачивает страницы. Из их текстов строится обратный индекс: для каждого слова — отсортированный список страниц, где оно встречается; строят его сортировкой пар «слово — страница», хранят сжатым, а слова находят по хеш-таблице. Запрос превращается в несколько обращений к индексу и пересечение коротких списков, поэтому время ответа зависит от длины этих списков, а не от числа страниц в вебе. Найденное упорядочивается по тексту и по ссылкам. По тексту — формулами вроде TF-IDF и BM25, где редкие слова весят больше, а повторы насыщаются. По ссылкам — PageRank: доля времени, которую случайный читатель проводит на странице, посчитанная заранее степенным методом. Индекс разрезан на тысячи машин, которые ищут параллельно, их лучшие ответы сливает куча, а подсказки строит бор. Доли секунды хватает потому, что прочесть нужно лишь несколько строк заранее составленного указателя.

Задачи

Три задачи — три детали поисковика: указатель, ранжирование по тексту и ранжирование по ссылкам. В каждой есть большой тест с секундомером.

Напишите build_index(docs): по списку текстов — обратный индекс, словарь «слово → список номеров документов, где оно есть», номера по возрастанию и без повторов. Слова — функция words из заготовки: строчные буквы и цифры. И search(index, query) — номера документов, где есть все слова запроса, по возрастанию. Если какого-то слова нет ни в одном документе или в запросе нет слов, ответ — пустой список. Последний тест строит индекс по 20 000 документов и задаёт 3000 запросов; на всё — три секунды.

Идите по документам по порядку. Если номер документа уже последний в списке слова — слово встретилось в этом документе второй раз, и записывать номер снова не нужно. Так списки получаются отсортированными сами собой.

Для поиска возьмите списки всех слов запроса (повторы в запросе не важны — set), отсортируйте их по длине и пересекайте, начиная с самого короткого: результат может только уменьшаться. Слово, которого нет в индексе, — это пустой список, а не KeyError: index.get(t, []).

Пересекать можно двумя пальцами, как в главе, или множествами. А вот проверять каждый документ на каждый запрос нельзя: 3000 запросов по 20 000 документов — шестьдесят миллионов проверок.

Построение указателя — один проход по всем словам, $O(\text{слов})$. Запрос стоит столько, сколько номеров в списках его слов, и при старте с короткого списка часто намного меньше: если в самом редком слове три документа, после первого пересечения останется не больше трёх. Ранний выход по пустому результату — бесплатная мелочь, которая на живых запросах экономит много.

Напишите tf_idf_rank(docs, query): номера документов, упорядоченные по убыванию оценки TF-IDF для запроса. Слова — та же функция words. Для слова $t$ запроса и документа $D$: $\text{tf} = \frac{\text{сколько раз } t \text{ в } D}{\text{сколько всего слов в } D}$, $\text{idf} = \ln \frac{N}{\text{df}}$, где $N$ — число документов, df — сколько из них содержат $t$. Оценка документа — сумма $\text{tf} \cdot \text{idf}$ по разным словам запроса. В ответ попадают только документы с положительной оценкой; при равных оценках раньше идёт меньший номер. Документ без слов — пустой — не получает ничего.

Сначала один проход по всем документам: разрежьте каждый на слова и посчитайте df — для каждого слова, в скольких документах оно есть. Внутри документа слово считается один раз: set(слова).

Потом для каждого документа — счётчик слов и сумма по словам запроса, которые в нём есть. Слово, которое есть во всех документах, даёт $\ln 1 = 0$, и документ, где есть только такие слова, в ответ не попадает. Пустой документ пропускайте до деления на его длину.

Порядок «по убыванию оценки, при равенстве — по номеру» даёт сортировка пар (-оценка, номер).

Повторы слов в запросе ничего не добавляют — так договорились в условии, и set об этом заботится. TF-IDF не требует, чтобы в документе были все слова запроса: документ с одним редким словом может обойти документ, где есть все, но частые. Поисковики обычно сначала отбирают документы со всеми словами, как в предыдущей задаче, а потом уже ранжируют.

Напишите pagerank(links, d=0.85). Граф — словарь «страница → список страниц, на которые она ссылается»; все страницы из списков есть и среди ключей, ссылок на себя нет. Верните словарь «страница → PageRank» с суммой 1, с точностью до $10^{-6}$. Читатель с вероятностью $d$ идёт по случайной ссылке со страницы, а с вероятностью $1 - d$ открывает случайную страницу из всех. Подвох в страницах без ссылок: в наших учебниках таких нет, а в вебе их много. Со страницы без ссылок читатель всегда уходит на случайную страницу из всех. Последний тест — 5000 страниц и почти 30 000 ссылок за три секунды.

Возьмите pagerank из главы и проследите, что она делает со страницей без ссылок: её важность никуда не передаётся и исчезает, сумма становится меньше единицы.

Соберите важность всех страниц без ссылок в одну копилку, умножьте на $d$ и раздайте поровну всем $N$ страницам — так же, как раздаются прыжки заскучавшего читателя.

Остановка: считайте, насколько изменился вектор за шаг — сумму модулей разностей, — и останавливайтесь, когда изменение меньше $10^{-10}$. Это меньше требуемой точности с хорошим запасом: ошибка сокращается в $1/d$ раз за шаг.

Один шаг — проход по всем ссылкам, $O(N + \text{ссылок})$, а шагов нужно $O(\log(1/\varepsilon) / \log(1/d))$: при $d = 0{,}85$ и $\varepsilon = 10^{-10}$ — не больше полутораста. Страница без ссылок в матричной записи — нулевой столбец, и без поправки матрица перестаёт быть матрицей переходов; поправка «уходит куда угодно» превращает этот столбец в столбец из одинаковых $1/N$. Так же поступают и в главе о собственных векторах «Царицы наук».

Куда дальше

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

Одного наш поисковик не умеет. Скрипт, собиравший учебники, выбросил из них код. Для поисковика все ячейки и программы курса — шум: русских слов в них нет, а for и print стоят в каждой второй. Но программа — тоже текст, и в нём есть смысл, которого не видит ни стеммер, ни BM25. Для мешка слов строка a, b = b, a % b — пять однобуквенных слов, а для Python — шаг алгоритма Евклида. Чтобы это понять, нужно читать текст не как мешок слов, а по правилам языка, на котором он написан. Языков программирования тысячи. Почему их так много и чем они различаются — в следующей главе; с неё начинается путь, в конце которого вы напишете программу, понимающую другую программу.