Реализация Левенштейна с PHP и базой данных

Question

У меня есть форма поиска.Если пользователь делает опечатку типа ager вместо anger, он все равно должен показывать релевантные результаты вместо отображения 0 найденных результатов.

Я сталкивался с PHP-функцией Левенштейна , и пример, который они привели с массивом, является именно тем, что я хочу [за исключением того, что пользователь может ввести предложение, а не одно слово], но яхотел бы реализовать его с базой данных, но понятия не имею, как реализовать его с базой данных.

Это мой код:

if(!empty($search))
{
    try {
        $query = $this->_db->prepare($sql);
        $query->execute();
        if(!$query->rowCount()==0)
        {
            $foundRows = $this->_db->query("SELECT FOUND_ROWS()")->fetchColumn();
            while($row = $query->fetch(PDO::FETCH_ASSOC))
            {
                $cQuote =  $this->highlightWords(htmlspecialchars($row['cQuotes']),$search);
                $search_result[] = array('success' => true, 'totalRows' => $foundRows, 'cQuotes' => $cQuote, 'vAuthor' => $this->h($row['vAuthor']), 'vBookName' => $this->h($row['vBookName']), 'vRef' => $this->h($row['vRef']));
            }
            $response = json_encode($search_result);
            echo $response;
            return TRUE;
        }
        else
        {
            $ex =  "No results found for " .$search;
            $this->errorMsg($ex);
        }
        $query->closeCursor();
    }
    catch (Exception $ex){
        $ex =  "Problem: " .$ex;
        $this->errorMsg($ex);
    }
}
else
{
    $ex =  "Please enter something";
    $this->errorMsg($ex);
}

Я должен добавить, что я использую MySQL + PDO.

Answer 1

Чтобы это работало, вам понадобятся три вещи:

• Реализация расстояния Левенштейна на конце MySQL
• Указатель найденных словв каждом тексте
• Разделите поисковый запрос на слова, LEFT JOIN для каждого слова и HAVING предложение

Пример схемы базы данных:

текст

+---------+----------------------------------------------+
| text_id | text                                         |
+---------+----------------------------------------------+
|       1 | The quick brown fox jumps over the lazy dog  |
|       2 | The slow brown foxes jump over the lazy dogs |
+---------+----------------------------------------------+

слово

+-------+---------+
| word  | text_id |
+-------+---------+
| fox   |       1 |
| foxes |       2 |
| dog   |       1 |
| dogs  |       2 |
+-------+---------+

Получив это, скажем, кто-то ищет "foxs dogg", вы будете строитьзапрос как этот:

SELECT text FROM text
    LEFT JOIN word w1 ON w1.text_id = text.text_id AND LEVENSHTEIN(w1.word, "foxs") < 3
    LEFT JOIN word w2 ON w2.text_id = text.text_id AND LEVENSHTEIN(w2.word, "dogg") < 3
    GROUP BY text.text_id
    HAVING COUNT(*) = 2

... где:

• Каждое слово имеет LEFT JOIN (например: foxs и dogg)
• У вас есть предложение HAVING, которое содержит общее количество слов (например: HAVING COUNT(*) = 2)
• Указано максимальное расстояние для каждого слова (например: LEVENSHTEIN(...) < 3)

Приведенное выше вернет обе записи.

Вот еще один пример:

SELECT text FROM text
    LEFT JOIN word w1 ON w1.text_id = text.text_id AND LEVENSHTEIN(w1.word, "foxs") < 3
    LEFT JOIN word w2 ON w2.text_id = text.text_id AND LEVENSHTEIN(w2.word, "slows") < 3
    GROUP BY text.text_id
    HAVING COUNT(*) = 2

Выше приведено только text_id = 2.

Теперь, прежде чем идтисумасшедшая реализация этого, вы должны знать, что несколько предложений JOINКак и выше, таблица, содержащая миллионы записей (слов), будет иметь очень большое влияние на производительность .

Хотя это рабочий пример, вы действительно должны посмотретьдля уже реализованного алгоритма поиска, например Solr's SpellCheck component.