php - 确定两个名称是否彼此接近

Question

我正在为我的学校建立一个系统，在那里我们可以在聚会和其他活动中检查学生是否被列入黑名单。我很容易检查一个学生是否被列入黑名单，因为我可以在我的数据库中查找这个学生，看看他/她是否被列入黑名单。
但这是困难的地方。
在我们的聚会上，每个学生可以邀请一个人。理论上，黑名单的学生可以被另一个学生邀请而绕过系统。
我无法查看黑名单学生的客人桌，因为在您邀请客人时只提供姓名。
所以我需要检查一个黑名单上的名字是否和一个客人的名字很接近，如果他们很接近，我会显示一个警告，不幸的是，有一些东西需要考虑。
名字可能完全不同。在丹麦，标准名称包含三个“名称”，如“niels faurskov andersen”
但学生可能只需输入“尼尔斯·福斯科夫”或“尼尔斯·安德森”，甚至删除一些字符。
所以像尼尔斯·福斯科夫·安徒生这样的全名
安徒生
尼尔斯·福斯科夫
安徒生
安徒生
安德森
尼尔斯·福斯科夫
尼尔斯·福斯科夫
等等…
另一件事是丹麦字母表除了通常的a-z之外还包含“__”，因此整个站点和数据库都是utf-8编码的。
我研究了各种方法来检查两个字符串之间的差异，而levenshtein距离并不能完全做到这一点。
我在stackoverflow上找到这个线程：Getting the closest string match
似乎提供了正确的数据，
但是我不太确定选择什么方法
我用php编写这部分代码，有人知道怎么做吗？也许用MySQL？或者是Levenshtein距离的修正版？regex有可能吗？

Answer 1

介绍
现在你的条件可能太宽泛了。但是，你可以使用levenshtein距离来检查你的单词。用它来实现所有期望的目标可能不太容易，比如听起来很相似。因此，我建议把你的问题分成其他问题。
例如，您可以创建一些自定义检查器，它将使用传递的可调用输入，该输入接受两个字符串，然后回答关于它们是否相同的问题（对于levenshtein将小于某个值的距离，对于similar_text-相似性的某个百分比，则由您定义规则）。
相似性，基于单词
好吧，如果我们在寻找部分匹配时讨论case，那么所有的内置函数都将失败，特别是在涉及非有序匹配时。因此，您需要创建更复杂的比较工具。你有：
数据字符串（例如，以db为单位）。看起来d=d0 d1 d2…DN
搜索字符串（将是用户输入）。看起来S=s0 s1…钐
在这里，空间符号意味着任何空间（我假设空间符号不会影响相似性）。也n > m。有了这个定义，您的问题是-在m中找到一组类似于D的S单词。我指的是任何无序的序列。因此，如果我们在set中发现任何这样的序列，那么D与S类似。
显然，如果D则输入包含的单词多于数据字符串。在这种情况下，您可能会认为它们与上面的不相似或类似，但会切换数据和输入（不过，这看起来有点奇怪，但在某种意义上是适用的）
实施
要完成这些工作，您需要能够创建一组字符串，这些字符串是n < m单词m的一部分。根据我的this question你可以用以下方法来完成：

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;
}

-因此，对于任何数组， D都将返回由每个 getAssoc()项组成的无序选择数组。
下一步是关于生产选择的顺序。我们应该在 m字符串中同时搜索 Niels Andersen和 Andersen Niels。因此，您需要能够为数组创建置换。这是很常见的问题，但我也会把我的版本放在这里：

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;
}

在此之后，您将能够创建 D单词的选择，然后对每个单词进行排列，得到所有变量，以便与搜索字符串 m进行比较。每次比较都将通过一些回调来完成，比如 S。这是样品：

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;
}

这将基于用户回调检查相似度，用户回调必须至少接受两个参数（即比较的字符串）。另外，您可能希望返回触发回调正返回的字符串。请注意，这段代码的大小写没有区别，但可能是您不希望这样的行为（然后只替换 levenshtein）。
完整代码的示例可以在 this listing中找到（我没有使用sandbox，因为我不确定代码列表在那里有多长时间可用）。使用此用法示例：

$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'
      )
   );

}

结果如下：
测试“尼尔斯·福斯科夫·安德森”
“尼尔斯·安徒生”与“尼尔斯·安徒生”匹配
“尼尔斯·福斯科夫”这个名字和“尼尔斯·福斯科夫”是一对。
“尼尔斯·福斯科夫·安徒生”与“尼尔斯·福斯科夫·安徒生”匹配
“尼尔斯·福斯科夫·安徒生”与“尼尔斯·福斯科夫·安徒生”匹配
“nils andersen”与“niels andersen”匹配
“尼尔斯·福斯科夫”这个名字和“尼尔斯·福斯科夫”是一对。
“尼尔斯·福斯科夫”这个名字和“尼尔斯·福斯科夫”是一对。
名称“niffdels faurskovffre”不匹配
- here是这段代码的演示，以防万一。
复杂性
因为您关心的不仅仅是任何方法，而且还关心它有多好，您可能会注意到，这样的代码将产生相当多的操作。我是说，至少，弦部分的产生。这里的复杂性包括两部分：
字符串部分生成部分。如果你想生成所有的字符串部分-你必须像我上面描述的那样做。改进无序字符串集生成的可能点（在置换之前）。但我仍然怀疑它是否可以做到，因为在提供的代码中的方法不会用“暴力”生成它们，而是用数学计算（基数为）
相似性检查部分。这里的复杂性取决于给定的相似性检查器。例如， strtolower()具有o（n3）复杂性，因此对于大型比较集，它将非常慢。
但您仍然可以通过动态检查来改进当前的解决方案。现在这段代码将首先生成所有字符串子序列，然后开始逐个检查它们。在一般情况下，您不需要这样做，所以您可能希望将其替换为行为，在生成下一个序列后，将立即检查它。然后，您将提高具有肯定答案的字符串的性能（但不适用于没有匹配的字符串）。