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 enadeau)

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 enadeau

  • Branch set to u/enadeau/implement_suffix_walk_for_suffix_tree

comment:2 Changed 2 years ago by enadeau

  • Commit set to 080c1797efa69a9a40214d77e410d02fd93c2ea5
  • Status changed from new to needs_review

New commits:

5519165Trac #23573: Implement count and skip trick for suffix tree
080c179Trac #23573: Implement suffix walk for suffix tree

comment:3 Changed 2 years ago by enadeau

  • Description modified (diff)

comment:4 Changed 2 years ago by git

  • Commit changed from 080c1797efa69a9a40214d77e410d02fd93c2ea5 to f9a5526998e75aae1ba253d8ecd2221098e25cf6

Branch pushed to git repo; I updated commit sha1. New commits:

f9a5526Merge 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 git

  • Commit changed from f9a5526998e75aae1ba253d8ecd2221098e25cf6 to a723bd9a41e96d6f1bf4be1e5efe0e286ff4575e

Branch pushed to git repo; I updated commit sha1. New commits:

a723bd9Minor formating changes

comment:6 Changed 2 years ago by vdelecroix

Recursion is slow in Python. You would better implement a more direct loop.

comment:7 Changed 2 years ago by git

  • Commit changed from a723bd9a41e96d6f1bf4be1e5efe0e286ff4575e to 56ea6ecfa7148cfe419ea01a33685f0e78232996

Branch pushed to git repo; I updated commit sha1. New commits:

56ea6ecTrac #23573: Derecusify _count_and_skip

comment:8 Changed 2 years ago by enadeau

  • Authors set to Émile Nadeau

comment:9 Changed 19 months ago by git

  • Commit changed from 56ea6ecfa7148cfe419ea01a33685f0e78232996 to ee6881721fe5a1badadf3ab5ecba2833dc68f82c

Branch pushed to git repo; I updated commit sha1. New commits:

ee68817Merge 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 git

  • Commit changed from ee6881721fe5a1badadf3ab5ecba2833dc68f82c to bf1a23af68ccd9656877973a94d6ed28e4c500ff

Branch pushed to git repo; I updated commit sha1. New commits:

bf1a23aMerge 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 enadeau

  • Cc nadialafreniere added

comment:12 Changed 5 months ago by enadeau

  • Keywords fpsac2019 added

comment:13 Changed 5 months ago by nadialafreniere

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 nadialafreniere

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 git

  • Commit changed from bf1a23af68ccd9656877973a94d6ed28e4c500ff to 0ba0630bdadedb2ba41fdee49c09ceeead641ccf

Branch pushed to git repo; I updated commit sha1. New commits:

0ba0630Fixed the bug of leaf returned as implicit.

comment:16 Changed 5 months ago by enadeau

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 git

  • Commit changed from 0ba0630bdadedb2ba41fdee49c09ceeead641ccf to e142b47d314e5d8dd7e37efbc18bc1a4af3841f2

Branch pushed to git repo; I updated commit sha1. New commits:

e142b47clarification in the doc of suffix_walk

comment:18 Changed 5 months ago by nadialafreniere

  • 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 vbraun

  • 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 vbraun

Note that the argument tuple unpacking was removed in Python 3: https://www.python.org/dev/peps/pep-3113/

comment:21 follow-up: Changed 5 months ago by git

  • Commit changed from e142b47d314e5d8dd7e37efbc18bc1a4af3841f2 to 1967ce87f34488068b22c0db73237e4a50ff3cf5

Branch pushed to git repo; I updated commit sha1. New commits:

1967ce8remove argument tuple unpacking

comment:22 in reply to: ↑ 21 ; follow-up: Changed 5 months ago by nadialafreniere

Replying to git:

Branch pushed to git repo; I updated commit sha1. New commits:

1967ce8remove 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 enadeau

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 enadeau

  • Status changed from needs_work to needs_review

comment:25 Changed 5 months ago by nadialafreniere

  • Status changed from needs_review to positive_review

comment:26 Changed 5 months ago by enadeau

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 hderycke

You can add old_s = None before the loop.

comment:28 Changed 5 months ago by git

  • 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:

a36e767add a line to comply with pyflake

comment:29 Changed 5 months ago by kdilks

  • 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 git

  • Commit changed from a36e7677fc310dba5b1c31809a88890a7ebb4d70 to 87e9c16ea140e526ca6eef4c1b4d995bc3c2fce2

Branch pushed to git repo; I updated commit sha1. New commits:

87e9c16Merge 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 git

  • Commit changed from 87e9c16ea140e526ca6eef4c1b4d995bc3c2fce2 to be5c111f82fb073a80f31e6ac23540077002503e

Branch pushed to git repo; I updated commit sha1. New commits:

be5c111improve docstring

comment:32 Changed 4 months ago by enadeau

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 nadialafreniere

  • 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 vbraun

  • Branch changed from u/enadeau/implement_suffix_walk_for_suffix_tree to be5c111f82fb073a80f31e6ac23540077002503e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.