Левенштейн: MySQL + PHP - PullRequest
Новая
       2

Левенштейн: MySQL + PHP

31 голосов
/ 12 января 2011 
$word = strtolower($_GET['term']); 

$lev = 0;

$q = mysql_query("SELECT `term` FROM `words`"); 
while($r = mysql_fetch_assoc($q)) 
{ 
    $r['term'] = strtolower($r['term']); 

    $lev = levenshtein($word, $r['term']);

    if($lev >= 0 && $lev < 5)
    {
        $word = $r['term'];
    }
}

Как я могу перенести все это в один запрос? Не нужно запрашивать все термины и выполнять фильтрацию в PHP.

Ответы [ 8 ]

59 голосов
/ 12 января 2011

Вам нужна функция Левенштейна в MySQL и запрос типа 

$word = mysql_real_escape_string($word);
mysql_qery("SELECT `term` FROM `words` WHERE levenshtein('$word', `term`) BETWEEN 0 AND 4");
11 голосов
/ 29 апреля 2012

Существует два способа реализации функции Левенштейна в MySQL.Первый заключается в создании хранимой функции, которая во многом похожа на хранимую транзакцию, за исключением того, что она имеет различные входные и выходные данные.Это хорошо для небольших наборов данных, но немного медленно для всего, что приближается к нескольким тысячам строк. 

CREATE FUNCTION levenshtein( s1 VARCHAR(255), s2 VARCHAR(255) )
RETURNS INT
DETERMINISTIC

BEGIN
DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
DECLARE s1_char CHAR;
-- max strlen=255
DECLARE cv0, cv1 VARBINARY(256);
SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
IF s1 = s2 THEN
  RETURN 0;
ELSEIF s1_len = 0 THEN
  RETURN s2_len;
ELSEIF s2_len = 0 THEN
  RETURN s1_len;
ELSE
  WHILE j <= s2_len DO
    SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
  END WHILE;
  WHILE i <= s1_len DO
    SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
    WHILE j <= s2_len DO
    SET c = c + 1;
    IF s1_char = SUBSTRING(s2, j, 1) THEN
      SET cost = 0; ELSE SET cost = 1;
    END IF;
    SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
    IF c > c_temp THEN SET c = c_temp; END IF;
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
      IF c > c_temp THEN
        SET c = c_temp;
      END IF;
      SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
    END WHILE;
    SET cv1 = cv0, i = i + 1;
  END WHILE;
END IF;

RETURN c;

END//

Сохраните вышеуказанный код в файле .sql и импортируйте его в свою базу данных следующим образом:*

Второй метод - реализовать пользовательскую функцию на C / C ++ и связать ее с MySQL в виде общей библиотеки (файл * .so).Этот метод также использует STORED FUNCTION для вызова библиотеки, что означает, что фактический запрос для этого или первого метода может быть идентичным (при условии, что входные данные для обеих функций одинаковы).Вы можете узнать больше об этом методе здесь: http://samjlevy.com/mysql-levenshtein-and-damerau-levenshtein-udfs/

При любом из этих методов ваш запрос будет выглядеть примерно так: 

SELECT term FROM words WHERE levenshtein(term, 'term') < 5;

Кроме того, помните, что значение 'threshold'должен измениться относительно оригинальной длины слова.Лучше думать об этом в терминах процентного значения, то есть половина вашего слова = 50%, половина термина = 2.

8 голосов
/ 25 апреля 2013

Если у вас огромная база данных, вы можете сначала отфильтровать слова, используя SOUNDEX: 

$word = strtolower(mysql_real_escape_string($_GET['term']));

$rs = mysql_query("SELECT LOWER(`term`) FROM `words` WHERE SOUNDEX(term) = SOUNDEX(" . $word . ")");

while ($row = mysql_fetch_assoc($rs)) { 

    $lev = levenshtein($word, $row['term']);

    ....

}

Если у вас есть достаточно времени, чтобы поиграть с расширением C или процедурой, вы можете добиться лучшей производительности, но фильтрация записей в MySQL перед применением реального Левенштейна сделает все быстрее без особых усилий.

6 голосов
/ 12 августа 2014

Если вы имеете дело с очень большими наборами данных, я обнаружил, что гораздо эффективнее обрабатывать операции Левенштейна и сортировку в PHP, чем в MySQL. например запрос около 1000 записей:

MySQL (~ 0,0050 с) -> PHP Левенштейн (~ 1,300 с)

против

MySQL Левенштейн (> = 5000 с) -> PHP (~ 0,250 с)

Есть также много других вариантов оптимизации поисковых систем, но если вы хотите использовать Левенштейна, просто помните о данных, которые вы будете обрабатывать, и о желаемых задержках.

1 голос
/ 29 июня 2015

Я предлагаю вам включить вызов levenshtein (ссылка: http://www.artfulsoftware.com/infotree/queries.php#552) в ваш запрос.

Вы должны использовать mysqli_query ($ q), потому что mysql_query ($ q) устарела и может бытьудалены в будущих версиях php! 

$word = mysql_real_escape_string($word);
$query = "SELECT `term` FROM `words` WHERE levenshtein('$word', `term`)   BETWEEN 0 AND 4";
mysqli_qery($query);
1 голос
/ 12 января 2011

Вы можете сделать этот код более аккуратным, но @profitphp прав, вы не можете сделать это в MySQL без библиотеки levenstein.

$word = strtolower($_GET['term']);

$q = mysql_uqery("SELECT LOWER(`term`) FROM `words`");

while($r = mysql_fetch_assoc($q)) { 

    $lev = levenshtein($word, $r['term']);

    ....

}
0 голосов
/ 12 января 2011

Я делаю это в Oracle, реализуя алгоритм в PL / SQL внутри функции, которую можно вызвать.

0 голосов
/ 12 января 2011

Это один запрос.Если вы спрашиваете, можете ли вы переместить функциональность levenshtein в mysql, вы не сможете.

Хорошо, вы можете, но это не легче, чем просто сделать это в php.

http://www.artfulsoftware.com/infotree/queries.php?&bw=1280#552

...