How to efficiently stream words and whitespace from a large text file

Question

I want to tokenize a large (~20 MB) file, opening it and streaming the words, but preserving the whitespace as well. Example:

stream = StringToStream["abc  def g\n  hi"]
readToken[stream]
   => {"", "abc"}
readToken[stream]
   => {"  ", "def"}
readToken[stream]
   => {" ", "g"}
readToken[stream]
   => {"\n  ", "hi"}

A word here is just a sequence of non-whitespace characters (space and newline). Read[stream, Word] nearly does the job, but discards the intervening whitespace. (I want to be able to reconstruct the file byte-for-byte from the tokens.) I know how to do it by reading lines at a time and using StringCases, but this doesn't handle the newlines well, is probably not very fast, and also uses global state to parcel out the results across later calls of the function. What is an efficient way to achieve this?

Answer 1

This answer is conceptually similar to that of Mario (aka OP), but I think, is in a way cleaner, uses more built-in functionality to get the right form straight away. Kudos to Leonid, from whom I've learned a nice application of Reap today in some other thread.

Anyway, here's the simpler code without an EndOfFile check:

readToken[stream_] := Join @@
  Reap[

   While[StringMatchQ[Sow[Read[stream, Character]], WhitespaceCharacter]]; 
   SetStreamPosition[stream, StreamPosition[stream] - 1]; 
   Read[stream, {Word}],

   _,

   "" <> Most@#2 &] // Reverse (* arguments of Reap separated by blank lines for clarity *)

This returns an error should the EOF be reached, but otherwise should probably be faster as there are less intermediate calculations.

Some kind of check for the EOF can be implemented like so:

smQ[EndOfFile] := EndOfFile
smQ[s_String] := StringMatchQ[s, WhitespaceCharacter]
readToken2[stream_] :=
 Reap[
     While[smQ[Sow[Read[stream, Character]]]]; 
     SetStreamPosition[stream, StreamPosition[stream] - 1]; 
     Read[stream, {Word}],

     _,

     If[Last@#2 === EndOfFile,
       {"" <> Most@#2, EndOfFile},
       "" <> Most@#2] &] // Reverse // Flatten // #[[;; 2]] &

This seems to work quite well, though I'm not sure, how much overhead is caused by all these checks (quite a lot, actually!).

Here's another version, that should be fast, handles EoF, using global variable as a flag for reaching EoF.

Unprotect[EndOfFile];
EndOfFile /: StringMatchQ[EndOfFile, _] := ($ = 1; False)
    Protect[EndOfFile];
    $=0;
readToken3[stream_] := 
Flatten@Reap[
While[StringMatchQ[Sow[Read[stream, Character]], 
  WhitespaceCharacter]];
SetStreamPosition[stream, StreamPosition[stream] - 1 + $];
Read[stream, {Word}], _, "" <> Most@#2 &] // Reverse

Of course, once the EoF is reached, the flag $ is set to 1 and needs to be reverted back to 0 before using readToken3 again.

Answer 2

Here is a Read[_, Word]-based solution using StreamPosition and SetStreamPosition. For some silly reason ReadList[stream, _, 0] returns unevaluated instead of {}, so it had to be special-cased. StringJoin@ReadList[stream, Character, n] doesn't seem like the most efficient way to read a fixed-length string from a stream, but it's the only one I can find.

readToken[stream_] := 
 Module[{p = StreamPosition[stream], p2, w, l, r}, 
  w = Read[stream, Word];
  If[w === EndOfFile, EndOfFile,
   l = StringLength[w]; 
   p2 = StreamPosition[stream];
   SetStreamPosition[stream, p]; 
   r = {If[# == 0, "", StringJoin@ReadList[stream, Character, #]] &[p2 - p - l], w};
   SetStreamPosition[stream, p2]; r]]

This benchmarks at 125.3 seconds for my test file (28816342 bytes, 3750496 words), a bit better than Aisamu's 693 second char-by-char method.

Answer 3

ClearAll[readToken]
readToken[stream_] := 
    readToken[stream, {}, Read[stream, Character]]
readToken[stream_, list : {whites : (" " | "\n") ..., chars : Except[(" " | "\n")] ..}, " " | "\n"] := 
    (SetStreamPosition[stream, StreamPosition[stream] - 1]; 
    {StringJoin@whites, StringJoin@chars})
readToken[stream_, list : {whites : (" " | "\n") ..., chars : Except[(" " | "\n")] ...}, EndOfFile] :=
    {StringJoin@whites, StringJoin@chars} /. {"", ""} -> EndOfFile
readToken[stream_, list_, newElem_] := 
    readToken[stream, Append[list, newElem], Read[stream, Character]]

Since the stream is consumed on a character-basis, there's probably little memory pressure. A benchmark against your current code is recommended!

Sample string results

stream = StringToStream["abc  def g\n  hi"];
Do[readToken[stream] // InputForm // Print, {6}]

(*
{"", "abc"}
{"  ", "def"}
{" ", "g"}
{"\n  ", "hi"}
EndOfFile
EndOfFile
*)

Answer 4

I've managed to "fix" ReadString to work properly with x:WordBoundary patterns, with minimal modification of any private symbols. None, in fact. Be wary, that internally, ReadString does BinaryReadStrin[stream, "Character8", 10000] and then uses standard string manipulation functions on the result, whereas Read[stream, Word] is, apparently, not written in Mathematica code. I'm really not sure, if ReadString is intrinsically fast in this respect.

Anyways, the problem with using a pattern like WordBoundary to read in the next word is that a string like "blahblah \n \t stuff" has a WordBoundary at position {1,0}, then at position {9,8}. One could think, that we should do repeatedly

{ReadString[stream, x:WordBoundary], Read[stream, Word]}

but that's not the case. See the linked thread for details. As Mario commented "it has some weird async stuff going on". Specifically, ReadString reads a big chunk of 10000 bytes in, saves this to a buffer and then works through the buffer, before reading in the next chunk. Read, on the other hand, reads stuff in from the current StreamPosition, which, after calling ReadString is already at the EoF.

I suppose, these are some limitation of reading stuff in in a binary format or something. This means, that if I want to use ReadString, then I can only use its functionality, and not that of Read.

When I do the call ReadString[stream, x:WordBoundary], it runs some internal checks, then calls ProcessLink`Private`genericGetString[stream, (*pattern*), (*timeConstraint*)].

If I want to read in the next sequence of whitespace, that's ok, because the first position at which a WordBoundary is found is not at the beginning of the string. If I want to read in the next word, I have a problem, because then I'm not interested in the boundary at the start of the string, but rather the one following it.

Thus, I roll my own variant of genericGetString that does what I want, stealing most of the code from the original definition of genericGetString.

Begin["ProcessLink`Private`"]
Global`ReadString2[st_, patt_] := genericGetString2[st, patt];
genericGetString2[st_, patt_] := Module[{str, buff = "", pos = {}},
   While[
    pos === {},
    str = cachedReadString[st];
    If[! StringQ[str],
     Return[If[buff === "", str, Message[ReadString::notfound]; buff]]
     ];
    buff = buff <> str;
    pos = StringPosition[buff, patt];];
   If[pos =!= {},
    setStreamCache[st, StringDrop[buff, pos[[2, 2]]]]; 
    StringTake[buff, pos[[2, 1]] - 1],
    buff]
   ];
End[];

What I have done here, is throw the time constraint checks out the window, but most importantly, in the 3rd and 4th lines from the bottom I have changed pos[[1,2]] -> pos[[2,2]] and pos[[1,1]] -> pos[[2,1]].

This now works:

readToken[str_] := 
  {ReadString[str, x:(WordBoundary|EndOfString)],
       ReadString2[str, x:(WordBoundary|EndOfString)]}

The result for the start of the stream is

{(* whitespace, even if of length 0 *), (* first word *)}

The result at the end of the stream is

{(* whitespace preceding last word *), (* last word *)}
{(* whitespace following last word, if none - EndOfFile *), EndOfFile}

This method fails if the value of ProcessLink`Private`binaryReadBlock is too small. One would think, that if the procedure doesn't find, what it's looking for, it would append another chunk to the current cache, but this seems to not be the case. Maybe later I'll have a stab at fixing this oversight too.

Answer 5

You can use ReadList

ReadList[stream, "String"]
(*{"abc  def g", "  hi"}*)

You can specify number of lines(records) to read as the third parameter, if you need to prevent overflow.

If you need to separate this into words, you can then use StringSplit