如何匹配阵列行口罩的阵列

我有这样的数组：如何匹配阵列行口罩的阵列

array('1224*', '543*', '321*' ...)巫包含17K“面具”或前缀

和第二阵列：

array('123456789', '123456788', '987654321' ....)巫包含有关250k数字。

现在我怎么能有效地匹配每个数字形式的第二个数组，以掩盖/前缀从数组1？

[编辑]

ARRAY1仅包含前缀，每个条目仅具有一个*在它的结束。

来源

2011-09-20 canni

也许在这种情况下使用trie可能会很好。 – mfonda

@mfonda我的英语不太好，我不明白我能用/应该用什么？ – canni

请参阅http://en.wikipedia.org/wiki/Trie – mfonda

那么，这里的一个解决方案：

Prelimary步骤：

排序阵列1中，切断*的。

搜索：

对于阵列2的每个数字做
1. 查找阵列1中的第一和最后一个条目，其中所述第一字符匹配number（二进制搜索）的这一点。
2. 对第二个字符做同样的事情，这次不是搜索整个数组，而是搜索first和last（二分搜索）。
3. 对第n个字符重复2，直到找到字符串。

这应该是O(k*n*log(n))其中n是平均数长度（位数）和k号的数目。

基本上这是一个一维Radix tree，以获得最佳性能，应实现它，但它可以是挺难的。

来源

2011-09-20 14:15:46 orlp

二进制搜索可能是一个非常好的主意indead :)但它会处理掩码可以从2到6个字符长的情况吗？（测试数字总是9个字符） – canni

@canni：是的，假设最短匹配总是最好的，通配符总是最后一个（所以'123 *'但不是'12 * 34'）。 – orlp

掩码始终以'*'结尾也许我写错了，数组1只包含前缀，并且这些前缀始终是唯一的，即。没有重叠（当'123 *'=>没有前缀'1234 *'） – canni

查看PHP函数array_intersect_key。

来源

2011-09-20 14:08:28 Tito

我想你误解了这个问题 – canni

我的两分钱....

$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 -function是从这个伟大的解决方案中的SO：startsWith() and endsWith() functions in PHP

来源

2011-09-20 14:19:59 Bjoern

这是一个很好的初始实现，但'startsWith'会变得太慢，将它变成'O（k * n * n）'算法。 – orlp

我完全同意你的看法。显然有很多方法可以优化这一点，以及针对这种问题的几种不同方法。我只想为这个问题展示一个基本的方法。 – Bjoern

另一种选择是在一个循环中使用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); 
}

不知道如何有效的，这将是，只是提供它作为替代。

来源

2011-09-20 14:40:59

如何匹配阵列行口罩的阵列

回答

相关问题