Opened 11 years ago
Last modified 8 years ago
#12225 new enhancement
Finite and lazy factorial languages
Reported by: | vdelecroix | Owned by: | vdelecroix |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | combinatorics | Keywords: | word, factorial language, symbolic dynamics |
Cc: | sstarosta, slabbe, tmonteil | Merged in: | |
Authors: | Vincent Delecroix | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12224 | Stopgaps: |
Description (last modified by )
1) Implement a data structure (similar to a tree with label on edges) for finite factorial language which extends the actual SuffixTrie? and SuffixTree? in sage/combinat/words/suffix_tree.py (a "RauzyCastle?").
2.a) Use it in a static version for the implementation of finite factorial language
2.b) Use it in a dynamical version for the implementation of some lazy languages (square free, cube free, overlap free, finite defect, ...)
Change History (9)
comment:1 Changed 11 years ago by
- Dependencies set to #12224
- Description modified (diff)
- Owner changed from Vincent Delecroix to vdelecroix
- Summary changed from Finite and some lazy factorial language to Finite and lazy factorial languages
comment:2 follow-ups: ↓ 3 ↓ 5 Changed 11 years ago by
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 11 years ago by
Hi Sebastien,
Nice ticket!
Thanks! It now needs work!
Related to this, I want to add that I want to remove the class and the file
nfactor_enumerable_word
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.
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).
Before submitting a patch, I want to fix #12224 (Use Parent/Element? and GradedEnumeratedSets? for Language).
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.
comment:4 in reply to: ↑ 3 Changed 11 years ago by
Nice ticket!
Thanks! It now needs work!
Indeed...
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).
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 : http://sage.math.washington.edu/home/slabbe/patches/ (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...
Before submitting a patch, I want to fix #12224 (Use Parent/Element? and GradedEnumeratedSets? for Language).
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.
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.
sage: w.factors(algorithm="first slow python implementation") sage: w.factors(algorithm="cython implementation")
Sébastien
comment:5 in reply to: ↑ 2 Changed 11 years ago by
Related to this, I want to add that I want to remove the class and the file
nfactor_enumerable_word
from Sage.
This is now : #12380
comment:6 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:7 Changed 9 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:8 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:9 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
Nice ticket!
Related to this, I want to add that I want to remove the class and the file
nfactor_enumerable_word
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.Sébastien