Find longest matching key

Hello,

I have two arrays like this:

$aSearch = array( 'A', 'B', 'C.D', 'E', 'F' );
$aSubject = array( 'A' => 0, 'A.B' => 1, 'X' => 2, 'C.D.E' => 3, 'A.B.C' =>
4 );

Now I want to search $aSubject for the longest key that consists of the
first x elements of $aSearch concatenated by "." (where x = 1...count(
$aSearch ) ). In other words, he algorithm involved should check for the
existence of the following keys in $aSubject:

A
A.B
A.B.C.D
A.B.C.D.E
A.B.C.D.E.F

and return the longest match - in the example 'A.B'. Now I could first
create an array of all keys to search for and then loop through them to find
a match in $aSubject, but I wonder if there is a more efficient, more
elegant solution. There doesn't seem to be any PHP function that could help
with this specific problem.

Greetings,
Thomas

--
C'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)

Re: Find longest matching key

Thomas Mlynarczyk wrote:

> I have two arrays like this:
>
> $aSearch = array( 'A', 'B', 'C.D', 'E', 'F' );
> $aSubject = array( 'A' => 0, 'A.B' => 1, 'X' => 2, 'C.D.E' => 3, 'A.B.C' =>
> 4 );
>
> Now I want to search $aSubject for the longest key that consists of the
> first x elements of $aSearch concatenated by "." (where x = 1...count(
> $aSearch ) ). In other words, he algorithm involved should check for the
> existence of the following keys in $aSubject:
>
> A
> A.B
> A.B.C.D
> A.B.C.D.E
> A.B.C.D.E.F
>
> and return the longest match - in the example 'A.B'.

foreach ($aSearch as $a)
{
$key = $a;
while (strlen($key) && !isset($aSubject[$key]))
$key = preg_replace('/\.?[^\.]*$/', '', $key);

if (strlen($key))
printf("Searched for '%s'. Closest match was '%s', value %s.\n",
$a,
$key,
$aSubject[$key]);
else
printf("Searched for '%s'. No matching key found.\n", $a);
}

A bit cleaner to use a function:

function array_component_search ($needle, &$haystack, &$value=NULL)
{
$key = $needle;
while (strlen($key) && !isset($haystack[$key]))
$key = preg_replace('/\.?[^\.]*$/', '', $key);

$value = strlen($key) ? $haystack[$key] : NULL;

return strlen($key) ? $key : FALSE;
}
foreach ($aSearch as $a)
{
$key = array_component_search($a, $aSubject, $value);

if ($key!==FALSE)
printf("Searched for '%s'. Closest match was '%s', value %s.\n",
$a,
$key,
$value);
else
printf("Searched for '%s'. No matching key found.\n", $a);
}

Note that array_component_search takes two required arguments:

$needle = Key you're searching for a close match for.
$haystack = Lookup array.

The closest matching key is returned by the function, and as a side-effect,
the value for that key may be placed in a variable passed to the function
as a third argument.

Helpful?

--
Toby A Inkster BSc (Hons) ARCS
[Geek of HTML/SQL/Perl/PHP/Python/Apache/Linux]
[OS: Linux 2.6.12-12mdksmp, up 11 days, 1:11.]
[Now Playing: ./stereophonics/handbags_and_gladrags.ogg.]

Belgium
http://tobyinkster.co.uk/blog/2007/11/17/belgium/

Re: Find longest matching key

Also sprach Toby A Inkster:

> foreach ($aSearch as $a)
> {
> $key = $a;
> while (strlen($key) && !isset($aSubject[$key]))
> $key = preg_replace('/\.?[^\.]*$/', '', $key);
>
> if (strlen($key))
> printf("Searched for '%s'. Closest match was '%s', value %s.\n",
> $a,
> $key,
> $aSubject[$key]);
> else
> printf("Searched for '%s'. No matching key found.\n", $a);
> }

This finds $aSubject['A'], but should find $aSubject['A.B'].
If I remove the foreach and put an
$a = implode( '.', $aSearch )
at the beginning, it will find $aSubject['A.B.C']. (Because, in the imploded
form, the information that 'C.D' is "indivisible" gets lost.)

Maybe I was not clear enough describing my problem. The algorithm should be
something equivalent to

$aSearch = array( 'A', 'B', 'C.D', 'E', 'F' );
$aSubject = array( 'A' => 0, 'A.B' => 1, 'X' => 2, 'C.D.E' => 3, 'A.B.C' =>
4 );


1)
Convert $aSearch somehow to
$aSearch =array(
'A.B.C.D.E.F',
'A.B.C.D.E',
'A.B.C.D',
'A.B', // Note: no 'A.B.C', as 'C.D' is "indivisible"
'A'
)

2)
foreach ( $aSearch as $sKey )
{
if ( array_key_exists( $sKey, $aSubject ) ) { echo "Found
$aSubject[$sKey]"; break; }
}

Meanwhile I've come up with this:

for ( $tmp = array(), $i = 0; $i < count( $aSearch ); $i++ )
{
$tmp[$i] = $i ? $tmp[ $i - 1 ] . '.' . $aSearch[$i] : $aSearch[$i];
}

foreach ( array_reverse( $tmp, true ) as $sKey )
{
if ( array_key_exists( $sKey, $aSubject ) ) { echo "Found
$aSubject[$sKey]"; break; }
}

But it does not look elegant/efficient enough to me.

Greetings,
Thomas


--
C'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)

Re: Find longest matching key

On Nov 17, 6:13 pm, "Thomas Mlynarczyk" webdesign.de> wrote:
> $aSearch = array( 'A', 'B', 'C.D', 'E', 'F' );
> $aSubject = array( 'A' => 0, 'A.B' => 1, 'X' => 2,
> 'C.D.E' => 3, 'A.B.C' => 4 );
>
> Now I want to search $aSubject for the longest key that consists of the
> first x elements of $aSearch concatenated by "."
....
> and return the longest match - in the example 'A.B'. Now I could first
....


function longestMatchingKey ($aSrch, $aSubj) {
if (array_key_exists($k=implode(".", $aSrch), $aSubj)) return $k;
for ($i=sizeof($aSrch);$k=substr($k,0,-strlen($aSrch[--$i])-1);)
if (array_key_exists($k, $aSubj)) break;
return $k; }


(5 lines total, one loop, no reversing, watch for wrapping) Though
perhaps not overly different from what you suggested...
Csaba Gabor from Vienna

Re: Find longest matching key

Also sprach Csaba Gabor:

> function longestMatchingKey ($aSrch, $aSubj) {
> if (array_key_exists($k=implode(".", $aSrch), $aSubj)) return $k;
> for ($i=sizeof($aSrch);$k=substr($k,0,-strlen($aSrch[--$i])-1);)
> if (array_key_exists($k, $aSubj)) break;
> return $k; }

> (5 lines total, one loop, no reversing, watch for wrapping) Though
> perhaps not overly different from what you suggested...

Maybe not overly different, but certainly much more efficient and elegant!
Thanks a lot! :-)

Greetings,
Thomas

--
C'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)