From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q2ILBPA0027741
	for <caml-list@sympa-roc.inria.fr>; Sun, 18 Mar 2012 22:11:25 +0100
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AjgHAOhOZk+wCYo3/2dsb2JhbABDgw2BW1axAoEHggkBAQMCDBcPAQ0BATYCDwkCGAICBRYLAgIJAwIBAgEPNhMGAgKICgemc22DPwGNTAaBL4gmhAWCDIEWkj6DLoVthUKEeYJo
X-IronPort-AV: E=Sophos;i="4.73,608,1325458800"; 
   d="scan'208";a="136651408"
Received: from mail.etorok.net ([176.9.138.55])
  by mail4-smtp-sop.national.inria.fr with ESMTP; 18 Mar 2012 22:11:24 +0100
Received: from [192.168.1.101] (unknown [79.114.61.38])
	by mail.etorok.net (Postfix) with ESMTPSA id DBBE046A2
	for <caml-list@inria.fr>; Sun, 18 Mar 2012 22:11:23 +0100 (CET)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=etorok.net;
	s=MAILOUT; t=1332105083;
	bh=13p4nWI0DgXXi1ZEl/DC7dFJq8hDkeCtqr35Z440vq0=;
	h=Message-ID:Date:From:MIME-Version:To:Subject:References:
	 In-Reply-To:Content-Type:Content-Transfer-Encoding;
	b=UdbK8lLOqCQAOBB0RTkkv2ewPMZ/zOAPiSTSW2bGSNynGgO1b2RUtvg3jSi20Wt4D
	 VCY3Bt8j5kh0aXjoRYtEMnC/nPYDfSn59qUvEMnO6AWTlnKPEpTpVNOIx5j8ms12dx
	 T0cLsWrBjcrNiD94gmgnQdbzcU2vtzel/q6IM76k=
Message-ID: <4F664F7B.6020405@etorok.net>
Date: Sun, 18 Mar 2012 23:11:23 +0200
From: =?UTF-8?B?VMO2csO2ayBFZHdpbg==?= <edwin+ml-ocaml@etorok.net>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:8.0) Gecko/20120216 Icedove/8.0
MIME-Version: 1.0
To: caml-list@inria.fr
References: <CAOOOohQV+nYWyTXFU-sKdLkJSNAAkZH+=UCkwKEpnxjAiE=ORg@mail.gmail.com> <20120316154901.76602deb@caladan.esterel-technologies.com>
In-Reply-To: <20120316154901.76602deb@caladan.esterel-technologies.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Virus-Scanned: clamav-milter 0.97.3 at mail
X-Virus-Status: Clean
Subject: Re: [Caml-list] Efficient scanning of large strings from files

On 03/16/2012 04:49 PM, Jérémie Dimino wrote:
> Le Fri, 16 Mar 2012 14:03:38 +0100,
> Philippe Veber <philippe.veber@gmail.com> a écrit :
> 
>> Say that you'd like to search a regexp on a file with lines so long
>> that you'd rather not load them entirely at once. If you can bound
>> the size of a match by k << length of a line, then you know that you
>> can only keep a small portion of the line in memory to search the
>> regexp. Typically you'd like to access substrings of size k from left
>> to right. I guess such a thing should involve buffered inputs and
>> avoid copying strings as much as possible. My question is as follows:
>> has anybody written a library to access these substrings gracefully
>> and with decent performance? Cheers,
> 
> You can use a non-backtracking regexp library to find offsets of the
> substrings, then seek in the file to extract them. You can use for
> example the libre library from Jérôme Vouillon [1]. It only accept
> strings as input but it would be really easy to make it work on input
> channels (just replace "s.[pos]" by "input_char ic").
> 
>   [1] http://sourceforge.net/projects/libre/
>       https://github.com/avsm/ocaml-re.git
> 

A nice library for regular expression matching is LibTRE (BSD licensed),
and it has a way to parse arbitrary data with callbacks:
http://laurikari.net/tre/documentation/reguexec/

According to the paper it is also good at finding substring matches
with its tagged NFA:
http://laurikari.net/ville/regex-submatch.pdf

If you don't use back-references (!tre_have_backrefs) then it guarantees linear-time matching.

I couldn't find an OCaml wrapper for it, but should be simple enough to write one.

Best regards,
--Edwin