Sage: Ticket #12225: Finite and lazy factorial languages
https://trac.sagemath.org/ticket/12225
<p>
1) Implement a data structure (similar to a tree with label on edges) for finite factorial language which extends the actual <a class="missing wiki">SuffixTrie?</a> and <a class="missing wiki">SuffixTree?</a> in sage/combinat/words/suffix_tree.py (a "<a class="missing wiki">RauzyCastle?</a>").
</p>
<p>
2.a) Use it in a static version for the implementation of finite factorial language
</p>
<p>
2.b) Use it in a dynamical version for the implementation of some lazy languages (square free, cube free, overlap free, finite defect, ...)
</p>
<p>
see also: <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/12224" title="enhancement: Language as parent / Word as element (needs_work)">#12224</a>, <a class="new ticket" href="https://trac.sagemath.org/ticket/12227" title="enhancement: Adic languages (new)">#12227</a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/12225
Trac 1.1.6vdelecroixFri, 23 Dec 2011 11:17:51 GMTowner, description, summary changed; dependencies set
https://trac.sagemath.org/ticket/12225#comment:1
https://trac.sagemath.org/ticket/12225#comment:1
<ul>
<li><strong>owner</strong>
changed from <em>Vincent Delecroix</em> to <em>vdelecroix</em>
</li>
<li><strong>dependencies</strong>
set to <em>#12224</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12225?action=diff&version=1">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Finite and some lazy factorial language</em> to <em>Finite and lazy factorial languages</em>
</li>
</ul>
TicketslabbeTue, 10 Jan 2012 19:55:08 GMT
https://trac.sagemath.org/ticket/12225#comment:2
https://trac.sagemath.org/ticket/12225#comment:2
<p>
Nice ticket!
</p>
<p>
Related to this, I want to add that I want to remove the class and the file <code>nfactor_enumerable_word</code> from Sage. Currently, only Finite Word class inherits from it. So it would be easy to fix by just moving the methods to the Finite Word class. I am sorry for having introduced this class into Sage : it was an error. This job must be done inside of the appropriate Language class... I still haven't created the ticket for it, but I definitively will.
</p>
<p>
Sébastien
</p>
TicketvdelecroixTue, 10 Jan 2012 21:34:43 GMT
https://trac.sagemath.org/ticket/12225#comment:3
https://trac.sagemath.org/ticket/12225#comment:3
<p>
Hi Sebastien,
</p>
<blockquote class="citation">
<p>
Nice ticket!
</p>
</blockquote>
<p>
Thanks! It now needs work!
</p>
<blockquote class="citation">
<p>
Related to this, I want to add that I want to remove the class and the file <code>nfactor_enumerable_word</code> from Sage. Currently, only Finite Word class inherits from it. So it would be easy to fix by just moving the methods to the Finite Word class. I am sorry for having introduced this class into Sage : it was an error. This job must be done inside of the appropriate Language class... I still haven't created the ticket for it, but I definitively will.
</p>
</blockquote>
<p>
I have some patch almost ready for it. It is just an update of suffix_trie into a prefix_suffix_trie. The data structure I used is perhaps not optimal (many dictionnaries that points toward other dictionnaries). It would be very nice to have a low-level implementation as the one used in Graph as well as a sparse and a dense version (certainly another ticket).
</p>
<p>
Before submitting a patch, I want to fix <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/12224" title="enhancement: Language as parent / Word as element (needs_work)">#12224</a> (Use <a class="missing wiki">Parent/Element?</a> and <a class="missing wiki">GradedEnumeratedSets?</a> for Language).
</p>
<p>
I have a questions for you : do we remove suffix_trie and use this new class instead ? (I made some timings and it seems that mine is twice slower, which is not so good or not so bad) Anyway, if yes, it is for another ticket.
</p>
TicketslabbeTue, 10 Jan 2012 22:06:45 GMT
https://trac.sagemath.org/ticket/12225#comment:4
https://trac.sagemath.org/ticket/12225#comment:4
<blockquote class="citation">
<blockquote class="citation">
<p>
Nice ticket!
</p>
</blockquote>
<p>
Thanks! It now needs work!
</p>
</blockquote>
<p>
Indeed...
</p>
<blockquote class="citation">
<p>
I have some patch almost ready for it. It is just an update of suffix_trie into a prefix_suffix_trie. The data structure I used is perhaps not optimal (many dictionnaries that points toward other dictionnaries). It would be very nice to have a low-level implementation as the one used in Graph as well as a sparse and a dense version (certainly another ticket).
</p>
</blockquote>
<p>
I once rewrote the code of suffix_tree and was able to improve timing (something like 40%) just by choosing better data structures (dict instead of list or vice versa). My patches does not apply anymore because of conflicts but it is here : <a class="ext-link" href="http://sage.math.washington.edu/home/slabbe/patches/"><span class="icon"></span>http://sage.math.washington.edu/home/slabbe/patches/</a> (starts with suffix_something). I did not push it any further, because I wanted instead to rewrite suffix tree code in cython, which we did for the suffix tree. But this construction is quadratic in the length of the (finite) word, and I want it to be linear. So, my next step was to implement the suffix_trie in cython, but I never did...
</p>
<blockquote class="citation">
<p>
Before submitting a patch, I want to fix <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/12224" title="enhancement: Language as parent / Word as element (needs_work)">#12224</a> (Use <a class="missing wiki">Parent/Element?</a> and <a class="missing wiki">GradedEnumeratedSets?</a> for Language).
</p>
<p>
I have a questions for you : do we remove suffix_trie and use this new class instead ? (I made some timings and it seems that mine is twice slower, which is not so good or not so bad) Anyway, if yes, it is for another ticket.
</p>
</blockquote>
<p>
Well, I would say not to delete it first. Just add a new implementation beside it. And, for some time, one could choose the algorithm or implementation. Later, we could delete the initial implementation.
</p>
<pre class="wiki">sage: w.factors(algorithm="first slow python implementation")
sage: w.factors(algorithm="cython implementation")
</pre><p>
Sébastien
</p>
TicketslabbeSun, 29 Jan 2012 04:12:13 GMT
https://trac.sagemath.org/ticket/12225#comment:5
https://trac.sagemath.org/ticket/12225#comment:5
<blockquote class="citation">
<p>
Related to this, I want to add that I want to remove the class and the file <code>nfactor_enumerable_word</code> from Sage.
</p>
</blockquote>
<p>
This is now : <a class="closed ticket" href="https://trac.sagemath.org/ticket/12380" title="enhancement: Move methods from Word_nfactor_enumerable to FiniteWord_class (closed: fixed)">#12380</a>
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/12225#comment:6
https://trac.sagemath.org/ticket/12225#comment:6
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/12225#comment:7
https://trac.sagemath.org/ticket/12225#comment:7
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/12225#comment:8
https://trac.sagemath.org/ticket/12225#comment:8
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/12225#comment:9
https://trac.sagemath.org/ticket/12225#comment:9
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
Ticket