Opened 5 years ago
Closed 3 years ago
#23573 closed enhancement (fixed)
Implement suffix walk for suffix tree
Reported by:  enadeau  Owned by:  

Priority:  major  Milestone:  sage8.9 
Component:  combinatorics  Keywords:  fpsac2019 
Cc:  saliola, nadialafreniere, kdilks  Merged in:  
Authors:  Émile Nadeau  Reviewers:  Nadia Lafrenière 
Report Upstream:  N/A  Work issues:  
Branch:  be5c111 (Commits, GitHub, GitLab)  Commit:  be5c111f82fb073a80f31e6ac23540077002503e 
Dependencies:  Stopgaps: 
Description (last modified by )
A suffix walk takes a node pathlabeled "aw" with "a" a letter and return the state pathlabeled "w".
Change History (34)
comment:1 Changed 5 years ago by
 Branch set to u/enadeau/implement_suffix_walk_for_suffix_tree
comment:2 Changed 5 years ago by
 Commit set to 080c1797efa69a9a40214d77e410d02fd93c2ea5
 Status changed from new to needs_review
comment:3 Changed 5 years ago by
 Description modified (diff)
comment:4 Changed 5 years ago by
 Commit changed from 080c1797efa69a9a40214d77e410d02fd93c2ea5 to f9a5526998e75aae1ba253d8ecd2221098e25cf6
Branch pushed to git repo; I updated commit sha1. New commits:
f9a5526  Merge branch 'u/enadeau/implement_suffix_walk_for_suffix_tree' of git://trac.sagemath.org/sage into t/23573/implement_suffix_walk_for_suffix_tree

comment:5 Changed 5 years ago by
 Commit changed from f9a5526998e75aae1ba253d8ecd2221098e25cf6 to a723bd9a41e96d6f1bf4be1e5efe0e286ff4575e
Branch pushed to git repo; I updated commit sha1. New commits:
a723bd9  Minor formating changes

comment:6 Changed 5 years ago by
Recursion is slow in Python. You would better implement a more direct loop.
comment:7 Changed 5 years ago by
 Commit changed from a723bd9a41e96d6f1bf4be1e5efe0e286ff4575e to 56ea6ecfa7148cfe419ea01a33685f0e78232996
Branch pushed to git repo; I updated commit sha1. New commits:
56ea6ec  Trac #23573: Derecusify _count_and_skip

comment:8 Changed 5 years ago by
comment:9 Changed 4 years ago by
 Commit changed from 56ea6ecfa7148cfe419ea01a33685f0e78232996 to ee6881721fe5a1badadf3ab5ecba2833dc68f82c
Branch pushed to git repo; I updated commit sha1. New commits:
ee68817  Merge branch 'u/enadeau/implement_suffix_walk_for_suffix_tree' of git://trac.sagemath.org/sage into t/23573/implement_suffix_walk_for_suffix_tree

comment:10 Changed 3 years ago by
 Commit changed from ee6881721fe5a1badadf3ab5ecba2833dc68f82c to bf1a23af68ccd9656877973a94d6ed28e4c500ff
Branch pushed to git repo; I updated commit sha1. New commits:
bf1a23a  Merge branch 'u/enadeau/implement_suffix_walk_for_suffix_tree' of git://trac.sagemath.org/sage into t/23573/implement_suffix_walk_for_suffix_tree

comment:11 Changed 3 years ago by
 Cc nadialafreniere added
comment:12 Changed 3 years ago by
 Keywords fpsac2019 added
comment:13 Changed 3 years ago by
In the documentation of the function, you should say what d
is (the last parameter of the output). It is not specified anywhere.
comment:14 Changed 3 years ago by
There probably is something I don't understand, but I don't see why when the node is a leaf, the algorithm for self._count_and_skip()
returns implicit
just like if it stopped on an edge. For example,
sage: T = ImplicitSuffixTree(Word("cacao")) sage: T._count_and_skip(3,(2,5)) ('implicit', (3, 1), 3)
It's coherent with the condition in the code if (trans[0][1] != None [...]):
, but I don't see how it is coherent with the documentation.
comment:15 Changed 3 years ago by
 Commit changed from bf1a23af68ccd9656877973a94d6ed28e4c500ff to 0ba0630bdadedb2ba41fdee49c09ceeead641ccf
Branch pushed to git repo; I updated commit sha1. New commits:
0ba0630  Fixed the bug of leaf returned as implicit.

comment:16 Changed 3 years ago by
Your last observation was in fact a mistake, it was introduced when I derecursify the _count_and_skip
method.
I've fixed it with other minor improvements.
comment:17 Changed 3 years ago by
 Commit changed from 0ba0630bdadedb2ba41fdee49c09ceeead641ccf to e142b47d314e5d8dd7e37efbc18bc1a4af3841f2
Branch pushed to git repo; I updated commit sha1. New commits:
e142b47  clarification in the doc of suffix_walk

comment:18 Changed 3 years ago by
 Milestone changed from sage8.1 to sage8.9
 Reviewers set to Nadia Lafrenière
 Status changed from needs_review to positive_review
Thanks for the fixes! It now looks good and I think it should enter in the next version of Sage.
comment:19 Changed 3 years ago by
 Status changed from positive_review to needs_work
