Subject: question regarding content search in array with PHP

From: ik <[email-masked]>
Date: Tue, 18 Dec 2007 19:06:55 +0200

Hello list,

I have an array that for the example will look as follows:

linux, windows, mac os, beos, os/2, freebsd, netbsd, irix ....

And a string:

"linux kernel 2.6.24"

Now I wish to find the closest value of the string in the array -> "linux".
But the problem as you can see, is that the string contain more
content then the array value.
I can think on many unefficient ways to find the part of string as an
array value, but I'm looking for an efficient way to do it. specially
if I need to serve a lot of strings on after the other...
The problem is, that I must use PHP (because I can think on an answer
using Perl, that I haven't tested).

Any ideas how I can do it in an efficient way ?

Thanks,
Ido
-- 
http://ik.homelinux.org/

---

From: Omer Zak <[email-masked]>
Date: Tue, 18 Dec 2007 19:45:43 +0200

Since you want to use PHP, I assume that you want to do this when
processing Web requests.
Therefore, I would store the array as a DB (such as MySQL) table.

The table will have two columns:
- Word (indexed, non-unique key)
- FullString

For 'linux', you'll have
'linux','linux'

For 'mac os', you'll have
'mac','mac os'
'os','mac os'

Then, when you get the string from the user, split it into words and
query for full strings corresponding to each word (using, for example:
SELECT FullString FROM StringsTable WHERE Word='os';
Of course, you should use the appropriate prepared queries to guard
against SQL injection vulnerabilities).

Now you'll have small number of full strings to be considered, and can
apply your complicated and inefficient heuristic algorithm to determine
which full string corresponds best to the user's string.

                                      --- Omer

-- 
MS-Windows is the Pal-Kal of the PC world.
My own blog is at http://www.zak.co.il/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS:  at http://www.zak.co.il/spamwarning.html

---

From: "Chen Shapira" <[email-masked]>
Date: Tue, 18 Dec 2007 20:20:04 -0800

If you don't need persistence for the array, don't use a DB such as
MySQL. DBs write everything to the disk. They are highly optimized to
never ever lose data, so they write to disk a lot. Then they read from
disk. IO operations are slow. So slow that you are probably better off
with the old algorithm.
If you want to go the DB way (and I certainly hope you'll find a
better way), try an in-memory database. As an Oracle DBA, I'll
recommend TimesTen - Oracle's in-memory database, but I'm sure you can
find an open-source solution as well.

Chen

---

From: ik <[email-masked]>
Date: Wed, 19 Dec 2007 20:48:59 +0200

First of all thank you for the answers.

I found a solution thanks to Oded Arbel, without using database, and
it is O(2*N) (if I remember the subject of complexity correctly).

It works as follows:

foreach ($names as $name_index => $name_value) {
   foreach ($namelist as $list_index => $list_value) {
      if (strncmp($list_value, $name_value, strlen($list_value)) == 0) {
         $name_found[] = $name_value;
      }
   }
}

Ido

-- 
http://ik.homelinux.org/

---

From: Shlomi Fish <[email-masked]>
Date: Sat, 22 Dec 2007 19:56:51 +0200

> it is O(2*N) (if I remember the subject of complexity correctly).

O(2*N) complexity is equivalent to O(N). Maybe you've meant O(N^2)? Your 
code's complexity seems to be O(N^2) or even O(N*M) where N and M are 
different scales.

> foreach ($names as $name_index => $name_value) {

You're not making use of $name_index, so I think you can simply use:

<<<
foreach ($names as $name_value) {

>          $name_found[] = $name_value;

This code will add $name_value to $name_found multiple times - once for each 
matching value in $namelist. If you don't want that, add a "break".

BTW, I found this code a bit hard to understand. I would choose a better 
variable naming if I were you.

Regards,

	Shlomi Fish

> >  > apply your complicated and inefficient heuristic algorithm to
> >  > determine which full string corresponds best to the user's string.
> >  >
> >  > --- Omer
> >  >
> >  > > Now I wish to find the closest value of the string in the array ->
> >  >
> >  > "linux".
> >  >
> >  > > I can think on many unefficient ways to find the part of string as
> >  > > an array value, but I'm looking for an efficient way to do it.
> >  > > specially if I need to serve a lot of strings on after the other...
> >  > > The problem is, that I must use PHP (because I can think on an
> >  > > answer using Perl, that I haven't tested).
> >  > >
> >  > They do not represent the official policy of any organization with
> >  > which I may be affiliated in any way.

---------------------------------------------------------------------
Shlomi Fish      [email-masked]
Homepage:        http://www.shlomifish.org/

I'm not an actor - I just play one on T.V.