220 38473 article Path: news.gmane.org!.POSTED!not-for-mail From: joshua.r.marshall.1991@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Adding Sorting with suffix subordering for suffix arrays Date: Mon, 4 Jun 2018 08:51:48 -0700 (PDT) Lines: 181 Approved: news@gmane.org Message-ID: References: <57aff230-b879-4205-9cc6-dc3382c7d580@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_33699_1337372668.1528127509002" X-Trace: blaine.gmane.org 1528127384 8746 195.159.176.226 (4 Jun 2018 15:49:44 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 4 Jun 2018 15:49:44 +0000 (UTC) Cc: florian.csdt@gmail.com To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCFIZIPVQEORBFOA2XMAKGQEENZNGXI@isocpp.org Mon Jun 04 17:49:40 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yb0-f199.google.com ([209.85.213.199]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fPrjn-0002Ax-KK for gclcip-std-proposals@m.gmane.org; Mon, 04 Jun 2018 17:49:39 +0200 Original-Received: by mail-yb0-f199.google.com with SMTP id f141-v6sf23156780yba.15 for ; Mon, 04 Jun 2018 08:51:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=7KY+cGelldqBeuKXrDReGTVgkWah8JcypBx0VUgEB48=; b=I2b/G42O5cxxkLOcEL6vgGppDC7WRrBEzTgQAdkxoMyEpa2NvHbHqWcTjHkGxHaOVS NuZf9P0+x6v4nbHBB5fYcvSE/L70RTl4XLYXNxkHsRCF6oAUgSdBeXRfIVIz27+fr7Xe oIBhJ3ni3IGCVTn7lb9jUPgOA0q2qvjJL9dNuuV+1OjbRm85xlvMfuwzr0LSh8LlcaFA d55kKipvUgcqcSrTXgMCmIP0d8RCJdhBNWtOt4U+WXgp77ORoQ4LsanXlUfSHdJv/XVw M5WP/+Tjg43iXzfQQPZ5tnvGxgbFBFIik0L2oxNPNl9j6VGirGfqYPl5NcXeAuvjCPXU bRGg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=7KY+cGelldqBeuKXrDReGTVgkWah8JcypBx0VUgEB48=; b=UIncfrsYJGMsax8de0qZJZmjg/zuvPHvBo6dCMBF5swGTJD+P3vZo9uKVGgT7HcwkA +iw1YjAPGhWjO/nXljQhltB8FUhCdFJrd93yn1lUG5RctHKrEZ67atNPmVweFLZteD8/ zCNvb5LYmih7HMiP2l8096UeTN9YsGNvipT6xAOcVV+34cCVsQxYwJzmmnyLTkDl89vq yUq+8/Kzg5tswC/B8V2X4z75ourQRpfhWGhqxRptULV0Y37Eq3nUjqDmF0IUQHPbehau jH4Bt5zCurXZT5wCOGJDwQ59bu4YNeaG0s+eh2EEPodlWgg3kgj2UfUdlCDqkhQ1o3ew 2Sjw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:message-id:in-reply-to :references:subject:mime-version:x-original-sender:reply-to :precedence:mailing-list:list-id:x-spam-checked-in-group:list-post :list-help:list-archive:list-subscribe:list-unsubscribe; bh=7KY+cGelldqBeuKXrDReGTVgkWah8JcypBx0VUgEB48=; b=gpNNTLW5znQBN0RntMjOxQgcQO1b/voNGZ7zZ0GrqJ9sGCu9jO0LlaRAqJ4b3YO0bJ V1vO9imMK2om+xubYqc80HuSEdvUI0OzL4N2iEgg2CdCxdcpK6gaXJP5z5nP0+y0hbgi R4zPZfBxVtTrF0+eANqMekiZsXEbcXeu4VW5ALIBBMdtF6uXNRQf13FYApJXQ+KXbM23 +RrFnt+it6fK4qBg06hBDrmJsbUKYUL//pPmamHhuR+X1UgVJJu9Yx6HFz0ahU/OUBEY TY8KSC15y4a8phBeaUs6tt5thVqi1AoLr0+Xxrcl0xWnLpN2i7FKzW60vCa6BblOKc/Y gF8w== X-Gm-Message-State: APt69E1G0xPEONrGWJBLUUpx9IP+RavtqSQO6lSUjdFpffPTR69mCKWL FeIBVfmH1InA5E4D2ZprQY1DIA== X-Google-Smtp-Source: ADUXVKKRm4g8MIT3sU+ezeQAwQgjkKSTDV6EY4/Y1Pncd2eWZrenO2bML6RRn9BAOXXBqohx1T/j7w== X-Received: by 2002:a25:b950:: with SMTP id s16-v6mr698180ybm.18.1528127510662; Mon, 04 Jun 2018 08:51:50 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a5b:8c9:: with SMTP id w9-v6ls10386600ybq.12.gmail; Mon, 04 Jun 2018 08:51:49 -0700 (PDT) X-Received: by 2002:a25:84c8:: with SMTP id x8-v6mr77710ybm.2.1528127509439; Mon, 04 Jun 2018 08:51:49 -0700 (PDT) In-Reply-To: <57aff230-b879-4205-9cc6-dc3382c7d580@isocpp.org> X-Original-Sender: joshua.r.marshall.1991@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:38473 Archived-At: ------=_Part_33699_1337372668.1528127509002 Content-Type: multipart/alternative; boundary="----=_Part_33700_1576302153.1528127509002" ------=_Part_33700_1576302153.1528127509002 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Unfortunately, that approach computes and is correct but is not efficient= =20 enough to be seriously considered in my area. That approach ends up being= =20 something like O(n^2 log n). Naive tuned algorithms are still in the realm= =20 on O(n^2) when using a normally linear sort. SACA-K is linear time and=20 constant workspace, and divsufsort is n log n time with some acceptable=20 workspace. On Monday, June 4, 2018 at 11:36:49 AM UTC-4, floria...@gmail.com wrote: > > I have the feeling we don't a new interface for that: > template< typename RandomAccess_Iterator, typename Output_Iterator > > void get_suffix_array(RandomAccess_Iterator begin, RandomAccess_Iterator= =20 > end, Output_Iterator out_begin) { > // few preparations > const auto n =3D end - begin; > auto out_end =3D out_begin + n; > > // actual work > std::iota(out_begin, out_end, 0); > std::sort(out_begin, out_end, [&begin](auto lhs, auto rhs) { return=20 > begin[lhs] < begin[rhs]; }); > } > > Would that be enough? > > Le lundi 4 juin 2018 17:14:52 UTC+2, joshua.r.ma...@gmail.com a =C3=A9cri= t : >> >> A more limited change to the sorts made available is adding a discrete= =20 >> suffix array function. For the uninitiated, a suffix array is unlike a= =20 >> typical sorting algorithm in two respects: the returned object is a=20 >> sequence of indexes or reference into the original container, and in the= =20 >> case of ties, subordering is dictated by a comparison of each index's or= =20 >> reference's following value in the original container with the terminal= =20 >> value being the global minimum value. >> >> The two significant algorithms for generating suffix arrays right now ar= e=20 >> SACA-K and divsufsort. >> >> I think a good call interface for this would be as follows: >> >> template< typename _Bidirectional_Iterator, typename _Output_Iterator > >> void get_suffix_array(_Bidirectional_Iterator begin,=20 >> _Bidirectional_Iterator end, _Output_Iterator out); >> >> This would have applications in compression, text searching, and sequenc= e=20 >> alignment. >> > --=20 You received this message because you are subscribed to the Google Groups "= ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp= ..org/d/msgid/std-proposals/bdda0670-d00a-49da-ba5b-1a477bd717ef%40isocpp.or= g. ------=_Part_33700_1576302153.1528127509002 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Unfortunately, that approach computes and is correct = but is not efficient enough to be seriously considered in my area.=C2=A0 Th= at approach ends up being something like O(n^2 log n).=C2=A0 Naive tuned al= gorithms are still in the realm on O(n^2) when using a normally linear sort= ..=C2=A0 SACA-K is linear time and constant workspace, and divsufsort is n l= og n time with some acceptable workspace.