The documentation doesn't build:
[dochtml] [combinat ] The inventory files are in local/share/doc/sage/inventory/en/reference/combinat. [dochtml] Error building the documentation. [dochtml] Traceback (most recent call last): [dochtml] File "/local/sagepatchbot/sage/local/lib/python2.7/runpy.py", line 174, in _run_module_as_main [dochtml] "__main__", fname, loader, pkg_name) [dochtml] File "/local/sagepatchbot/sage/local/lib/python2.7/runpy.py", line 72, in _run_code [dochtml] exec code in run_globals [dochtml] File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__main__.py", line 2, in <module> [dochtml] main() [dochtml] File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 1719, in main [dochtml] builder() [dochtml] File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 354, in _wrapper [dochtml] getattr(get_builder(document), 'inventory')(*args, **kwds) [dochtml] File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 550, in _wrapper [dochtml] build_many(build_ref_doc, L) [dochtml] File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 288, in _build_many [dochtml] ret = x.get(99999) [dochtml] File "/local/sagepatchbot/sage/local/lib/python2.7/multiprocessing/pool.py", line 572, in get [dochtml] raise self._value [dochtml] OSError: WARNING: error while formatting arguments for sage.combinat.words.suffix_trees.ImplicitSuffixTree.suffix_walk: unhashable type: 'list' Makefile:2035: recipe for target 'dochtml' failed make[1]: *** [dochtml] Error 1
comment:20 Changed 3 years ago by
Note that the argument tuple unpacking was removed in Python 3: https://www.python.org/dev/peps/pep3113/
comment:21 followup: ↓ 22 Changed 3 years ago by
 Commit changed from e142b47d314e5d8dd7e37efbc18bc1a4af3841f2 to 1967ce87f34488068b22c0db73237e4a50ff3cf5
Branch pushed to git repo; I updated commit sha1. New commits:
1967ce8  remove argument tuple unpacking

comment:22 in reply to: ↑ 21 ; followup: ↓ 23 Changed 3 years ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
1967ce8 remove argument tuple unpacking
Does that affect ticket:28182?
Otherwise, the doc now seems to build.
comment:23 in reply to: ↑ 22 Changed 3 years ago by
Yes ticket:28182 is affected. Minor changes in function call will be sufficient. I'm working on it.
comment:24 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:25 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:26 Changed 3 years ago by
The patchbot does not pass the pyflakes test but the error mentioned is completely unrelated to the changes that were made. Moreover, as far as I can tell, the error reported is not a real error since the if statement on line 123125 won't be entered on the first pass of the loop when old_s
is still undefined. Hence, I don't think any change to the code is needed.
Is there any way to silence the error?
========== pyflakes ========== git checkout patchbot/ticket_merged Bereits auf 'patchbot/ticket_merged' src/sage/combinat/words/suffix_trees.py:125: undefined name 'old_s' found 1 pyflakes errors in the modified files Traceback (most recent call last): File "/home/sagepatchbot/.local/lib/python3.5/sitepackages/sage_patchbot/patchbot.py", line 1126, in test_a_ticket baseline=baseline, **kwds) File "/home/sagepatchbot/.local/lib/python3.5/sitepackages/sage_patchbot/plugins.py", line 281, in pyflakes raise ValueError(full_msg) ValueError: found 1 pyflakes errors in the modified files pyflakes  0 seconds ========== end pyflakes ==========
comment:27 Changed 3 years ago by
You can add old_s = None
before the loop.
comment:28 Changed 3 years ago by
 Commit changed from 1967ce87f34488068b22c0db73237e4a50ff3cf5 to a36e7677fc310dba5b1c31809a88890a7ebb4d70
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
a36e767  add a line to comply with pyflake

comment:29 Changed 3 years ago by
 Cc kdilks added
I'll make some minor changes to the docstring phrasing while I'm at Sage Days to have it be a little bit more in line with the General Conventions ( http://doc.sagemath.org/html/en/developer/coding_basics.html#thedocstringofafunctioncontent ). Then you can feel free to reset positive review if you're ok with my changes.
comment:30 Changed 3 years ago by
 Commit changed from a36e7677fc310dba5b1c31809a88890a7ebb4d70 to 87e9c16ea140e526ca6eef4c1b4d995bc3c2fce2
Branch pushed to git repo; I updated commit sha1. New commits:
87e9c16  Merge branch 'u/enadeau/implement_suffix_walk_for_suffix_tree' of git://trac.sagemath.org/sage into t/23573/implement_suffix_walk_for_suffix_tree

comment:31 Changed 3 years ago by
 Commit changed from 87e9c16ea140e526ca6eef4c1b4d995bc3c2fce2 to be5c111f82fb073a80f31e6ac23540077002503e
Branch pushed to git repo; I updated commit sha1. New commits:
be5c111  improve docstring

comment:32 Changed 3 years ago by
I've updated the branch for 8.9beta4 and updated the docstring. kdilks did you have anything other improvements in mind for the doctring?
comment:33 Changed 3 years ago by
 Status changed from needs_review to positive_review
Since kdilks doesn't answer, I am resetting the positive review. The patchbot tests now seem fine.
Thanks Émile for this contribution!
comment:34 Changed 3 years ago by
 Branch changed from u/enadeau/implement_suffix_walk_for_suffix_tree to be5c111f82fb073a80f31e6ac23540077002503e
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac #23573: Implement count and skip trick for suffix tree
Trac #23573: Implement suffix walk for suffix tree