Поиск в иерархических данных в переполнении стека
Вот структура данных, которую я имею (она упрощена для более ясного понимания):
• USA
• Alabama
• Montgomery
• Birmingham
• Arizona
• Phoenix
• Mesa
• Gilbert
• Germany
• West Germany
• Bonn
• Cologne
Мне нужно вернуть весь путь для данного узла — т.е. если пользователь вводит ArizonaМне нужно вернуться USA → Arizona, Если ввести BirminghamМне нужно вернуться USA → Alabama → Birmingham,
Есть ли в PHP простой способ поиска в таких структурах?
Решение
Если у вас нет огромной структуры данных, вы можете использовать синтаксический анализ XML. Это хорошо известно и легко реализуемо. У него есть желаемая возможность доступа к родительскому элементу.
Вот простой пример:
$xml = <<<XML
<list>
<state name="USA">
<region name="Alabama">
<city name="Montgomery" />
<city name="Birmingham" />
</region>
<region name="Arizona">
<city name="Phoenix" />
<city name="Mesa" />
<city name="Gilbert" />
</region>
</state>
<state name="Germany">
<region name="West Germany">
<city name="Bonn" />
<city name="Cologne" />
</region>
</state>
</list>
XML;$doc = new \DOMDocument;
$doc->preserveWhiteSpace = false;
$doc->loadXML($xml);
$xpath = new \DOMXPath($doc);
// XPath query to match all elements with
// attribute name equals to your searched phrase
$locations = $xpath->query("//*[@name='Cologne']");
function parse($list) {
$response = [];
foreach ($list as $node) {
$response[] = $node->attributes->getNamedItem('name')->nodeValue;
$parentNode = $node->parentNode;
// traverse up to root element
// root element has no attributes
// feel free to use any other condition, such as checking to element's name
while ($parentNode->hasAttributes()) {
$response[] = $parentNode->attributes->getNamedItem('name')->nodeValue;
$parentNode = $parentNode->parentNode;
}
}
return $response;
}
$parsedLocations = array_reverse(parse($locations));
echo implode(' → ', $parsedLocations), PHP_EOL;
Другие решения
Вот возможная стратегия, которая строит путь по частям: вы начинаете с первого уровня массива и проверяете, равен ли искомый термин ключу. Если нет, вы проверяете значение, а в противном случае, если значение является массивом (is_array ()) вы повторяете поиск, используя префикс.
Набор данных:
$str = array(
"USA" => array(
"Alabama" => array(
"Montgomery",
"Birmingham"),
"Arizona" => array(
"Phoenix",
"",
"Gilbert"),
"West Germany" => array(
"Bonn",
"",
"Cologne")
),
"Germany" => array(
"West Germany" => array(
"Bonn",
"Mesa",
"Cologne")
)
);
Функция:
function getPath($haystack, $needle, $prefix=""){
$path = "";
foreach($haystack as $key=>$value){
if($path!="")break;
if($key===$needle){
return $prefix.$key;
break;
}
elseif($value===$needle) {
return $prefix.$value;
break;
}
elseif(is_array($value)) {
$path.=getPath($value,$needle,$prefix.$key."=>");
}
}
return $path;
}
тест:
echo getPath($str,"Mesa");
В случае дубликатов вы получите первый результат. Если поисковый термин не найден, вы получите пустую строку.
Поскольку «структура данных» очень расплывчата, а ваш единственный намек на то, что вы используете PHP, я предполагаю, что ваша «структура данных» означает следующее:
[
'USA' =>
[
'Alabama' =>
[
'Montgomery',
'Birmingham'
],
'Arizona' =>
[
'Phoenix',
'Mesa',
'Gilbert'
]
],
'Germany' =>
[
'West Germany' =>
[
'Bonn',
'Cologne'
]
]
]
И я предполагаю, что вы хотите, чтобы ваш результат в форме
['USA', 'Alabama', 'Birmingham']
Если это не так, пожалуйста, сообщите нам о том, как ваши данные на самом деле доступны и как вы хотите, чтобы ваш результат.
Есть ли в PHP простой способ поиска в таких структурах?
Это зависит от вашего определения «простой».
Для меня решение, которое вписывается в одну функцию, является «простым».
Однако для этого нет готового решения, которое можно было бы использовать в одной строке.
Если вам нужно только найти «листья», вы можете использовать RecursiveIteratorIterator через RecursiveArrayIterator как в этот вопрос StackOverflow.
Но так как вам нужно найти промежуточные ключи, это не совсем вариант.
То же самое касается array_walk_recursive.
Вы могли бы, вероятно, использовать ArrayIterator или же array_walk, но в этом примере они не могут ничего сделать foreach Цикл не может, кроме того, усложнять вещи.
Так что я бы просто пойти с foreach цикл:
function findMyThing($needle, $haystack) // Keep argument order from PHP array functions
{
// We need to set up a stack array + a while loop to avoid recursive functions for those are evil.
// Recursive functions would also complicate things further in regard of returning.
$stack =
[
[
'prefix' => [],
'value' => $haystack
]
];
// As long as there's still something there, don't stop
while(count($stack) > 0)
{
// Copy the current stack and create a new, empty one
$currentStack = $stack;
$stack = [];
// Work the stack
for($i = 0; $i < count($currentStack); $i++)
{
// Iterate over the actual array
foreach($currentStack[$i]['value'] as $key => $value)
{
// If the value is an array, then
// 1. the key is a string (so we need to match against it)
// 2. we might have to go deeper
if(is_array($value))
{
// We need to build the current prefix list regardless of what we're gonna do below
$prefix = $currentStack[$i]['prefix'];
$prefix[] = $key;
// If the current key, is the one we're looking for, heureka!
if($key == $needle)
{
return $prefix;
}
// Otherwise, push prefix & value onto the stack for the next loop to pick up
else
{
$stack[] =
[
'prefix' => $prefix,
'value' => $value
];
}
}
// If the value is NOT an array, then
// 1. the key is an integer, so we DO NOT want to match against it
// 2. we need to match against the value itself
elseif($value == $needle)
{
// This time append $value, not $key
$prefix = $currentStack[$i]['prefix'];
$prefix[] = $value;
return $prefix;
}
}
}
}
// At this point we searched the entire array and didn't find anything, so we return an empty array
return [];
}
Тогда просто используйте это как
$path = findMyThing('Alabama', $array);
@Siguza
избегать рекурсивных функций для тех, кто является злом
Рекурсия не является злом (или оценкой) и хорошо работает со стеками
function df($v,array &$in,array &$stack,$search) {
$stack[] = $v;
if ( $v == $search ) {
return [true,$stack];
}
if ( is_array($in) ) {
foreach ($in as $vv => $k) {
if ( is_array($k) ) {
$r = df($vv, $k, $stack, $search);
if ($r[0]) {
return $r;
}
}
else if ($k == $search) {
$stack[] = $k;
return [true,$stack];
}
}
}
array_pop($stack);
return [false,null];
}
Использование:
$s = [];
$r = df('',$in,$s,'Bonn');
print_r($r);
$s = [];
$r = df('',$in,$s,'West Germany');
print_r($r);
$s = [];
$r = df('',$in,$s,'NtFound');
print_r($r);
Выход:
Array
(
[0] => 1
[1] => Array
(
[0] =>
[1] => Germany
[2] => West Germany
[3] => Bonn
)
)
Array
(
[0] => 1
[1] => Array
(
[0] =>
[1] => Germany
[2] => West Germany
)
)
Array
(
[0] =>
[1] =>
)
Согласно вашей структуре данных.
$data['USA'] = ['Alabama' => ['Montgomery','Birmingham'],'Arizona' => ['Phoenix','Mesa','Gilbert']];
$data['Germany'] = ['West Germany' => ['Bonn','Cologne']];
function getHierarchy($location, $data){
$totalCountries = count($data);
//Get Array Keys of rows eg countries.
$keys = array_keys($data);
$hierarchy= [];
//Loop Through Countries
for($i = 0; $i < $totalCountries; $i++){
//If we have found the country then return it.
if($location == $keys[$i]) return [$keys[$i]];
$hierarchy[] = $keys[$i];
foreach($data[$keys[$i]] as $city => $places){
// if we have found the city then return it with country.
if($city == $location){
$hierarchy[] = $city;
return $hierarchy;
}
// if we have found the place in our places array then return it with country -> city -> place.
if(in_array($location, $places)){
$hierarchy[] = $city;
$hierarchy[] = $location;
return $hierarchy;
}
}
// Reset Hirarcy if we do not found our location in previous country.
$hierarchy = [];
}
}
$found = getHierarchy('Birmingham', $data);
if($found){
echo implode(' -> ', $found);
// Output will be USA -> Alabama -> Birmingham
}
Он может найти только один город и места в стране, и если будет найдено какое-либо место, он нарушит всю функцию и вернет первое местоположение с указанием города и места.
Вот более улучшенная версия, которая также может найти несколько мест.
https://gist.github.com/touqeershafi/bf89351f3b226aae1a29
Надеюсь, это поможет вам.