220 38478 article Path: news.gmane.org!.POSTED!not-for-mail From: florian.csdt@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Adding Sorting with suffix subordering for suffix arrays Date: Mon, 4 Jun 2018 09:29:27 -0700 (PDT) Lines: 245 Approved: news@gmane.org Message-ID: References: <57aff230-b879-4205-9cc6-dc3382c7d580@isocpp.org> <65056fa4-3634-4430-9ca3-ca2254eb308b@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_25863_481596994.1528129767281" X-Trace: blaine.gmane.org 1528129643 10265 195.159.176.226 (4 Jun 2018 16:27:23 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 4 Jun 2018 16:27:23 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBC26HM4V3MIRB2GR2XMAKGQETCWGQ6Q@isocpp.org Mon Jun 04 18:27:19 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yw0-f197.google.com ([209.85.161.197]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fPsKE-0002YD-F8 for gclcip-std-proposals@m.gmane.org; Mon, 04 Jun 2018 18:27:18 +0200 Original-Received: by mail-yw0-f197.google.com with SMTP id d129-v6sf12797567ywe.4 for ; Mon, 04 Jun 2018 09:29:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to: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=aMSv8rHIJsk/C++65PWHEc3q6tjCnU5i9n3mBsUjKcY=; b=yS6Mp59nZ51TZWAvy1XRJ7AuenuP8kQdIk8zNqEtzVgiGCWU+3CJVc48XvkGWYF4xx SorhUr14Cv92aIkBxaHKUGmhuVc7gjhB1HAvwcOTmMM38FOttAkiArXOU7CgTNIwPZ3A 2YyzOx/oGzrUmFxAvOSpF4yj3Ym9pKJrvMWo2ZK64sKcbTysXvWOpd3Jq8Y4KHuJmPon LSoGxRGPIJzPq9kMZmZIRXFMq+8mUX4qHsdDazt5zkxyOKaGY+yYDKUeHA4or5WVJFZI TsZbNeJb2SwEDQJ2WukC4E2RbeEdNJye8rFDsdEfFKEeUi/OHlXJr5htaWrrUWfP717Z OvVQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to: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=aMSv8rHIJsk/C++65PWHEc3q6tjCnU5i9n3mBsUjKcY=; b=pTTWAhuRUD7CSsGC+C37kQBm/SbDKug6Xr9HflNyRiZNtBAZc7AdHuYmqnPNXqxKIg xaWlMVaKqdvEpaSo6iqJt7FIfyXhehst7H8zWFMVcZcPNxtEEldSBvsM+5VQ1naVBALF pdLZaskvnWVWkoyS4essILa6OdyUHVJPFg3iyPilXlTQaDJTY2aJOOwo9+Kov+mKNMgk C66/WklOhElqgSueoHk/xxeR7g8vfQJm/UCMXWd+VpEy6kjBFi1XjZgPLIgBnaLy2q42 Z61C/FwdXUAyYi/JkIKSD5T8U1et5a1SCpocQDy/nrY8pxMMn1NhGqdXbReiSFiQNcO5 CAGA== 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: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=aMSv8rHIJsk/C++65PWHEc3q6tjCnU5i9n3mBsUjKcY=; b=jdqfGBQ/NcKyQJ4RluiMGB9Ndk9Mlv2P5PgfH9l2YESEnG3XJaf818CGeCdyzf5Gw+ /aplHXO7oj7fnnUawGMxaoVVZ2+aIxwT3rZksQo3Bsxbh51wjYKS912i8mVIbiTKEfwv SF7JQ5v13M438EYSsDOXMokH5+C71B7aMu4HHdQ/gYlfMMRhKg8tdTNZ6YaI1Fv8Ai86 vID2VQOhtaAle+zPJXZsRRNqHx6Klf7GpLeP45RwKhwKtLv/x3YSkPfd1eDc3gJbXP5Y Xmh/tdUCeJ5srsbQCTmlVYibLIHt4IKsXfGHll8YkXTyXAUvmQbU1+asLOy9M3iVSQpB fZkw== X-Gm-Message-State: APt69E1t7bJNAL2QxPcYqKA5nC6ozwv+hgkhCPEhXjFab6YHqbI0OOwg sw1lvoGqNaXbyM97oeFdDA8DZw== X-Google-Smtp-Source: ADUXVKKycZbAL3MLz8V5heqKMTFLn2W8bMF/lmxVkC+45139lXWVACP0B5E7xzsMalUELkDa1DKjyg== X-Received: by 2002:a0d:d54f:: with SMTP id x76-v6mr2273457ywd.3.1528129769222; Mon, 04 Jun 2018 09:29:29 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a81:28c3:: with SMTP id o186-v6ls503096ywo.22.gmail; Mon, 04 Jun 2018 09:29:28 -0700 (PDT) X-Received: by 2002:a81:9a4f:: with SMTP id r76-v6mr936563ywg.0.1528129767687; Mon, 04 Jun 2018 09:29:27 -0700 (PDT) In-Reply-To: <65056fa4-3634-4430-9ca3-ca2254eb308b@isocpp.org> X-Original-Sender: florian.csdt@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:38478 Archived-At: ------=_Part_25863_481596994.1528129767281 Content-Type: multipart/alternative; boundary="----=_Part_25864_1229247947.1528129767281" ------=_Part_25864_1229247947.1528129767281 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable My bad, I did not understand the algorithm. And my implementation is not=20 correct (my comparison predicate compares single characters). you should probably try to explain better what it is to avoid ambiguities. Le lundi 4 juin 2018 18:15:03 UTC+2, joshua.r.ma...@gmail.com a =C3=A9crit = : > > Not quite. Because these have to track backwards from the each starting= =20 > point, there are many successive comparisons, especially over the common= =20 > case of small alphabets. So take your expected length before mismatch of= =20 > strings, O(n/2) worst case, O(log(n)/log(|alphabet|))) best case, and=20 > multiply each comparison by that. Comparisons are not O(1). > > On Monday, June 4, 2018 at 12:02:48 PM UTC-4, floria...@gmail.com wrote: >> >> How is it O(n=C2=B2 log n)? >> end - begin is O(1) (random access iterator) >> out_begin + n is O(1) (random access iterator) >> std::iota(out_begin, out_end, 0) is O(n) >> std::sort(out_begin, out_end, [&begin](auto lhs, auto rhs) { return=20 >> begin[lhs] < begin[rhs]; }) is O(n log n) ( begin[] is O(1)) >> >> In the end, this is O(n log n). >> Maybe I have assumed random access iterators where they are not, but=20 >> otherwise, it is O(n log n). >> >> Le lundi 4 juin 2018 17:51:49 UTC+2, joshua.r.ma...@gmail.com a =C3=A9cr= it : >>> >>> Unfortunately, that approach computes and is correct but is not=20 >>> efficient enough to be seriously considered in my area. That approach = ends=20 >>> up being something like O(n^2 log n). Naive tuned algorithms are still= in=20 >>> the realm on O(n^2) when using a normally linear sort. SACA-K is linea= r=20 >>> time and constant workspace, and divsufsort is n log n time with some= =20 >>> acceptable 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,=20 >>>> RandomAccess_Iterator 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=A9= crit : >>>>> >>>>> A more limited change to the sorts made available is adding a discret= e=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 termin= al=20 >>>>> value being the global minimum value. >>>>> >>>>> The two significant algorithms for generating suffix arrays right now= =20 >>>>> are 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=20 >>>>> sequence 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/bd3e0341-6843-43d2-82d6-27fb7a9529d7%40isocpp.or= g. ------=_Part_25864_1229247947.1528129767281 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
My bad, I did not understand the algorithm. And my impleme= ntation is not correct (my comparison predicate compares single characters)= ..

