如何将数组中的行与掩码数组匹配？

Question

如何将数组中的行与掩码数组匹配？

4

我有一个类似这样的数组：array('1224*','543*','321*' ...)，包含大约17,00个"掩码"或前缀。
我还有一个数组：array('123456789','123456788','987654321' ....)，包含大约250,000个数字。
现在，我如何高效地使用掩码/前缀数组匹配第二个数组中的每个数字？
[编辑]
第一个数组仅包含前缀，并且每个条目结尾只有一个*。

- canni

也许在这种情况下使用 Trie 数据结构会很有效。 - mfonda

@mfonda，我的英语不太好，我不明白应该使用什么。 - canni

请见http://en.wikipedia.org/wiki/Trie - mfonda

1

17k个口罩，250k个数字。用数组吗？你不觉得用不同于PHP的编程语言甚至是数据库处理会更好吗？我无法想象无论你如何使用PHP，它都无法快速完成此任务。 - Berry Langerak

最大的掩码有6个字符（不包括“*”），所有数字都是9个字符长。 - canni

显示剩余2条评论

5个回答

2

我个人认为....

$s = array('1234*', '543*', '321*');
$f = array('123456789', '123456788', '987654321');

foreach ($f as $haystack) {
    echo $haystack."<br>";
    foreach ($s as $needle) {
        $needle = str_replace("*","",$needle);
        echo $haystack "- ".$needle.": ".startsWith($haystack, $needle)."<br>";
    }
}

function startsWith($haystack, $needle) {
    $length = strlen($needle);
    return (substr($haystack, 0, $length) === $needle);
}

为了提高性能，最好先对两个数组进行排序，并在内部的foreach循环中添加退出条件。

顺便说一下，startWith函数来自于这个很棒的SO解决方案：PHP中的startsWith()和endsWith()函数。

- Bjoern

这是一个不错的初始实现，但 startsWith 方法会变得非常慢，将使其成为一个 O(k*n*n) 的算法。 - orlp

我完全同意你的观点。显然有很多方法可以优化这个问题，也有几种不同的解决方案。我只是想展示一个针对当前问题的基本方法。 - Bjoern

0

另一个选项是在循环中使用 preg_grep：

$masks = array('1224*', '543*', '321*' ...);
$data = array('123456789', '123456788', '987654321' ....);

$matches = array();
foreach($masks as $mask) {
    $mask = substr($mask, 0, strlen($masks) - 2); // strip off trailing *
    $matches[$mask] = preg_grep("/^$mask/", $data);
}

不知道这种方法的效率如何，只是提供它作为一种替代方案。

- Marc B

0

尽管正则表达式并不以“快速”而闻名，但我想知道如果将模式简化到最简形式并仅调用一次（不在循环中），preg_grep()能够表现得有多好。

通过删除被较短掩码覆盖的较长掩码，可以大大减少模式。这种减少会有多少呢？当然，我不能确定，但是有17,000个掩码，肯定会有相当数量的冗余。

代码：（演示）

$masks = ['1224*', '543*', '321*', '12245*', '5*', '122488*'];
sort($masks);
$needle = rtrim(array_shift($masks), '*');
$keep[] = $needle;
foreach ($masks as $mask) {
    if (strpos($mask, $needle) !== 0) {
        $needle = rtrim($mask, '*');
        $keep[] = $needle;
    }
}
// now $keep only contains: ['1224', '321', '5']

$numbers = ['122456789', '123456788', '321876543234567', '55555555555555555', '987654321'];

var_export(
    preg_grep('~^(?:' . implode('|', $keep) . ')~', $numbers)
);

输出：

array (
  0 => '122456789',
  2 => '321876543234567',
  3 => '55555555555555555',
)

- mickmackusa

-1

请看一下 PHP 函数 array_intersect_key。

- Tito

3

我认为你误解了问题。 - canni

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- orlp · Accepted Answer

好的，这里有一个解决方案：

预备步骤：

对数组1进行排序，去掉 *。

搜索：

对于数组2中的每个数字，执行以下操作：
1. 查找第一个和最后一个与 number 的第一个字符匹配的数组1条目（二分查找）。
2. 对于第二个字符，执行相同的操作，但是这次在 first 和 last 之间搜索而不是整个数组（二分查找）。
3. 重复步骤2，直到找到一个字符串。

这应该是 O(k*n*log(n))，其中 n 是平均数长度（以位数表示），k 是数字的数量。

基本上这是一个一维的基数树，为了实现最优性能，您应该实现它，但这可能很困难。