Opened 13 years ago

Last modified 13 years ago

#7642 needs_work enhancement

Add an implementation of LCA to sage.combinat.words.suffix_trees

Reported by: Arnaud Bergeron Owned by:
Priority: major Milestone:
Component: combinatorics Keywords: lca suffix_tree
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

I have implemented the linear time preprocessing, constant-time queries algorithm for the lowest common ancestor (LCA) in the context of the suffix trees for words.

The only thing I'm not very sure about is where to place the bit manipulation functions.

Attachments (1)

trac_7642.patch (14.2 KB) - added by Arnaud Bergeron 13 years ago.

Download all attachments as: .zip

Change History (5)

Changed 13 years ago by Arnaud Bergeron

Attachment: trac_7642.patch added

comment:1 Changed 13 years ago by Arnaud Bergeron

Status: newneeds_review

comment:2 Changed 13 years ago by Nathann Cohen

Several comments about this patch :

  • leftmost_one naturally fails on 0, as it computes a logarithm... Shouldn't this be documented, or the exception handled inside the function, to return something like -1 ?
  • bits_left_of seems to me a bit vague for what the function does... What would you think of leftmost_bits ? The docstring could be more explicit, like : substracts from x the leftmost i bits in its "base-2 expression" (I do not know how this is said in english) :-) Same remark for bits_right_of
  • I have no idea of what a MSB is, and could find its definition nowhere. Could you at least write its full name ? ( samek remark for lca, which appears very often in the docstrings )
  • I think you should define _ldata inside of the init function
  • I am not a big fan of your algorithm = best argument in LCA. The user is bound to know if the tree has been preprocessed, as he has to call it himself. I think it is just a sourc e of silent failures to use the "fast" algorithm.

What you are doing in this patch is out of my field, so my remarks could just come from this. I thought it would just be an algorithm on trees, but many details not being explicit in the docstrings, it is difficult for me to fill the holes... :-)

Nathann

comment:3 Changed 13 years ago by David Kirkby

Owner: Sage Combinat CC user deleted

Has this been checked on Solaris?

There's general information about building on Solaris at

http://wiki.sagemath.org/solaris

Information specifically for 't2' at

http://wiki.sagemath.org/devel/Building-Sage-on-the-T5240-t2

Both the source (4.3.0.1 is the latest to build on Solaris) and a binary which will run on any SPARC can be found at http://www.sagemath.org/download-source.html

Dave

comment:4 Changed 13 years ago by Nathann Cohen

Status: needs_reviewneeds_work
Note: See TracTickets for help on using tickets.