you should probably try to explain better what it is to avoid ambi= guities.


Le lundi 4 juin 2018 18:15:03 UTC+2, joshua.r.ma...@gma= il.com a =C3=A9crit=C2=A0:
Not quite.=C2=A0 Because these have to track backwards from th= e each starting point, there are many successive comparisons, especially ov= er the common case of small alphabets.=C2=A0 So take your expected length b= efore mismatch of strings, O(n/2) worst case, O(log(n)/log(|alphabet|))) be= st case, and multiply each comparison by that.=C2=A0 Comparisons are not O(= 1).

On Monday, June 4, 2018 at 12:02:48 PM UTC-4, floria...@gmail= ..com wrote:
How= is it O(n=C2=B2 log n)?
end - begin is O(1) (random access iterator)
out_begin + n is O(1) (random acces= s iterator)
std::iota(= out_begin, out_end, 0) is O(n)
std::sort(out_begin, out_end, [&begin](auto lhs, auto r= hs) { return begin[lhs] < begin[rhs]; }) is O(n log n)=C2=A0 ( be= gin[] is O(1))

In the end, this is O(n log n).
Maybe I have assum= ed random access iterators where they are not, but otherwise, it is O(n log= n).

Le lundi 4 juin 2018 17:51:49 UTC+2, joshua.r.ma...@gmail.co= m a =C3=A9crit=C2=A0:
Unfortunately, that approach computes and is correct but is n= ot efficient enough to be seriously considered in my area.=C2=A0 That appro= ach ends up being something like O(n^2 log n).=C2=A0 Naive tuned algorithms= 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 log n tim= e with some acceptable workspace.


On Monday, Ju= ne 4, 2018 at 11:36:49 AM UTC-4, floria...@gmail.com wrote:
I have the feeling we don&#= 39;t a new interface for that:
<= code>
template< typename RandomAccess_Iterator, typename Output_Iterator >
void get_suffix_array(RandomAccess_Iterator <= /span>begin, RandomAc= cess_Iterator end, Output_Iterator out_begin) {
=C2=A0 =C2=A0<= /span>// fe= w preparations
=C2=A0 =C2=A0const auto n =3D end - begin;
=C2=A0 =C2=A0auto o= ut_end =3D out_begin + n;
=C2= =A0 =C2=A0 // actual work
=C2=A0 =C2=A0std::iota(out_begin, out_end, 0);<= /span>
= =C2=A0 =C2=A0std::sort(out_begin, out_end, [&begin](auto lhs, auto rhs) { return begin[lhs] <= ; begin[rhs]; });
}

W= ould that be enough?

Le lundi 4 juin 2018 17:14:52 UTC+2, joshua.= r.ma...@gmail.com a =C3=A9crit=C2=A0:
A more limited change to the sorts made availab= le is adding a discrete suffix array function.=C2=A0 For the uninitiated, a= suffix array is unlike a typical sorting algorithm in two respects: the re= turned object is a sequence of indexes or reference into the original conta= iner, and in the case of ties, subordering is dictated by a comparison of e= ach index's or reference's following value in the original containe= r with the terminal value being the global minimum value.

The two significant algorithms for generating suffix arrays right n= ow are SACA-K and divsufsort.

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

template&l= t; typename _Bidirectional_Iterator, typename _Output_Iterator >
void get_suffix_array(_Bidirectional_Iterator begin, _Bidirectional= _Iterator end, _Output_Iterator out);

This would h= ave applications in compression, text searching, and sequence alignment.

--
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/bd3e0341-6843-43d2-82d6-27fb7a9529d7= %40isocpp.org.
------=_Part_25864_1229247947.1528129767281-- ------=_Part_25863_481596994.1528129767281-- .