By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,850 Members | 967 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,850 IT Pros & Developers. It's quick & easy.

Find longest matching key

P: n/a
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)
Nov 17 '07 #1
Share this Question
Share on Google+
4 Replies


P: n/a
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/
Nov 17 '07 #2

P: n/a
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)
Nov 17 '07 #3

P: n/a
On Nov 17, 6:13 pm, "Thomas Mlynarczyk" <tho...@mlynarczyk-
webdesign.dewrote:
$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
Nov 17 '07 #4

P: n/a
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)
Nov 18 '07 #5

This discussion thread is closed

Replies have been disabled for this discussion.