1

所以,

问题

第一个案例

我有一个包含一些值的数组 - 首先,让它们都是字符串(或者可以简单地视为字符串)。例子:

$rgData = ['foo', 'feo', 'bar', 'baz', 'bee'];

现在,我想从中创建唯一的数组,其中两个项目之间的Levenshtein 距离小于 2。即项目$x$y被视为相等 if levenshtein($x, $y) < 2。例如,fooandfeo是相等的,and also barand baz- 但不是barand bee

第二种情况

我有一个数组,[x, y]每个点都有坐标,例如:

$rgData = [[0, 0.1], [-5, 4.5], [0, 0.5], [-5.5, 4.5]];

现在,我想从中创建唯一的数组,其中两点之间的距离小于 1。即点$x$y被视为相等,如果pow((pow($x[0]-$y[0], 2) + pow($x[1]-$y[1],2)), 0.5)<1

很明显,这两种情况都可以通过一些函数来解决,这将类似于标准的 PHP array_unique() - 但它接受比较函数来检查项目是否相等。我的问题是关于那个功能。

我的方法

现在,我有最简单的功能解决方案:

function array_uunique($rgData, $fnCompare=null)
{
    if(!isset($fnCompare))
    {
        return array_unique($rgData);
    }
    if(!is_callable($fnCompare))
    {
        return null;
    }
    if(!count($rgData))
    {
        return array();
    }
    $rgResult = array();
    foreach($rgData as $mItem)
    {
        foreach($rgResult as $mTest)
        {
           if(!call_user_func_array($fnCompare, [$mItem, $mTest]))
           {
              continue 2;
           }
        }
        $rgResult[]=$mItem;
    }
    return $rgResult;
}

- 它接受回调作为第二个参数,并返回不等于此比较规则的元素,即对于 levenshtein,所描述的结果将是:

$rgResult = array_uunique(['foo', 'feo', 'bar', 'baz', 'bee'], function($x, $y)
{
   return levenshtein($x, $y)>1; //or !levenshtein($x, $y)<2
});

- 这将导致

数组(3){
  [0]=>
  字符串(3)“富”
  [1]=>
  字符串(3)“酒吧”
  [2]=>
  字符串(3)“蜜蜂”
}

- 你可以用这个小提琴来测试它。

细节

如上所述,这是最简单的方法,但它内部包含 2 个嵌套的依赖循环。因此,这种构造的复杂性将是O(N^2)- 这很可悲 - 并且对我不起作用,特别是如果比较函数操作成本很高 - 因为我将在数据数组中有大量元素(至少〜1E5..1E6) .

我的问题是 - 如何改善这一点?可能还有另一种好的算法吗?或者可能是我的代码可以以某种方式改进?

更新(基于下面的好评论):我知道在常见情况下,这样的问题会导致传递函数问题,即xFy = yFz => xFz- 例如,levenshtein()不是传递的。因此,在常见情况下,整个结果将至少取决于项目顺序(但不仅来自它)- 现在这对我来说不是问题,因为我确定我的数据顺序和内容(或者,至少,它是与是否barbaz将通过levenshtein比较返回无关)。所以,我的目标是尽量减少比较次数(我认为比较函数是否传递或没有改变什么,因为我想优化甚至重新创建比较算法本身)

4

1 回答 1

1

输入集 = {a,b,c,...} 矩阵,

   a b c . . .
a  1
b  1 1
C  0 0 1
.        1
.          1
.            1

如果两个元素在同一组中,则为 1,对角线具有反射特性,计算 olny 下三角形具有对称特性。在第 n 行,如果找到匹配项,则开始与 cols 进行比较,放入 1,然后删除第 n 个 col,形成进一步的比较。我希望这是可以理解的。

最坏的情况:如果每个组都有一个元素。

于 2013-09-16T18:15:46.997 回答