Переставить слова, используя расстояние Левенштейна - PullRequest
Новая
       28

Переставить слова, используя расстояние Левенштейна

0 голосов
/ 19 января 2019

Резюме

Я пытаюсь найти процент совпадения имен в php, но перед этим мне нужно переставить слова в строке в соответствии с 1-й строкой.

О чем исходный код?

У меня есть две строки.Сначала я добавляю обе строки в массив, если в строке найдено пространство, добавляю его в массив.$ arraydataBaseName и $ arraybankData из моего первого массива, т.е. $ arraydataBaseName. Я ищу все значения $ arraybankData и получаю ключ.Я получаю правильное расположение клавиш, но не могу расположить значение в определенных местах в новом массиве. 

$dataBaseName = "Jardine Lloyd Thompson";
$bankdata = "Thompson Thompson Jardine"; 

$replacedataBaseName = preg_replace("#[\s]+#", " ", $dataBaseName);
$replacebankData = preg_replace("#[\s]+#", " ", $bankdata); 

$arraydataBaseName = explode(" ",$replacedataBaseName);
$arraybankData = explode(" ",$replacebankData); 

echo "<br/>";
print_r($arraydataBaseName);

$a="";
$i="";
$arraysize =  count($arraydataBaseName);

$push=array();
for($i=0;$i< $arraysize;$i++)
{     
  if(array_search($arraybankData[$i],$arraydataBaseName)>0)
  {
    ${"$a$i"} =  array_search($arraybankData[$i],$arraydataBaseName); 
    //echo ${"$a$i"};
    array_push($push,${"$a$i"});
   }    
 }
 print_r($push);

Случай 1:

Ввод

DatabaseName = Jardine Lloyd Thompson

BankName = Thompson Jardine Lloyd

Выход

Ожидаемый выход = Jardine Lloyd Thompson

Случай 2: ##

Ввод

DatabaseName = Jardine Lloyd Thompson

BankName = Thoapson Jordine Llayd

Если слова не найденыв указанном выше имени_базы_данных ожидаемый поиск будет основываться на слованском алгоритмическом слове с меньшим расстоянием, которое будет рассматриваться как ключ

Выход

ExpectedOutput = Джордин Ллэйд Тоапсон

Описание проблемы

Обновление вопроса

Когда пользовательский ввод $bankdata содержит больше слов, оставшихся несопоставимыми, мне нужно добавить их в конец.

Ответы [ 2 ]

0 голосов
/ 19 января 2019

Это простая версия, которая последовательно находит слово за словом для наилучшего соответствия. 

declare (strict_types=1);

$dataBaseName = 'Jardine Lloyd Thompson';

$bankdataRows =
[
  'Thompson Jardine Lloyd',
  'Blaaa  Llayd Thoapson   f***ing user input   Jordine   aso. ',
];

// assume the "database" is already stored trimmed since it is server-side controlled
$dbWords = preg_split("#[\s]+#", $dataBaseName);

foreach ($bankdataRows as $bankdata)
{
  // here we trim the data received from client-side.
  $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($bankWord, $dbWord)) < $least)
        {
          $least = $lv;
          $idx   = $k;
        }

      $result[] = $bankWords[$idx];
      unset($bankWords[$idx]);
    }

  $result = array_merge($result, $bankWords);
  var_dump($result);
}

результат 

array(3) {
  [0] =>
  string(7) "Jardine"
  [1] =>
  string(5) "Lloyd"
  [2] =>
  string(8) "Thompson"
}

array(8) {
  [0] =>
  string(7) "Jordine"
  [1] =>
  string(5) "Llayd"
  [2] =>
  string(8) "Thoapson"
  [3] =>
  string(5) "Blaaa"
  [4] =>
  string(7) "f***ing"
  [5] =>
  string(4) "user"
  [6] =>
  string(5) "input"
  [7] =>
  string(4) "aso."
}

См. Живую скрипку

Возможно, вы захотите расширить этот подход, сначала вычислив расстояние Левенштейна для каждой возможной комбинации, а затем выберите наилучшее полное совпадение.

0 голосов
/ 19 января 2019

Я разбил код в случаях 1 и 2.
Но, очевидно, если var_export имеет значение false, вы делаете код случая 2 с теми же переменными. 

//Case 1:
$DatabaseName = "Jardine Lloyd Thompson";
$BankName = "Thompson Jardine Lloyd";

//Split and sort them
$data = explode(" ", $DatabaseName);
$bank = explode(" ", $BankName);
sort($data);
sort($bank);
Var_export(($data == $bank)); //true

//Case 2
$DatabaseName = "Jardine Lloyd Thompson";
$BankName = "Thoapson Jordine Llayd";

//Split and sort
$data = explode(" ", $DatabaseName);
$bank = explode(" ", $BankName);
sort($data);
sort($bank);

// Loop and accumulate the levenshtein return
$lev = 0;
foreach($data as $key => $name){
    $lev += levenshtein($name, $bank[$key]);
}

echo PHP_EOL . $lev; // 3 letters "off"

https://3v4l.org/eP5PE

Пример случаев 1 и 2 в одном коде.

$DatabaseName = "Jardine Lloyd Thompson";
$BankName = "Thoapson Jordine Llayd";

$data = explode(" ", $DatabaseName);
$bank = explode(" ", $BankName);
sort($data);
sort($bank);
if($data == $bank){
    echo "true";
    exit;
    // No need to do levenshtein
}

$lev = 0;
foreach($data as $key => $name){
    $lev += levenshtein($name, $bank[$key]);
}

echo PHP_EOL . $lev;

https://3v4l.org/RJSiB

...