PHP оптимизация орфографии итерации

Question

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

Не принимая во внимание алгоритма levensthein (я работаю с/на разных вариантах), я повторяю каждое слово словаря и вычисляю расстояние 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 How to Write a Spelling Corrector. Хотя в статье используется Python, другие реализовали ее в PHP here и here.

Answer 2

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