| 1 |
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
| 2 |
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"> |
| 3 |
<title>Search</title> |
| 4 |
<link href="doxygen.css" rel="stylesheet" type="text/css"> |
| 5 |
</head><body> |
| 6 |
<!-- Generated by Doxygen 1.3.8 --> |
| 7 |
<div class="qindex"> <form class="search" action="search.php" method="get"> |
| 8 |
<a class="qindex" href="main.html">Main Page</a> | <a class="qindex" href="annotated.html">Data Structures</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="functions.html">Data Fields</a> | <a class="qindex" href="globals.html">Globals</a> | <span class="searchHL"><u>S</u>earch for |
| 9 |
<?php |
| 10 |
|
| 11 |
function search_results() |
| 12 |
{ |
| 13 |
return "Search Results"; |
| 14 |
} |
| 15 |
|
| 16 |
function matches_text($num) |
| 17 |
{ |
| 18 |
if ($num==0) |
| 19 |
{ |
| 20 |
return "Sorry, no documents matching your query."; |
| 21 |
} |
| 22 |
else if ($num==1) |
| 23 |
{ |
| 24 |
return "Found <b>1</b> document matching your query."; |
| 25 |
} |
| 26 |
else // $num>1 |
| 27 |
{ |
| 28 |
return "Found <b>$num</b> documents matching your query. Showing best matches first."; |
| 29 |
} |
| 30 |
} |
| 31 |
|
| 32 |
function report_matches() |
| 33 |
{ |
| 34 |
return "Matches: "; |
| 35 |
} |
| 36 |
|
| 37 |
function readInt($file) |
| 38 |
{ |
| 39 |
$b1 = ord(fgetc($file)); $b2 = ord(fgetc($file)); |
| 40 |
$b3 = ord(fgetc($file)); $b4 = ord(fgetc($file)); |
| 41 |
return ($b1<<24)|($b2<<16)|($b3<<8)|$b4; |
| 42 |
} |
| 43 |
|
| 44 |
function readString($file) |
| 45 |
{ |
| 46 |
$result=""; |
| 47 |
while (ord($c=fgetc($file))) $result.=$c; |
| 48 |
return $result; |
| 49 |
} |
| 50 |
|
| 51 |
function readHeader($file) |
| 52 |
{ |
| 53 |
$header =fgetc($file); $header.=fgetc($file); |
| 54 |
$header.=fgetc($file); $header.=fgetc($file); |
| 55 |
return $header; |
| 56 |
} |
| 57 |
|
| 58 |
function computeIndex($word) |
| 59 |
{ |
| 60 |
if (strlen($word)<2) return -1; |
| 61 |
// high char of the index |
| 62 |
$hi = ord($word{0}); |
| 63 |
if ($hi==0) return -1; |
| 64 |
// low char of the index |
| 65 |
$lo = ord($word{1}); |
| 66 |
if ($lo==0) return -1; |
| 67 |
// return index |
| 68 |
return $hi*256+$lo; |
| 69 |
} |
| 70 |
|
| 71 |
function search($file,$word,&$statsList) |
| 72 |
{ |
| 73 |
$index = computeIndex($word); |
| 74 |
if ($index!=-1) // found a valid index |
| 75 |
{ |
| 76 |
fseek($file,$index*4+4); // 4 bytes per entry, skip header |
| 77 |
$index = readInt($file); |
| 78 |
if ($index) // found words matching first two characters |
| 79 |
{ |
| 80 |
$start=sizeof($statsList); |
| 81 |
$count=$start; |
| 82 |
fseek($file,$index); |
| 83 |
$w = readString($file); |
| 84 |
while ($w) |
| 85 |
{ |
| 86 |
$statIdx = readInt($file); |
| 87 |
if ($word==substr($w,0,strlen($word))) |
| 88 |
{ // found word that matches (as substring) |
| 89 |
$statsList[$count++]=array( |
| 90 |
"word"=>$word, |
| 91 |
"match"=>$w, |
| 92 |
"index"=>$statIdx, |
| 93 |
"full"=>strlen($w)==strlen($word), |
| 94 |
"docs"=>array() |
| 95 |
); |
| 96 |
} |
| 97 |
$w = readString($file); |
| 98 |
} |
| 99 |
$totalFreq=0; |
| 100 |
for ($count=$start;$count<sizeof($statsList);$count++) |
| 101 |
{ |
| 102 |
$statInfo = &$statsList[$count]; |
| 103 |
fseek($file,$statInfo["index"]); |
| 104 |
$numDocs = readInt($file); |
| 105 |
$docInfo = array(); |
| 106 |
// read docs info + occurrence frequency of the word |
| 107 |
for ($i=0;$i<$numDocs;$i++) |
| 108 |
{ |
| 109 |
$idx=readInt($file); |
| 110 |
$freq=readInt($file); |
| 111 |
$docInfo[$i]=array("idx"=>$idx,"freq"=>$freq,"rank"=>0.0); |
| 112 |
$totalFreq+=$freq; |
| 113 |
if ($statInfo["full"]) $totalFreq+=$freq; |
| 114 |
} |
| 115 |
// read name an url info for the doc |
| 116 |
for ($i=0;$i<$numDocs;$i++) |
| 117 |
{ |
| 118 |
fseek($file,$docInfo[$i]["idx"]); |
| 119 |
$docInfo[$i]["name"]=readString($file); |
| 120 |
$docInfo[$i]["url"]=readString($file); |
| 121 |
} |
| 122 |
$statInfo["docs"]=$docInfo; |
| 123 |
} |
| 124 |
for ($count=$start;$count<sizeof($statsList);$count++) |
| 125 |
{ |
| 126 |
$statInfo = &$statsList[$count]; |
| 127 |
for ($i=0;$i<sizeof($statInfo["docs"]);$i++) |
| 128 |
{ |
| 129 |
$docInfo = &$statInfo["docs"]; |
| 130 |
// compute frequency rank of the word in each doc |
| 131 |
$statInfo["docs"][$i]["rank"]= |
| 132 |
(float)$docInfo[$i]["freq"]/$totalFreq; |
| 133 |
} |
| 134 |
} |
| 135 |
} |
| 136 |
} |
| 137 |
return $statsList; |
| 138 |
} |
| 139 |
|
| 140 |
function combine_results($results,&$docs) |
| 141 |
{ |
| 142 |
foreach ($results as $wordInfo) |
| 143 |
{ |
| 144 |
$docsList = &$wordInfo["docs"]; |
| 145 |
foreach ($docsList as $di) |
| 146 |
{ |
| 147 |
$key=$di["url"]; |
| 148 |
$rank=$di["rank"]; |
| 149 |
if (in_array($key, array_keys($docs))) |
| 150 |
{ |
| 151 |
$docs[$key]["rank"]+=$rank; |
| 152 |
$docs[$key]["rank"]*=2; // multiple matches increases rank |
| 153 |
} |
| 154 |
else |
| 155 |
{ |
| 156 |
$docs[$key] = array("url"=>$key, |
| 157 |
"name"=>$di["name"], |
| 158 |
"rank"=>$rank |
| 159 |
); |
| 160 |
} |
| 161 |
$docs[$key]["words"][] = array( |
| 162 |
"word"=>$wordInfo["word"], |
| 163 |
"match"=>$wordInfo["match"], |
| 164 |
"freq"=>$di["freq"] |
| 165 |
); |
| 166 |
} |
| 167 |
} |
| 168 |
return $docs; |
| 169 |
} |
| 170 |
|
| 171 |
function normalize_ranking(&$docs) |
| 172 |
{ |
| 173 |
$maxRank = 0.0000001; |
| 174 |
// compute maximal rank |
| 175 |
foreach ($docs as $doc) |
| 176 |
{ |
| 177 |
if ($doc["rank"]>$maxRank) |
| 178 |
{ |
| 179 |
$maxRank=$doc["rank"]; |
| 180 |
} |
| 181 |
} |
| 182 |
reset($docs); |
| 183 |
// normalize rankings |
| 184 |
while (list ($key, $val) = each ($docs)) |
| 185 |
{ |
| 186 |
$docs[$key]["rank"]*=100/$maxRank; |
| 187 |
} |
| 188 |
} |
| 189 |
|
| 190 |
function filter_results($docs,&$requiredWords,&$forbiddenWords) |
| 191 |
{ |
| 192 |
$filteredDocs=array(); |
| 193 |
while (list ($key, $val) = each ($docs)) |
| 194 |
{ |
| 195 |
$words = &$docs[$key]["words"]; |
| 196 |
$copy=1; // copy entry by default |
| 197 |
if (sizeof($requiredWords)>0) |
| 198 |
{ |
| 199 |
foreach ($requiredWords as $reqWord) |
| 200 |
{ |
| 201 |
$found=0; |
| 202 |
foreach ($words as $wordInfo) |
| 203 |
{ |
| 204 |
$found = $wordInfo["word"]==$reqWord; |
| 205 |
if ($found) break; |
| 206 |
} |
| 207 |
if (!$found) |
| 208 |
{ |
| 209 |
$copy=0; // document contains none of the required words |
| 210 |
break; |
| 211 |
} |
| 212 |
} |
| 213 |
} |
| 214 |
if (sizeof($forbiddenWords)>0) |
| 215 |
{ |
| 216 |
foreach ($words as $wordInfo) |
| 217 |
{ |
| 218 |
if (in_array($wordInfo["word"],$forbiddenWords)) |
| 219 |
{ |
| 220 |
$copy=0; // document contains a forbidden word |
| 221 |
break; |
| 222 |
} |
| 223 |
} |
| 224 |
} |
| 225 |
if ($copy) $filteredDocs[$key]=$docs[$key]; |
| 226 |
} |
| 227 |
return $filteredDocs; |
| 228 |
} |
| 229 |
|
| 230 |
function compare_rank($a,$b) |
| 231 |
{ |
| 232 |
if ($a["rank"] == $b["rank"]) |
| 233 |
{ |
| 234 |
return 0; |
| 235 |
} |
| 236 |
return ($a["rank"]>$b["rank"]) ? -1 : 1; |
| 237 |
} |
| 238 |
|
| 239 |
function sort_results($docs,&$sorted) |
| 240 |
{ |
| 241 |
$sorted = $docs; |
| 242 |
usort($sorted,"compare_rank"); |
| 243 |
return $sorted; |
| 244 |
} |
| 245 |
|
| 246 |
function report_results(&$docs) |
| 247 |
{ |
| 248 |
echo "<table cellspacing=\"2\">\n"; |
| 249 |
echo " <tr>\n"; |
| 250 |
echo " <td colspan=\"2\"><h2>".search_results()."</h2></td>\n"; |
| 251 |
echo " </tr>\n"; |
| 252 |
$numDocs = sizeof($docs); |
| 253 |
if ($numDocs==0) |
| 254 |
{ |
| 255 |
echo " <tr>\n"; |
| 256 |
echo " <td colspan=\"2\">".matches_text(0)."</td>\n"; |
| 257 |
echo " </tr>\n"; |
| 258 |
} |
| 259 |
else |
| 260 |
{ |
| 261 |
echo " <tr>\n"; |
| 262 |
echo " <td colspan=\"2\">".matches_text($numDocs); |
| 263 |
echo "\n"; |
| 264 |
echo " </td>\n"; |
| 265 |
echo " </tr>\n"; |
| 266 |
$num=1; |
| 267 |
foreach ($docs as $doc) |
| 268 |
{ |
| 269 |
echo " <tr>\n"; |
| 270 |
echo " <td align=\"right\">$num.</td>"; |
| 271 |
echo "<td><a class=\"el\" href=\"".$doc["url"]."\">".$doc["name"]."</a></td>\n"; |
| 272 |
echo " <tr>\n"; |
| 273 |
echo " <td></td><td class=\"tiny\">".report_matches()." "; |
| 274 |
foreach ($doc["words"] as $wordInfo) |
| 275 |
{ |
| 276 |
$word = $wordInfo["word"]; |
| 277 |
$matchRight = substr($wordInfo["match"],strlen($word)); |
| 278 |
echo "<b>$word</b>$matchRight(".$wordInfo["freq"].") "; |
| 279 |
} |
| 280 |
echo " </td>\n"; |
| 281 |
echo " </tr>\n"; |
| 282 |
$num++; |
| 283 |
} |
| 284 |
} |
| 285 |
echo "</table>\n"; |
| 286 |
} |
| 287 |
|
| 288 |
function main() |
| 289 |
{ |
| 290 |
if(strcmp('4.1.0', phpversion()) > 0) |
| 291 |
{ |
| 292 |
die("Error: PHP version 4.1.0 or above required!"); |
| 293 |
} |
| 294 |
if (!($file=fopen("search.idx","rb"))) |
| 295 |
{ |
| 296 |
die("Error: Search index file could NOT be opened!"); |
| 297 |
} |
| 298 |
if (readHeader($file)!="DOXS") |
| 299 |
{ |
| 300 |
die("Error: Header of index file is invalid!"); |
| 301 |
} |
| 302 |
$query=""; |
| 303 |
if (array_key_exists("query", $_GET)) |
| 304 |
{ |
| 305 |
$query=$_GET["query"]; |
| 306 |
} |
| 307 |
echo "<input class=\"search\" type=\"text\" name=\"query\" value=\"$query\" size=\"20\" accesskey=\"s\"/>\n"; |
| 308 |
echo "</span>\n"; |
| 309 |
echo "</form>\n"; |
| 310 |
echo "</div>\n"; |
| 311 |
$results = array(); |
| 312 |
$requiredWords = array(); |
| 313 |
$forbiddenWords = array(); |
| 314 |
$foundWords = array(); |
| 315 |
$word=strtok($query," "); |
| 316 |
while ($word) // for each word in the search query |
| 317 |
{ |
| 318 |
if (($word{0}=='+')) { $word=substr($word,1); $requiredWords[]=$word; } |
| 319 |
if (($word{0}=='-')) { $word=substr($word,1); $forbiddenWords[]=$word; } |
| 320 |
if (!in_array($word,$foundWords)) |
| 321 |
{ |
| 322 |
$foundWords[]=$word; |
| 323 |
search($file,$word,$results); |
| 324 |
} |
| 325 |
$word=strtok(" "); |
| 326 |
} |
| 327 |
$docs = array(); |
| 328 |
combine_results($results,$docs); |
| 329 |
// filter out documents with forbidden word or that do not contain |
| 330 |
// required words |
| 331 |
$filteredDocs = filter_results($docs,$requiredWords,$forbiddenWords); |
| 332 |
// normalize rankings so they are in the range [0-100] |
| 333 |
normalize_ranking($filteredDocs); |
| 334 |
// sort the results based on rank |
| 335 |
$sorted = array(); |
| 336 |
sort_results($filteredDocs,$sorted); |
| 337 |
// report results to the user |
| 338 |
report_results($sorted); |
| 339 |
fclose($file); |
| 340 |
} |
| 341 |
|
| 342 |
main(); |
| 343 |
|
| 344 |
|
| 345 |
?> |
| 346 |
<hr size="1"><address style="align: right;"><small>Generated on Thu Sep 16 18:10:52 2004 for libSPF v1.0 by |
| 347 |
<a href="http://www.doxygen.org/index.html"> |
| 348 |
<img src="doxygen.png" alt="doxygen" align="middle" border=0 ></a> 1.3.8 </small></address> |
| 349 |
</body> |
| 350 |
</html> |
