Aproximative string matching

[javuchi]

I'm searching for a library which makes aproximative string matching,
for example, searching in a dictionary the word "motorcycle ", but
returns similar strings like "motorcicle ".

Is there such a library?

[elbertlev@hotmail.com]

Re: Aproximative string matching

This algorithm is called soundex. Here is one implementation example.

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52213

here is another:

http://effbot.org/librarybook/soundex.htm

[elbertlev@hotmail.com]

Re: Aproximative string matching

This algorithm is called soundex. Here is one implementation example.

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52213

here is another:

http://effbot.org/librarybook/soundex.htm

[Steven D'Aprano]

Re: Aproximative string matching

elbertlev@hotma il.com wrote:
[color=blue]
> This algorithm is called soundex. Here is one implementation example.
>
> http://aspn.activestate.com/ASPN/Coo...n/Recipe/52213
>
> here is another:
> http://effbot.org/librarybook/soundex.htm[/color]

Soundex is *one* particular algorithm for approximate
string matching. It is optimised for matching
Anglo-American names (like Smith/Smythe), and is
considered to be quite old and obsolete for all but the
most trivial applications -- or so I'm told.

Soundex will not match arbitrary changes -- it will
match both cat and cet, but it won't match cat and mat.

A more sophisticated approximate string matching
algorithm will use the Levenshtein distance. You can
find a Useless implementation here:

http://www.uselesspython.com/download.php?script_id=108

Given a function levenshtein(s1, s2) that returns the
distance between two strings, you could use it for
approximate matching like this:

def approx_matching (strlist, target, dist=1):
"""Matches approximately strings in strlist to
a target string.

Returns a list of strings, where each string
matched is no further than an edit distance of
dist from the target.
"""
found = []
for s in strlist:
if levenshtein(s, target) <= dist:
found.append(s)
return s



--
Steven.

[Steven D'Aprano]

Re: Aproximative string matching

elbertlev@hotma il.com wrote:
[color=blue]
> This algorithm is called soundex. Here is one implementation example.
>
> http://aspn.activestate.com/ASPN/Coo...n/Recipe/52213
>
> here is another:
> http://effbot.org/librarybook/soundex.htm[/color]

Soundex is *one* particular algorithm for approximate
string matching. It is optimised for matching
Anglo-American names (like Smith/Smythe), and is
considered to be quite old and obsolete for all but the
most trivial applications -- or so I'm told.

Soundex will not match arbitrary changes -- it will
match both cat and cet, but it won't match cat and mat.

A more sophisticated approximate string matching
algorithm will use the Levenshtein distance. You can
find a Useless implementation here:

http://www.uselesspython.com/download.php?script_id=108

Given a function levenshtein(s1, s2) that returns the
distance between two strings, you could use it for
approximate matching like this:

def approx_matching (strlist, target, dist=1):
"""Matches approximately strings in strlist to
a target string.

Returns a list of strings, where each string
matched is no further than an edit distance of
dist from the target.
"""
found = []
for s in strlist:
if levenshtein(s, target) <= dist:
found.append(s)
return s



--
Steven.

[Tim Roberts]

Re: Aproximative string matching

"javuchi" <javuchi@gmail. com> wrote:[color=blue]
>
>I'm searching for a library which makes aproximative string matching,
>for example, searching in a dictionary the word "motorcycle ", but
>returns similar strings like "motorcicle ".
>
>Is there such a library?[/color]

There is an algorithm called Soundex that replaces each word by a
4-character string, such that all words that are pronounced similarly
encode to the same string.

The algorithm is easy to implement; you can probably find one by Googling.
--
- Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

[Tim Roberts]

Re: Aproximative string matching

"javuchi" <javuchi@gmail. com> wrote:[color=blue]
>
>I'm searching for a library which makes aproximative string matching,
>for example, searching in a dictionary the word "motorcycle ", but
>returns similar strings like "motorcicle ".
>
>Is there such a library?[/color]

There is an algorithm called Soundex that replaces each word by a
4-character string, such that all words that are pronounced similarly
encode to the same string.

The algorithm is easy to implement; you can probably find one by Googling.
--
- Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

[Daniel Dittmar]

Re: Aproximative string matching

javuchi wrote:[color=blue]
> I'm searching for a library which makes aproximative string matching,
> for example, searching in a dictionary the word "motorcycle ", but
> returns similar strings like "motorcicle ".
>
> Is there such a library?
>[/color]

agrep (aproximate grep) allows for a certain amount of errors and there
exist Python bindings (http://www.bio.cam.ac.uk/~mw263/pyagrep.html)

Or google for "agrep python".

Daniel

[Daniel Dittmar]

Re: Aproximative string matching

javuchi wrote:[color=blue]
> I'm searching for a library which makes aproximative string matching,
> for example, searching in a dictionary the word "motorcycle ", but
> returns similar strings like "motorcicle ".
>
> Is there such a library?
>[/color]

agrep (aproximate grep) allows for a certain amount of errors and there
exist Python bindings (http://www.bio.cam.ac.uk/~mw263/pyagrep.html)

Or google for "agrep python".

Daniel

[Fredrik Lundh]

Re: Aproximative string matching

Tim Roberts wrote:
[color=blue][color=green]
> >I'm searching for a library which makes aproximative string matching,
> >for example, searching in a dictionary the word "motorcycle ", but
> >returns similar strings like "motorcicle ".
> >
> >Is there such a library?[/color]
>
> There is an algorithm called Soundex that replaces each word by a
> 4-character string, such that all words that are pronounced similarly
> encode to the same string.
>
> The algorithm is easy to implement; you can probably find one by Googling.[/color]

Python used to ship with a soundex module, but it was removed
in 1.6, for various reasons. here's a replacement:

http://orca.mojam.com/~skip/python/soundex.py

</F>

[Fredrik Lundh]

Re: Aproximative string matching

Tim Roberts wrote:
[color=blue][color=green]
> >I'm searching for a library which makes aproximative string matching,
> >for example, searching in a dictionary the word "motorcycle ", but
> >returns similar strings like "motorcicle ".
> >
> >Is there such a library?[/color]
>
> There is an algorithm called Soundex that replaces each word by a
> 4-character string, such that all words that are pronounced similarly
> encode to the same string.
>
> The algorithm is easy to implement; you can probably find one by Googling.[/color]

Python used to ship with a soundex module, but it was removed
in 1.6, for various reasons. here's a replacement:

http://orca.mojam.com/~skip/python/soundex.py

</F>