PHP 解决圣经背诵问题

在网上看到这样一个题目,听说是腾讯的面试题目,于是决定先用 PHP 来尝试试解决这个问题。
题目如下:

我们碰到了大麻烦,一个新来的传教士惹恼了上帝,上帝很愤怒,要求我们把圣经背熟,直至他说哪个单词,我们就要飞快的回答出这个单词在第几行第几个单词位置。听说你是个优秀的程序员,那么帮助我们完成这个不可能的任务吧。
要求如下:
1)/myworks/example/bbe.txt,98版本英文圣经一本
2)输入部分要求如下:php ./example.php [单词]
3)输出部分如下:[单词] 1,2 2,4 5,6表示:此单词在1行2列(第二个单词),2行4列…
说明:
1)此文本4MB之巨…
2)单词的含义:由英文字母(大小写),数字(0-9)组成的串
3)提供给你的机器OS为ubuntu 9.10,内存只有1G,而且,很不幸的,其中700M用来做了别的
4)上机考试不允许上网,但我装了man文档以及读取CHM以及PDF的阅读器,在电脑的桌面的CHM文件夹中,有相应的PHP参考手册
5)算法复杂度要求不能大于O(N^2)(就是N的平方)
6)什么?PHP低效且用起来不顺手,好的,你可以用别的语言来实现。但注意:提供给你的机器上只有python 2.4/perl 5.8/gcc[g++] 4.1

思路:
一、将圣经一次读入内存,然后逐词匹配,同时控控制好行号和单词索引变化,这种方式相对简单,但是在限制内存的情况下就会有点乏力。
二、每次从圣经中读入指定数量的字符到缓冲区中,然后缓冲区中的单词进行匹配,这里要解决一个关键性的问题就是缓冲区的边界问题,
即,缓冲区的单词可能是单词的中间,一个单词会先后两次进去缓冲区,为了解决这一问题,我们需要用另一个缓冲去来存储前一次处理
遗留下载的不完整单词,将它与本次读入的前部拼接。

两个思路中间共同部分就是在缓冲区中匹配单词,控制好行号和单词索引变化,然后就是判断字符是否能构成单词:

/**
 * 盘读 $sChar 构成单词的字符
 * @param string $sChar
 * @return bool
 */
function is_digit_or_letter($sChar){
	$iCode = ord($sChar);
	return ($iCode >= 65 && $iCode <= 90) || ($iCode >= 97 && $iCode <= 122) || ($iCode >= 48 && $iCode <= 57);
}

/**
 * 在包含完整单词的缓冲区中匹配单词
 * @param string $sWord 被查找的单词
 * @param int $iWordLen 被查找的单词长度
 * @param string $sBuffer 缓冲区
 * @param int $i 缓冲区中查找开始位置
 * @param int $iEnd 缓冲区中查找结束位置
 * @param int $iLine 行号
 * @param int $iWords 单词索引
 * @param array $aFound 找到的单词
 */
function find_word_in_buffer(
	$sWord,
	$iWordLen,
	$sBuffer,
	$i,
	$iEnd,
	&$iLine,
	&$iWords,
	&$aFound
){
	while($i < $iEnd){
		$sChar = $sBuffer[$i++];
		if("\r" === $sChar){
			if("\n" === $sBuffer[$i]){
				$i++;
			}
			$iLine++;
			$iWords = 1;
		}
		else if("\n" === $sChar){
			$iLine++;
			$iWords = 1;
		}
		else if(is_digit_or_letter($sChar)){
			$j = 1;
			while($i < $iEnd && $j < $iWordLen && ($sBuffer[$i] == $sWord[$j])){
				$i++; $j++;
			}
			if($j === $iWordLen && !is_digit_or_letter($sBuffer[$i])){
				array_push($aFound, array($iLine, $iWords));
			}
			while($i < $iEnd && is_digit_or_letter($sBuffer[$i])){
				$i++;
			}
			$iWords++;
		}
	}
}

思路一的实现:

function find_word_in_bible_all($sWord, $sBibleFile){
	$iWordLen = strlen($sWord);
	$sBuffer  = file_get_contents($sBibleFile);
	$iLine = 1;
	$iWords = 1;
	$aFound = array();
	find_word_in_buffer($sWord, $iWordLen, $sBuffer, 0, strlen($sBuffer), $iLine, $iWords, $aFound);
	return $aFound;
}

