5
\$\begingroup\$

I built a simple PHP spellchecker and suggestions app that uses PHP's similar_text() and levenshtein() functions to compare words from a dictionary that is loaded into an array.

  • How it works is first I load the contents of the dictionary into an array.
  • I split the user's input into words and spell check each of the words.
  • I spell check by checking if the word is in the array that is the dictionary.
  • If it is, then I echo a congratulations message and move on.
  • If not, I iterate through the dictionary-array comparing each word, in the dictionary-array, with the assumed misspelling.
  • If the inputted word, in lower-case and without punctuation, is 90% or more similar to a word in the dictionary array, then I copy that word from the dictionary array into an array of suggestions.
  • If no suggestions were found using the 90% or higher similarity comparison, then I use levenshtein() to do a more liberal comparison and add suggestions to the suggestions array.
  • Then I iterate through the suggestions array and echo each suggestion.

I noticed that this is running slowly. Slow enough to notice. And I was wondering how I could improve the speed and efficiency of this spell checker.

Any and all changes, improvements, suggestions, and code are welcome and appreciated.

Here is the code (For syntax highlighted code, please visit here):

<?php
function addTo($line){
    return strtolower(trim($line));
}
$words = array_map('addTo', file('dictionary.txt'));
$words = array_unique($words);
function checkSpelling($input, $words){
$suggestions = array();
if(in_array($input, $words)){
    echo "you spelled the word right!";
}
else{
    foreach($words as $word){
        $percentageSimilarity=0.0;
        $input = preg_replace('/[^a-z0-9 ]+/i', '', $input);
        similar_text(strtolower(trim($input)), strtolower(trim($word)), $percentageSimilarity);
        if($percentageSimilarity>=90 && $percentageSimilarity<100){
                if(!in_array($suggestions)){
                    array_push($suggestions, $word);
        }
        }
    }
if(empty($suggestions)){
    foreach($words as $word){
    $input = preg_replace('/[^a-z0-9 ]+/i', '', $input);
    $levenshtein = levenshtein(strtolower(trim($input)), strtolower(trim($word)));
    if($levenshtein<=2 && $levenshtein>0){
         if(!in_array($suggestions)){
           array_push($suggestions, $word);
          }
        }
    }
}
    echo "Looks like you spelled that wrong. Here are some suggestions: <br />";
         foreach($suggestions as $suggestion){
             echo "<br />".$suggestion."<br />";
         }
    }
}
if(isset($_GET['check'])){
    $input = trim($_GET['check']);
    $sentence='';
    if(stripos($input, ' ')!==false){
    $sentence = explode(' ', $input);
    foreach($sentence as $item){
        checkSpelling($item, $words);
    }
    }
    else{
         checkSpelling($input, $words);
    }
 }
 ?>
<!Doctype HTMl>
<html lang="en">
    <head>
        <meta charset="utf-8" />
        <title>Spell Check</title>
    </head>
    <body>
        <form method="get">
             <input type="text" name="check" autocomplete="off" autofocus />
        </form>
    </body>
 </html>
\$\endgroup\$
  • \$\begingroup\$ Any reason why you aren't using an existing spellchecker? Spellcheck for PHP has already been solved a number of times. \$\endgroup\$ – Dave Jarvis Jun 12 '13 at 16:49
  • 1
    \$\begingroup\$ @DaveJarvis I wanted to invent a solution myself / code it myself even if I was using other's code or algorithms. It is the journey I was looking for. And where? All the solutions I found had a restricted number of API calls or were outdated as of PHP 5.3 \$\endgroup\$ – JayGatz Jun 13 '13 at 0:42
  • 1
    \$\begingroup\$ @DaveJarvis In the sample code, it says it requires a license key. \$\endgroup\$ – JayGatz Jun 14 '13 at 0:05
  • \$\begingroup\$ So it does, which is a shame. I was planning to use it. \$\endgroup\$ – Dave Jarvis Jun 14 '13 at 4:00
  • \$\begingroup\$ Use this API with SSL also. Easy for translation API also. It'll give you direct access by Curl. \$\endgroup\$ – Jagroop Singh Buttar Apr 19 '14 at 17:21
3
\$\begingroup\$

Here are a couple of tweaks that could help performance:

  1. Rather than storing the dictionary in-memory, offload that to a database (potentially even caching commonly misspelled words as an optimization)

  2. Ignore words under a certain length (for example, MySQL's fulltext searching ignores words with fewer than 4 characters by default)

The thing that concerns me most with your algorithm is how much time it would take to compare every single word in the dictionary. This problem compounds with more words in the search query.

There has to be a way to quickly filter the dictionary to a smaller list of higher probability similarities (i.e. by word length, first letter, etc. ?)

\$\endgroup\$
  • 1
    \$\begingroup\$ MySQL will also allow for SOUNDEX expressions which help on spellcheckers too! \$\endgroup\$ – phpisuber01 Jun 13 '13 at 13:58
  • \$\begingroup\$ @phpisuber01 That would be a great way to limit potential matches \$\endgroup\$ – landons Jun 13 '13 at 14:00
2
\$\begingroup\$

Try loading the words into a Binary Search Tree instead of an Array, a BST is much faster when it comes to search compared to the array

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.