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

Question

我正在为我的学校制作一个系统,我们可以检查学生是否入围黑人,参加派对和其他活动.我很容易检查学生是否被列入黑名单,因为我可以在我的数据库中查看学生并查看他/她是否列入黑名单.

这是困难的地方.

在我们的聚会上,每个学生都可以邀请一个人.理论上,黑名单的学生可以被另一名学生邀请并绕过该系统.我无法查看黑名单上的学生的客人表,因为当您邀请客人时只提供姓名.

因此,我需要检查列入黑名单的名称是否接近访客姓名,如果它们已经关闭则显示警告,遗憾的是有些内容需要考虑.

名字可能完全不同.在丹麦,标准名称包含三个"名字",如"Niels Faurskov Andersen"但学生可能只需键入"Niels Faurskov"或"Niels Andersen",甚至可以删除一些字符.

所以像Niels Faurskov Andersen这样的全名可能是

• 尼尔斯安徒生
• Niels Faurskov
• Niels Faurskov Andersen
• Nils Faurskov Andersen
• 尼尔斯安徒生
• 尼尔斯福斯科夫
• 尼尔斯福斯科夫

等等...

另一件事是丹麦字母除了通常的az之外还包含"æøå".据说,整个站点和数据库都是UTF-8编码的.

我已经研究了各种方法来检查两个字符串之间的区别,而Levenshtein距离并没有完全发挥作用.

我在StackOverflow上找到了这个线程:获得最接近的字符串匹配

这似乎提供了正确的数据,但我不太确定选择哪种方法

我在php编写这部分代码,是否有人知道如何做到这一点？也许与MySQL？或Levenshtein距离的修改版本？正则表达式可以吗？

Answer 1

介绍

现在您的匹配条件可能过于宽泛.但是,您可以使用levenshtein距离来检查您的单词.用它来实现所有期望的目标可能不太容易,例如声音相似性.因此,我建议将您的问题分成其他一些问题.

例如,你可以创建一些自定义检查器,它将使用传递的可调用输入,它接受两个字符串然后回答问题是否相同(因为levenshtein距离小于某个值,因为similar_text- 相似性的某些百分比 - 它取决于你定义规则).

相似性,基于单词

好吧,如果我们在寻找部分匹配的情况下讨论案例,所有内置函数都将失败 - 特别是如果它是关于非有序匹配的话.因此,您需要创建更复杂的比较工具.你有:

• 数据字符串(例如,将在DB中).它看起来像D = D ₀ D ₁ D ₂ ... D _n
• 搜索字符串(将是用户输入).它看起来像S = S ₀ S ₁ ... S _m

这里空间符号仅表示任何空间(我假设空间符号不会影响相似性).还有n > m.根据这个定义,您的问题是 - 找到与之类似的m单词集.通过我的意思是任何无序顺序.因此,如果我们发现任何这样的序列中,那么类似.DSsetDSD

显然,如果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 ³)复杂度,因此对于大的比较集,它将非常慢.

但您仍然可以通过即时检查来改进当前的解决方案.现在,此代码将首先生成所有字符串子序列,然后逐个开始检查它们.在通常情况下,您不需要这样做,因此您可能希望将其替换为行为,在生成下一个序列后,将立即检查它.然后,您将提高具有肯定答案的字符串的性能(但不会针对那些没有匹配的字符串).