Web technologies and search

HTML, CSS and JavaScript, client and server side processing, indexing and PageRank.

A12.9Networks and the webA level30 min

Do this lesson in the simulator

A web page reaches your browser as three kinds of text: HTML for its content and structure, CSS for how it looks, and JavaScript for how it behaves. This lesson reads each, then asks where code should run: in the browser (client side) or on the web server (server side). The second half is about finding pages at all: how a search engine builds an index, and how Google's original PageRank algorithm decided which results to put first.

HTML

HTML (hypertext markup language) describes the content and structure of a page with tags. Most tags come in pairs, an opening tag and a closing tag, around the content they mark up. Tags can carry attributes that give extra information.

<!DOCTYPE html>
<html>
<head>
  <title>BugBot results</title>
  <link rel="stylesheet" href="style.css">
</head>
<body>
  <h1>Class results</h1>
  <p id="intro" class="note">Fastest runs this week.</p>
  <img src="bugbot.png" width="200" height="120" alt="A BugBot">
  <ul>
    <li>Ada: 12.4 s</li>
    <li>Sam: 13.1 s</li>
  </ul>
  <a href="https://lessons.bugbot.example">Back to the lessons</a>
  <form>
    <input type="text" id="runner" name="runner" value="">
    <input type="button" value="Add" onclick="addRunner()">
  </form>
  <script src="results.js"></script>
</body>
</html>
Tag Purpose
<html> the whole document
<head> information about the page, not shown in it: the <title> for the browser tab, <link> to a stylesheet, <meta> data
<body> everything shown on the page
<h1> to <h6> headings, from most to least important
<p> a paragraph
<img src="..."> an image; width and height set its size
<a href="..."> a hyperlink to another page
<ul>, <ol>, <li> an unordered (bulleted) list, an ordered (numbered) list, and a list item
<div> a division: a block that groups content so it can be styled or moved together
<form>, <input> a form, and a box, button or other control inside it
<script> JavaScript, written inside or loaded from a file

CSS

CSS (cascading style sheets) controls presentation: colours, fonts, sizes, borders and layout. Keeping style separate from content means one stylesheet can restyle a whole site, and pages load faster because the stylesheet is cached. A CSS rule is a selector and a block of property: value pairs:

body { font-family: Arial, sans-serif; background-color: #F4F4F4; }
h1 { color: navy; font-size: 28px; }
#intro { border-style: solid; border-width: 2px; border-color: #FF8000; }
.note { color: grey; width: 400px; }

An element selector (h1) styles every element of that kind. An id selector (#intro) styles the one element with id="intro"; an id must be unique in a page. A class selector (.note) styles every element with class="note", and many elements can share a class. CSS can be external (a separate .css file linked in the head), internal (in a <style> block) or inline (a style="..." attribute on one element).

JavaScript

JavaScript makes a page interactive. It runs in the browser and can read and change the page through the document object model, respond to events such as clicks, check form input before it is sent, and request data from a server without reloading.

function addRunner() {
  var name = document.getElementById("runner").value;
  if (name == "") {
    alert("Type a name first");
  } else {
    document.getElementById("intro").innerHTML = "Added " + name;
  }
}

Client side and server side

Client-side processing is done by the browser, on the user's own computer, usually in JavaScript. Server-side processing is done on the web server, in a language such as Python or PHP, before the response is sent.

Client side Server side
Speed immediate feedback with no round trip to the server each action needs a request and a response
Server load reduces the load on the server and the traffic on the network the server does all the work for every user
Security code is visible to the user and can be changed or switched off, so it cannot be trusted code and data stay on the server, out of the user's reach
Access to data cannot reach the server's database directly can query the database and keep secrets such as passwords
Compatibility depends on the user's browser supporting it works whatever browser the user has

So form validation is often done twice: on the client, so the user is told at once that the postcode is missing, and again on the server, because anyone can bypass the page and send any data they like.

Search engine indexing

A search engine cannot read the whole web each time someone searches. Instead, programs called crawlers (or spiders) visit pages in advance, following every link they find to reach new pages. For each page, the search engine records the words in it, and where they appear (title, headings, links, meta data), in an index: a data structure that maps each word to the list of pages containing it. A search then looks the words up in the index, which is fast however large the web is.

PageRank

The index finds every page that contains "robot". PageRank decides which of them to show first. Its idea is that a link from page T to page A is a vote for A, and a vote counts for more if T is itself important, and less if T links to many other pages as well. The original formula is:

PR(A) = (1 − d) + d × ( PR(T1)/C(T1) + … + PR(Tn)/C(Tn) )

  • T1 to Tn are the pages that link to A;
  • C(T) is the number of outbound links on page T, so T's vote is shared equally between the pages it links to;
  • d is the damping factor, usually 0.85: the probability that a person clicking at random follows a link rather than jumping to a random page.

Every page's rank depends on the ranks of others, so the algorithm starts every page at the same value (1) and iterates, recalculating every rank from the previous round's ranks, until the values stop changing.

Take four pages: A links to B and C; B links to C; C links to A; D links to C. In the first iteration, from all ranks 1:

  • PR(A) = 0.15 + 0.85 × (1/1) = 1.0, from C, which has one link
  • PR(B) = 0.15 + 0.85 × (1/2) = 0.575, from A, which has two links
  • PR(C) = 0.15 + 0.85 × (1/2 + 1/1 + 1/1) = 2.275, from A, B and D
  • PR(D) = 0.15, as nothing links to it
links = {"A": ["B", "C"], "B": ["C"], "C": ["A"], "D": ["C"]}
d = 0.85
rank = {page: 1.0 for page in links}
for iteration in range(1, 21):
    new = {}
    for page in links:
        votes = 0.0
        for other in links:
            if page in links[other]:
                votes = votes + rank[other] / len(links[other])
        new[page] = (1 - d) + d * votes
    rank = new
    if iteration in (1, 2, 20):
        print(iteration, {p: round(r, 3) for p, r in rank.items()})

Run this in the simulator

After 20 iterations the ranks settle at about A 1.49, B 0.78, C 1.58, D 0.15. C is ranked highest because three pages vote for it; A comes next because its only vote is the whole of C's high rank.

Task: index and rank

A small website has five pages. pages maps each page name to its text; links maps each page name to the list of pages it links to. Every page links to at least one other.

  1. Build an index: a dictionary mapping each word (split the text on spaces) to the list of pages that contain it, with no page listed twice for one word.
  2. Work out the PageRank of every page with d = 0.85. Start every page at 1.0 and do exactly 30 iterations, calculating each iteration's ranks only from the previous iteration's ranks.
  3. For each page, in the order of pages, print <page> <rank> with the rank to 2 decimal places.
  4. For each of the words robot and simulator, in that order, print search <word>: <pages>, the pages containing that word from highest rank to lowest, separated by single spaces.

That is 7 lines. The robot does not drive.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

pages = {
    "home": "bugbot lessons for your robot in python",
    "sim": "the robot simulator runs python in the browser",
    "kit": "buy a robot kit for your school",
    "blog": "news about the simulator and the kit",
    "faq": "questions about python and the robot",
}
links = {
    "home": ["sim", "kit", "faq"],
    "sim": ["home"],
    "kit": ["home", "sim"],
    "blog": ["sim", "kit"],
    "faq": ["home", "sim"],
}
D = 0.85
rank = {page: 1.0 for page in pages}

Challenges

  1. Add a page that links to faq only. Predict which ranks change before you run it.
  2. Stop iterating when no rank changes by more than 0.0001, and print how many iterations that took.
  3. Write the HTML for a page that lists the five pages as links, and CSS that shows the highest-ranked page's link in bold.