Tetris-ing a array

Considere a seguinte matriz:

/www/htdocs/1/sites/lib/abcdedd /www/htdocs/1/sites/conf/xyz /www/htdocs/1/sites/conf/abc/def /www/htdocs/1/sites/htdocs/xyz /www/htdocs/1/sites/lib2/abcdedd 

Qual é a maneira mais rápida e elegante de detectar o caminho base comum – neste caso

 /www/htdocs/1/sites/ 

e removê-lo de todos os elementos da matriz?

 lib/abcdedd conf/xyz conf/abc/def htdocs/xyz lib2/abcdedd 

Escreva uma function longest_common_prefix que leva duas strings como input. Em seguida, aplique-o às cordas em qualquer ordem para reduzi-las ao prefixo comum. Uma vez que é associativo e comutativo, a ordem não importa para o resultado.

Isso é o mesmo que para outras operações binárias, como, por exemplo, adição ou maior divisor comum.

Coloque-os em uma estrutura de dados. Começando a partir do nó pai, veja o que é ter uma contagem infantil maior do que uma. Depois de encontrar esse nó mágico, basta desmontar a estrutura do nó pai e ter o nó atual como root.

 $common = PHP_INT_MAX; foreach ($a as $item) { $common = min($common, str_common($a[0], $item, $common)); } $result = array(); foreach ($a as $item) { $result[] = substr($item, $common); } print_r($result); function str_common($a, $b, $max) { $pos = 0; $last_slash = 0; $len = min(strlen($a), strlen($b), $max + 1); while ($pos < $len) { if ($a{$pos} != $b{$pos}) return $last_slash; if ($a{$pos} == '/') $last_slash = $pos; $pos++; } return $last_slash; } 

Bem, considerando que você pode usar o XOR nesta situação para encontrar as partes comuns da string. Sempre que você xor dois bytes forem iguais, você obtém um nullbyte como saída. Então podemos usar isso para nossa vantagem:

 $first = $array[0]; $length = strlen($first); $count = count($array); for ($i = 1; $i < $count; $i++) { $length = min($length, strspn($array[$i] ^ $first, chr(0))); } 

Após esse loop único, a variável $length será igual à parte básica mais longa entre a matriz de strings. Então, podemos extrair a parte comum do primeiro elemento:

 $common = substr($array[0], 0, $length); 

E lá você tem isso. Como uma function:

 function commonPrefix(array $strings) { $first = $strings[0]; $length = strlen($first); $count = count($strings); for ($i = 1; $i < $count; $i++) { $length = min($length, strspn($strings[$i] ^ $first, chr(0))); } return substr($first, 0, $length); } 

Note que ele usa mais de uma iteração, mas essas iterações são feitas em bibliotecas, então, em linguagens interpretadas, isso terá um enorme ganho de eficiência ...

Agora, se você quiser apenas caminhos completos, precisamos truncar para o último / personagem. Assim:

 $prefix = preg_replace('#/[^/]*$', '', commonPrefix($paths)); 

Agora, pode cortar excessivamente duas cordas, como /foo/bar e /foo/bar/baz serão cortadas para /foo . Mas é pouco de adicionar outra rodada de iteração para determinar se o próximo personagem é ou / fim de cadeia, não consigo ver uma maneira de contornar isso ...

Uma abordagem ingênua seria explodir os caminhos no / e comparar sucessivamente cada elemento nos arrays. Então, por exemplo, o primeiro elemento seria vazio em todos os arrays, então ele será removido, o próximo elemento será www , é o mesmo em todos os arrays, para que ele seja removido, etc.

Algo como ( não testado )

 $exploded_paths = array(); foreach($paths as $path) { $exploded_paths[] = explode('/', $path); } $equal = true; $ref = &$exploded_paths[0]; // compare against the first path for simplicity while($equal) { foreach($exploded_paths as $path_parts) { if($path_parts[0] !== $ref[0]) { $equal = false; break; } } if($equal) { foreach($exploded_paths as &$path_parts) { array_shift($path_parts); // remove the first element } } } 

Depois, você só precisa implodir os elementos em $exploded_paths novamente:

 function impl($arr) { return '/' . implode('/', $arr); } $paths = array_map('impl', $exploded_paths); 

O que me dá:

 Array ( [0] => /lib/abcdedd [1] => /conf/xyz [2] => /conf/abc/def [3] => /htdocs/xyz [4] => /conf/xyz ) 

Isso pode não funcionar bem;)

Ok, não tenho certeza de que isso seja à prova de balas, mas acho que funciona:

 echo array_reduce($array, function($reducedValue, $arrayValue) { if($reducedValue === NULL) return $arrayValue; for($i = 0; $i < strlen($reducedValue); $i++) { if(!isset($arrayValue[$i]) || $arrayValue[$i] !== $reducedValue[$i]) { return substr($reducedValue, 0, $i); } } return $reducedValue; }); 

