4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think, ReadString[stream, " "|"\n"] is a reasonable place to start tweaking. $\endgroup$ – LLlAMnYP Mar 4 '16 at 18:02
  • $\begingroup$ @LLlAMnYP I think you have something there, but it acts strangely. I tried some tests with it, and it has some weird async stuff going on. In my tests I would often end up with old data from the previous test prepended to the string returned from ReadString, even if I closed all streams and cleared all variables before the test. Also the value returns sometimes after other print statements, even though it claims to be a blocking function. Finally, the StreamPosition ends up at the end of the file after one read, which is very strange. If you can overcome these though you may have a winner. $\endgroup$ – Mario Carneiro Mar 4 '16 at 20:20
  • $\begingroup$ yes, @mario, I've noted the same strange behavior and it's not covered by the documentation too well. The documentation also says, it can take string patterns as terminators, although I had to do stuff like Alternatives[Whitespace,Whitespace] instead of just Whitespace and still I got the buggy behavior. I know, that ReadString requires a file to be opened with the BinaryFormat option, but I don't really understand how they all interact with one another. Like I said, the docs are poor on this functionality. $\endgroup$ – LLlAMnYP Mar 5 '16 at 13:22
  • $\begingroup$ I'm not sure why, but my pingbacks, if inserted at the beginning of a comment are getting removed from the message, so here's another one @mario $\endgroup$ – LLlAMnYP Mar 5 '16 at 13:24
  • 2
    $\begingroup$ @LLlAMnYP I also noticed the pattern problem; it can also be fixed by naming the pattern e.g. x:Whitespace. Regarding pingbacks, the @Mario is removed because I am the OP so I get notified even if you don't put the @ sign. If you want to use my name at the beginning of a sentence, just drop the @. $\endgroup$ – Mario Carneiro Mar 5 '16 at 23:15
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your first solution is indeed very fast; I used Timing@While[Check[readToken[stream]; True, False]] and got 45.2 seconds, almost as good as Read[_, Word]'s 11 seconds. The second solution benchmarked at 185.7 seconds. Maybe there is a way to use Check on the first solution and switch over to the second to satisfy the spec. $\endgroup$ – Mario Carneiro Mar 6 '16 at 0:04
  • $\begingroup$ @Mario Yes, I think that would be trivial, actually. For example, Check[$current=readToken[stream],parse[$current]] where parse is some function designed to massage the output with the error messages into the correct form. Alternatively, you could measure the byte-length of the file being read and check the value of StreamPosition. If it reaches the end of the file, then again just apply parse to the latest result. $\endgroup$ – LLlAMnYP Mar 6 '16 at 0:20
  • $\begingroup$ @MarioCarneiro also the checks I provide in my second example are inefficient and should be implemented either through UpValues of EndOfFile or by reordering the definitions. The problem is, that an attempt to match smQ[input] to smQ[EndOfFile] is tried first, and only then the string pattern is checked. Similar considerations hold for the If statement. $\endgroup$ – LLlAMnYP Mar 6 '16 at 1:08
  • $\begingroup$ @MarioCarneiro I've added a very primitive check that should lead to minimal overhead. $\endgroup$ – LLlAMnYP Mar 6 '16 at 1:16
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$
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
*)
$\endgroup$
  • $\begingroup$ Very nice. I didn't know about SetStreamPosition; that opens a lot more options. The biggest issue with this method is that it is quite slow; Timing@While[readToken[stream] =!= EndOfFile] gives 693 seconds over 11.87 seconds for Timing@While[Read[stream, Word] =!= EndOfFile] (although that's probably not a fair comparison since Read[_,Word] is built in). Perhaps ReadList with a decent buffer size would improve the number of individual IO calls. $\endgroup$ – Mario Carneiro Mar 3 '16 at 18:02
  • $\begingroup$ That, and also that reading a stream byte by byte is bound to be slower than reading it by larger chunks. But it is not really useful to benchmark against something that does not meet the specification! I tried before with Read[_,Word], but there were so many small issues that I gave up and went for Read[_,Character`] instead. $\endgroup$ – Aisamu Mar 3 '16 at 20:58
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't want to read the entire file in, just word by word. It also has to return the words one at a time, unless there is a way to do a C# yield return -type trick in the middle of a Scan[]. Also this doesn't preserve newlines. $\endgroup$ – Mario Carneiro Mar 2 '16 at 1:47
  • $\begingroup$ @MarioCarneiro to get one line, You can specify number of lines(records) to read as the third parameter, StringSplit /@ ReadList[stream, "String",1] Gives you all words on a given line $\endgroup$ – Peter Roberge Mar 2 '16 at 1:55
  • $\begingroup$ This is a long way from a workable solution. How is this supposed to remember its state so that calls to nextToken give the next word and not the next line or the same word, or the list of all words? I know about Read (the List is not necessary, since we only want one word at a time) and I already explained in the OP why it (alone) doesn't fit my needs. $\endgroup$ – Mario Carneiro Mar 2 '16 at 2:09
  • $\begingroup$ @MarioCarneiro you need to edit and clarify your question $\endgroup$ – Peter Roberge Mar 2 '16 at 4:11
  • 1
    $\begingroup$ I thought the specification was fairly clear. How would you define readToken so that it behaves as in the example? Sorry to be so harsh, but I'm concerned about your current non-answer taking the Q off the unanswered queue and dissuading others from providing their own answers. $\endgroup$ – Mario Carneiro Mar 2 '16 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.