Переставить слова в массиве в соответствии с позицией вычисления расстояния Левенштейна Php

Question

Перестановка слов в массиве на основе положения первого массива.В моем коде есть два массива, мой первый массив - это базовый массив, из которого я собираюсь сравнить его со вторым массивом и сделать позицию такой же, как и в первом массиве.

Рассмотрим 2 входа, считая 1 вход как базу iЯ применяю levenshtein (метафон (каждая база данных слов), метафон (каждое слово банка)), основываясь на том, что расположение слов банковских данных в новом массиве

databaseName = LAL BAHADUR SHASTRI bankdata = SHASTRI LAL исходный код будет только переставлять банковские данные исохраненный в новом массиве токовый вывод bankdata : LAL SHASTRI

Перестановка происходит правильно, просто нужно упорядочить слова в массиве

        $db = 'LAL BAHADUR SHASTRI YADAV';
        $bank = 'SHASTRI LAL';
        $a = reArrangeArray($db,$bank);

        function reArrangeArray($db,$bank)
        {
            $dataBaseName = $db;
            $bankdataRows = [$db,$bank,];
            $dbWords = preg_split("#[\s]+#", $dataBaseName);     
            foreach ($bankdataRows as $bankdata)
            {
            $bankWords = preg_split("#[\s]+#", trim($bankdata));
            $result    = [];    
            if(!empty($bankWords))
                foreach ($dbWords as $dbWord)
                {
                $idx   = null;
                $least = PHP_INT_MAX;
                foreach ($bankWords as $k => $bankWord)
                    if (($lv = levenshtein(metaphone($bankWord),metaphone($dbWord))) < $least)
                    {
                    $least = $lv;
                    $idx   = $k;
                    }
                @$result[] = $bankWords[$idx];
                unset($bankWords[$idx]);
                }
            $result = array_merge($result, $bankWords);
            var_dump($result);
            }
        }

Случай 1: ТЕКУЩИЙ ВЫХОД

        array (size=4)
        0 => string 'LAL' (length=3)
        1 => string 'BAHADUR' (length=7)
        2 => string 'SHASTRI' (length=7)
        3 => string 'YADAV' (length=5)

        array (size=4)
        0 => string 'LAL' (length=3)
        1 => string 'SHASTRI' (length=7)
        2 => null
        3 => null

Ожидаемый вывод

Мне нужно положение массива такое же, как и в databaseArray

        $dbName = 'LAL BAHADUR SHASTRI YADAV';
        $bankName = 'SHASTRI LAL';

        array of db (size=4)
        0 => string 'LAL' (length=3)
        1 => string 'BAHADUR' (length=7)
        2 => string 'SHASTRI' (length=7)
        3 => string 'YADAV' (length=5)

        array of bankname (size=4)
        0 => string 'LAL' (length=3)
        1 => #
        2 => string 'SHASTRI' (length=7)
        3 => ###

, если слово не найдено в первом массиве, его следует поместить с#, поскольку позиция равна 3, у которой нет соответствующего элемента, он имеет 3 #

        array (size=4)
        0 => string 'LAL' (length=3)
        1 => string 'BAHADUR' (length=7)
        2 => string 'SHASTRI' (length=7)
        3 => string 'YADAV' (length=5)

        array (size=4)
        0 => string 'LAL' (length=3)
        1 => string 'SHASTRI' (length=7)
        2 => null
        3 => null

Ожидаемый вывод

Мне нужна позиция массива, такая же, как databaseArray

        $dbName = 'LAL BAHADUR SHASTRI YADAV';
        $bankName = 'SHARI LAL';

        array of db (size=4)
        0 => string 'LAL' (length=3)
        1 => string 'BAHADUR' (length=7)
        2 => string 'SHASTRI' (length=7)
        3 => string 'YADAV' (length=5)

        array of bankname (size=4)
        0 => string 'LAL' (length=3)
        1 => #
        2 => string 'SHARI' (length=7)
        3 => ###

Этот случай будет рассчитываться на основе levenshtein(metaphone($bankWord),metaphone($dbWord))

Случай 2

Ввод:

$dbName = NikithaRani MohanRao $bankdata = Nikitha Rani Mohan Rao

Output : $newbankdata = NikithaRani MohanRao

Следует объединить слово, если оно найденообъединены в $ dbName

Примечание

Положение слова рассчитывается просто нужно сдвинуть слово в массиве путем сравнения первого массива

Answer 1

Я не уверен, что понимаю весь вопрос, но давайте попробуем решить только проблему перестановки массива:

$a1 = explode(" ", "LAL BAHADUR SHASTRI YADAV");
// sort $a1 to whatever order you need
$a2 = explode(" ", "SHASTRI LAL");

foreach($a1 as $key => $e) { // for each element set him or fill with "#"
    $res[$key] = in_array($e, $a2) ? $e : str_repeat("#", $key); 
}

str-repeat является дубликатом символа для x раз.Этот код работал в O(n*m) - его можно изменить на O(n) при необходимости (когда n - номер элемента в первом массиве).

Я надеюсь, что это помогает, а если нет, то можетекомментарий

Отредактировано:

Сначала определите функцию для нахождения минимального расстояния Левенштейна:

function foundLevenshteinMinIndex($word, $arr) {
    $word = metaphone($word);
    foreach ($arr as $k =>$e)
        $a[] = levenshtein($word,metaphone($e));
    return array_search(min($a), $a);
}

Теперь используется тот же $a1, $a2, что и:

foreach($a2 as $w) {
    $i = foundLevenshteinMinIndex($w, $a1);
    if (!isset($res[$i]) || (levenshtein(metaphone($a1[$i]), metaphone($res[$i])) > levenshtein(metaphone($a1[$i]), metaphone($w))))
        $res[$i] = $w;
}

for($i = 0; $i < count($a1); $i++) 
    if (!isset($res[$i])) // if not set in the index fill with "#'
        $res[$i] = str_repeat("#", $i);
// rearrange by int indexs
ksort($res);

Отредактировано 2

Посмотрите на эту реализацию:

$a1 = explode(" ", 'LAL BAHADUR SHASTRI YADAV');
$a2 = explode(" ",'SHASTRI LAL NABA');

function getDist($a1, $a2) {
    foreach($a2 as $k1 => $w1)
        foreach($a1 as $k2 => $w2)
            $arr[$k1][$k2] = levenshtein(metaphone($w1), metaphone($w2));
    return $arr;
}

function getMin($arr) {
    $min = PHP_INT_MAX;
    $minX = $minY = null;
    foreach($arr as $x => $row)
        foreach($row as $y => $cell)
            if ($cell < $min) {
                $min = $cell;
                $minX = $x;
                $minY = $y;
            }
    return array($minX, $minY);
}

function removeIndex($arr, $x, $y) {
    unset($arr[$x]);
    foreach($arr as &$row)
        unset($row[$y]);
    return $arr;
}

$arr = getDist($a1, $a2);
while (count($arr) && count(reset($arr))) {
    list($x, $y) = getMin($arr);
    if (!isset($res[$y]))
        $res[$y] = $a2[$x];
    $arr = removeIndex($arr, $x, $y);
}

for($i = 0; $i < count($a1); $i++)
    if (!isset($res[$i])) // if not set in the index fill with "#'
        $res[$i] = str_repeat("#", $i);
ksort($res);

Обратите внимание, что этот код имеет временную сложность O(n*(m^2)) при n это первый массив, m - второй