473,221 Members | 2,140 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,221 software developers and data experts.

compressed suffix trie

Hi all,

I want to build a compressed suffix trie from a string for string
matching.instead of doing like:

input:a string with 10 chars

insert char array 10
insert char array 9,10
insert char array 8,9,10
....
insert char array 1,2,3,4,5,6,7,8,9,10
is there any efficient way to build a trie?
the above method is toooo slow and consum much memory!


Thanks a lot guys
Jul 22 '05 #1
3 4342
Joseph wrote:
I want to build a compressed suffix trie from a string for string
matching.instead of doing like:

input:a string with 10 chars

insert char array 10
insert char array 9,10
insert char array 8,9,10
...
insert char array 1,2,3,4,5,6,7,8,9,10
is there any efficient way to build a trie?
the above method is toooo slow and consum much memory!


char array[11] = {0};
const char * const trie[] = { array + 9, array + 8, ... , array };

Now input your 10 chars in 'array' and use 'trie[5]' to get to
the fifth (sixth) "string".

You can use the same method for dynamically sized string and trie.

Victor
Jul 22 '05 #2
Victor Bazarov <v.********@comAcast.net> wrote in news:ZAi4d.2801$Ae.2102
@newsread1.dllstx09.us.to.verio.net:
Joseph wrote:
I want to build a compressed suffix trie from a string for string
matching.instead of doing like:

input:a string with 10 chars

insert char array 10
insert char array 9,10
insert char array 8,9,10
...
insert char array 1,2,3,4,5,6,7,8,9,10
is there any efficient way to build a trie?
the above method is toooo slow and consum much memory!


char array[11] = {0};
const char * const trie[] = { array + 9, array + 8, ... , array };

Now input your 10 chars in 'array' and use 'trie[5]' to get to
the fifth (sixth) "string".

You can use the same method for dynamically sized string and trie.

Victor


Oh ,sorry ,I mean,is there any faster way to do the compression?
OR a dynamic way ?to do the insertion and compression at same time
Jul 22 '05 #3
Joseph wrote:
Victor Bazarov <v.********@comAcast.net> wrote in news:ZAi4d.2801$Ae.2102
@newsread1.dllstx09.us.to.verio.net:

Joseph wrote:
I want to build a compressed suffix trie from a string for string
matching.instead of doing like:

input:a string with 10 chars

insert char array 10
insert char array 9,10
insert char array 8,9,10
...
insert char array 1,2,3,4,5,6,7,8,9,10
is there any efficient way to build a trie?
the above method is toooo slow and consum much memory!


char array[11] = {0};
const char * const trie[] = { array + 9, array + 8, ... , array };

Now input your 10 chars in 'array' and use 'trie[5]' to get to
the fifth (sixth) "string".

You can use the same method for dynamically sized string and trie.

Victor

Oh ,sorry ,I mean,is there any faster way to do the compression?
OR a dynamic way ?to do the insertion and compression at same time


Oh, sorry, I thought you're asking a C++ language question. You should
find a better place to ask general programming questions, like forum
'comp.programming' or anything related to compression...

V
Jul 22 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: Keith Bowes | last post by:
I have a script for requesting HTTP resources and I want it to use HTTP compression (to reduce bandwidth), if possible. What's the best way to do this? I've tried using zlib functions but they...
7
by: Klaus Neuner | last post by:
Hello, I need a function that converts a list into a set of regexes. Like so: string_list = print string_list2regexes(string_list) This should return something like:
8
by: Dennis Hotson | last post by:
Hi, I'm trying to write a function that adds a file-like-object to a compressed tarfile... eg ".tar.gz" or ".tar.bz2" I've had a look at the tarfile module but the append mode doesn't support...
0
by: Polar | last post by:
Hi! Do you know a C library for trie data structures (a particular type of tree)? And some link about trie with C language? Thank you Polar
3
by: Paul | last post by:
Does anyone have an example of a trie data structure implemented in c#? I'm looking for a string trie to use to hold the word list for my spell checker. Any examples or suggestions would be great....
4
by: Pavel | last post by:
Hello. I am trying to make a folder compressed and failing miserably. Below are three ways that I tried to make it compressed, all of them compile and run w/o any problems, but the folder is...
8
by: robert | last post by:
Hello, I want to put (incrementally) changed/new files from a big file tree "directly,compressed and password-only-encrypted" to a remote backup server incrementally via FTP,SFTP or DAV.... At...
0
by: clintp | last post by:
I've seen a few people asking for this elsewhere, so here's a basic implementation of a string trie in C#. I'm using this to load and search a dictionary of about two hundred thousand words. It's...
5
by: iaminsik | last post by:
I implemented a TRIE in memory by myself in C. But, as you know, when a size of data increases, loading time of data becomes longer. I want to implement a TRIE in file, which means division of...
1
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.