473,322 Members | 1,408 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,322 software developers and data experts.

is there any FAST ALGORITHM about Forward Maximum Match of string?

"Forward maximum match" mean that there is a dictionary contains
thousands of items which are single words. For example, "kid", "nice",
"best"...
And here get a string "kidnicebs", the forward maximum match algorithm
need to find the longest string that matches the string in dictionary.
Because the longest string in the dictionary has a length of 4, so the
algoritm pick the first four characters of the string(that's why it's
called forward):

kidn-------not find in dictionary
then, first three: kid --------find in dictionay

then kid is picked out as a segment, then the algorithm continue with
"nicebs"...

I'm wondering is there any fast algorithm to deal with this demand,
what kind of data structure should I use? Thanks for helping me.

Dec 15 '06 #1
1 2579
hn********@gmail.com wrote:
"Forward maximum match" mean that there is a dictionary contains
thousands of items which are single words. For example, "kid", "nice",
"best"...
And here get a string "kidnicebs", the forward maximum match algorithm
need to find the longest string that matches the string in dictionary.
Because the longest string in the dictionary has a length of 4, so the
algoritm pick the first four characters of the string(that's why it's
called forward):

kidn-------not find in dictionary
then, first three: kid --------find in dictionay

then kid is picked out as a segment, then the algorithm continue with
"nicebs"...

I'm wondering is there any fast algorithm to deal with this demand,
what kind of data structure should I use? Thanks for helping me.
Firstly, don't multi-post to c.l.c++ and c.l.c++.m. You're off topic
for both. Posting to comp.programming and setting followup to same.

You can do it with having to examine each character in the input
string only once. There may be a temptation to try to exploit some
sort of skip ahead based on the length of the longest string found
so far but I suspect that number of potential target words nullifies
any advantage of skip ahead since it's likely to only be 1. I'll
let others have fun with this.

btw, this isn't a homework problem, is it?

--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.
Dec 15 '06 #2

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

Similar topics

6
by: Jack Smith | last post by:
Hello, any help appreciated with following problem. I figured out the algorithm (I think), just having trouble proving it is optimal. Suppose we are given n tasks each of which takes 1 unit...
24
by: Alex Vinokur | last post by:
Consider the following statement: n+i, where i = 1 or 0. Is there more fast method for computing n+i than direct computing that sum? -- Alex Vinokur email: alex DOT vinokur AT gmail DOT...
13
by: M | last post by:
Hi, I've searched through the previous posts and there seems to be a few examples of search and replacing all occurrances of a string with another string. I would have thought that the code...
6
by: DC | last post by:
Hi, I am programming a search catalogue with 200000 items (and growing). I am currently using the SQL Server 2000 fulltext engine for this task but it does not fit the requirements anymore. ...
2
by: The One We Call 'Dave' | last post by:
I have a list of DateTime objects stored in a collection: SortedList<DateTime,Object> MyDates=new SortedList<DateTime,Object>(); The dates, which can be accessed via MyDates.Keys, are stored in...
6
by: thecodemachine | last post by:
Hi, I'm looking for a fast and simple one to one hash function, suitable for longer strings (up to 2048 in length). I'd like keys to be relatively short, I doubt I'd be creating more than 256...
23
by: mark.moore | last post by:
I know this has been asked before, but I just can't find the answer in the sea of hits... How do you forward declare a class that is *not* paramaterized, but is based on a template class? ...
95
by: hstagni | last post by:
Where can I find a library to created text-based windows applications? Im looking for a library that can make windows and buttons inside console.. Many old apps were make like this, i guess ...
4
prometheuzz
by: prometheuzz | last post by:
Hello (Java) enthusiasts, In this article I’d like to tell you a little bit about graphs and how you can search a graph using the BFS (breadth first search) algorithm. I’ll address, and...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

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.