Re: [Seqan-dev] Simple radix tree for a set of strings

["Tran Ngoc Hieu (Dr)" <NHTran@ntu.edu.sg>]

Hi Enrico,

Thank you for your advice, I will try to work it out.

Regards,
Hieu

-----Original Message-----
From: Siragusa, Enrico [mailto:Enrico.Siragusa@fu-berlin.de] 
Sent: Monday, 3 August, 2015 10:31 PM
To: SeqAn Development
Cc: Tran Ngoc Hieu (Dr)
Subject: Re: [Seqan-dev] Simple radix tree for a set of strings

Dear Hieu,

You can implement a static trie (having edges labeled by single characters) using the IndexSa class. Such data structure stores only trie leaves (i.e. the suffix array), while its iterator derives inner nodes via binary search.

Alternatively, you can implement a static radix tree (having edges labeled by substrings) by means of the IndexWotd class (i.e. a lazy suffix tree). This data structure explicitly stores inner nodes, thus it consumes slightly more space than IndexSa.

The construction API is very minimal (see https://github.com/seqan/seqan/issues/1063), but it's not yet documented as it's not standardized - if you need further assistance, we could continue this discussion on github (https://github.com/seqan/seqan/issues/1063).

After construction, both indices can be iterated top-down just like virtual suffix tries/trees (see http://seqan.readthedocs.org/en/master/Tutorial/IndexIterators.html).

Cheers,
Enrico

On 24 Jul 2015, at 08:24, Tran Ngoc Hieu (Dr) <NHTran@ntu.edu.sg> wrote:

> Dear All,
>  
> Could you please advise if there is any built-in way to construct a simple radix tree of a given set of strings? I don't need random access to prefixes or suffixes of individual strings. I only need a DFS iterator to traverse from the first to the last character of each string.
>  
> A simple example: if my set is {"to", "tea", "ten"}, then I need to process in this order: "t", "te", "tea", "ten", "to".
>  
> I know that some built-in SeqAn indices, e.g. IndexSa, can do what I want, and even offer more support but they also require more memory space. So is there any simple way to do that?
>  
> Thanks a lot!
>  
> Regards,
> Hieu
>  
> 
> CONFIDENTIALITY: This email is intended solely for the person(s) named and may be confidential and/or privileged. If you are not the intended recipient, please delete it, notify us and do not copy, use, or disclose its contents.
> Towards a sustainable earth: Print only when necessary. Thank you. _______________________________________________
> seqan-dev mailing list
> seqan-dev@lists.fu-berlin.de
> https://lists.fu-berlin.de/listinfo/seqan-dev