Opened 5 years ago

Closed 5 years ago

#23568 closed enhancement (fixed)

Improve crochemore factorization for word

Reported by: Emile Nadeau Owned by: Emile Nadeau
Priority: major Milestone: sage-8.1
Component: combinatorics Keywords: words, suffix tree, factorization
Cc: Franco Saliola Merged in:
Authors: Émile Nadeau Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: b0350fa (Commits, GitHub, GitLab) Commit: b0350fa4e5fa55df5c7cf69edc63b4f29112d158
Dependencies: Stopgaps:

Status badges

Description (last modified by Vincent Delecroix)

Implement Lempel-Ziv computation for suffix tree and use it to improve the Crochemore factorization for words.

Add alias so the user can use either LZ_decomposition or crochemore_factorization to get the results.

Change History (16)

comment:1 Changed 5 years ago by Emile Nadeau

Owner: set to Emile Nadeau

comment:2 Changed 5 years ago by Emile Nadeau

Milestone: sage-8.0sage-8.1

comment:3 Changed 5 years ago by Emile Nadeau

Branch: u/enadeau/improve_crochemore_factorization_for_word

comment:4 Changed 5 years ago by Emile Nadeau

Commit: b4e9dbffc9c6d38efbb63a6ad041b76158aaa27e
Status: newneeds_review

New commits:

38317beTrac #23568: Implement LZ-decomposition for suffix tree
b4e9dbfTrac #23568: Improve crochemore factorization for word using the

comment:5 Changed 5 years ago by Emile Nadeau

Cc: Franco Saliola added

comment:6 Changed 5 years ago by git

Commit: b4e9dbffc9c6d38efbb63a6ad041b76158aaa27ee661747d6fdecd1a2d6a37fac499e738afbaf38c

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

e661747Trac #23568: Correct code formating

comment:7 Changed 5 years ago by Vincent Delecroix

Reviewers: Vincent Delecroix
Status: needs_reviewneeds_work

The code looks good. Here are two organization remarks.

If you really want LZ_decomposition as an alias you would better do

class A:
    def f(self):
       ...

    g = f

That way the documentation appears identical on both methods.

In the documentation you should respect spaces around equality sign: A = B and not A=B.

comment:8 Changed 5 years ago by git

Commit: e661747d6fdecd1a2d6a37fac499e738afbaf38cbd356b7c1ba6d9b72a118edac00298b9d5fd9d1b

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

870223dMerge branch 'u/enadeau/improve_crochemore_factorization_for_word' of git://trac.sagemath.org/sage into t/23568/improve_crochemore_factorization_for_word
bd356b7Formating and correct definition of the alias

comment:9 Changed 5 years ago by Emile Nadeau

Status: needs_workneeds_review

comment:10 Changed 5 years ago by Vincent Delecroix

Last tiny remark. As you can read in the developer manual the documentation should start with a one line description. Then you can have an extended description , INPUT/OUTPUT blocks, etc.

comment:11 Changed 5 years ago by git

Commit: bd356b7c1ba6d9b72a118edac00298b9d5fd9d1bb0350fa4e5fa55df5c7cf69edc63b4f29112d158

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

b0350faAdd a short sentence description of LZ_decomposition

comment:12 Changed 5 years ago by Emile Nadeau

I think it's good now. Thank you for the review

comment:13 Changed 5 years ago by Vincent Delecroix

Description: modified (diff)

You still need to fill the "Authors" field of the ticket.

comment:14 Changed 5 years ago by Emile Nadeau

Authors: Émile Nadeau

comment:15 Changed 5 years ago by Vincent Delecroix

Status: needs_reviewpositive_review

comment:16 Changed 5 years ago by Volker Braun

Branch: u/enadeau/improve_crochemore_factorization_for_wordb0350fa4e5fa55df5c7cf69edc63b4f29112d158
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.