Isso levará o primeiro valor na matriz como seqüência de referência. Em seguida, ele itera sobre a seqüência de referência e compara cada char com o char da segunda string na mesma posição. Se um char não corresponder, a cadeia de referência será encurtada na posição do char e a próxima string será comparada. A function retornará a string mais correspondente então.

O desempenho depende das cordas dadas. Quanto mais cedo a cadeia de referência ficar mais curta, mais rápido o código terminará. Eu realmente não tenho idéia de como colocar isso em uma fórmula.

Descobri que a abordagem da Artefacto para classificar as cordas aumenta o desempenho. Adicionando

 asort($array); $array = array(array_shift($array), array_pop($array)); 

antes do array_reduce aumentará significativamente o desempenho.

Observe também que isso retornará a subseqüente substring inicial mais longa , que é mais versátil, mas não lhe dará o caminho comum . Você tem que correr

 substr($result, 0, strrpos($result, '/')); 

sobre o resultado. E então você pode usar o resultado para remover os valores

 print_r(array_map(function($v) use ($path){ return str_replace($path, '', $v); }, $array)); 

o que deve dar:

 [0] => /lib/abcdedd [1] => /conf/xyz/ [2] => /conf/abc/def [3] => /htdocs/xyz [4] => /lib2/abcdedd 

Comentários bem-vindos.

