Маша, давайте подумаем о том, как работает поисковик в интернете. По-теории он должен создать свою базу данных, в которой будет отмечено, что на таком-то сайте такая и такая информация. И если человек введет такое-то слово, то ему надо под его запрос вывести такие-то ссылки... Но вот вопрос в чем! Как можно за 0,25 сек проверить такую базу данных, в которой только 4 370 000 записей соответствовало нужному запросу? Как это сделать?
Давайте думать вместе.Начнем с примитивнейшего поисковика, который может найти слово или совокупность слов, но не в состоянии найти фразу или, скажем совокупность слов в заданной последовательности.
А потом мы вместе будем думать дальше.
Такой примитивный поисковик действительно может работать быстро.
Естественно, он не будет по запросу заходить в миллионы сайтов и читать их.
Но он создаст несколько таблиц.
1. Таблица сайтов (блоков) где каждому блоку будет присвоен номер. Т.е. таблица с номером как индекс и линком на блок, как содержимое этого индекса.
Каждый новый блок получает свой номер, естественно.
2. Таблица слов.
Эта таблица - более сложная.
Индекс для неё - слово и все слова просортированы (для конкретного языка слов не так много - единицы миллионов)
А данными для каждого слова будет список номеров блоков, где это слово встречается. В принципе эту информацию можно сжать, введя, например, ещё и тип записи - если слово встречается редко - список номеров блоков, где встречается, если очень часто - список блоков, где не встреч ается, если средне - битвектор, где 1-ми будут помечены индексы, где встречаются, 0-ми - остальное.
Тогда слово в такой таблице найти просто и быстро...
Записан