PHP: использование levenshtein расстояние до слов соответствия

Question

Я читал и тестировал несколько примеров на php levenshtein. Сравнивая $ ввод в $ слова выходы сравнения

$input = 'hw r u my dear angel'; 

    // array of words to check against 
    $words = array('apple','pineapple','banana','orange','how are you', 
        'radish','carrot','pea','bean','potato','hw are you'); 

выходы

Input word: hw r u my dear angel 
Did you mean: hw are you? 

сравнения, удалить HW ты в массиве.

$input = 'hw r u my dear angel'; 

    // array of words to check against 
    $words = array('apple','pineapple','banana','orange','how are you', 
        'radish','carrot','pea','bean','potato'); 

в второй извлекая ш ты в выходах массива

Input word: hw r u my dear angel 
Did you mean: orange? 

где в similar_text()

echo '<br/>how are you:'.similar_text($input,'how are you'); 
    echo '<br/>orange:'.similar_text($input,'orange'); 
    echo '<br/>hw are you:'.similar_text($input,'hw are you'); 

how are you:6 
orange:5 
hw are you:6 

на втором сравнить почему это выход оранжевый когда хау у вас также имеет 6 похожих te xt как hw вы? Есть ли способ улучшить или улучшить метод об этом? Кроме того, я сохраняю все возможные входные данные в базе данных. должен ли я запросить его и сохранить в array, а затем использовать foreach, чтобы получить levenshtein distance? но это будет медленно, если у вас есть миллионы.

КОД

<?php 
    // input misspelled word 
    $input = 'hw r u my dear angel'; 

    // array of words to check against 
    $words = array('apple','pineapple','banana','orange','how are you', 
        'radish','carrot','pea','bean','potato','hw are you'); 


    // no shortest distance found, yet 
    $shortest = -1; 

    $closest = closest($input,$words,$shortest); 


    echo "Input word: $input<br/>"; 
    if ($shortest == 0) { 
     echo "Exact match found: $closest\n"; 
    } else { 
     echo "Did you mean: $closest?\n"; 
    } 
    echo '<br/><br/>'; 

    $shortest = -1; 
    $words = array('apple','pineapple','banana','orange','how are you', 
        'radish','carrot','pea','bean','potato'); 
    $closest = closest($input,$words,$shortest); 
    echo "Input word: $input<br/>"; 
    if ($shortest == 0) { 
     echo "Exact match found: $closest\n"; 
    } else { 
     echo "Did you mean: $closest?\n"; 
    } 

    echo '<br/><br/>'; 
    echo 'Similar text'; 
    echo '<br/>how are you:'.similar_text($input,'how are you'); 
    echo '<br/>orange:'.similar_text($input,'orange'); 
    echo '<br/>hw are you:'.similar_text($input,'hw are you'); 



    function closest($input,$words,&$shortest){ 
     // loop through words to find the closest 
    foreach ($words as $word) { 

     // calculate the distance between the input word, 
     // and the current word 
     $lev = levenshtein($input, $word); 

     // check for an exact match 
     if ($lev == 0) { 

      // closest word is this one (exact match) 
      $closest = $word; 
      $shortest = 0; 

      // break out of the loop; we've found an exact match 
      break; 
     } 

     // if this distance is less than the next found shortest 
     // distance, OR if a next shortest word has not yet been found 
     if ($lev <= $shortest || $shortest < 0) { 
      // set the closest match, and shortest distance 
      $closest = $word; 
      $shortest = $lev; 
     } 


    } 
    return $closest; 
    } 
    ?> 

Answer 1

Прежде всего, это не имеет значения, что выводит similar_text(), поскольку он использует другой алгоритм для вычисления подобия между строками.

Давайте попытаемся понять, почему levenstein() думает, что г у HW мой дорогой Анж ближе к оранжевый чем «Как вы. В Википедии есть good definition того расстояния Левенштейна.

Неофициально, расстояние Левенштейна между двумя словами - это минимальное количество односимвольных изменений (вставка, удаление, замена), необходимых для смены одного слова на другое.

Теперь давайте считать, сколько редактирует мы должны сделать, чтобы изменить Hw Р о дорогой мой ангел в оранжевый.

1. HW RU мой милый ангел → HW RU мой дорогой Анж (удаление последнего символа)
2. HW RU мой дорогой Анж → HW RU мой dearange (удаление последнего пространства)
3. HW RU мой dearange → arange (удаление первых 12 символов)
4. arange → оранжевый (замещение с о)

Так оно принимает 1 + 1 + 12 + 1 = 15 изменения всего изменить Hw ру мой дорогой ангел на оранжевый.

А вот преобразование Hw г у дорогой мой ангел в как ты.

1. HW RU мой дорогой ангел → как RU мой дорогой ангел (вставка орто характера)
2. как RU мой милый ангел → как дорогой ангел (делеция 7 символов)
3. как дорогой ангел → как ар ангел (удаление 2-х символов)
4. как ар ангел → как это ангел (вставка электронного характера)
5. , как это ангел → как это анг (удаление последних 2-х символов)
6. , как это анг → как вы (подстановка последних 3 символов)

Всего 1 + 7 + 2 + 1 + 5 = 16 редактирование. Так как вы можете видеть, с точки зрения Левинштейн расстояния оранжевый ближе к ш ру мой дорогой ангел ;-)

Answer 2

нашел что-то .. но использует MySQL http://www.artfulsoftware.com/infotree/queries.php#552 Я думаю, что это гораздо лучше, чем обрабатывать его на PHP поскольку мои данные хранятся в базе данных.

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; 

И вспомогательная функция:

CREATE FUNCTION levenshtein_ratio(s1 VARCHAR(255), s2 VARCHAR(255)) 
    RETURNS INT 
    DETERMINISTIC 
    BEGIN 
    DECLARE s1_len, s2_len, max_len INT; 
    SET s1_len = LENGTH(s1), s2_len = LENGTH(s2); 
    IF s1_len > s2_len THEN 
     SET max_len = s1_len; 
    ELSE 
     SET max_len = s2_len; 
    END IF; 
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2)/max_len) * 100); 
    END; 

, но я не знаю, почему эта причина ошибки You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near '' at line 5