Req: Need suggestions for search algorithm

[Ben Fidge]

Hi

I'm working on a site which requires the users to specify a hotel at which
they're staying in London. The complete list of hotels comes to something
like 1600 records. Each record consists of Hotel Name, Street Address and
Postcode.

We need to make it as simple as possible for users to pick their hotel, but
I don't want to put 1600 hotel names in a drop-down list, and we have to
consider the fact that not every user is going to know the full name and
address of their hotel. Furthermore, we have to assume that misspellings
will be common and also the shortening of address elements. For example,

"Road" could be entered as "Rd", "Rd." or "Road"
"Street" could be "St", "St." or "Street"
"Lane" could be "Ln", "Lne" or "Lane" etc

Taking all these scenarios and requirements into hand can anyone suggest a
fool-proof yet easy to use mechanism for providing this sort of search
capability on a web-page?

I'm using ADO.NET to interface to Sql Server 2000 db. Would Full-text
indexing on this table be of any use?

I'm intersted to know how people would go about this themselves.

Thanks

Ben

 

[Kevin Spencer]

Hi Ben,

A little while ago, just before Google went public, Microsoft tried to buy
them. Why? Because they have the best search engine in the world. But, you
might ask, why would Microsoft, a software company that employs thousands of
programmers need to buy a search engine, when they can write their own? The
answer is simple: Google does almost nothing but search software. And it is
not easy to write. In fact, Google has thousands of computers to share the
load. Their search routines, while secret, must be humongous.

So, in answer to your question:

Taking all these scenarios and requirements into hand can anyone suggest a
fool-proof yet easy to use mechanism for providing this sort of search
capability on a web-page?

The answer is "no." Not fool-proof, and by no stretch of the imagination
easy!

--
HTH,

Kevin Spencer
Microsoft MVP
..Net Developer
What You Seek Is What You Get.

 

[Ben Fidge]

Hi Kevin,

I appreciate your comments but I'm still left with the task of providing
this functionality to our end-users. As you are probably aware, the average
web-user gets distracted or bored very easily, so the easier and more
intuitive I can make an interface the better. The aim here is to guide their
selection of hotel from a list using the most efficient and time-saving
means possible. As programmers, we need to be aware that 99% of the time our
users are not techies, but just want to buy products quickly and easily.

This is not an uncommon scenario, and i'm sure there's many developers out
there who may offer some insight into how they've tackled similar problems
in the past, be it a propritry solution or some third-party library we can
buy in.

Kind regards

Ben

 

[Kevin Spencer]

in the past, be it a propritry solution or some third-party library we can

buy in.

Now, there's an idea. Try Googling it. I wouldn't be surprised if you can
find something that works fairly well.

--
HTH,

Kevin Spencer
Microsoft MVP
..Net Developer
What You Seek Is What You Get.

 

[Patrice]

I saw once someone who used an algorithm that computes the minimal amount of
elementary changes (ie. letter deletion or letter addition and perhaps
swaps) to match a particular target word. It gives a kind of "proximity"
level between two words...

If I remember I suggested to divide this result by the length of the word to
have a similar range regardless of the length word (to have a number of
changes per letter rather than just a number of changes).

Unfortunately I don't remember how it's named but you should hopefully find
it from its description

Patrice


--

 

[Shane Thomas]

Now, there's an idea. Try Googling it. I wouldn't be surprised if you can
find something that works fairly well.

I think you might even be able to license Google technology...

 

[Patrice]

This is the "Levenshtein Distance" also called sometimes the "Edit
Distance".

Try :
http://www.merriampark.com/ld.htm

Patrice

--

 

[Bruce Barker]

you need to write an address normalization routine. In the US several exist
for use CRIS tapes (address lists from the post office). if you look for
address matching software in the UK you may find one. YOu local post office
can probably give you rules.

a street address is usually in the format (US anyway - I don't know UK)

<house number> <optional direction> <street name(s)> <suffix> <optional
direction>

ex:

123 n 123 st
123 123 st nw

you sould remove periods, convert suffixs (place, way, avenue, blvd) to a
standard. i usually do a phonetic of the street name (might be able to use
the sqlserver one) to catch spelling errors. with treet and number, you can
find missing suffix and direction

ex

user enters: 1234 main

computer responds did you mean: 1234 main street or 1234 main blvd?.

you can refine, by linking to hotel name.


-- bruce (sqlwork.com)

 

[Ben Fidge]

Hi Patrice,

I have heard of Levenshtein Distance algorithm. I'll look to see how I can
use it.

Thanks for the positive help.

Ben