Best algorithm for search engine?

veshman

Hi, I'm trying to build a searchable database of diagnosis codes and I'm finding out that making intelligent searches is not as easy as I though it would be.

I have a database of about 15000+ entries. These are the fields:

CodeID
DxName
DxExcludes

Essentially, I only need to be able to search the DxName field, which can be very long, depending on how many diagnoses use the same code.

I want the search engine to be able to find partial word matches (i.e. TYMPANIC and tuboTYPMANIC) and close matches (e.g. RUPTURE even if you typed in RUPTURED or PERFORATED even if you typed in PERFORATION). I also need it to be able to find things even they are not next to each other (i.e. a search for "serosanguinous externa" should find "serosanginous otitis externa").
I need to be able to score these in a way that the most likely diagnosis will be at the top. This is important because typing in common things like "otitis" will yield a relatively large number of results. If I need to use any kind of OR statement, the number of results becomes huge. One way I will tackle this problem is to add a field which I can use to flag common diagnoses, since there will only be a few hundred. That way, I can sort by that column first.

Here is a sample of the data (a SELECT query on like "tympanic"):

| code | dxname | dxexclude |
| 384 |Other disorders of tympanic membrane||
| 384.8 |Other specified disorders of tympanic membrane||
| 384.20 |Perforation of tympanic membrane, unspecified||
| 384.21 |Central perforation of tympanic membrane||
| 384.23 |Other marginal perforation of tympanic membrane||
| 384.24 |Multiple perforations of tympanic membrane||
| 384.25 |Total perforation of tympanic membrane||
| 385.01 |Tympanosclerosis involving tympanic membrane only||
| 384.9 |Unspecified disorder of tympanic membrane||
| 384.82 |Atrophic nonflaccid tympanic membrane||
| 385.02 |Tympanosclerosis involving tympanic membrane and ear ossicles||
| 389.02 |Conductive hearing loss, tympanic membrane||
| 384.22 |Attic perforation of tympanic membrane! Pars flaccida||
| 385.03 |Tympanosclerosis involving tympanic membrane, ear ossicles, and middle ear||
| 384.81 |Atrophic flaccid tympanic membrane! Healed perforation of ear drum||
| 384.2 |Perforation of tympanic membrane! Perforation of ear drum:! NOS! persistent posttraumatic! postinflammatory|Excludes: otitis media with perforation of tympanic membrane (382.00-382.9)! traumatic perforation [current injury] (872.61)|| code | dxname | dxexclude |
| 384 |Other disorders of tympanic membrane||
| 384.8 |Other specified disorders of tympanic membrane||
| 384.20 |Perforation of tympanic membrane, unspecified||
| 384.21 |Central perforation of tympanic membrane||
| 384.23 |Other marginal perforation of tympanic membrane||
| 384.24 |Multiple perforations of tympanic membrane||
| 384.25 |Total perforation of tympanic membrane||
| 385.01 |Tympanosclerosis involving tympanic membrane only||
| 384.9 |Unspecified disorder of tympanic membrane||
| 384.82 |Atrophic nonflaccid tympanic membrane||
| 385.02 |Tympanosclerosis involving tympanic membrane and ear ossicles||
| 389.02 |Conductive hearing loss, tympanic membrane||
| 384.22 |Attic perforation of tympanic membrane! Pars flaccida||
| 385.03 |Tympanosclerosis involving tympanic membrane, ear ossicles, and middle ear||
| 384.81 |Atrophic flaccid tympanic membrane! Healed perforation of ear drum||
| 384.2 |Perforation of tympanic membrane! Perforation of ear drum:! NOS! persistent posttraumatic! postinflammatory|Excludes: otitis media with perforation of tympanic membrane (382.00-382.9)! traumatic perforation [current injury] (872.61)|

Any guidance and hand holding is greatly appreciated!

Regards,

Bhavesh Patel

jeremuck

a good place to start is with LIKE and wildcard syntax.

