Skip to content

Instantly share code, notes, and snippets.

@asterite
Created September 12, 2011 15:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save asterite/1211582 to your computer and use it in GitHub Desktop.
Save asterite/1211582 to your computer and use it in GitHub Desktop.
My searching algorithm
<?
class Dictionary {
function __construct($filename) {
$this->filename = $filename;
$this->sortedFilename = "${filename}.sorted";
}
function search($search) {
if (!file_exists($this->sortedFilename)) {
$this->sortWords();
}
$searchWithComma = ",$search,";
$size = filesize($this->sortedFilename);
$file = fopen($this->sortedFilename, 'r');
$down = 0;
$up = $size - 1;
while ($down < $up) {
$mid = (int)(($down + $up) / 2);
fseek($file, $mid);
$line = fread($file, 1024);
if (strpos($line, $searchWithComma) !== false) {
fclose($file);
return true;
}
$firstComma = strpos($line, ',');
$secondComma = strpos($line, ',', $firstComma + 1);
$word = substr($line, $firstComma + 1, $secondComma - $firstComma - 1);
if ($search < $word) {
$up = $mid - 1;
} else {
$down = $mid + 1;
}
}
fclose($file);
return false;
}
private function sortWords() {
$string = file_get_contents($this->filename);
$pieces = preg_split('/,/', $string);
sort($pieces);
$output = fopen($this->sortedFilename, 'w');
foreach($pieces as $piece) {
fwrite($output, ',');
fwrite($output, $piece);
}
fwrite($output, ',');
fclose($output);
}
}
function searchAndPrint($dictionary, $search) {
if ($dictionary->search($search)) {
echo "$search => found\n";
} else {
echo "$search => not found\n";
}
}
$dictionary = new Dictionary('dictionary2.txt');
searchAndPrint($dictionary, 'AAX');
searchAndPrint($dictionary, 'ABNEGATING');
searchAndPrint($dictionary, 'SLAVISHLY');
searchAndPrint($dictionary, 'ZZZZ');
searchAndPrint($dictionary, 'ZZZA');
?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment