title: PHP/MySQL Search Engine Using Levenshtein Distance
body: <p>I'm trying to create a simple search engine where users can query a database and be returned results that both match <em>and</em> are close to their query. At first I was just using wildcards (<code>%</code>) to find results that were relevant to a users search. The PHP for that looked something like this:</p>
  
  <pre><code>// Users search terms is saved in $_POST['q']
  $q = $_POST['q'];
  // Prepare statement
  $search = $db-&gt;prepare("SELECT `id`, `name` FROM `users` WHERE `name` LIKE ?");
  // Execute with wildcards
  $search-&gt;execute(array("%$q%"));
  // Echo results
  foreach($search as $s) {
    echo $s['name'];
  }
  </code></pre>
  
  <p>The above code works fine, however, it's rather limited. While it can fetch results that are close to but don't exactly match the users query (because of the wildcards), it still doesn't return all relevant results; the user's query still has to have an exact match to something in the database. For example, if I had a database with the name "Tim" as a row, searching for "Timothy" wouldn't work. So my new approach looks something like this:</p>
  
  <pre><code>// Users search terms is saved in $_POST['q']
  $q = $_POST['q'];
  // Create array for the names that are close to or match the search term
  $results = array();
  foreach($db-&gt;query('SELECT `id`, `name` FROM `users`') as $name) {
    // Keep only relevant results
    if (levenshtein($q, $name['name']) &lt; 4) {
      array_push($results,$name['name']);
    }
  }
  // Echo out results
  foreach ($results as $result) {
    echo $result."\n";
  }
  </code></pre>
  
  <p>This code technically <em>works</em>, however, it's pretty inefficient and I'm wondering how it can be improved. The biggest problem is that as all results have to be retrieved from the database <em>and then</em> sorted, an unnecessarily large SQL query is created, which is especially problematic as I have a <strong>big</strong> database. Furthermore I wanted to know if simply using the <code>levenshtein</code> function is sufficient for getting relevant results, or if there is a better way to sort out the irrelevant results. Some other ways of sorting the relevant results I came up with:</p>
  
  <pre><code>if (levenshtein(metaphone($q), metaphone($name['name'])) &lt; 4) {
    array_push($results,$name['name']);
  }
  </code></pre>
  
  <p>or</p>
  
  <pre><code>if (similar_text(metaphone($q), metaphone($name)['name']) &lt; 2) {
    array_push($results,$name['name']);
  }
  </code></pre>
  
  <p>or</p>
  
  <pre><code>if (similar_text($q, $name['name']) &gt; 2) {
   array_push($results,$name['name']);
  }
  </code></pre>
  
  <p>I think using <code>levenshtein</code> with <code>metaphone</code> may actually work the best as it would better take into account simple spelling errors. But I'm not sure which would be the best to use, especially considering that the way I'm doing it now is already very expensive (the large SQL query + the expensive functions that take place in a loop don't bode well for performance).</p>
  
  <p>Thanks in advance</p>