LIKE "%RUPTURE%" will find RUPTURED

and will work for every example you listed, EXCEPT:

LIKE "%PERFORATION%" will not find PERFORATED.

You can look on the mysql site for documentation.

if you want to get really fancy, I suppose you could use some algorithm to parse words into their word roots and put wildcards on that. You might also find words that sound alike using soundex and metaphone and whatnot.

You should get a book on mysql or something.

veshman

Hi, thanks for your response!

Well, I've played around with the like statement already, and it works OK, but it is not that great which is what prompted this post.

For example, if someone typed in "serosanguinous externa", nothing would come up.

LIKE '%serosanguinous externa%' will miss "serosanguinous otitis externa"

There does not seem to be a way in sql<version 4.0 to do a boolean search (like '%serosanguinous%' and '%otitis%').

Parsing the language would not be too hard. I could strip endings such as -ed, -tion, -itis and use Like or regexp.

I've heard that LIKE is brutally slow, however. Is REGEXP faster?
I've played around a bit with FULLTEXT and REGEXP and that seems to be more powerful than LIKE.

Will I just have to write some intelligence into a PHP script? What are some good intelligent algorithms?

Thanks,

Bhavesh

PHPdev

This is kind of fast and just off the top of my head... but here goes....

Something you could do is to set a max number of records to be returned... say 50 or 100. So do a search on the exact term the user enteres such as LIKE '%serosanguinous externa%'. Then see how many results that will produce. If that does not meet a the preset limit of 50 or 100, then begin breaking down the search string and doing more queries.

I know there has been tons of research done on searching and search algorythims, but generally these are company trade secrets, my sugestion would be to turn to some Computer Science Journals and maybe even a few AI Journals. They should have information on the type of research you are looking for.

Just my .02

PHPdev

jeremuck

turn "serosanguinous externa"

into "%serosanguinous%" AND "%externa%"

that's not hard at all.

yeah, include some intelligent parsing in your script before you send the query out. It seems like you've already thought through what you need to match.

I guess, overall it depends how fancy you want to get. Have you tried searching for code at various code repositories?
sourceforge.com
phpclasses.com

evolt.org has some articles I've found useful in the past.

jeremuck

I found this:

http://sourceforge.net/projects/dadabik/

this might do what you want.
It looks very useful.

veshman

Thanks for the replies on this. I will check out dadbik, I had heard about it before.

I guess as far as LIKE was concerned, I thought you couldn't do AND

i.e.

SELECT * from TABLE where COLUMN LIKE "%String1%" AND
"%string2%"

I thought LIKE coudn't be used this way.

I'm so new at this..I may have tried it and forgotten what I got.

I'll try it again.

Thanks,

Bhavesh

Vigil

I guess as far as LIKE was concerned, I thought you couldn't do AND

i.e.

SELECT * from TABLE where COLUMN LIKE "%String1%" AND
"%string2%"

I thought LIKE coudn't be used this way.

It can't, but you can build it up into "SELECT * from TABLE where field LIKE "%String1%" AND field LIKE
"%string2%" .

Incidentally, and not a problem you face:

If you want to search for multiple strings in multiple fields it can get really messy, because normally you'll need to give each field its own LIKE statement for each search-string. With 4 fields to search and 4 strings to search for, you'll end up with 16 different LIKE statements. And if you use an AND search you may still want to retrieve results that match in any of the fields, not all of them, which means using groups of ORs in parentheses joined with ANDs.

One workaround for this is to use CONCAT_WS(' ', field1, field2, ... fieldn) LIKE "%String1%" AND CONCAT_WS(' ', field1, field2, ... fieldn) LIKE "%String2%", etc. This joins all the fields you want together into one big lump and searches that lump, instead of searching each field individually.

This may be an extremely inefficient solution, I don't know, but it stops the query string ending up 5 miles long. Maybe I have my priorities wrong; is there a more efficient way to handle multi-field multi-string searches?