Введение

Теперь ваши условия соответствия могут быть слишком широкими. Однако вы можете использовать расстояние Левенштейна, чтобы проверить свои слова. С его помощью может быть не слишком легко достичь всех желаемых целей, таких как звуковое сходство. Таким образом, я предлагаю разделить вашу проблему на несколько других вопросов.

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

Сходство, основанное на словах

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

• Строка данных (которая будет находиться, например, в БД). Это выглядит как D= D₀ D₁ D₂ ... D_n
• Строка поиска (это будет ввод пользователем). Это выглядит как S = S₀ С₁ ... S_м

Здесь символы пробела означают просто любое пространство (я предполагаю, что символы пробела не повлияют на сходство). Также n > m. С этим определением ваша проблема заключается в том, чтобы найти набор слов m в D, которые будут похожи на S. По set Я имею в виду любую неупорядоченную последовательность. Следовательно, если мы найдем любая такая последовательность в D, то S аналогична D.

Очевидно, что если n < m, то ввод содержит больше слов, чем строка данных. В этом случае вы можете либо подумать, что они не похожи, либо действовать так, как описано выше, но переключать данные и ввод (что, однако, выглядит немного странно, но в некотором смысле применимо)

Реализация

Чтобы сделать это, вам нужно будет иметь возможность создавать набор строк, которые являются частями m слов из D. Основываясь на моем этом вопросе, вы можете сделать это с помощью:

protected function nextAssoc($assoc)
{
   if(false !== ($pos = strrpos($assoc, '01')))
   {
      $assoc[$pos]   = '1';
      $assoc[$pos+1] = '0';
      return substr($assoc, 0, $pos+2).
             str_repeat('0', substr_count(substr($assoc, $pos+2), '0')).
             str_repeat('1', substr_count(substr($assoc, $pos+2), '1'));
   }
   return false;
}

protected function getAssoc(array $data, $count=2)
{
   if(count($data)<$count)
   {
      return null;
   }
   $assoc   = str_repeat('0', count($data)-$count).str_repeat('1', $count);
   $result = [];
   do
   {
      $result[]=array_intersect_key($data, array_filter(str_split($assoc)));
   }
   while($assoc=$this->nextAssoc($assoc));
   return $result;
}

- таким образом, для любого массива getAssoc() вернет массив неупорядоченных выборок, состоящий из m элементов каждый.

Следующий шаг касается порядка в произведенном выборе. Мы должны искать как Niels Andersen, так и Andersen Niels в нашей строке D. Поэтому вам нужно будет иметь возможность создавать перестановки для массива. Это очень распространенная проблема, но я тоже выложу свою версию здесь:

protected function getPermutations(array $input)
{
   if(count($input)==1)
   {
      return [$input];
   }
   $result = [];
   foreach($input as $key=>$element)
   {
      foreach($this->getPermutations(array_diff_key($input, [$key=>0])) as $subarray)
      {
         $result[] = array_merge([$element], $subarray);
      }
   }
   return $result;
}

После этого вы сможете создавать выбор слов m, а затем, переставляя каждое из них, получите все варианты для сравнения со строкой поиска S. Это сравнение каждый раз будет выполняться с помощью некоторого обратного вызова, такого как levenshtein. Вот пример:

public function checkMatch($search, callable $checker=null, array $args=[], $return=false)
{
   $data   = preg_split('/\s+/', strtolower($this->data), -1, PREG_SPLIT_NO_EMPTY);
   $search = trim(preg_replace('/\s+/', ' ', strtolower($search)));
   foreach($this->getAssoc($data, substr_count($search, ' ')+1) as $assoc)
   {
       foreach($this->getPermutations($assoc) as $ordered)
       {
           $ordered = join(' ', $ordered);
           $result  = call_user_func_array($checker, array_merge([$ordered, $search], $args));
           if($result<=$this->distance)
           {
               return $return?$ordered:true;
           }
       }
   }

   return $return?null:false;
}

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

Пример полного кода доступен в этом списке (я не использовал песочницу, так как не уверен, как долго там будет доступен список кода). С этим примером использования:

$data   = 'Niels Faurskov Andersen';
$search = [
    'Niels Andersen',
    'Niels Faurskov',
    'Niels Faurskov Andersen',
    'Nils Faurskov Andersen',
    'Nils Andersen',
    'niels faurskov',
    'niels Faurskov',
    'niffddels Faurskovffre'//I've added this crap
];

$checker = new Similarity($data, 2);

echo(sprintf('Testing "%s"'.PHP_EOL.PHP_EOL, $data));
foreach($search as $name)
{
   echo(sprintf(
      'Name "%s" has %s'.PHP_EOL, 
      $name, 
      ($result=$checker->checkMatch($name, 'levenshtein', [], 1))
         ?sprintf('matched with "%s"', $result)
         :'mismatched'
      )
   );

}

Вы получите результат, подобный:

Testing "Niels Faurskov Andersen"

Name "Niels Andersen" has matched with "niels andersen"
Name "Niels Faurskov" has matched with "niels faurskov"
Name "Niels Faurskov Andersen" has matched with "niels faurskov andersen"
Name "Nils Faurskov Andersen" has matched with "niels faurskov andersen"
Name "Nils Andersen" has matched with "niels andersen"
Name "niels faurskov" has matched with "niels faurskov"
Name "niels Faurskov" has matched with "niels faurskov"
Name "niffddels Faurskovffre" has mismatched

- вот демонстрация этого кода, на всякий случай.

Сложность

Поскольку вы заботитесь не только о каких-либо методах, но и о том, насколько это хорошо, вы можете заметить, что такой код будет производить довольно избыточные операции. Я имею в виду, по крайней мере, генерацию струнных частей. Сложность здесь состоит из двух частей:

• Часть генерации частей строк. Если вы хотите сгенерировать все строковые части - вам придется сделать это так, как я описал выше. Возможный пункт для улучшения - генерация неупорядоченных наборов строк (это происходит до перестановки). Но все же я сомневаюсь, что это можно сделать, потому что метод в предоставленном коде будет генерируйте их не "грубой силой", а так, как они математически рассчитаны (с мощностью )
• Часть проверки сходства. Здесь ваша сложность зависит от заданной проверки сходства. Например, similar_text() имеет O(N³) сложность, поэтому при больших наборах сравнения это будет чрезвычайно медленно.

Но вы все еще можете улучшить текущее решение с помощью проверки на лету. Теперь этот код сначала сгенерирует все строковые подпоследовательности, а затем начнет проверяя их одного за другим. В общем случае вам не нужно этого делать, поэтому вы можете заменить это поведением, когда после генерации следующей последовательности оно будет немедленно проверено. Затем вы увеличите производительность для строк с положительным ответом (но не для тех, у которых нет совпадения).