Find longest matching key

[Thomas Mlynarczyk]

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)

[Toby A Inkster]

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($aSubjec t[$key]))
$key = preg_replace('/\.?[^\.]*$/', '', $key);

if (strlen($key))
printf("Searche d for '%s'. Closest match was '%s', value %s.\n",
$a,
$key,
$aSubject[$key]);
else
printf("Searche d 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($haystac k[$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("Searche d for '%s'. Closest match was '%s', value %s.\n",
$a,
$key,
$value);
else
printf("Searche d 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_gl adrags.ogg.]

Belgium

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

[Thomas Mlynarczyk]

Re: Find longest matching key

Also sprach Toby A Inkster:

foreach ($aSearch as $a)
{
$key = $a;
while (strlen($key) && !isset($aSubjec t[$key]))
$key = preg_replace('/\.?[^\.]*$/', '', $key);
>
if (strlen($key))
printf("Searche d for '%s'. Closest match was '%s', value %s.\n",
$a,
$key,
$aSubject[$key]);
else
printf("Searche d 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 "indivisibl e" 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 "indivisibl e"
'A'
)

2)
foreach ( $aSearch as $sKey )
{
if ( array_key_exist s( $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_exist s( $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)

[Csaba Gabor]

Re: Find longest matching key

On Nov 17, 6:13 pm, "Thomas Mlynarczyk" <tho...@mlynarc zyk-
webdesign.dewro te:

$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 longestMatching Key ($aSrch, $aSubj) {
if (array_key_exis ts($k=implode(" .", $aSrch), $aSubj)) return $k;
for ($i=sizeof($aSr ch);$k=substr($ k,0,-strlen($aSrch[--$i])-1);)
if (array_key_exis ts($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

[Thomas Mlynarczyk]

Re: Find longest matching key

Also sprach Csaba Gabor:

function longestMatching Key ($aSrch, $aSubj) {
if (array_key_exis ts($k=implode(" .", $aSrch), $aSubj)) return $k;
for ($i=sizeof($aSr ch);$k=substr($ k,0,-strlen($aSrch[--$i])-1);)
if (array_key_exis ts($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)