From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id C6CDB7FACE for ; Thu, 25 Sep 2014 17:57:59 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of anthony.tavener@gmail.com) identity=pra; client-ip=209.85.220.169; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="anthony.tavener@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of anthony.tavener@gmail.com designates 209.85.220.169 as permitted sender) identity=mailfrom; client-ip=209.85.220.169; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="anthony.tavener@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-vc0-f169.google.com) identity=helo; client-ip=209.85.220.169; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="postmaster@mail-vc0-f169.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjsCABg7JFTRVdypm2dsb2JhbABgg2FNCgSCfbYoj1iBbYdOAnwIFgERAQEBAQEGCwsJFCyEBAEBAwESER0BGxILAQMBCwYFBAcaHQICIQEBEQEFAQoSBhMIChCIBwEDCQgNn0ZuizCBcoMQiSEKGScDCmaGFgERAQUOjWCBWFQEB4J4gVMFhRMFhjSDfIMdgzWCPoI7ghCBYo0thFUYKYUzHi+BBoFEAQEB X-IPAS-Result: AjsCABg7JFTRVdypm2dsb2JhbABgg2FNCgSCfbYoj1iBbYdOAnwIFgERAQEBAQEGCwsJFCyEBAEBAwESER0BGxILAQMBCwYFBAcaHQICIQEBEQEFAQoSBhMIChCIBwEDCQgNn0ZuizCBcoMQiSEKGScDCmaGFgERAQUOjWCBWFQEB4J4gVMFhRMFhjSDfIMdgzWCPoI7ghCBYo0thFUYKYUzHi+BBoFEAQEB X-IronPort-AV: E=Sophos;i="5.04,598,1406584800"; d="scan'208";a="80906203" Received: from mail-vc0-f169.google.com ([209.85.220.169]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 25 Sep 2014 17:57:58 +0200 Received: by mail-vc0-f169.google.com with SMTP id id10so7146969vcb.28 for ; Thu, 25 Sep 2014 08:57:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=JrvBWqKo7OtO5R8O1d3dgqm1YpnV7d+ENsE36sYrd4M=; b=X8cib+nMrgrYM2zCPG87AVR/k7Vm5j+WqIkZNbVl+MJFGkEbI4MWuHoX5fJpTrSvr8 lWJU1k1V06caTn3XnguT6Vm9ZL8U++FPBuBLgQ/CAkgXZrAWPxhW9ZJ6AgTQNft5ObAR TrRNDEwcPfH079gB+nD3t/O7zmst/OwwmNLf5HA/TwkXvlouR/FL6Rk1vsSvcHhU1Lp4 qPkWPz56V54u9PfEwxsPGkew0PvuNHKNRGXPBqSiAgsl281yhDl520EAwWsRBsGNy1AB FAwDBhBr8hEzAumyilQAlR6NYPYJdZCt+omX2OskOClMlGpH+lOArQgAQdHMn0jVz0VY vqNg== MIME-Version: 1.0 X-Received: by 10.52.145.234 with SMTP id sx10mr636633vdb.79.1411660677658; Thu, 25 Sep 2014 08:57:57 -0700 (PDT) Received: by 10.220.159.141 with HTTP; Thu, 25 Sep 2014 08:57:57 -0700 (PDT) In-Reply-To: References: Date: Thu, 25 Sep 2014 09:57:57 -0600 Message-ID: From: Anthony Tavener To: Yoriyuki Yamagata Cc: Caml List Content-Type: multipart/alternative; boundary=bcaec51a70ae3c3d550503e5ddf5 Subject: Re: [Caml-list] Succinct data structures --bcaec51a70ae3c3d550503e5ddf5 Content-Type: text/plain; charset=UTF-8 I'd never heard of these terms before. After some searching and finding papers which describe what LOUDS (level order unary degree sequence) is, I realize I use these (in a trivial form). I used the term "hierarchical bitfield", and over the years I've tried searching for the technique using various terms -- with no success. I must say I never would have guessed "level order unary degree sequence". :) So, thank you for finally providing a name, and a means to find other work using this structure. My uses are in games: succinctly representing hierarchical data in a manner which I can do fast bitmatches. Unfortunately, I don't have a nice library for building and working with these datastructures, as my uses are fairly limited: trees that can be encoded within 64 bits. Hopefully someone out there knows of a library in OCaml, but if not, the "bitstring" library might be a useful building block... or, of course, the option of binding to a C library. Good luck! Sorry I couldn't be more helpful, while you've helped me by asking a question. On Thu, Sep 25, 2014 at 6:48 AM, Yoriyuki Yamagata wrote: > Hi, list, > > Does anyone try to implement succinct data structures, such as > compressed suffix array or LOUDS in OCaml? The search does not show > anything. > > -- > Yoriyuki Yamagata > http://yoriyuki.info/ > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > --bcaec51a70ae3c3d550503e5ddf5 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I'd never heard of these terms before. After some= searching and finding papers
which describe what LOUDS (level or= der unary degree sequence) is, I realize I
use these (in a trivia= l form). I used the term "hierarchical bitfield", and
o= ver the years I've tried searching for the technique using various term= s --
with no success. I must say I never would have guessed "= ;level order unary
degree sequence". :)

=
So, thank you for finally providing a name, and a means to find other = work
using this structure. My uses are in games: succinctly repre= senting
hierarchical data in a manner which I can do fast bitmatc= hes. Unfortunately, I
don't have a nice library for building = and working with these datastructures,
as my uses are fairly limi= ted: trees that can be encoded within 64 bits.

Hop= efully someone out there knows of a library in OCaml, but if not, the
=
"bitstring" library might be a useful building block... or, = of course, the
option of binding to a C library.

Good luck! Sorry I couldn't be more helpful, while you've = helped me by asking
a question.


On Thu, Sep 25, 2014 at = 6:48 AM, Yoriyuki Yamagata <yoriyuki.y@gmail.com> wrote:<= br>
Hi, list,

Does anyone try to implement succinct data structures, such as
compressed suffix array or LOUDS in OCaml?=C2=A0 The search does not show anything.

--
Yoriyuki Yamagata
http://yoriyuki.info/

--
Caml-list mailing list.=C2=A0 Subscription management and archives:
ht= tps://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

--bcaec51a70ae3c3d550503e5ddf5--