PHP Simple Spell Checker (Binary Search help)

Question

I need help with performing a binary search with a search term ($searchTerm) and comparing it to a dictionary ($dictionary).

Basically, it reads a dictionary file into an array. The user inputs some words, that string becomes $checkMe. I do an explode function and it turns into $explodedCheckMe. I pass each term in $checkMe to binarySearch as $searchTerm (Okay, my code is confusing). I think my logic is sound, but my syntax isn't ...

I've been using this a lot: http://us3.php.net/manual/en/function.strcasecmp.php

here is my code: paste2.org/p/457232

Answer 1

So you are looking up exact strings in the dictionary. Why don't you a simple array for this? The native PHP's hash table is definitely going to be faster than a binary search implemented in PHP.

while (!feof($file)) {
    $dictionary[strtolower(fgets($file))] = 1;
}

...

function search($searchTerm, $dictionary) {
    if ($dictionary[strtolower($searchTerm)]) {
        // do something
    }
}

But if you really want to use a binary search, try this:

function binarySearch($searchTerm, $dictionary) {
    $minVal = 0;
    $maxVal = count($dictionary);
    while ($minVal < $maxVal) {
        $guess = intval($minVal + ($maxVal - $minVal) / 2);
        $result = strcasecmp($dictionary[$guess], $searchTerm);
        if ($result == 0) {
            echo "FOUND";
            return;
        }
        elseif ($result < 0) {
            $minVal = $guess + 1;
        }
        else {
            $maxVal = $guess;
        }
    }
}

The main problem was that you can't set $maxval to $guess - 1. See the wikipedia article on binary search, it's really good.

Answer 2

I know this doesn't directly answer your question, but have you considered using pspell and a custom dictionary?