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

$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 ответов

Решение

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

$word = mysql_real_escape_string($word);
mysql_qery("SELECT `term` FROM `words` WHERE levenshtein('$word', `term`) BETWEEN 0 AND 4");
Источник

Есть два способа реализовать функцию Левенштейна в 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 и импортируйте его в свою базу данных следующим образом:

source /tmp/mysql_udf.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;

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

Источник

Если у вас огромная база данных, вы можете сначала отфильтровать слова, используя 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 перед применением реального Левенштейна сделает все быстрее, почти без усилий.

Источник

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

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

против

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

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

Источник

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

Вы должны использовать 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);
Источник

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

$ word = strtolower ($ _ GET ['term']);

$ q = mysql_uqery ("ВЫБЕРИТЕ НИЖЕ (` term`) ИЗ `слов`");

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

    $lev = левенштейн ($word, $r['term']);

    ....

}
Источник

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

Источник

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

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

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

Источник
Другие вопросы по тегам