Tetrisowanie tablicy

Rozważmy następującą tablicę:

/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

jaki jest najkrótszy i najbardziej elegancki sposób wykrywania wspólnej ścieżki bazowej - w tym przypadku

/www/htdocs/1/sites/

i usuwając go ze wszystkich elementów tablicy?

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

Napisz funkcję, longest_common_prefixktóra pobiera dwa ciągi jako dane wejściowe. Następnie zastosuj go do łańcuchów w dowolnej kolejności, aby zredukować je do ich wspólnego przedrostka. Ponieważ jest skojarzona i przemienna, kolejność nie ma znaczenia dla wyniku.

Jest to to samo, co w przypadku innych operacji binarnych, takich jak na przykład dodawanie lub największy wspólny dzielnik.

Załaduj je do trie struktury danych. Zaczynając od węzła nadrzędnego, zobacz, który z elementów potomnych jest większy niż jeden. Gdy znajdziesz ten magiczny węzeł, po prostu zdemontuj strukturę węzła macierzystego i ustaw bieżący węzeł jako główny.

$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;
}

Cóż, biorąc pod uwagę, że możesz użyć XORw tej sytuacji, aby znaleźć wspólne części ciągu. Za każdym razem, gdy xorujesz dwa takie same bajty, jako wyjście otrzymasz zerowy bajt. Więc możemy to wykorzystać na naszą korzyść:

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

Po tej pojedynczej pętli $lengthzmienna będzie równa najdłuższej wspólnej części bazowej między tablicą ciągów. Następnie możemy wyodrębnić część wspólną z pierwszego elementu:

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

I masz to. Jako funkcja:

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);
}

Zwróć uwagę, że używa więcej niż jednej iteracji, ale te iteracje są wykonywane w bibliotekach, więc w językach interpretowanych będzie to miało ogromny wzrost wydajności ...

Teraz, jeśli chcesz tylko pełnych ścieżek, musimy skrócić do ostatniego /znaku. Więc:

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

Teraz może nadmiernie przeciąć dwie struny, takie jak /foo/bari /foo/bar/bazzostanie przycięte /foo. Ale brakuje dodając kolejną rundę iteracji, aby ustalić, czy następny znak jest albo / czy końcówki łańcucha, nie widzę sposób wokół, że ...

Naiwnym podejściem byłoby eksplodowanie ścieżek /i sukcesywne porównywanie każdego elementu w tablicach. Czyli np. Pierwszy element byłby pusty we wszystkich tablicach, więc zostanie usunięty, następny element będzie wwwtaki sam we wszystkich tablicach, więc zostanie usunięty itp.

Coś jak (niesprawdzone)

$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
        }
    }
}

Następnie wystarczy ponownie implodować elementy $exploded_paths:

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

Co daje mi:

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

To może nie być dobrze skalowane;)

Ok, nie jestem pewien, czy to jest kuloodporne, ale myślę, że działa:

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;
});

Spowoduje to pobranie pierwszej wartości z tablicy jako łańcucha odniesienia. Następnie przeprowadzi iterację po ciągu referencyjnym i porówna każdy znak ze znakiem drugiego łańcucha w tej samej pozycji. Jeśli znak nie pasuje, ciąg referencyjny zostanie skrócony do pozycji znaku i porównany zostanie następny ciąg. Funkcja zwróci wówczas najkrótszy pasujący ciąg.

Wydajność zależy od podanych strun. Im wcześniej ciąg referencyjny zostanie skrócony, tym szybciej zakończy się kod. Naprawdę nie mam pojęcia, jak to ująć w formule.

Odkryłem, że podejście Artefacto do sortowania strun zwiększa wydajność. Dodawanie

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

przed array_reduceznacznie zwiększy wydajność.

Zwróć również uwagę, że zwróci to najdłuższy pasujący podciąg początkowy , który jest bardziej wszechstronny, ale nie daje wspólnej ścieżki . Musisz biec

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

na wynik. Następnie możesz użyć wyniku, aby usunąć wartości

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

co powinno dać:

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

Opinie mile widziane.

Najszybciej możesz usunąć prefiks, czytając każdy znak tylko raz:

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);
}

Ma to dużą zaletę, ponieważ nie ma liniowej złożoności czasowej; jednak w większości przypadków operacja ta na pewno nie zajmie więcej czasu.

