Release-1.6.1-20091222

1 files changed, 314 insertions, 0 deletions

diff --git a/src/search.php b/src/search.php
new file mode 100644
index 0000000..d899ade
--- /dev/null
+++ b/src/search.php
@@ -0,0 +1,314 @@
+function readInt($file)
+{
+  $b1 = ord(fgetc($file)); $b2 = ord(fgetc($file));
+  $b3 = ord(fgetc($file)); $b4 = ord(fgetc($file));
+  return ($b1<<24)|($b2<<16)|($b3<<8)|$b4;
+}
+
+function readString($file)
+{
+  $result="";
+  while (ord($c=fgetc($file))) $result.=$c;
+  return $result;
+}
+
+function readHeader($file)
+{
+  $header =fgetc($file); $header.=fgetc($file);
+  $header.=fgetc($file); $header.=fgetc($file);
+  return $header;
+}
+
+function computeIndex($word)
+{
+  // Simple hashing that allows for substring search
+  if (strlen($word)<2) return -1;
+  // high char of the index
+  $hi = ord($word{0});
+  if ($hi==0) return -1;
+  // low char of the index
+  $lo = ord($word{1});
+  if ($lo==0) return -1;
+  // return index
+  return $hi*256+$lo;
+}
+
+function search($file,$word,&$statsList)
+{
+  $index = computeIndex($word);
+  if ($index!=-1) // found a valid index
+  {
+    fseek($file,$index*4+4); // 4 bytes per entry, skip header
+    $index = readInt($file);
+    if ($index) // found words matching the hash key
+    {
+      $start=sizeof($statsList);
+      $count=$start;
+      fseek($file,$index);
+      $w = readString($file);
+      while ($w)
+      {
+        $statIdx = readInt($file);
+        if ($word==substr($w,0,strlen($word)))
+        { // found word that matches (as substring)
+          $statsList[$count++]=array(
+              "word"=>$word,
+              "match"=>$w,
+              "index"=>$statIdx,
+              "full"=>strlen($w)==strlen($word),
+              "docs"=>array()
+              );
+        }
+        $w = readString($file);
+      }
+      $totalHi=0;
+      $totalFreqHi=0;
+      $totalFreqLo=0;
+      for ($count=$start;$count<sizeof($statsList);$count++)
+      {
+        $statInfo = &$statsList[$count];
+        $multiplier = 1;
+        // whole word matches have a double weight
+        if ($statInfo["full"]) $multiplier=2;
+        fseek($file,$statInfo["index"]); 
+        $numDocs = readInt($file);
+        $docInfo = array();
+        // read docs info + occurrence frequency of the word
+        for ($i=0;$i<$numDocs;$i++)
+        {
+          $idx=readInt($file); 
+          $freq=readInt($file); 
+          $docInfo[$i]=array("idx"  => $idx,
+                             "freq" => $freq>>1,
+                             "rank" => 0.0,
+                             "hi"   => $freq&1
+                            );
+          if ($freq&1) // word occurs in high priority doc
+          {
+            $totalHi++;
+            $totalFreqHi+=$freq*$multiplier;
+          }
+          else // word occurs in low priority doc
+          {
+            $totalFreqLo+=$freq*$multiplier;
+          }
+        }
+        // read name and url info for the doc
+        for ($i=0;$i<$numDocs;$i++)
+        {
+          fseek($file,$docInfo[$i]["idx"]);
+          $docInfo[$i]["name"]=readString($file);
+          $docInfo[$i]["url"]=readString($file);
+        }
+        $statInfo["docs"]=$docInfo;
+      }
+      $totalFreq=($totalHi+1)*$totalFreqLo + $totalFreqHi;
+      for ($count=$start;$count<sizeof($statsList);$count++)
+      {
+        $statInfo = &$statsList[$count];
+        $multiplier = 1;
+        // whole word matches have a double weight
+        if ($statInfo["full"]) $multiplier=2;
+        for ($i=0;$i<sizeof($statInfo["docs"]);$i++)
+        {
+          $docInfo = &$statInfo["docs"];
+          // compute frequency rank of the word in each doc
+          $freq=$docInfo[$i]["freq"];
+          if ($docInfo[$i]["hi"])
+          {
+            $statInfo["docs"][$i]["rank"]=
+              (float)($freq*$multiplier+$totalFreqLo)/$totalFreq;
+          }
+          else
+          {
+            $statInfo["docs"][$i]["rank"]=
+              (float)($freq*$multiplier)/$totalFreq;
+          }
+        }
+      }
+    }
+  }
+  return $statsList;
+}
+
+function combine_results($results,&$docs)
+{
+  foreach ($results as $wordInfo)
+  {
+    $docsList = &$wordInfo["docs"];
+    foreach ($docsList as $di)
+    {
+      $key=$di["url"];
+      $rank=$di["rank"];
+      if (in_array($key, array_keys($docs)))
+      {
+        $docs[$key]["rank"]+=$rank;
+      }
+      else
+      {
+        $docs[$key] = array("url"=>$key,
+            "name"=>$di["name"],
+            "rank"=>$rank
+            );
+      }
+      $docs[$key]["words"][] = array(
+               "word"=>$wordInfo["word"],
+               "match"=>$wordInfo["match"],
+               "freq"=>$di["freq"]
+               );
+    }
+  }
+  return $docs;
+}
+
+function filter_results($docs,&$requiredWords,&$forbiddenWords)
+{
+  $filteredDocs=array();
+  while (list ($key, $val) = each ($docs)) 
+  {
+    $words = &$docs[$key]["words"];
+    $copy=1; // copy entry by default
+    if (sizeof($requiredWords)>0)
+    {
+      foreach ($requiredWords as $reqWord)
+      {
+        $found=0;
+        foreach ($words as $wordInfo)
+        { 
+          $found = $wordInfo["word"]==$reqWord;
+          if ($found) break;
+        }
+        if (!$found) 
+        {
+          $copy=0; // document contains none of the required words
+          break;
+        }
+      }
+    }
+    if (sizeof($forbiddenWords)>0)
+    {
+      foreach ($words as $wordInfo)
+      {
+        if (in_array($wordInfo["word"],$forbiddenWords))
+        {
+          $copy=0; // document contains a forbidden word
+          break;
+        }
+      }
+    }
+    if ($copy) $filteredDocs[$key]=$docs[$key];
+  }
+  return $filteredDocs;
+}
+
+function compare_rank($a,$b)
+{
+  if ($a["rank"] == $b["rank"]) 
+  {
+    return 0;
+  }
+  return ($a["rank"]>$b["rank"]) ? -1 : 1; 
+}
+
+function sort_results($docs,&$sorted)
+{
+  $sorted = $docs;
+  usort($sorted,"compare_rank");
+  return $sorted;
+}
+
+function report_results(&$docs)
+{
+  echo "<table cellspacing=\"2\">\n";
+  echo "  <tr>\n";
+  echo "    <td colspan=\"2\"><h2>".search_results()."</h2></td>\n";
+  echo "  </tr>\n";
+  $numDocs = sizeof($docs);
+  if ($numDocs==0)
+  {
+    echo "  <tr>\n";
+    echo "    <td colspan=\"2\">".matches_text(0)."</td>\n";
+    echo "  </tr>\n";
+  }
+  else
+  {
+    echo "  <tr>\n";
+    echo "    <td colspan=\"2\">".matches_text($numDocs);
+    echo "\n";
+    echo "    </td>\n";
+    echo "  </tr>\n";
+    $num=1;
+    foreach ($docs as $doc)
+    {
+      echo "  <tr>\n";
+      echo "    <td align=\"right\">$num.</td>";
+      echo     "<td><a class=\"el\" href=\"".$doc["url"]."\">".$doc["name"]."</a></td>\n";
+      echo "  <tr>\n";
+      echo "    <td></td><td class=\"tiny\">".report_matches()." ";
+      foreach ($doc["words"] as $wordInfo)
+      {
+        $word = $wordInfo["word"];
+        $matchRight = substr($wordInfo["match"],strlen($word));
+        echo "<b>$word</b>$matchRight(".$wordInfo["freq"].") ";
+      }
+      echo "    </td>\n";
+      echo "  </tr>\n";
+      $num++;
+    }
+  }
+  echo "</table>\n";
+}
+
+function main()
+{
+  if(strcmp('4.1.0', phpversion()) > 0) 
+  {
+    die("Error: PHP version 4.1.0 or above required!");
+  }
+  if (!($file=fopen("search/search.idx","rb"))) 
+  {
+    die("Error: Search index file could NOT be opened!");
+  }
+  if (readHeader($file)!="DOXS")
+  {
+    die("Error: Header of index file is invalid!");
+  }
+  $query="";
+  if (array_key_exists("query", $_GET))
+  {
+    $query=$_GET["query"];
+  }
+  end_form(preg_replace("/[^a-zA-Z0-9\-\_\.]/i", " ", $query ));
+  echo "&nbsp;\n<div class=\"searchresults\">\n";
+  $results = array();
+  $requiredWords = array();
+  $forbiddenWords = array();
+  $foundWords = array();
+  $word=strtok($query," ");
+  while ($word) // for each word in the search query
+  {
+    if (($word{0}=='+')) { $word=substr($word,1); $requiredWords[]=$word; }
+    if (($word{0}=='-')) { $word=substr($word,1); $forbiddenWords[]=$word; }
+    if (!in_array($word,$foundWords))
+    {
+      $foundWords[]=$word;
+      search($file,strtolower($word),$results);
+    }
+    $word=strtok(" ");
+  }
+  $docs = array();
+  combine_results($results,$docs);
+  // filter out documents with forbidden word or that do not contain
+  // required words
+  $filteredDocs = filter_results($docs,$requiredWords,$forbiddenWords);
+  // sort the results based on rank
+  $sorted = array();
+  sort_results($filteredDocs,$sorted);
+  // report results to the user
+  report_results($sorted);
+  echo "</div>\n";
+  fclose($file);
+}
+
+main();
+