Splitting Into Words, Two Ways

Introduction

A tidy line is one string: TAKE THE BRASS LANTERN. The parser wants four strings, one word each, so that it can look each one up. There are two natural ways to take a line apart in Turbo Pascal, and they give exactly the same words. They do not take the same time.

The Words Go In An Array

W: array[1..20] of Str12;
N: Integer;

N says how many of W are in use. A line of 40 characters cannot hold more than 20 words, so 20 is enough, and twelve letters is longer than any word BEACON knows.

The First Way: Let Turbo Find The Spaces

Add a space to the end of the line, so that every word, the last included, has a space after it. Then, until the line is used up:

1. P := Pos(' ', S) finds the first space.
2. If it is not the very first character, Copy(S, 1, P - 1) is a word.
3. Delete(S, 1, P) throws away the word and its space.

The test in step 2 is for a doubled space: two spaces together make an empty "word" between them, and the test skips it.

The added space matters. Without it, the last word has no space after it, Pos gives 0, and Delete(S, 1, 0) deletes nothing, so the loop never ends.

The Second Way: Walk Along The Line

Look at each character in turn. A character that is not a space, and comes after a space or at the very start, begins a new word: add one to N and start W[N] empty. Every non-space character is then added to the end of W[N].

This way never changes the line, and copes with doubled spaces without any special test.

Which Is Faster

The program below splits the same line 500 times each way, so that the difference is big enough to see. Watch the screen.

The walk looks less like work, but it is slower. W[N] := W[N] + S[I] builds a new string every time it adds one letter, and a word of seven letters is seven of those. Pos, Copy and Delete are part of Turbo itself, and each handles a whole word in one call. Where Turbo has a routine that does the job, it is usually quicker than the same job written in Pascal. Exercise 6.2 tries a third way, and you can see whether it proves the rule.

The Code

program Split;
type
  Str40 = string[40];
  Str12 = string[12];
var
  Line: Str40;
  W: array[1..20] of Str12;
  N, K: Integer;

procedure SplitPos(S: Str40);
var
  P: Integer;
begin
  N := 0;
  S := S + ' ';
  while S <> '' do
  begin
    P := Pos(' ', S);
    if P > 1 then
    begin
      N := N + 1;
      W[N] := Copy(S, 1, P - 1);
    end;
    Delete(S, 1, P);
  end;
end;

procedure SplitWalk(var S: Str40);
var
  I: Integer;
begin
  N := 0;
  for I := 1 to Length(S) do
    if S[I] <> ' ' then
    begin
      if (I = 1) or (S[I - 1] = ' ') then
      begin
        N := N + 1;
        W[N] := '';
      end;
      W[N] := W[N] + S[I];
    end;
end;

procedure Show;
var
  I: Integer;
begin
  for I := 1 to N do
    Write('[', W[I], ']');
  Writeln;
end;

begin
  Line := 'TAKE THE  BRASS LANTERN';
  Writeln('Go');
  for K := 1 to 500 do
    SplitPos(Line);
  Write('Pos: ');
  Show;
  for K := 1 to 500 do
    SplitWalk(Line);
  Write('Walk: ');
  Show;
end.

The line has two spaces between THE and BRASS on purpose.

Starting from

A new work file SPLIT.

What you should see

Go
Pos: [TAKE][THE][BRASS][LANTERN]
Walk: [TAKE][THE][BRASS][LANTERN]

with about three seconds between Go and Pos:, and about five more before Walk:.

Change One Thing

• In SplitPos, take out the if P > 1 then test (and its begin and end), so that every Copy becomes a word. What does Pos: show now?
• Change Str12 = string[12] to string[4]. What happens to the words, and which method minds?
• Change both 500s to 50. How long do the two take now?

Exercises

6.1 Print the words one to a line, numbered.

6.2 Write a third way, SplitEnds: walk along the line to find where each word starts and where it ends, and Copy each word out in one go, instead of building it a letter at a time. Time it beside the other two.

6.3 After splitting PUT THE KEY IN THE LOCK, count how many of the words are THE.

Worked solutions are in Appendix II.

When It Goes Wrong

Summary

Both ways give the same words. Adding a space to the end and using Pos, Copy and Delete takes about 3.3 seconds for 500 lines; walking the line and adding a letter at a time takes about 5.3. Turbo's own routines beat loops written in Pascal, and BEACON splits with Pos.

Next

S7, Recognising Words: knowing what a word is once you have it.