Opened 2 years ago
Closed 4 months ago
#23573 closed enhancement (fixed)
Implement suffix walk for suffix tree
Reported by: | enadeau | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.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) | Commit: | be5c111f82fb073a80f31e6ac23540077002503e |
Dependencies: | Stopgaps: |
Description (last modified by )
A suffix walk takes a node path-labeled "aw" with "a" a letter and return the state path-labeled "w".
Change History (34)
comment:1 Changed 2 years ago by
- Branch set to u/enadeau/implement_suffix_walk_for_suffix_tree
comment:2 Changed 2 years ago by
- Commit set to 080c1797efa69a9a40214d77e410d02fd93c2ea5
- Status changed from new to needs_review
comment:3 Changed 2 years ago by
- Description modified (diff)
comment:4 Changed 2 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 2 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 2 years ago by
Recursion is slow in Python. You would better implement a more direct loop.
comment:7 Changed 2 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 2 years ago by
comment:9 Changed 19 months 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 5 months 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 5 months ago by
- Cc nadialafreniere added
comment:12 Changed 5 months ago by
- Keywords fpsac2019 added
comment:13 Changed 5 months 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 5 months 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 5 months 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 5 months 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 5 months 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 5 months ago by
- Milestone changed from sage-8.1 to sage-8.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 5 months 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/sage-patchbot/sage/local/lib/python2.7/runpy.py", line 174, in _run_module_as_main [dochtml] "__main__", fname, loader, pkg_name) [dochtml] File "/local/sage-patchbot/sage/local/lib/python2.7/runpy.py", line 72, in _run_code [dochtml] exec code in run_globals [dochtml] File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module> [dochtml] main() [dochtml] File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1719, in main [dochtml] builder() [dochtml] File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 354, in _wrapper [dochtml] getattr(get_builder(document), 'inventory')(*args, **kwds) [dochtml] File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 550, in _wrapper [dochtml] build_many(build_ref_doc, L) [dochtml] File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 288, in _build_many [dochtml] ret = x.get(99999) [dochtml] File "/local/sage-patchbot/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 'doc-html' failed make[1]: *** [doc-html] Error 1
comment:20 Changed 5 months ago by
Note that the argument tuple unpacking was removed in Python 3: https://www.python.org/dev/peps/pep-3113/
comment:21 follow-up: ↓ 22 Changed 5 months 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 ; follow-up: ↓ 23 Changed 5 months 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 5 months ago by
Yes ticket:28182 is affected. Minor changes in function call will be sufficient. I'm working on it.
comment:24 Changed 5 months ago by
- Status changed from needs_work to needs_review
comment:25 Changed 5 months ago by
- Status changed from needs_review to positive_review
comment:26 Changed 5 months 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 123-125 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/sage-patchbot/.local/lib/python3.5/site-packages/sage_patchbot/patchbot.py", line 1126, in test_a_ticket baseline=baseline, **kwds) File "/home/sage-patchbot/.local/lib/python3.5/site-packages/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 5 months ago by
You can add old_s = None
before the loop.
comment:28 Changed 5 months 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 5 months 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#the-docstring-of-a-function-content ). Then you can feel free to reset positive review if you're ok with my changes.
comment:30 Changed 4 months 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 4 months 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 4 months 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 4 months 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 4 months 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