php-关联链接的生成2

接着上一个话题继续说（上一话题）

通过DB查询的方式来确定内容包含多少少关联词肯定不是长久之计，那有没有更好的方法呢，我想肯定是有的。

现将我的思路整理如下：

平时我们经常用的查询是给定一个关键词，然后从数据库中查找出相关的条目。基本一条sql语句就可以搞定的。只要你的数据量不是特别的大，索引合理。基本是不会有很大问题的。而这个查询正好相反了，是给定许多条目，然后从一个文本中查找相关的条目，明显跟原来的思路不太一样。那我们怎么办？就没法了吗？

回归本质，让我们回想一下查找算法

1. 顺序查找:时间复杂度：O(n)，这个明显的不行。
2. 分查找(折半查找):时间复杂度：O(logn).这个查找的前提得有有序.要将所以字符串转换成数字，然后再查找，也是不可取的。
3. 二叉排序树查找:表示不太懂，只能无视了。
4. 哈希表法(散列表):几乎是O(1)，取决于产生冲突的多少.
5. 分而治之(分块查找):只是一将将大数据分组的方法，并不能提高性能

总上所说，要是能想办法，做成哈希表法就会好多了，怎么实现呢?

回想一下字符串的基本的包含的算法：如何确定一个长串是否包含一个短字符呢?

1. 最笨的办法，两个遍历。时间复杂度为O(m*n)
2. 字符串匹配的Boyer-Moore算法

想想原来是这么会事，是遍历比较，再通过算法来优化遍历的次数。

现在回归正题，来说我实现的关联算法。

function str_issub($desc_string , $sub_array , $word_min = 3 , $word_max = 10 )
{
	$keyword_list['sum'] = 0;
	if ( empty($desc_string) || !is_array($sub_array) ){
		return false;
	}
	$msg = strip_tags(trim($desc_string));//排除首尾空格并去除 HTML 和 PHP 标记
	$msg = str_replace(array("\r","\n"),'',$msg);
	$len = mb_strlen($msg);
	$i_max = ($len-$word_min+1);
	for ($i = 0; $i < $i_max ; $i++) {
		//echo "$i:start<br/>";
		$j = $word_min;
		$j_max = $len-$i;
		if ( $j_max > $word_max ){
			$j_max = $word_max; 
		}
		while( $j <= $j_max ){
			$temp = mb_substr($msg,$i,$j);
			//echo $temp."<br/>";
			if ( @$sub_array[$temp] ){
				$keyword_list[] = $sub_array[$temp];
			}	
			$j++;
			$keyword_list['sum']++;
		}
		//echo "$i:end<br/><hr/>";
	}
	return $keyword_list;
}

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

$time_start = microtime_float();

mb_internal_encoding("utf8"); 

$s =<<<EOT
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
1234567890
EOT;

$hash[123] = 123;
for ($i = 1; $i <= 1000000; $i++) {
    $key = rand(111111,99999);
    $hash[$key] = $key;
}

var_dump(str_issub($s,$hash));

$time_end = microtime_float();
$time = $time_end - $time_start;

echo "<br/>Did nothing in $time seconds\n";

1. 这个算法的思想就是:
2. 事先生成好关联链接，并且转换组合是一个以关联词为key的hash表。
3. 遍历要匹配的长字符串，通过控制关联词的最小长度和最大长度来优化遍历次数
4. 因为要替换文本，所以事先将空格，html源码去掉，减少源串长度，减少遍历。

通过上面的测试,100W的关联词都可以在1秒之内匹配出相关的数据。上面全是用的PHP操作，包括hash表，这样会占用大内存。不是很好。可以将hash表存在memcached或redis或其他第三方k-v数据库中，这样判断是只要根据key来判断就行了，避免了占用大量内存的问题。

i think it odd and I dig it
porno Why women are so obsessed with fashion bags