Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Michael Selik Newsgroups: comp.lang.python Subject: Re: Detecting repeated subsequences of identical items Date: Thu, 21 Apr 2016 06:49:52 +0000 Lines: 39 Message-ID: References: <571843f9$0$1585$c3e8da3$5496439d@news.astraweb.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: news.uni-berlin.de tVduFQhxiI3xpd0hSoizOQxCW4Ee6Adw6w1Y/Vxe8EMg== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.038 X-Spam-Evidence: '*H*': 0.92; '*S*': 0.00; '21,': 0.07; 'subsequence': 0.07; 'wed,': 0.15; 'thu,': 0.15; '2016': 0.16; 'clustering': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'repetitions': 0.16; 'statement.': 0.16; 'subject:Detecting': 0.16; 'subsequences': 0.16; 'to:addr:pearwood.info': 0.16; "to:name:steven d'aprano": 0.16; 'wrote:': 0.16; 'have:': 0.18; 'nested': 0.18; 'email addr:gmail.com>': 0.18; 'first,': 0.20; 'to:2**1': 0.21; 'url:edu': 0.24; 'header:In-Reply-To:1': 0.24; 'skip:" 20': 0.26; 'least': 0.27; 'message-id:@mail.gmail.com': 0.27; 'defining': 0.27; 'correct': 0.28; '"no': 0.29; "i'm": 0.30; 'skip:& 30': 0.30; 'checked': 0.31; 'problem': 0.33; 'michael': 0.33; "d'aprano": 0.33; 'steven': 0.33; 'open': 0.33; 'this?': 0.34; 'add': 0.34; 'received:google.com': 0.35; 'received:74.125.82': 0.35; 'problem.': 0.35; 'but': 0.36; 'too': 0.36; 'to:addr:python-list': 0.36; 'subject:: ': 0.37; 'two': 0.37; 'skip:& 10': 0.37; 'detail': 0.38; 'minimum': 0.38; 'does': 0.39; 'to:addr:python.org': 0.40; 'some': 0.40; 'your': 0.60; 'more': 0.63; 'url:pdf': 0.64; 'series': 0.65; '20,': 0.66; 'url:2014': 0.66; 'results': 0.66; 'results.': 0.67; 'sound': 0.72; 'paper': 0.73; 'sounds': 0.76; 'music': 0.78; 'metaphor.': 0.84; 'territory.': 0.84; 'url:ucr': 0.84 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=dHquGvXssRwbPumreBDYkgsWa9hdjjnk5w/yFJfiqXY=; b=hz7mOVBPTDqiiRQrFzCaq/c6nOs7K2grzPI2dHKcVUXngICdf4wwgftIzShNjxu+jm iNq2unETa8NyP1vvuLAC4qZi+UXxI3Om4eA/snF8ls7WdA2qUBBisVOrsEFb+yPW9EjO uQluqc34G+L6kGhUznOUKksR3tCiBKsd13eHKpws9SNYhsweaMdnCDAW7o80Uvqhags6 tvqBYNPuumKZGQ/QHgkxQVYKMp2NxYgabwKmWRoPImQiPYowsj3VRwHtZutD+nWUcHTS VtQuDNdFFwiCmnWSirxBqlRJbYy6/KtRnQiestUI28LOWynUGcHwegNgOFBrC50gctVq LdVw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=dHquGvXssRwbPumreBDYkgsWa9hdjjnk5w/yFJfiqXY=; b=c2+6KL6zJ50H0fNgd+JNfPMlbnqYmpAWzpMolyHEl5GlGwvhan8LKRA90DsgEPoVw+ +xUXmOqqIaMjbENNXtYVlulMEj3ifpzKgxcQloEOPANK1H228DbRaAgbxqyuR953XVOX wUMDbxVH1DMckHcHJRJ47EW+PMLlNjUCiBXke1RJTDVHv2+lHAm6Nylv0Zl/FO7BEp85 gfWAZwLEmXDFkeWiEqQ0Kr/Y40gGOedDsvLy2JpK/i3FRdpW6uiOEgnSuRIOYsrAcO7R tUIjS6mZ3icXm64WNzCBdDD7vQRkqrg22ld8xHcD+fgD7gI5rBQQ/eNYQMZAtlSUIZcD 6Sng== X-Gm-Message-State: AOPr4FWUvBMGh75uh7bDtTbEu5uJlV1V5tYZIh0H6dSKXBtsluP46rl0Pnw/D6pC9wtlC+dH3aLjG1dpjO85xg== X-Received: by 10.28.20.198 with SMTP id 189mr34218581wmu.103.1461221401421; Wed, 20 Apr 2016 23:50:01 -0700 (PDT) In-Reply-To: X-Content-Filtered-By: Mailman/MimeDel 2.1.22 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Mailman-Original-Message-ID: X-Mailman-Original-References: <571843f9$0$1585$c3e8da3$5496439d@news.astraweb.com> Xref: csiph.com comp.lang.python:107438 On Thu, Apr 21, 2016 at 2:35 AM Michael Selik wrote: > On Wed, Apr 20, 2016 at 11:11 PM Steven D'Aprano > wrote: > >> I want to group [repeated] subsequences. For example, I have: >> "ABCABCABCDEABCDEFABCABCABCB" >> and I want to group it into repeating subsequences. I can see two >> ways... How can I do this? Does this problem have a standard name and/or >> solution? >> > > I'm not aware of a standard name. This sounds like an unsupervised > learning problem. There's no objectively correct answer unless you add more > specificity to the problem statement. > > Regexes may sound tempting at first, but because a repeating subsequence > may have nested repeating subsequences and this can go on infinitely, I > think we at least need a push-down automata. > > I checked out some links for clustering algorithms that work on series > subsequences and I found some fun results. > > Clustering is meaningless! > http://www.cs.ucr.edu/~eamonn/meaningless.pdf > > I think you're in "no free lunch" territory. "Clustering of subsequence > time series remains an open issue in time series clustering" > http://www.hindawi.com/journals/tswj/2014/312521/ > > Any more detail on the problem to add constraints? > Some light reading suggests that you can improve your problem by defining a minimum size for a subsequence to qualify. One paper suggests calling these more interesting repetitions a "motif" to use a music metaphor. Looking for any repetitions results in too many trivial results. Is that valid for your usage?