FindInString Fast

[Bee]

I need a very fast string search as follows.
Typically strings being searched are several megabytes long.
The search string is typically only one or a few characters.
This is for the standard character set only.
Currently I am doing a Mid$ per character loop that is very slow.

Something like
Find the first occurance of one of the groups of characters.
e.g.
sGroup(0)="A"
sGroup(1)="AC"
sGroup(2)="AB"
...
sGroup(n)="AD"

Prototype
lFoundPos=FindInString(lStartPos As Long, sText As String, sGroup() As
String, , lGroupIndex As Long, Optional CompareMethod as vbCompare =
vbBinaryCompare)

FindInString returns either 0, if nothing found or the position of the
match with the lowest found position. If, as in the example, the
string at the found position is AB, the group index returned would be =2.

e.g.
lFoundPos = FindInString(2, "!@#$AB#AC@!", sGroup, lGrpIdx)

lGrpIdx would be 2.

Option: have the ability to include wildcards like
Find A*X or A?X.
There would always be a legit character (non-wildcard) at the beginning.

I tired simple but complex looping doing a Mid$ on each characters; that is
slow.
I can try looping on Instr but I am not sure if the effort to try this
code is worth the effort if someone has a better way, please share.
I can try looping on a byte array (??? in parallel with a string
array??? or not) and see if looping on the byte array is faster for this.
This code is keeping my old neurons firing and I need your help making
them fire in the right direction.

[Patrice]

Hello,

My understanding is that you want to search multiple strings in a single
string. http://en.wikipedia.org/wiki/Aho-Corasick_algorithm could perhaps
help.

--
Patrice

[C. Kevin Provance]

I don't know if it's been suggested to you yet, but have you considered
string mapping?

Google it. Lots of stuff out there.

- Kev

"Bee" <B...@discussions.microsoft.com> wrote in message
news:5284C7B7-BA31-4AB1...@microsoft.com...

[Mike Williams]

"Bee" <B...@discussions.microsoft.com> wrote in message
news:5284C7B7-BA31-4AB1...@microsoft.com...

> I need a very fast string search as follows.

> Typically strings being searched are several megabytes long.
> The search string is typically only one or a few characters.
> This is for the standard character set only.
> Currently I am doing a Mid$ per character loop that is very slow.

There are all sorts of string searching algorithms and others have already
posted some links for you, and the VB Instr function is itself very fast if
you can incorprate that into some of them, but regardless of the algorithm
you eventually choose if part of it involves examining individual characters
in a loop then you will find that persuading VB to deal with the contents of
the String as though it was the contents of an Array of Integers and
examining the individual Integers is very much faster than examining the
individual characters of the String using the Mid$ function. To see the
speed difference for yourself, try the following example code, which
examines a 5000000 character VB String which has the character "A" at
position 4900000, examining each character individually until it finds "A".
You should find that looping through character by character when treating
the String as an array of Integers is very much faster than looping through
using the Mid$ function. In fact on my own machine when run as a standard
native code compiled exe it is more than fifty times faster, and if you
optimise the compile by removing array bounds checks and integer overflow
checks it is about one hundred times faster. Naturally, in this very simple
example, using the VB Instr function to find the first occurrence of "A" is
just as fast as the compile optimized "character by character Integer array"
loop method, but the Integer array method comes into its own when your
search is more complex than the simple things that the VB Instr function can
readily handle. Paste the following example into a VB Form containing two
Command Buttons.

Mike

Option Explicit
Private Declare Function timeBeginPeriod Lib "winmm.dll" _
(ByVal uPeriod As Long) As Long
Private Declare Function timeEndPeriod Lib "winmm.dll" _
(ByVal uPeriod As Long) As Long
Private Declare Function timeGetTime Lib "winmm.dll" () As Long
Private Declare Function VarPtrArray Lib "msvbvm60.dll" _
Alias "VarPtr" (Ptr() As Any) As Long
Private Declare Sub CopyMemory Lib "kernel32" Alias _
"RtlMoveMemory" (Destination As Any, Source As Any, _
ByVal Length As Long)
Private Type SAFEARRAY1D
cDims As Integer
fFeatures As Integer
cbElements As Long
cLocks As Long
pvData As Long
cElements As Long
lLbound As Long
End Type
Private s1 As String

Private Sub Form_Load()
timeBeginPeriod 1
s1 = Space$(5000000)
Mid$(s1, 4900000, 1) = "A"
End Sub

Private Sub Form_Unload(Cancel As Integer)
timeEndPeriod 1
End Sub

Private Sub Command1_Click()
' loop through the String s1 character by character
' using the Mid$ function looking for "A"
Dim t1 As Long, t2 As Long, n As Long
t1 = timeGetTime
For n = 1 To 5000000
If Mid$(s1, n, 1) = "A" Then
Print "A was found at position " & n & " ";
Exit For
End If
Next n
t2 = timeGetTime
Print "(" & t2 - t1 & " m/secs for Mid$)"
Print
End Sub

Private Sub Command2_Click()
' loop through the String s1 character by character
' treating the String as an array of Integers
' looking for "A"
Dim t1 As Long, t2 As Long, n As Long
Dim SA1 As SAFEARRAY1D, d1() As Integer
CopyMemory ByVal VarPtrArray(d1), VarPtr(SA1), 4
t1 = timeGetTime
' point an otherwise empty Integer array to the String
With SA1
.cDims = 1
.cbElements = 2
.lLbound = 1
.cElements = Len(s1)
.pvData = StrPtr(s1)
End With
CopyMemory ByVal VarPtrArray(d1), VarPtr(SA1), 4
'
For n = 1 To 5000000
If d1(n) = 65 Then
Print "A was found at position " & n & " ";
Exit For
End If
Next n
' set the Integer array back to its original empty condition
CopyMemory ByVal VarPtrArray(d1), 0&, 4
t2 = timeGetTime
Print "(" & t2 - t1 & " m/secs for String data in Integer Array)"
Print
End Sub

[Mike Williams]

"Bee" <B...@discussions.microsoft.com> wrote in message
news:5284C7B7-BA31-4AB1...@microsoft.com...

> Currently I am doing a Mid$ per character loop that is very slow.

Oops! In the code I just posted there was an extra CopyMemory that somehow
crept in there (just before the first timeGetTime line). It doesn't affect
the way the code works, but it could be confusing because it is not
necessary. Here is what the Command2 Click event should really be . . .

Mike

Private Sub Command2_Click()
' loop through the String s1 character by character
' treating the String as an array of Integers
' looking for "A"
Dim t1 As Long, t2 As Long, n As Long
Dim SA1 As SAFEARRAY1D, d1() As Integer

[Bee]

Thanks Mike. I have been playing with something similar and see the benefit
of using the array.

I used a byte array.
Turns out that Instr works with a byte array.
Just took a chance and tried it.

Now i need a fast replace routine for byte arrays.
Going to see if I can find some copymemory routines to help with insert and
delete within a byte array. Sort of a fast Mid$ for byte arrays.
Hmmm.... going to try Mid with a byte array now ...

"Mike Williams" wrote:

> .
>