Common Words By Number

Introduction

Zork had a second trick. Its story file holds 96 words and phrases that come up again and again (the, You, There, Unfortunately), once each, and wherever one occurs in a message, a single code stands in for it. The opening sentence of Zork I uses eight of them. This section does the same for BEACON, and then weighs everything part two has found.

A Table Of Common Words

Sixteen words, each with the space after it, are the commonest in BEACON's text, weighted by how much each would save:

Table: array[1..Count] of Str6 =
  ('the ', 'The ', 'door ', 'and ',
   'is ', 'You ', 'of ', 'iron ',
   'with ', 'light ', 'great ',
   'lamp ', 'in ', 'a ', 'to ',
   'from ');

BEACON's text uses only ordinary characters, all with codes below 128. So the codes 128 to 143 are free, and code 127 + N can stand for word N: the becomes one byte, 128.

Encoding And Decoding

Encode walks the message. At the start of a word, it tries every entry in the table; if one matches the text from there, it writes the code and jumps past the word. Otherwise it copies the character.

The test for the start of a word matters. Without it, is would match the end of This, and the the end of breathe. The text would still come back, but encoding would take longer.

Decode is short: each character of 128 or over is replaced by its word, and every other character is copied.

What It Saves, And What It Costs

the alone was replaced 51 times. Here is the beach, encoded, with each code shown as its number in braces:

{6}are on {14}strip {7}shingle at {1}foo
t {7}{1}cliffs. ...

Weighing It All

Part two has now tried five ways of keeping BEACON's text:

Zork's story file is 84,876 bytes, and the game reads it from the disc as you play (S16). It packs every letter and calls up common words by number, both at once, and every byte saved is a byte less to keep on the disc and to read from it.

BEACON is small. Its messages fit on the disc several times over, and nothing is gained by making the player wait half a second for every room. So BEACON keeps its messages in a typed file, one to a record, and Seeks straight to them: the fastest way, at the price of disc space it has plenty of. If the game grew to Zork's size, this section and the last are where to come back to.

The Code

program Common;
type
  Str255 = string[255];
  Str6 = string[6];
const
  Count = 16;
  Table: array[1..Count] of Str6 =
    ('the ', 'The ', 'door ', 'and ',
     'is ', 'You ', 'of ', 'iron ',
     'with ', 'light ', 'great ',
     'lamp ', 'in ', 'a ', 'to ',
     'from ');
var
  F: file of Str255;
  Msg, Code, Back: Str255;
  K, Chars, Bytes: Integer;
  Same: Boolean;

function Encode(S: Str255): Str255;
var
  T: Str255;
  I, J, Hit: Integer;
begin
  T := '';
  I := 1;
  while I <= Length(S) do
  begin
    Hit := 0;
    if (I = 1) or (S[I - 1] = ' ') then
      for J := 1 to Count do
        if Copy(S, I, Length(Table[J]))
           = Table[J] then
          Hit := J;
    if Hit > 0 then
    begin
      T := T + Chr(127 + Hit);
      I := I + Length(Table[Hit]);
    end
    else
    begin
      T := T + S[I];
      I := I + 1;
    end;
  end;
  Encode := T;
end;

function Decode(S: Str255): Str255;
var
  T: Str255;
  I: Integer;
begin
  T := '';
  for I := 1 to Length(S) do
    if S[I] >= #128 then
      T := T + Table[Ord(S[I]) - 127]
    else
      T := T + S[I];
  Decode := T;
end;

begin
  Assign(F, 'BEACON.MSG');
  Reset(F);
  Chars := 0;
  Bytes := 0;
  Same := True;
  for K := 1 to FileSize(F) do
  begin
    Read(F, Msg);
    Code := Encode(Msg);
    if Decode(Code) <> Msg then
      Same := False;
    Chars := Chars + Length(Msg);
    Bytes := Bytes + Length(Code);
  end;
  Writeln('Characters: ', Chars);
  Writeln('Encoded bytes: ', Bytes);
  Writeln('All came back: ', Same);
  Seek(F, 20);
  Read(F, Msg);
  Code := Encode(Msg);
  Writeln('Go');
  for K := 1 to 20 do
    Back := Decode(Code);
  Writeln('Decoded');
  Writeln(Copy(Back, 1, 38));
  Close(F);
end.

Starting from

A new work file COMMON, on the primer's disc.

What you should see

After about half a minute of encoding:

Characters: 2652
Encoded bytes: 2089
All came back: TRUE
Go

then about eleven seconds for twenty decodings, and

Decoded
You strike a match and hold it to the

Change One Thing

• Take out the start-of-word test, if (I = 1) or (S[I - 1] = ' ') then, so that the for loop runs at every character. Does every message still come back? Is the result smaller or bigger, and how long does it take?
• In Decode, change >= #128 to > #128. What does the check say, and which word has gone?
• Change the decoding loop to 1 to 1. How long does one decoding take?

Exercises

15.1 Count how many times each word in the table was used, and print the sixteen counts.

15.2 Print the encoded beach, with each code shown as its number in braces.

15.3 Time Encode of the winning message, five times.

Worked solutions are in Appendix II.

When It Goes Wrong

Summary

Sixteen common words as one-byte codes took BEACON's text to 79 per cent. Decoding is short to write but takes over half a second for a long message; encoding is slower, but done once. Zork, reading an 84,876-byte story from the disc, packed its letters and numbered its common words. BEACON, small enough not to need either, keeps each message whole in a typed file and goes straight to it.

Next

S16, How The Real Games Did It: everything the three games' discs showed, together.