<div dir="ltr"><span style="font-size:12.8px">Interesting, thanks for the link. However we're trying to do _even less_ than that - this is just the "scan the document to produce the Elias-Fano encoding" step, except without needing to keep a hold of it for later. It's not quite as trivial as that paper makes out as (a) it doesn't mention the possibility that the documents might not be well-formed, and (b) it doesn't really talk about dealing with the special delimiting characters within string literals, for which you need to drag along a bunch of state while you're scanning.</span><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">This'd be pretty trivial to do in a C-like language now we've got the DFA tables built, and I may resort to that at some point if we can't work out how to avoid the allocations in Haskell-land, but I'd quite like to be able to solve problems of this form without unnecessarily resorting to C.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Cheers,</div><div class="gmail_extra"><br><div class="gmail_quote">On 11 May 2017 at 17:30, Bardur Arantsson <span dir="ltr"><<a href="mailto:spam@scientician.net" target="_blank">spam@scientician.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 2017-05-11 18:12, David Turner wrote:<br>
> Dear Café,<br>
><br>
> We have a stream of ~900byte JSON documents (lazy ByteStrings) that we<br>
> would like to validate (NB not parse) as quickly as possible. We just<br>
> need to check that the bytes are a syntactically valid JSON document and<br>
> then pass them elsewhere; we do not care what the content is. The<br>
> documents are encoded in UTF-8 and have no extraneous whitespace.<br>
><br>
<br>
</span>No particular recommendations, but you might want to look into<br>
semi-indexing[1] as a strategy. It looks plausible that it would be<br>
possible to do that without a lot of allocation; see the paper for<br>
details. (I there's also a demo implementation in Python on GH.)<br>
<br>
[1] <a href="http://www.di.unipi.it/~ottavian/files/semi_index_cikm.pdf" rel="noreferrer" target="_blank">http://www.di.unipi.it/~<wbr>ottavian/files/semi_index_<wbr>cikm.pdf</a><br>
<br>
______________________________<wbr>_________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/haskell-<wbr>cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div><br></div></div>