On Mo= nday, June 4, 2018 at 11:36:49 AM UTC-4, floria...@gmail.com wrote:
I have the feeling we= don't a new interface for that:
template< typename RandomAccess_Iterator,<= span style=3D"color:#000"> typename= Output_Iterat= or >=
void get_suffix_array(RandomAccess_Iterator begin, Ran= domAccess_Iterator end, Output_Iterator out_begin) {
=C2=A0 = =C2=A0// few preparations
=C2=A0 =C2=A0const auto n =3D end - begin;
=
=C2=A0 =C2= =A0auto out_end =3D out_begin + n;

=C2=A0 =C2=A0 // actual work
=C2=A0 =C2=A0std::iota(out_begin, out= _end, 0)= ;
=C2=A0 =C2=A0std::sort(out_begin, out_end, [&begin](auto lhs, <= /span>auto<= /span> rhs) { return begin= [lhs] < begin[rhs]; });
}

Would that be enough?

Le lundi 4 juin 2018 17:14:52 UTC+2, <= a>joshua.r.ma...@gmail.com a =C3=A9crit=C2=A0:
A more limited change to the sorts mad= e available is adding a discrete suffix array function.=C2=A0 For the unini= tiated, a suffix array is unlike a typical sorting algorithm in two respect= s: the returned object is a sequence of indexes or reference into the origi= nal container, and in the case of ties, subordering is dictated by a compar= ison of each index's or reference's following value in the original= container with the terminal value being the global minimum value.

The two significant algorithms for generating suffix array= s right now are SACA-K and divsufsort.

I think a g= ood call interface for this would be as follows:

t= emplate< typename _Bidirectional_Iterator, typename _Output_Iterator >= ;
void get_suffix_array(_Bidirectional_Iterator begin, _Bidi= rectional_Iterator end, _Output_Iterator out);

Thi= s would have applications in compression, text searching, and sequence alig= nment.

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/bdda0670-d00a-49da-ba5b-1a477bd717ef= %40isocpp.org.
------=_Part_33700_1576302153.1528127509002-- ------=_Part_33699_1337372668.1528127509002-- .