Ein Array testen

Betrachten Sie das folgende 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

Was ist die kürzeste und eleganteste Art, den gemeinsamen Basispfad zu erkennen - in diesem Fall

/www/htdocs/1/sites/

und entfernen Sie es von allen Elementen im Array?

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

Schreiben Sie eine Funktion longest_common_prefix, die zwei Zeichenfolgen als Eingabe verwendet. Wenden Sie es dann in beliebiger Reihenfolge auf die Zeichenfolgen an, um sie auf ihr gemeinsames Präfix zu reduzieren. Da es assoziativ und kommutativ ist, spielt die Reihenfolge für das Ergebnis keine Rolle.

Dies ist dasselbe wie für andere binäre Operationen wie zum Beispiel Addition oder größter gemeinsamer Divisor.

Laden Sie sie in eine Trie-Datenstruktur. Sehen Sie ausgehend vom übergeordneten Knoten, welcher untergeordnete Knoten mehr als eins zählt. Wenn Sie diesen magischen Knoten gefunden haben, zerlegen Sie einfach die übergeordnete Knotenstruktur und haben Sie den aktuellen Knoten als 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;
}

Nun, wenn man bedenkt, dass Sie XORin dieser Situation die gemeinsamen Teile der Zeichenfolge finden können. Jedes Mal, wenn Sie zwei oder zwei Bytes identisch sind, erhalten Sie ein Nullbyte als Ausgabe. Das können wir also zu unserem Vorteil nutzen:

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

Nach dieser einzelnen Schleife entspricht die $lengthVariable dem längsten gemeinsamen Basisteil zwischen den Zeichenfolgen. Dann können wir den gemeinsamen Teil aus dem ersten Element extrahieren:

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

Und da hast du es. Als eine Funktion:

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

Beachten Sie, dass mehr als eine Iteration verwendet wird, diese Iterationen jedoch in Bibliotheken durchgeführt werden. In interpretierten Sprachen bedeutet dies einen enormen Effizienzgewinn ...

Wenn Sie nur vollständige Pfade möchten, müssen Sie das letzte /Zeichen abschneiden . So:

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

Jetzt können zwei Saiten übermäßig geschnitten werden, z. B. /foo/barund /foo/bar/bazwerden zugeschnitten /foo. Aber ohne eine weitere Iterationsrunde hinzuzufügen, um festzustellen, ob das nächste Zeichen eines / oder ein Ende der Zeichenfolge ist, sehe ich keinen Weg daran vorbei ...

Ein naiver Ansatz wäre, die Pfade am zu explodieren /und nacheinander jedes Element in den Arrays zu vergleichen. ZB wäre das erste Element in allen Arrays leer, also wird es entfernt, das nächste Elementwww , es ist in allen Arrays gleich, also wird es entfernt usw.

Etwas wie (ungetestet)

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

Danach müssen Sie nur noch die Elemente $exploded_pathserneut implodieren :

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

Welches gibt mir:

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

Dies ist möglicherweise nicht gut skalierbar;)

Ok, ich bin nicht sicher, ob dies kugelsicher ist, aber ich denke, es funktioniert:

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

Dadurch wird der erste Wert im Array als Referenzzeichenfolge verwendet. Dann wird die Referenzzeichenfolge durchlaufen und jedes Zeichen mit dem Zeichen der zweiten Zeichenfolge an derselben Position verglichen. Wenn ein Zeichen nicht übereinstimmt, wird die Referenzzeichenfolge auf die Position des Zeichens gekürzt und die nächste Zeichenfolge verglichen. Die Funktion gibt dann die kürzeste übereinstimmende Zeichenfolge zurück.

Die Leistung hängt von den angegebenen Zeichenfolgen ab. Je früher die Referenzzeichenfolge kürzer wird, desto schneller wird der Code beendet. Ich habe wirklich keine Ahnung, wie ich das in eine Formel einfügen soll.

Ich fand heraus, dass Artefactos Ansatz zum Sortieren der Saiten die Leistung erhöht. Hinzufügen

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

vor dem array_reducewird die Leistung deutlich steigern.

Beachten Sie auch, dass dies die längste übereinstimmende anfängliche Teilzeichenfolge zurückgibt , die vielseitiger ist, Ihnen jedoch nicht den gemeinsamen Pfad gibt . Du musst rennen

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

auf das Ergebnis. Und dann können Sie das Ergebnis verwenden, um die Werte zu entfernen

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

was geben sollte:

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

Feedback willkommen.

Sie können das Präfix am schnellsten entfernen, indem Sie jedes Zeichen nur einmal lesen:

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

Dies hat den Vorteil, keine lineare Zeitkomplexität zu haben; In den meisten Fällen ist die Sortierung jedoch definitiv nicht die Operation, die mehr Zeit in Anspruch nimmt.

Grundsätzlich ist der clevere Teil (zumindest konnte ich keinen Fehler finden), dass Sie nach dem Sortieren nur den ersten Pfad mit dem letzten vergleichen müssen.

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

EDIT Variante meiner ursprünglichen Methode mit einem array_walk zum Neuerstellen des Arrays

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

BEARBEITEN

Die effizienteste und eleganteste Antwort besteht wahrscheinlich darin, Funktionen und Methoden aus jeder der bereitgestellten Antworten zu übernehmen

Ich würde explodedie Werte basierend auf dem / verwenden und dann verwenden array_intersect_assoc, um die gemeinsamen Elemente zu erkennen und sicherzustellen, dass sie den richtigen entsprechenden Index im Array haben. Das resultierende Array könnte neu kombiniert werden, um den gemeinsamen Pfad zu erzeugen.

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

Dies ist nicht getestet, aber die Idee ist, dass das $commonPathArray immer nur die Elemente des Pfads enthält, die in allen Pfadarrays enthalten waren, die mit ihm verglichen wurden. Wenn die Schleife abgeschlossen ist, kombinieren wir sie einfach mit /, um das Wahre zu erhalten$commonPath

Update Wie von Felix Kling hervorgehoben, array_intersectwerden Pfade mit gemeinsamen Elementen, aber in unterschiedlicher Reihenfolge, nicht berücksichtigt. Um dies zu lösen, habe ich array_intersect_assocstattdessen verwendetarray_intersect

Update Hinzugefügter Code, um den allgemeinen Pfad (oder tetris it!) Auch aus dem Array zu entfernen.

Das Problem kann vereinfacht werden, wenn es nur aus dem String-Vergleichswinkel betrachtet wird. Dies ist wahrscheinlich schneller als das Aufteilen von Arrays:

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

Vielleicht os.path.commonprefix(m)würde es funktionieren, den von Python verwendeten Algorithmus zu portieren ?

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]

Das heißt, äh ... so etwas wie

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

Danach können Sie jedes Element der ursprünglichen Liste mit der Länge des gemeinsamen Präfixes als Startoffset unterteilen.

Ich werde meinen Hut in den Ring werfen ...

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

Verwendung:

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

Nun, hier gibt es bereits einige Lösungen, aber nur weil es Spaß gemacht hat:

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

Ausgabe:

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

Dies funktioniert gut ... ähnlich wie Mark Baker, verwendet jedoch str_replace

Wahrscheinlich zu naiv und noobisch, aber es funktioniert. Ich habe diesen Algorithmus verwendet :

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

Ausgabe:

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

:) :)