оптимизация проверки орфографии php

Question

Недавно приступив к работе над проектом, который может нуждаться в (хороших) возможностях масштабирования, у меня возник следующий вопрос:

Не принимая во внимание алгоритм levensthein (я работаю с / наразличные варианты), я перебираю каждое словарное слово и вычисляю левенство между словарным словом и каждым из слов в моей входной строке.Что-то вроде:

<?php
$input_words = array("this", "is", "a", "test");
foreach ($dictionary_words as $dictionary_word) {
    foreach ($input_words as $input_word) {
        $ld = levenshtein($input_word, $accepted_word);
        if ($ld < $distances[$input_word] || $distances[$word] == NULL) {
            $distances[$input_word] = $ld;
            if ($ld == 0)
                continue;
        }
    }
}
?>

Мой вопрос касается наилучшей практики: время выполнения составляет ~ 1-2 секунды.Я имею в виду запуск «сервера словарей», который при запуске загружает слова словаря в память и затем выполняет итерацию как часть проверки орфографии (как описано выше), когда запрос получен.Это уменьшит время выполнения или медленная часть - итерация (для циклов)?Если да, могу ли я что-нибудь сделать для правильной оптимизации?

Google "Вы имели в виду:?"не требуется несколько секунд, чтобы проверить ту же строку ввода;)

Заранее спасибо и счастливого Нового года.

Answer 1

Прочтите Norvig's Как написать корректор орфографии . Хотя в статье используется Python, другие реализовали его на PHP здесь и здесь .

Answer 2

Вы бы хорошо реализовали свой словарь в виде бинарного дерева или другой более эффективной структуры данных.Дерево значительно сократит время поиска.