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" <be*******@btopenworld.com> wrote in message
news:%2****************@TK2MSFTNGP14.phx.gbl... 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

[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" <ke***@DIESPAMMERSDIEtakempis.com> wrote in message
news:e3**************@tk2msftngp13.phx.gbl...

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" <be*******@btopenworld.com> wrote in message
news:%2****************@TK2MSFTNGP14.phx.gbl...

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]

> 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.

"Ben Fidge" <be*******@btopenworld.com> wrote in message
news:uw**************@TK2MSFTNGP15.phx.gbl... 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" <ke***@DIESPAMMERSDIEtakempis.com> wrote in message
news:e3**************@tk2msftngp13.phx.gbl...

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" <be*******@btopenworld.com> wrote in message
news:%2****************@TK2MSFTNGP14.phx.gbl...

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

[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
--

"Ben Fidge" <be*******@btopenworld.com> a écrit dans le message de
news:uw**************@TK2MSFTNGP15.phx.gbl...

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" <ke***@DIESPAMMERSDIEtakempis.com> wrote in message
news:e3**************@tk2msftngp13.phx.gbl...

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" <be*******@btopenworld.com> wrote in message
news:%2****************@TK2MSFTNGP14.phx.gbl...

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

[Shane Thomas]

"Kevin Spencer" <ke***@DIESPAMMERSDIEtakempis.com> wrote in message
news:ke***@DIESPAMMERSDIEtakempis.com:

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.

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

--

-shane

[Patrice]

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

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

Patrice

--

"Patrice" <no****@nowhere.com> a écrit dans le message de
news:%2****************@TK2MSFTNGP12.phx.gbl...

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
--

"Ben Fidge" <be*******@btopenworld.com> a écrit dans le message de
news:uw**************@TK2MSFTNGP15.phx.gbl...

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" <ke***@DIESPAMMERSDIEtakempis.com> wrote in message
news:e3**************@tk2msftngp13.phx.gbl...

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" <be*******@btopenworld.com> wrote in message
news:%2****************@TK2MSFTNGP14.phx.gbl...
> 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
>

[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" <be*******@btopenworld.com> wrote in message
news:%2****************@TK2MSFTNGP14.phx.gbl...

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

[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

"Patrice" <no****@nowhere.com> wrote in message
news:O$**************@TK2MSFTNGP12.phx.gbl...

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

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

Patrice

--

"Patrice" <no****@nowhere.com> a écrit dans le message de
news:%2****************@TK2MSFTNGP12.phx.gbl...

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
--

"Ben Fidge" <be*******@btopenworld.com> a écrit dans le message de
news:uw**************@TK2MSFTNGP15.phx.gbl...

> 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" <ke***@DIESPAMMERSDIEtakempis.com> wrote in message
> news:e3**************@tk2msftngp13.phx.gbl...
> > 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" <be*******@btopenworld.com> wrote in message
> > news:%2****************@TK2MSFTNGP14.phx.gbl...
> >> 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
> >>
> >
> >
>
>