Как найти точное или наиболее близкое совпадение из большого массива в большой строке?

Question

Учтите следующее. У меня очень большой массив со всеми названиями дорог в данной стране, упорядоченный по длине строки, например:

$roadNames = ['Ivy Lane','East Road','The Maltings','Greenhill Road', 'Woodlands Close']; //And many, many more

Теперь я хочу найти точное совпадение в длинной строке

$string = "
..... ALOT OF TEXT ..... 
..... ALOT OF TEXT ..... 

You can find us at: Greenhill Road 1, 11111, The City 

..... ALOT OF TEXT .....
..... ALOT OF TEXT ..... 
";

Найти точное совпадение довольно просто, я просто делаю следующее:

foreach ($roadNames as $roadName) {
    if(stripos($string, $roadName) !== false){
        echo 'Exact match: '.$roadName;
        break;
    }
}

Но что, если название дороги написано с ошибкой в ​​одной букве, fx. лишний пробел / пробел отсутствует, буква меньше / больше, или 1 буква неверна. Fx. «Гринхил-роуд», «Гринхилл-роуд», «Гринхилл-роад», «Грин-хилл-роуд», «Кринхилл-роуд»? Как теперь я могу найти наилучшее совпадение всех моих названий дорог в массиве, если имя дороги в $ string было одним из примеров? Есть ли математический способ сделать это? Или, может быть, я могу купить регулярное выражение?

Я думаю, что-то вроде этого, хотя это кажется излишним (и не работает)

<code>foreach ($roadNames as $roadName) {
    if (stripos($string, $roadName)) {
        echo 'Exact match: ' . $roadName;
        break;
    } else {
        $alphabet = range('a', 'z');
        $alphabet[] = ' ';
        $roadName_split = str_split($roadName);
        $test_array = array();
        foreach ($roadName_split as $strpos => $letter) {
            foreach ($alphabet as $letter_in_alphabet) {
                $test_array[] = $letter_in_alphabet;
            }
            foreach ($test_array as $key => $value) {
                $test_array[$key] .= substr($roadName, $strpos, 1);
            }
        }
        echo '<pre>';
        print_r($test_array);
        echo '

'; умереть; foreach ($ test_array as $ misplled_value) {if (stripos ($ string, $ misplled_value)) {echo 'найдено близкое соответствие:'. $ RoadName; перемена; }} // ИЛИ Что-то вроде регулярного выражения, не знаю, как это должно быть // $ roadName_split = str_split ($ roadName); // $ re = ''; // foreach ($ roadName_split as $ strpos => $ letter) {// $ re. = "$ letter?"; //}}}

Answer 1

Я наконец-то нашел решение с вдохновением от: { ссылка }

Я делаю регулярное выражение для каждого roadName, позволяя ввести одну букву с ошибкой, одну букву или пробел, слишком короткую или слишком много, с помощью этой функции:

function generateRegex($word) {
    $len = strlen($word);
    $regex = "/(($word)";
    $word_split = str_split($word);
    foreach ($word_split as $strpos => $letter) {
        $temp = $word;
        $temp[$strpos - 1] = '.';
        if ($strpos === 0) {
            $temp1 = substr($word, ($strpos + 1));
            $temp2 = '.' . substr($word, $strpos);
        } else {
            $temp1 = substr($word, 0, $strpos) . substr($word, ($strpos + 1));
            $temp2 = substr($word, 0, $strpos) . '.' . substr($word, $strpos);
        }
        $regex .= "|($temp)";
        $regex .= "|($temp1)";
        $regex .= "|($temp2)";
    }
    $regex = $regex . ")/mi";
    return $regex;
}

1. $ temp заботится о 1 букве с ошибкой (например, Creenhill Road) и заменяет 1 букву точкой, столько раз, сколько возможно
2. $ temp1 обрабатывает 1 букву / пробел слишком коротко (например, Grenhill Road ИЛИ GreenhillRoad) и удаляет 1 букву столько раз, сколько возможно
3. $ temp2 слишком много заботится о 1 букве / пробел (Например, Грин-Хилл-Роуд ИЛИ Гриннхилл-Роуд) и добавляем точку к каждой букве столько раз, сколько это возможно

Таким образом, окончательный сценарий выглядит следующим образом:

function generateRegex($word) {
    $len = strlen($word);
    $regex = "/(($word)";
    $word_split = str_split($word);
    foreach ($word_split as $strpos => $letter) {
        $temp = $word;
        $temp[$strpos - 1] = '.';
        if ($strpos === 0) {
            $temp1 = substr($word, ($strpos + 1));
            $temp2 = '.' . substr($word, $strpos);
        } else {
            $temp1 = substr($word, 0, $strpos) . substr($word, ($strpos + 1));
            $temp2 = substr($word, 0, $strpos) . '.' . substr($word, $strpos);
        }
        $regex .= "|($temp)";
        $regex .= "|($temp1)";
        $regex .= "|($temp2)";
    }
    $regex = $regex . ")/mi";
    return $regex;
}

function findBestMatch($roadNames, $string) {
    foreach ($roadNames as $roadName) {
        if (stripos($string, $roadName)) {
            $return = 'Exact match found: ' . $roadName;
            break;
        } else {
            $re = generateRegex($roadName);
            if (preg_match($re, $string)) {
                $return = 'Close match found: ' . $roadName;
                break;
            }
        }
    }
    if (!isset($return) OR empty($return)) {
        return 'Match not found';
    } else {
        return $return;
    }
}

$roadNames = ['Greenhill Road', 'Ivy Lane', 'East Road', 'The Maltings', 'Woodlands Close']; //And many, many more
$misspelled_examples = ['Greenhill Road', 'Crennhill Road', 'Green hill Road', 'Greennhill Road', 'GreenhillRoad', 'Grenhill Road', 'GrenhilRoad'];

foreach ($misspelled_examples as $value) {
    $strings[] = "
..... ALOT OF TEXT ..... 
..... ALOT OF TEXT ..... 

You can find us at: $value 1, 11111, The City 

..... ALOT OF TEXT .....
..... ALOT OF TEXT ..... 
";
}

foreach ($strings as $key => $string) {
    echo 'Input road-name: ' . $misspelled_examples[$key];
    echo '<br>';
    echo findBestMatch($roadNames, $string);
    echo '<hr>';
}