Рассмотрим следующий массив:
/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
каков самый короткий и самый элегантный способ обнаружения общего базового пути - в этом случае
/www/htdocs/1/sites/
и удалить его из всех элементов массива?
lib/abcdedd
conf/xyz
conf/abc/def
htdocs/xyz
lib2/abcdedd
Напишите функцию longest_common_prefix, которая принимает две строки в качестве входных данных. Затем примените его к строкам в любом порядке, чтобы уменьшить их до общего префикса. Поскольку он ассоциативен и коммутативен, порядок не имеет значения для результата.
Это то же самое, что и для других двоичных операций, таких как, например, сложение или наибольший общий делитель.
Загрузите их в структуру данных trie. Начиная с родительского node, см., Что имеет число детей, отличное от одного. Как только вы обнаружите, что магия node, просто демонтируйте родительскую структуру node и введите текущий node как пользователь 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;
}
Хорошо, учитывая, что вы можете использовать XOR в этой ситуации, чтобы найти общие части строки. Каждый раз, когда вы xor два байта одинаковы, вы получаете нулевой байт в качестве вывода. Поэтому мы можем использовать это в наших интересах:
$first = $array[0];
$length = strlen($first);
$count = count($array);
for ($i = 1; $i < $count; $i++) {
$length = min($length, strspn($array[$i] ^ $first, chr(0)));
}
После этого одиночного цикла переменная $length будет равна самой длинной общей базовой части между массивом строк. Затем мы можем извлечь общую часть из первого элемента:
$common = substr($array[0], 0, $length);
И у вас это есть. Как функция:
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);
}
Обратите внимание, что он использует более одной итерации, но эти итерации выполняются в библиотеках, поэтому в интерпретируемых языках это будет иметь большую эффективность...
Теперь, если вы хотите только полные пути, нам нужно усечь до последнего символа /. Итак:
$prefix = preg_replace('#/[^/]*$', '', commonPrefix($paths));
Теперь он может чрезмерно разрезать две строки, такие как /foo/bar и /foo/bar/baz, нарезать на /foo. Но, не добавляя еще один раунд итерации, чтобы определить, есть ли следующий символ либо / , либо конец строки, я не вижу пути вокруг этого...
Наивный подход заключается в том, чтобы взорвать пути в / и последовательно сравнивать каждый элемент в массивах. Так, например, первый элемент будет пустым во всех массивах, поэтому он будет удален, следующий элемент будет www, он будет одинаковым во всех массивах, поэтому он будет удален и т.д.
Что-то вроде (untested)
$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
}
}
}
Впоследствии вам просто нужно снова взорвать элементы в $exploded_paths:
function impl($arr) {
return '/' . implode('/', $arr);
}
$paths = array_map('impl', $exploded_paths);
Что дает мне:
Array
(
[0] => /lib/abcdedd
[1] => /conf/xyz
[2] => /conf/abc/def
[3] => /htdocs/xyz
[4] => /conf/xyz
)
Это может плохо масштабироваться;)
Хорошо, я не уверен, что это пуленепробиваемый, но я думаю, что он работает:
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;
});
Это займет первое значение в массиве в качестве ссылочной строки. Затем он перебирает ссылочную строку и сравнивает каждую char с char второй строки в той же позиции. Если char не совпадает, эталонная строка будет сокращена до позиции char, а следующая строка будет сравниваться. Затем функция вернет самую короткую совпадающую строку.
Производительность зависит от заданных строк. Чем раньше ссылочная строка становится короче, тем быстрее заканчивается код. Я действительно не знаю, как это выразить в формуле.
Я обнаружил, что подход Artefacto для сортировки строк увеличивает производительность. Добавление
asort($array);
$array = array(array_shift($array), array_pop($array));
до array_reduce значительно повысит производительность.
Также обратите внимание, что это вернет самую длинную совпадающую начальную подстроку, которая более универсальна, но не даст вам общий путь. Вы должны запустить
substr($result, 0, strrpos($result, '/'));
на результат. И затем вы можете использовать результат для удаления значений
print_r(array_map(function($v) use ($path){
return str_replace($path, '', $v);
}, $array));
который должен дать:
[0] => /lib/abcdedd
[1] => /conf/xyz/
[2] => /conf/abc/def
[3] => /htdocs/xyz
[4] => /lib2/abcdedd
Обратная связь.
Вы можете удалить префикс самым быстрым способом, прочитав каждый символ только один раз:
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);
}
$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 Вариант моего исходного метода с помощью array_walk для восстановления массива
$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>';
ИЗМЕНИТЬ
Самый эффективный и изящный ответ, вероятно, будет включать в себя выполнение функций и методов из каждого из предоставленных ответов.
Это имеет преимущество не иметь линейной сложности времени; однако в большинстве случаев сортировка определенно не будет выполняться с большим количеством времени.
В принципе, умная часть (по крайней мере, я не могу найти с ней ошибку), заключается в том, что после сортировки вам нужно будет сравнить только первый путь с последним.
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);
Я бы использовал explode значения, основанные на /, а затем использовал array_intersect_assoc для обнаружения общих элементов и обеспечения их правильного соответствующего индекса в массиве. Результирующий массив может быть рекомбинирован для создания общего пути.
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;
}
Это не проверено, но идея состоит в том, что массив $commonPath только когда-либо содержит элементы пути, которые содержались во всех массивах путей, которые были сопоставлены с ним. Когда цикл завершен, мы просто рекомбинируем его с/для получения истинного $commonPath
Обновление
Как отметил Феликс Клинг, array_intersect не будет рассматривать пути, которые имеют общие элементы, но в разных порядках... Чтобы решить эту проблему, я использовал array_intersect_assoc вместо array_intersect
Обновление Добавлен код для удаления общего пути (или tetris it!) Из массива.
Проблема может быть упрощена, если только просмотреть из угла сравнения строк. Вероятно, это быстрее, чем разбиение массива:
$longest = $tetris[0]; # or array_pop()
foreach ($tetris as $cmp) {
while (strncmp($longest+"/", $cmp, strlen($longest)+1) !== 0) {
$longest = substr($longest, 0, strrpos($longest, "/"));
}
}
Возможно, портирование алгоритма Python os.path.commonprefix(m) будет работать?
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]
То есть, что-то вроде
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);
}
После этого вы можете просто подстроить каждый элемент исходного списка длиной общего префикса в качестве начального смещения.
Я брошу свою шляпу в кольцо...
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);
}
Применение:
$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);
Ну, здесь уже есть некоторые решения, но только потому, что это было весело:
$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>';
Вывод:
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 ) );
Это отлично работает... похоже на mark baker, но использует str_replace
Наверное, слишком наивно и noobish, но он работает. Я использовал этот алгоритм:
<?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 the first character, so it clearly only 1 character long
$CSL[$i][$j] = 1;
else
//it 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);
Вывод:
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"
}
:)