Você pode remover o prefixo da maneira mais rápida, lendo cada personagem apenas uma vez:

 function findLongestWord($lines, $delim = "/") { $max = 0; $len = strlen($lines[0]); // read first string once for($i = 0; $i < $len; $i++) { for($n = 1; $n < count($lines); $n++) { if($lines[0][$i] != $lines[$n][$i]) { // we've found a difference between current token // stop search: return $max; } } if($lines[0][$i] == $delim) { // we've found a complete token: $max = $i + 1; } } return $max; } $max = findLongestWord($lines); // cut prefix of len "max" for($n = 0; $n < count($lines); $n++) { $lines[$n] = substr(lines[$n], $max, $len); } 

Isso tem a vantagem de não ter complexidade linear do tempo; no entanto, para a maioria dos casos, o tipo definitivamente não será a operação levando mais tempo.

Basicamente, a parte inteligente (pelo menos eu não consegui encontrar uma falha com isso) aqui é que após a sorting, você só terá que comparar o primeiro caminho com o último.

 sort($a); $a = array_map(function ($el) { return explode("/", $el); }, $a); $first = reset($a); $last = end($a); for ($eqdepth = 0; $first[$eqdepth] === $last[$eqdepth]; $eqdepth++) {} array_walk($a, function (&$el) use ($eqdepth) { for ($i = 0; $i < $eqdepth; $i++) { array_shift($el); } }); $res = array_map(function ($el) { return implode("/", $el); }, $a); 
 $values = array('/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); function splitArrayValues($r) { return explode('/',$r); } function stripCommon($values) { $testValues = array_map('splitArrayValues',$values); $i = 0; foreach($testValues[0] as $key => $value) { foreach($testValues as $arraySetValues) { if ($arraySetValues[$key] != $value) break 2; } $i++; } $returnArray = array(); foreach($testValues as $value) { $returnArray[] = implode('/',array_slice($value,$i)); } return $returnArray; } $newValues = stripCommon($values); echo '
'; var_dump($newValues); echo '

';

EDITAR Variante do meu método original usando um array_walk para reconstruir a matriz

 $values = array('/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); function splitArrayValues($r) { return explode('/',$r); } function rejoinArrayValues(&$r,$d,$i) { $r = implode('/',array_slice($r,$i)); } function stripCommon($values) { $testValues = array_map('splitArrayValues',$values); $i = 0; foreach($testValues[0] as $key => $value) { foreach($testValues as $arraySetValues) { if ($arraySetValues[$key] != $value) break 2; } $i++; } array_walk($testValues, 'rejoinArrayValues', $i); return $testValues; } $newValues = stripCommon($values); echo '
'; var_dump($newValues); echo '

';

EDITAR

A resposta mais eficiente e elegante provavelmente envolverá a tomada de funções e methods de cada uma das respostas fornecidas

Eu explode os valores com base no / e então use array_intersect_assoc para detectar os elementos comuns e garantir que eles tenham o índice correspondente correto na matriz. A matriz resultante pode ser recombinada para produzir o caminho comum.

 function getCommonPath($pathArray) { $pathElements = array(); foreach($pathArray as $path) { $pathElements[] = explode("/",$path); } $commonPath = $pathElements[0]; for($i=1;$i 

Isso não é testado, mas, a idéia é que a matriz $commonPath sempre contém os elementos do caminho que foram contidos em todos os arrays de caminho que foram comparados contra ele. Quando o loop está completo, nós simplesmente o recombinamos com / para obter o verdadeiro $commonPath

Atualização Como apontado por Felix Kling, array_intersect não considerará caminhos que tenham elementos comuns, mas em ordens diferentes ... Para resolver isso, usei array_intersect_assoc vez de array_intersect

Atualize o código adicionado para remover o caminho comum (ou tetris ele!) Da matriz também.

O problema pode ser simplificado se apenas visto a partir do ângulo de comparação de cordas. Provavelmente, é mais rápido do que dividir em matrizes:

 $longest = $tetris[0]; # or array_pop() foreach ($tetris as $cmp) { while (strncmp($longest+"/", $cmp, strlen($longest)+1) !== 0) { $longest = substr($longest, 0, strrpos($longest, "/")); } } 

Talvez portando o algoritmo os os.path.commonprefix(m) de os.path.commonprefix(m) da Python funcionariam?

 def commonprefix(m): "Given a list of pathnames, returns the longest common leading component" if not m: return '' s1 = min(m) s2 = max(m) n = min(len(s1), len(s2)) for i in xrange(n): if s1[i] != s2[i]: return s1[:i] return s1[:n] 

Ou seja, uh … algo como

 function commonprefix($m) { if(!$m) return ""; $s1 = min($m); $s2 = max($m); $n = min(strlen($s1), strlen($s2)); for($i=0;$i<$n;$i++) if($s1[$i] != $s2[$i]) return substr($s1, 0, $i); return substr($s1, 0, $n); } 

Depois disso, você pode apenas substrar cada elemento da lista original com o comprimento do prefixo comum como o deslocamento inicial.

Vou jogar meu chapéu no ringue …

 function longestCommonPrefix($a, $b) { $i = 0; $end = min(strlen($a), strlen($b)); while ($i < $end && $a[$i] == $b[$i]) $i++; return substr($a, 0, $i); } function longestCommonPrefixFromArray(array $strings) { $count = count($strings); if (!$count) return ''; $prefix = reset($strings); for ($i = 1; $i < $count; $i++) $prefix = longestCommonPrefix($prefix, $strings[$i]); return $prefix; } function stripPrefix(&$string, $foo, $length) { $string = substr($string, $length); } 

Uso:

 $paths = array( '/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd', ); $longComPref = longestCommonPrefixFromArray($paths); array_walk($paths, 'stripPrefix', strlen($longComPref)); print_r($paths); 

Bem, já existem algumas soluções aqui, mas só porque foi divertido:

 $values = array( '/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); function findCommon($values){ $common = false; foreach($values as &$p){ $p = explode('/', $p); if(!$common){ $common = $p; } else { $common = array_intersect_assoc($common, $p); } } return $common; } function removeCommon($values, $common){ foreach($values as &$p){ $p = explode('/', $p); $p = array_diff_assoc($p, $common); $p = implode('/', $p); } return $values; } echo '
'; print_r(removeCommon($values, findCommon($values))); echo '

';

Saída:

 Array ( [0] => lib/abcdedd [1] => conf/xyz [2] => conf/abc/def [3] => htdocs/xyz [4] => lib2/abcdedd ) 
 $arrMain = array( '/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); function explodePath( $strPath ){ return explode("/", $strPath); } function removePath( $strPath) { global $strCommon; return str_replace( $strCommon, '', $strPath ); } $arrExplodedPaths = array_map( 'explodePath', $arrMain ) ; //Check for common and skip first 1 $strCommon = ''; for( $i=1; $i< count( $arrExplodedPaths[0] ); $i++) { for( $j = 0; $j < count( $arrExplodedPaths); $j++ ) { if( $arrExplodedPaths[0][ $i ] !== $arrExplodedPaths[ $j ][ $i ] ) { break 2; } } $strCommon .= '/'.$arrExplodedPaths[0][$i]; } print_r( array_map( 'removePath', $arrMain ) ); 

Isso funciona bem ... semelhante a Mark Baker, mas usa str_replace

Provavelmente também ingênuo e noobish, mas funciona. Eu usei esse algoritmo :

  $intLargestSize ){ //remember this as the largest $intLargestSize = $CSL[$i][$j]; //wipe any previous results $ret = array(); //and then fall through to remember this new value } if( $CSL[$i][$j] == $intLargestSize ) //remember the largest string(s) $ret[] = substr($str1, $i-$intLargestSize+1, $intLargestSize); } //else, $CSL should be set to 0, which it was already initialized to } } //return the list of matches return $ret; } $arr = array( '/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); // find the common substring $longestCommonSubstring = strlcs( $arr[0], $arr[1] ); // remvoe the common substring foreach ($arr as $k => $v) { $arr[$k] = str_replace($longestCommonSubstring[0], '', $v); } var_dump($arr); 

Saída:

 array(5) { [0]=> string(11) "lib/abcdedd" [1]=> string(8) "conf/xyz" [2]=> string(12) "conf/abc/def" [3]=> string(10) "htdocs/xyz" [4]=> string(12) "lib2/abcdedd" } 

🙂

Intereting Posts