Thread: Search question

I was thinking about search functions, and how they work, and while I imagine this has been done before, I want to know if it's a good idea:

Code:

search(char target[], char strtofind[], int stfsiz)
{
int i = 0;
int dectr;
while((i+stfsiz) <= MAXTARGETSIZE && target[i] != '\0'){
	if(target[i] == strtofind[0]){
		dectr = stfsiz;
		while(dectr>0){
			if(target[i+dectr] == strtofind[dectr]){
				if(dectr==0)
					return i;
				else
					dectr--;
				}
			else {
				i++;
				break;
				}
			}
		}
	else
		i++;
	}
return -1;
}

The logic here is that if the string you're searching for in the target is very long, it's probably a good idea to start at the end of it and 'search back' from where the end of the string being searched for would be, assuming i is the beginning of a match. This works on the assumption that it's more likely that you'll run into divergence between a match and a non-match further from the beginning of them than closer.

IE., I am assuming that while searching for, for example, "mushroom" in an arbitrary string of letters, that I'm less likely to encounter an m and then an o and another o while searching backward from the i+7th char than I will be to find an u, s, and h counting forward.

I know there are better ways to impliment this, but hopefully this will demonstrate the idea I have without making me have to work too much on an idea I'm not even sure is valid.

I'm trying to increase the speed at which a non-hit will be detected.

Basically, the answer to the question I have is mostly statistical, since it deals with the chance a stream of data will diverge/reconverge with the string being searched for.

So maybe I should go find a statistics board and ask there...

>I'm trying to increase the speed at which a non-hit will be detected.
Just for fun, try something like this:

Code:

loop over each character
  if length(text[i]) < length(match)
    return not found
  if text[i] == match[0] and text[i + length(match)] == match[length(match)]
    do thorough test

If the first and last characters of both the text and search string match, what's the probability that it'll be a hit? What if the first, last, and middle characters match? The trick for optimizing for search misses is to minimize how many comparisons you make. This is more difficult for general search algorithms because you can't assume anything about the data. But it's an entertaining exercise, if nothing else.

Prelude:
That's pretty much how I was operating; assuming that as long as you keep the number of operations per comparison low, and distribute the location of the comparisons such that they're at least not completely linear, that some performance would be gained...

The code you just wrote out was actually nearly identical to another idea I had, though I was considering extending it to perform a rotating search from the 'middle out' of the target section of the array. I think I might enjoy writing search functions once I get a better grip on C overall.

Of course you cannot impliment a search algo that does not check the length of the search string, but there are surely ways to, without compromising that stipulation, compare all pertinent elements in a manner that will detect non-hits sooner.

Almost all search scenarios have the one reliable condition of their target data sets be that the 'hits' will outnumber the 'non-hits'.

In other words, it does not really matter so much most of the time how long it takes to assure yourself that your potential match is actually a match, as long as this time penalty is offset by your efficiency in eliminating all non-hits that do not share a high level of similarity with the search string, assuming the target does not contain an inordinately high number of these 'almost-hits'.

PS. I also will take a look at these algos mentioned, maybe they will give me some ideas(or show me how poor my current ones are).