Re: Searching in byte buffer


"Jatin" <TripleDerby100-ng@xxxxxxxxx> wrote in message
news:jZr9f.22808$6e1.13267@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

> I am searching relatively small buffers of byte data retrieved from
> soundcard. The information searched for is textual (not multi-bute
> characters) which is fed into the sound card through LINE-IN port, from a
> Ham radio receiver.

Sorry, but it isn't really clear to me. The exact details of your problem
can make a huge difference on the optimal search algorithm choice. If the
buffer (B) being searched is relatively small, say < 1KB, and the pattern
(S) being sought is relatively short, say length < 4, a linear search may
be the optimal choice. If, OTOH, S doesn't change on each search and/or
length (s) > 3, Boyer-Moore or a variant thereof may prove optimal.

Boyer-Moore achieves its efficiency by not examining every character in the
search space. Simply, it works on the principal that if the last character,
S [n], of the pattern is <> B [i] (where i starts at n), then B [(i - n)
thru i] cannot match S. The next character that needs examining depends on
if B [i] exists in S. If it does, the next character compared to S [n] is
at B [i + index of B [n] in S]. Otherwise its at B [i + n + 1]. The setup
cost is in building the structure that allows for the rapid calculation of
the index of B [i] in S.

Boyer-Moore may still prove a good choice if S doesn't change for each B
searched, even if n is < 3 (but > 1), and length B is < 1KB, but > 2-3 n.
If more than one S must be sought in each B, however, a state driven search
may prove more efficient.


.

Relevant Pages