471,339 Members | 1,415 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

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

Which is the fastest pattern matching algorithm?

Hi!

I'm looking for a way to find the position of a certain pattern within a
string. On my search on the internet I've come accross various algorithms
such as Knuth-Morris-Pratt and Boyer-Moore (just to name two). But which is
the fastest?

Thanks already in advance!
Jul 21 '05 #1
2 2537
Run both in your real world conditions ;-)

Don't know but generally speaking you don't have a "faster" algorihtm. For
example one of these two could be quicker on small strings and the other
could be quicker on long strings, one could be quicker when there is
numerous close match etc etc.....

For a start I would use the regular expression that are readily available in
the .NET framework and that likely uses already something quite efficient.
Only if I can measure it doesn't fit my needs, I would then search if I
could do better. Try :

http://msdn.microsoft.com/library/de...ClassTopic.asp

(Also if the pattern is simple you could use the usual string functions...)

Patrice

--

"tommazzo" <to******@discussions.microsoft.com> a écrit dans le message de
news:80**********************************@microsof t.com...
Hi!

I'm looking for a way to find the position of a certain pattern within a
string. On my search on the internet I've come accross various algorithms
such as Knuth-Morris-Pratt and Boyer-Moore (just to name two). But which is the fastest?

Thanks already in advance!

Jul 21 '05 #2
Thanks a lot for your help! I'll conduct a few tests on both algorithms now.
However in the meantime I've already read that although the KMP algorithm has
a smaller number of worst-case character comparisons, the BM algorithm
usually turns up with the result after less comparisons and can thus be
considered more efficient.

"Patrice" wrote:
Run both in your real world conditions ;-)

Don't know but generally speaking you don't have a "faster" algorihtm. For
example one of these two could be quicker on small strings and the other
could be quicker on long strings, one could be quicker when there is
numerous close match etc etc.....

For a start I would use the regular expression that are readily available in
the .NET framework and that likely uses already something quite efficient.
Only if I can measure it doesn't fit my needs, I would then search if I
could do better. Try :

http://msdn.microsoft.com/library/de...ClassTopic.asp

(Also if the pattern is simple you could use the usual string functions...)

Patrice

--

"tommazzo" <to******@discussions.microsoft.com> a écrit dans le message de
news:80**********************************@microsof t.com...
Hi!

I'm looking for a way to find the position of a certain pattern within a
string. On my search on the internet I've come accross various algorithms
such as Knuth-Morris-Pratt and Boyer-Moore (just to name two). But which

is
the fastest?

Thanks already in advance!


Jul 21 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

9 posts views Thread by Xah Lee | last post: by
3 posts views Thread by Day Of The Eagle | last post: by
reply views Thread by Yoon Soo | last post: by
2 posts views Thread by RobC | last post: by
5 posts views Thread by olaufr | last post: by
8 posts views Thread by 116Rohan | last post: by
9 posts views Thread by Chris | last post: by

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.