Zasadniczo sprytną częścią (przynajmniej nie mogłem znaleźć w tym żadnej usterki) tutaj jest to, że po sortowaniu będziesz musiał tylko porównać pierwszą ścieżkę z ostatnią.

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 '<pre>';
var_dump($newValues);
echo '</pre>';

EDYTUJ Wariant mojej oryginalnej metody wykorzystujący array_walk do odbudowania tablicy

$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 '<pre>';
var_dump($newValues);
echo '</pre>';

EDYTOWAĆ

Najbardziej wydajna i elegancka odpowiedź będzie prawdopodobnie polegać na przejęciu funkcji i metod z każdej z udzielonych odpowiedzi

Chciałbym explodewartości oparte na /, a następnie użyć array_intersect_assocdo wykrycia wspólnych elementów i zapewnienia, że ​​mają prawidłowy odpowiedni indeks w tablicy. Powstała macierz może zostać ponownie połączona w celu utworzenia wspólnej ścieżki.

function getCommonPath($pathArray)
{
    $pathElements = array();

    foreach($pathArray as $path)
    {
        $pathElements[] = explode("/",$path);
    }

    $commonPath = $pathElements[0];

    for($i=1;$i<count($pathElements);$i++)
    {
        $commonPath = array_intersect_assoc($commonPath,$pathElements[$i]);
    }

    if(is_array($commonPath) return implode("/",$commonPath);
    else return null;
}

function removeCommonPath($pathArray)
{
    $commonPath = getCommonPath($pathArray());

    for($i=0;$i<count($pathArray);$i++)
    {
        $pathArray[$i] = substr($pathArray[$i],str_len($commonPath));
    }

    return $pathArray;
}

Nie jest to testowane, ale idea polega na tym, że $commonPathtablica zawsze zawiera tylko elementy ścieżki, które zostały zawarte we wszystkich tablicach ścieżek, które zostały z nią porównane. Kiedy pętla jest kompletna, po prostu łączymy ją ponownie z /, aby uzyskać prawdę$commonPath

Aktualizacja Jak wskazał Felix Kling, array_intersectnie będzie rozważać ścieżek, które mają wspólne elementy, ale w innej kolejności ... Aby rozwiązać ten problem, użyłem array_intersect_assoczamiastarray_intersect

Aktualizacja Dodano kod usuwający wspólną ścieżkę (lub tetris it!) Z tablicy.

Problem można uprościć, patrząc tylko pod kątem porównania ciągów. Jest to prawdopodobnie szybsze niż dzielenie tablicy:

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

Może przeniesienie algorytmu używanego przez Pythona os.path.commonprefix(m)zadziała?

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]

To znaczy ... coś w stylu

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);
}

Następnie możesz po prostu wstawić każdy element oryginalnej listy z długością wspólnego przedrostka jako przesunięciem początkowym.

Rzucę swój kapelusz na ring…

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);
}

Stosowanie:

$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);

Cóż, są już tutaj rozwiązania, ale tylko dlatego, że było fajnie:

$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 '<pre>';
print_r(removeCommon($values, findCommon($values)));
echo '</pre>';

Wynik:

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 ) );

To działa dobrze ... podobnie do mark baker, ale używa str_replace

Prawdopodobnie zbyt naiwny i niedbały, ale działa. Użyłem tego algorytmu :

<?php

function strlcs($str1, $str2){
    $str1Len = strlen($str1);
    $str2Len = strlen($str2);
    $ret = array();

    if($str1Len == 0 || $str2Len == 0)
        return $ret; //no similarities

    $CSL = array(); //Common Sequence Length array
    $intLargestSize = 0;

    //initialize the CSL array to assume there are no similarities
    for($i=0; $i<$str1Len; $i++){
        $CSL[$i] = array();
        for($j=0; $j<$str2Len; $j++){
            $CSL[$i][$j] = 0;
        }
    }

    for($i=0; $i<$str1Len; $i++){
        for($j=0; $j<$str2Len; $j++){
            //check every combination of characters
            if( $str1[$i] == $str2[$j] ){
                //these are the same in both strings
                if($i == 0 || $j == 0)
                    //it's the first character, so it's clearly only 1 character long
                    $CSL[$i][$j] = 1; 
                else
                    //it's one character longer than the string from the previous character
                    $CSL[$i][$j] = $CSL[$i-1][$j-1] + 1; 

                if( $CSL[$i][$j] > $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);

Wynik:

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"
}

:)