function find_word($sWord){
	$sWord = trim($sWord);
	echo $sWord . "\t";
	$aFound = find_word_in_bible_all($sWord, 'bible.txt');
	foreach($aFound as $aWordInfo ){
		echo $aWordInfo[0], ",", $aWordInfo[1], " ";
	}
	echo "[", count($aFound), "]\n";
	echo "\n";
}

find_word($argv[1]);

思路二的实现:


function find_word_in_bible($sWord, $sBibleFile, $iBufferSize = 1024){
	$iWordLen = strlen($sWord);
	$aFound = array();
	if($iWordLen < 1){
		echo "Word Should not be empty.\n";
		return $aFound;
	}
	$hFile = fopen($sBibleFile, 'r');
	$iLine = 1;
	$iWords = 1;
	$sSwap = '';
	$iLastLen = 0;
	while(!feof($hFile)){
		$sBuffer = fread($hFile, $iBufferSize);
		$iLen = strlen($sBuffer) ;
		$j = $iLen - 1;
		$i = 0;
		while($i <= $iLen && is_digit_or_letter($sBuffer[$i])){
			$i++;
		}
		while($i <= $iLen && !is_digit_or_letter($sBuffer[$i])){
			$i++;
		}
		while($j >= 0 && !is_digit_or_letter($sBuffer[$j])){
			$j--;
		}
		while($j >= 0 && is_digit_or_letter($sBuffer[$j])){
			$j--;
		}
		$j++;

		$sSwap = $sSwap . substr($sBuffer, 0, $i);
		find_word_in_buffer($sWord, $iWordLen, $sSwap, 0, $iLastLen + $i, $iLine, $iWords, $aFound);

		$iLastLen = $iLen - $j;
		$sSwap = ($j === $iLen) ? '' : substr($sBuffer, $j);
		find_word_in_buffer($sWord, $iWordLen, $sBuffer, $i, $j, $iLine, $iWords, $aFound);
	}

	find_word_in_buffer($sWord, $iWordLen, $sSwap, 0, $iLastLen, $iLine, $iWords, $aFound);

	fclose($hFile);
	return $aFound;
}

function find_word($sWord){
	$sWord = trim($sWord);
	echo $sWord . "\t";
	$aFound = find_word_in_bible($sWord, 'bible.txt', 1024);
	foreach($aFound as $aWordInfo ){
		echo $aWordInfo[0], ",", $aWordInfo[1], " ";
	}
	echo "[", count($aFound), "]\n";
	echo "\n";
}

find_word($argv[1]);

两个还算都能得出正确结果:

php find-word-in-bible.php beginning
beginning	1,6 245,6 322,26 1217,30 1477,13 1819,11 5221,26 5465,31 5801,32 6714,23 7150,32 7183,28 8590,47 8591,23 10009,11 10873,45 12117,12 13037,6 13935,16 15804,11 16059,10 16408,11 16625,10 16626,12 16649,11 16888,5 16976,12 17371,36 17438,13 17507,5 17681,20 18000,35 18005,30 18442,20 18456,15 18478,9 18597,9 18618,12 18620,9 18622,12 18631,20 18890,7 19370,10 19574,6 19598,6 19620,14 20162,19 20352,12 21479,15 22010,24 22012,6 22097,5 22466,19 22593,19 23628,15 23767,22 23771,26 23801,26 23966,8 23979,16 24217,5 24595,7 24737,17 24896,14 25941,20 26019,5 26039,20 26046,6 26047,9 26106,12 26107,5 26322,18 26391,20 26407,27 26426,26 26727,18 26731,36 26946,4 27312,11 27323,21 27461,13 27829,9 29261,20 29458,12 29484,17 29675,27 29974,9 30010,15 30068,12 30521,42 30527,28 30542,10 30558,22 30558,35 30564,19 30565,20 30575,17 30575,26 30588,19 30591,15 30651,28 30652,26 30706,10 30761,26 31060,18 31094,10 [106]

One Trackback

  1. By 使用 C 语言解决圣经背诵问题 – 薹翮 on 2012 年 6 月 8 日 at 下午 1:02

    […] PHP 解决圣经背诵问题 这一篇中我们使用 PHP […]

Post a Comment

Your email is never shared. Required fields are marked *

*
*