Page 2 of 2 FirstFirst 12
Results 31 to 32 of 32

Thread: BWTIL: a set of tools to work with BWT-based text indexes

  1. #31
    Member
    Join Date
    Aug 2014
    Location
    Udine
    Posts
    17
    Thanks
    2
    Thanked 3 Times in 1 Post
    Quote Originally Posted by nburns View Post
    With respect to de Bruijn sequences being a worst case, I was thinking of the hypothetical hash table (due to potentially ballooning memory requirements), not your data structures.
    Ah, yes you are right, probably with some hash functions de Bruijn seq represent the worst case since they present all possible combinations of input.

    Quote Originally Posted by nburns View Post
    It's an interesting feature of text problems that the best case for one algorithm is the worst case for another and vice versa.
    Totally agree

  2. #32
    Member
    Join Date
    Aug 2014
    Location
    Udine
    Posts
    17
    Thanks
    2
    Thanked 3 Times in 1 Post
    Quote Originally Posted by nburns View Post
    The online construction for deBruijn automata probably parallels the one for suffix trees.
    yap, it resembles Ukkonen's algorithm, though is much simpler: once in a state, if you read character 'c' in the text and edge labeled 'c' does not exists, then create it together with the new state. Otherwise, follow the edge.

Page 2 of 2 FirstFirst 12

Similar Threads

  1. Rawzor, how does it work?
    By SZGY in forum Data Compression
    Replies: 33
    Last Post: 23rd November 2017, 00:43
  2. Quo Vadis JPEG - ISO Work Starts
    By thorfdbg in forum Data Compression
    Replies: 0
    Last Post: 2nd November 2012, 17:04
  3. Why does BWT work on images?
    By m^2 in forum Data Compression
    Replies: 6
    Last Post: 21st September 2012, 03:46
  4. Getting JOCL to work.
    By Piotr Tarsa in forum The Off-Topic Lounge
    Replies: 1
    Last Post: 27th October 2010, 23:50
  5. Interesting tools
    By lunaris in forum Data Compression
    Replies: 2
    Last Post: 25th August 2009, 23:50

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •