calling genius - string comparator - you'll learn something :)

[sfullman]

so I have this idea, a search phrase like "candy apple red" against another string of equal or more words (if lesser, we do the search comparision backwards).

So, I put my finger on the word candy in candy apple red on the left side, and then start going through my comparison string:

"I want an apple and my red candy is hot",

let's say. I hit I, want, an, apple, .. , then CANDY - so I found one word. I now move my finger to APPLE on the left, and "is" on the right, then move to hot - now, I "flip" or roll back to the first entry on the right - I've had one flip. now I put my finger on I, want, an, APPLE - so I found two words. I then move to RED on the left, and on the right move my finger to and, my, RED ..

so we found 3 words and 1 flip. The more flips (rollovers), the more out of order we are, and the more words we find the better the match. You geniuses can do what you want with it - long as you share it with me but is my code flawed in any way.

The parameter that would be good to add is closeness or proximity - less number of words between matches, the tighter the cluster and we can evaluate that too.

Appreciate your review of my code!

echo '<pre>';
function search_compare_strings($needle, $haystack, $mode=''){
	if(!$mode /* early version */){
		return (strtolower($needle)==strtolower($haystack) ? 1 : 0);
	}else if($mode=='tight keywords'){
		/*
		"tight" means one space between, small length
		*/
		//we are not looking for repeats, just a percentage match
		if(!$needle || !$haystack) return 0;
		if($needle==$haystack) return 1;
		if(strtolower($needle)==strtolower($haystack))return .95;
		$needle=explode(' ',$needle);
		$haystack=explode(' ',$haystack);
		$sub=(count($haystack)>count($needle) ? $needle : $haystack);
		$super=($sub==$needle ? $haystack : $needle);
		print_r($sub);
		print_r($super);
		$supercount=count($super);
		while(list(,$a) = each($sub)){
			echo 'loop level 1<br>';
			echo 'each word[1] = '.$a . '<br>';
			while(list(,$b) = each($super)){
				$j++;
				echo 'loop level 2, super = '.$b . '<br>';
				if(isset($lastIdx) && $j==$lastIdx){
					//couldn't find the word, move to next word
					echo 'cannot find the word<br>';
					if(!(list(,$a)=each($sub))) break; //get the next word from sub
					echo 'each word[2] = '.$a . '<br>';
				}
				//case mismatch not currently considered
				if(strtolower($a)==strtolower($b)){
					$wordMatch++;
					echo 'found the word '.$a . '<br>';
					$lastIdx=$j;
					//get the next word
					echo '.<br>';
					if(!(list(,$a)=each($sub))) break;
					echo 'each word[3] = '.$a . '<br>';
				}
				//continue to roll around the super list
				if(current($super)===false){
					echo 'resetting<br>';
					$j=0;
					$flips++;
					reset($super);
				}

		}
	}
	//stats
	echo 'flips: ' . $flips.'<br />';
	echo 'words: ' . $wordMatch.'<br />';
}
}
$a='istocome was cool is';
$b='I am he who is and was and istocome';
search_compare_strings($a,$b,'tight keywords');

[laserlight]

Moved to Code Critique.

Instead of just describing your algorithm and showing an implementation, perhaps you would like to state what problem this algorithm was designed to solve.

[Weedpacket]

I'm still trying to work out what it's supposed to achieve (e.g., "now, I 'flip' or roll back to the first entry on the right - I've had one flip": what? why?), but I can say straight off there are better ways of specifying "modes" than passing arbitrary strings.

Attached is a dump of what results from the sample input

Array
(
    [0] => istocome
    [1] => was
    [2] => cool
    [3] => is
)
Array
(
    [0] => I
    [1] => am
    [2] => he
    [3] => who
    [4] => is
    [5] => and
    [6] => was
    [7] => and
    [8] => istocome
)
loop level 1
each word[1] = istocome

Notice: Undefined variable: j in C:\test.php on line 25

Call Stack:
    0.0012   1. {main}() C:\test.php:0
    0.0012   2. search_compare_strings() C:\test.php:60

loop level 2, super = I
loop level 2, super = am
loop level 2, super = he
loop level 2, super = who
loop level 2, super = is
loop level 2, super = and
loop level 2, super = was
loop level 2, super = and
loop level 2, super = istocome

Notice: Undefined variable: wordMatch in C:\test.php on line 35

Call Stack:
    0.0012   1. {main}() C:\test.php:0
    0.0012   2. search_compare_strings() C:\test.php:60

found the word istocome
.
each word[3] = was
resetting

Notice: Undefined variable: flips in C:\test.php on line 47

Call Stack:
    0.0012   1. {main}() C:\test.php:0
    0.0012   2. search_compare_strings() C:\test.php:60

loop level 2, super = I
loop level 2, super = am
loop level 2, super = he
loop level 2, super = who
loop level 2, super = is
loop level 2, super = and
loop level 2, super = was
found the word was
.
each word[3] = cool
loop level 2, super = and
loop level 2, super = istocome
resetting
loop level 2, super = I
loop level 2, super = am
loop level 2, super = he
loop level 2, super = who
loop level 2, super = is
loop level 2, super = and
loop level 2, super = was
cannot find the word
each word[2] = is
loop level 2, super = and
loop level 2, super = istocome
resetting
loop level 2, super = I
loop level 2, super = am
loop level 2, super = he
loop level 2, super = who
loop level 2, super = is
found the word is
.
flips: 3
words: 3

Nothing is returned from the function.

[sfullman]

laserlight;10887865 wrote:

Moved to Code Critique.

Instead of just describing your algorithm and showing an implementation, perhaps you would like to state what problem this algorithm was designed to solve.

What I am attempting to do by this is determine how much of the substring is in the string, and how out of order it is, and eventually how much spacing (proximity) is present. The method is to iterate the substring, and sub-iterate the superstring for each word in the substring. If I get to the end in the superstring, I roll back to the top, but obviously I only need to go back to the last position I found the previous substring word. At that point I go to the next substring word, and so forth.

If the superstring has all the words in the same order, I won't need to "roll around" at all so there will be none. If the substring contained a b c and the superstring contained c b a, then there would be two resets on the superstring. More resets = more out of order.

This algorithm is intended to find substrings in relatively short superstrings like page titles, meta keywords and descriptions. I havent' created a return on the function just yet, and need to consider proximity of the group (how many words are in between the group) with no words in between being 100% and many words approaching zero.

The goal is then to take "out of order-ness", word count and proximity and weigh them to create a relevance score. Figure I can compete with Goooogle by next week 🙂 but

1. any critique on would this function not accomplish the proposed algorithm in certain cases (I don't use while, each and reset that much)

2. any links to similar URL's or theses on this type of order-and-proximity matching woudl be great too

Samuel

[Weedpacket]

Question: are the words in the substring supposed to be unique (as the use of the word "keywords" would seem to imply)?

Let's see if I've got this straight: searching for the sequence of keywords [font=monospace]a, b, c[/font] in [font=monospace]d b a c[/font] involves one reset, because after scanning [font=monospace]a[/font] the scanner has to go backwards to read [font=monospace]b[/font], and can read forward to find [font=monospace]c[/font]. (Or is that two, because it reads forwards, then reads backwards, then reads forwards again?)

[sfullman]

your first statement is correct. The scan of the superstring has to go back to start one time to get b and c (in order). so, a-b-c in the substring matches up with b-a-c in the superstring with one "flip" - and similarly bac is one turn away from abc. so you have 3 matches and 1 flip, and I'm deciding how to rank those as a separate algorithm.

I think the maximum number of flips you can have would be either n or n-1 where n is the number of substring words. words=flips SHOULD mean that the superstring is completely backwards.

My next development would be quantifying word proximity/sparseness - how far the words are from each other - with these three I think I could use a secondary algorithm to determine relevance quite solidly.

And that's not even mentioning plurality (apples vs apple, data vs. datum), or case matching where it might be important (in = "in" but IN = Indiana maybe) 🙂

Again I'm interested in cases where the algorithm might fail or loop endlessly. I hope this can be of use to others, thanks.

[Weedpacket]

You're effectively counting permutation runs; (the permutation being on the set of keywords). It's complicated by the fact that a keyword may appear more than once in the string being searched; for n keywords, if the number of times keyword w[i] appears in the sequence is c[i], then the total number of ways the entire set of keywords appears is Sum(i)(w[i]c[i]) (since you're wanting to compare the size of gaps between words, [font=monospace]a,a,c,b[/font] and [font=monospace]a,a,c,b[/font] are distinct results.)

It would probably be easier to maintain keyword positions, rather than the keywords themselves; an array, indexed by keyword, that contains lists of those positions where the keyword appears. Then it would be much easier to tell if one keyword appears before another because its position would be less, and you would no longer be continually doing string comparisons. It would also be much easier to count how many intervening words there are, because it would just be one less than the difference in their positions. Even if you do continue to use string comparisons, it would be much less work to do the strtolower once before the loops begin.

[sfullman]

good points WP and thank you for the link - I appreciate it and this is the most in depth algorithm work I've done so far.

I definitely agree that indexing keywords would speed things up. This is meant to compare a brief google-like search "candy apple red" with relatively short meta-tags like title, keyword and description. Comparing longer strings would

1. require greater efficiency
2. require consideration of multiple instances
3. require consideration of repetitive words in either string ("duck duck goose" or "run baby run")
4. case sensitive comparisons will be important in some cases - may make the difference between finding a relevant match or not 🙂

I may edit this post as I come at some rankings of words, flips and proximities later on..