I need to find the fastest way in terms of storage and searching to
determine if a given string contains one of a member of a list of strings.
So, think of it in terms of this: I have a string such as the following:
"Smith said the dog belongs (or did belong) to the secretary, an employee of
the company."
Then the list contains the following (and this list is MUCH larger in the
real situation):
Adams
Alan
Jones
Jacobs
Smith
Thaxton
Vela
Zulu
I would need to stop the processing and return (true) as soon as Smith was
found. On the other hand, if the string was changed to the following, there
would be no match and I would return (false):
"Smitherson said the dog belongs (or did belong) to the secretary, an
employee of the company."
In the given string, do know that the matches should begin at a given point
(zero position), but I need to keep processing until I have exhausted the
candidate string in the list - as shown above - to prevent a false match.
I have played around with some different data structures, such as prefix and
suffix trees, an these work in the case that you have a string that you are
trying to match in a list, not vice versa. The approach is required to be
very performant because it will be evaluated millions of times. I am also
okay with an unsafe code approach that works. I just need the evaluations to
terminate as soon as possible rather than looping through every single item
in the list. Even an IndexOf is too slow. 7 4694
I think RegEx will help you out here. As far as not iterating over the
entire list, I've no clue how you can selectively not fall through given the
only match in the list is the last item in the list or when there is no
match at all.
"Karch" <news.microsoft.comwrote in message
news:e9**************@TK2MSFTNGP06.phx.gbl...
>I need to find the fastest way in terms of storage and searching to determine if a given string contains one of a member of a list of strings. So, think of it in terms of this: I have a string such as the following:
"Smith said the dog belongs (or did belong) to the secretary, an employee
of the company."
Then the list contains the following (and this list is MUCH larger in the
real situation):
Adams
Alan
Jones
Jacobs
Smith
Thaxton
Vela
Zulu
I would need to stop the processing and return (true) as soon as Smith was
found. On the other hand, if the string was changed to the following,
there would be no match and I would return (false):
"Smitherson said the dog belongs (or did belong) to the secretary, an
employee of the company."
In the given string, do know that the matches should begin at a given
point (zero position), but I need to keep processing until I have
exhausted the candidate string in the list - as shown above - to prevent a
false match.
I have played around with some different data structures, such as prefix
and suffix trees, an these work in the case that you have a string that
you are trying to match in a list, not vice versa. The approach is
required to be very performant because it will be evaluated millions of
times. I am also okay with an unsafe code approach that works. I just need
the evaluations to terminate as soon as possible rather than looping
through every single item in the list. Even an IndexOf is too slow.
Karch wrote:
I need to find the fastest way in terms of storage and searching to
determine if a given string contains one of a member of a list of strings.
So, think of it in terms of this: I have a string such as the following:
"Smith said the dog belongs (or did belong) to the secretary, an employee of
the company."
Then the list contains the following (and this list is MUCH larger in the
real situation):
Adams
Alan
Jones
Jacobs
Smith
Thaxton
Vela
Zulu
Could you give us some idea of the likely length of the list? And
whether it's static or dynamic ?
jd
On Wed, 05 Mar 2008 09:05:22 -0800, Karch <news.microsoft.comwrote:
I need to find the fastest way in terms of storage and searching to
determine if a given string contains one of a member of a list of
strings.
I don't know if RegEx has optimizations for dealing with this sort of
thing. It could, but given how long a search string for RegEx could be if
you concatenate all of your possible matches, maybe it doesn't.
That'd be my first try though. It seems like the actual RegEx search
string would be simple (just "or" all of your possible matches together).
If it performs well enough, there you go.
If not, I'd guess there's a fair amount of research into algorithms like
this, but a fairly basic approach is a state graph. It's memory
intensive, but rewards you with good performance. This came up awhile ago
and I posted some sample code to get someone else started. You can find
that post here: http://groups.google.com/group/micro...06f696d4500b77
I've referred to this post a couple of other times, and while I've never
had anyone say it actually turned out to be useful, they've never said it
wasn't either. :)
I suppose if I'm going to keep referring people to it, maybe I ought to
clean it up a little bit more. But what's there does work and should be
enough to get you pointed in the right direction.
Pete
One problem I see with this is that you apparently are not doing
simply a string search, but some kind of word search, without defining
what a word is.
You say the "Smithperson said ..." should not have any matches, so
while the string Smith is a substring, it does not match.
Would it match:
(Smith
(Smith)
Smith,
Smith;
Smith-
smith
etc.
The answer to this will probably constrian your possible algorithms.
If it didn't get too many false hits, doing a string search first and
then re-checking to see if the matches are valid word matches might be
OK.
On Wed, 5 Mar 2008 11:05:22 -0600, "Karch" <news.microsoft.comwrote:
>I need to find the fastest way in terms of storage and searching to determine if a given string contains one of a member of a list of strings. So, think of it in terms of this: I have a string such as the following:
"Smith said the dog belongs (or did belong) to the secretary, an employee of the company."
Then the list contains the following (and this list is MUCH larger in the real situation):
Adams Alan Jones Jacobs Smith Thaxton Vela Zulu
I would need to stop the processing and return (true) as soon as Smith was found. On the other hand, if the string was changed to the following, there would be no match and I would return (false):
"Smitherson said the dog belongs (or did belong) to the secretary, an employee of the company."
In the given string, do know that the matches should begin at a given point (zero position), but I need to keep processing until I have exhausted the candidate string in the list - as shown above - to prevent a false match.
I have played around with some different data structures, such as prefix and suffix trees, an these work in the case that you have a string that you are trying to match in a list, not vice versa. The approach is required to be very performant because it will be evaluated millions of times. I am also okay with an unsafe code approach that works. I just need the evaluations to terminate as soon as possible rather than looping through every single item in the list. Even an IndexOf is too slow.
The list is static (read into memory during initialization) and could be up
to approximately 1000 items (hence the need for a fast method)
"John Daragon" <jo**@argv.co.ukwrote in message
news:47***********************@news.zen.co.uk...
Karch wrote:
>I need to find the fastest way in terms of storage and searching to determine if a given string contains one of a member of a list of strings. So, think of it in terms of this: I have a string such as the following:
"Smith said the dog belongs (or did belong) to the secretary, an employee of the company."
Then the list contains the following (and this list is MUCH larger in the real situation):
Adams Alan Jones Jacobs Smith Thaxton Vela Zulu
Could you give us some idea of the likely length of the list? And whether
it's static or dynamic ?
jd
On Thu, 06 Mar 2008 10:12:51 -0800, Karch <news.microsoft.comwrote:
The Hashtable would work great alongside a tokenized string, but the
problem
is that I don't have a distinct delimiter since the string to be matched
can
span multiple words. It's really a question of "do any of these strings
appear in this source string", irrespective of whitespace.
Then how do you distinguish "Smith" from "Smitherson", as in your
example? Can you at least make a requirement that the search pattern will
always begin and end on a space, even if it includes spaces within?
Pete
Mufaka wrote:
Karch wrote:
>The Hashtable would work great alongside a tokenized string, but the problem is that I don't have a distinct delimiter since the string to be matched can span multiple words. It's really a question of "do any of these strings appear in this source string", irrespective of whitespace.
<snip>
This is a little different than your original post, but if you can't
delimit search string, you might try something like the following:
Hash the static list of words
Keep a list of unique lengths for those words
for each unique length, iterate the string pulling out substrings of
that length
see if that substring is in your hashed list of words
It at least reduces the amount of InString's you'd have to do.
I'd be interested in seeing how this performs against large strings.
Here's my test code:
<snip>
>
if (text.Length < length) break;
<snip>
That should be continue instead of break. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Christopher W. Douglas |
last post by:
I am writing a VB.NET application in Visual Studio 2003. I have written a
method that handles several events, such as closing a form and changing the
visible status of a form. I have some code...
|
by: HumanJHawkins |
last post by:
The following query works perfectly (returning all words on a list called
"Dolch" that do not contain a form of "doing"):
SELECT 'Dolch' AS , dbo.Dolch.vchWord
FROM dbo.Dolch LEFT OUTER JOIN...
|
by: Chris Simmons |
last post by:
I know that a String is immutable, but I don't understand why this
piece of code fails in nUnit:
// BEGIN CODE
using System;
class Test
{
public static void Main( String args )
|
by: Tom |
last post by:
Is there such a thing as a CONTAINS for a string variable in VB.NET? For
instance, I want to do something like the following:
If strTest Contains ("A","B", "C") Then
Debug.WriteLine("Found...
|
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
...
|
by: =?Utf-8?B?bWFnZWxsYW4=?= |
last post by:
Hi,
I'd appreciae any advice on how to do this in VB 2005.
I have a simple array;e..g, a list of States, e.g., CA, WA, ID, AL, and
etc...
I like to determine how many unqiue "States" are...
|
by: |
last post by:
I am interested in scanning web pages for content of interest, and then
auto-classifying that content. I have tables of metadata that I can use for
the classification, e.g. : "John P. Jones" "Jane...
|
by: jacob navia |
last post by:
Abstract:
Continuing the discussion about abstract data types, in this
discussion group, a string collection data type is presented,
patterned after the collection in C# and similar languages...
|
by: Karch |
last post by:
I need to find the fastest way in terms of storage and searching to
determine if a given string contains one of a member of a list of strings.
So, think of it in terms of this: I have a string such...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |