将数组中的单词重新排列到匹配位置计算 Levenshtein 距离 Php

Question

根据第一个数组的位置重新排列数组中的单词。在我的代码中有两个数组，我的第一个数组是基础数组，我将从中将它与第二个数组进行比较，并使位置与第一个数组相同。

通过将 1 个输入作为基础来考虑 2 个输入新数组中的银行数据

databaseName = LAL BAHADUR SHASTRI bankdata = SHASTRI LAL 源代码只会重新排列 bankdata 并存储在 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))

计算

案例二

输入：

$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 是第一个数组中的元素数时）。

希望对您有所帮助，如有不便，请随时发表评论

已编辑：

首先定义寻找 Levenshtein 最小距离的函数：

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 是第二个数组

将数组中的单词重新排列到匹配位置计算 Levenshtein 距离 Php

Rearrange words in array to matching position calculating Levenshtein distance Php

php

arrays

sorting

fuzzywuzzy