From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q2HGs4cE001820 for ; Sat, 17 Mar 2012 17:54:04 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ar0DAErBZE/AbSoIe2dsb2JhbABChT6fOpFIIgEBFiYEI4IJAQEFIw8BOwsQCQIJDwICCR0CAhQNCxkYExKHeAQHqAORYhOBHIgmhhEzYwSOAIdnizCHYA X-IronPort-AV: E=Sophos;i="4.73,602,1325458800"; d="scan'208";a="149942196" Received: from einhorn.in-berlin.de ([192.109.42.8]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 17 Mar 2012 17:54:01 +0100 X-Envelope-From: oliver@first.in-berlin.de Received: from first (e178014045.adsl.alicedsl.de [85.178.14.45]) (authenticated bits=0) by einhorn.in-berlin.de (8.13.6/8.13.6/Debian-1) with ESMTP id q2HGrxUf000431 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Sat, 17 Mar 2012 17:53:59 +0100 Received: by first (Postfix, from userid 1000) id ABB381540144; Sat, 17 Mar 2012 17:53:58 +0100 (CET) Date: Sat, 17 Mar 2012 17:53:58 +0100 From: oliver To: Francois????Charles Matthieu????Berenger Cc: Edgar Friendly , Philippe Veber , "caml-list@inria.fr" Message-ID: <20120317165358.GA5801@siouxsie> References: <4F634AD1.20402@gmail.com> <1331918628011613.Berenger@riken.jp> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <1331918628011613.Berenger@riken.jp> User-Agent: Mutt/1.5.20 (2009-06-14) X-Scanned-By: MIMEDefang_at_IN-Berlin_e.V. on 192.109.42.8 Subject: Re: Re: [Caml-list] Efficient scanning of large strings from files DNA: C, G, A, T, \n On Sat, Mar 17, 2012 at 02:23:48AM +0900, Francois????Charles Matthieu????Berenger wrote: > ｈｉ　philippe, > > i am curious, is your string a dna sequencｅｓｏ　ｔｈａｔ　ｓ　ｗｈｙ　ｉｔ　ｉｓ　ｓｏ　ｌｏｎｇ？ > > ｒｅｇａｒｄｓ，ｆ > > > On Fri, 16 Mar 2012 10:14:41 -0400 > Edgar Friendly wrote: > > > On 03/16/2012 09:03 AM, Philippe Veber wrote: > > > Dear camlers, > > > > > > 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, > > > Philippe. > > > > > This is tricky to do, as incremental matching implies DFA-based > > matching, but returning matching substrings implies backtrack-based > > matching. The re2 library returns matching substrings by matching > > forward to find the end of patterns, and then matching backwards on the > > reversed regex from that point to find their beginning. I don't know if > > even it supports this on incremental input. > > > > Subject to the assumption that starting to match implies either > > finishing or aborting a match (i.e. once you've started to match your > > regex, no other match will start before either this match attempt > > finishes successful or not), this is not unreasonable to do. Without > > this assumption, it requires tracking many match start locations and > > somehow knowing which of them match or fail to match. I'm not sure this > > has been done before. > > > > E. > > > > -- > > Caml-list mailing list. Subscription management and archives: > > https://sympa-roc.inria.fr/wws/info/caml-list > > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > > Bug reports: http://caml.inria.fr/bin/caml-bugs > > > > > > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs >