PHP Simple Spell Checker (Справка по бинарному поиску)

Question

Мне нужна помощь в выполнении бинарного поиска по поисковому запросу ($ searchTerm) и сравнении его со словарем ($ dictionary).

По сути, он читает файл словаря в массив. Пользователь вводит несколько слов, эта строка становится $ checkMe. Я делаю функцию разнесения, и она превращается в $ explodedCheckMe. Я передаю каждый член в $ checkMe для binarySearch как $ searchTerm (хорошо, мой код сбивает с толку). Я думаю, что моя логика правильна, но мой синтаксис не ...

Я часто этим пользуюсь: http://us3.php.net/manual/en/function.strcasecmp.php

вот мой код: paste2.org/p/457232

Answer 1

Я знаю, что это не дает прямого ответа на ваш вопрос, но вы рассматривали возможность использования pspell и пользовательского словаря?

Answer 2

Итак, вы ищете точные строки в словаре. Почему бы вам не простой массив для этого? Хеш-таблица нативного PHP определенно будет быстрее, чем бинарный поиск, реализованный в PHP.

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

...

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

Но если вы действительно хотите использовать бинарный поиск, попробуйте это:

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;
        }
    }
}

Основная проблема заключалась в том, что вы не можете установить $maxval на $guess - 1. Смотрите статью в Википедии о бинарном поиске , это действительно хорошо.