Professional Web Applications Themes

Levenshtein Based Search Suggest - MySQL

Ok - Here is a situational problem. I want to implement a search query using the Levenshtein algorithm to suggest what the user "might" have meant (those suggestions already being entries in the database). Simple, just create a user defined function, and run the thing purely in MySQL. Problem solved, right? Wrong. My client's host is running MySQL version 4.1.21, which pre-dates the user defined function capability. Doh. So the only viable option I see is to select all the possible values from the database, create a php array with these values and run the built in php Levenshtein function ...

  1. #1

    Default Levenshtein Based Search Suggest

    Ok -

    Here is a situational problem. I want to implement a search query using
    the Levenshtein algorithm to suggest what the user "might" have meant
    (those suggestions already being entries in the database). Simple, just
    create a user defined function, and run the thing purely in MySQL.

    Problem solved, right?
    Wrong.

    My client's host is running MySQL version 4.1.21, which pre-dates the
    user defined function capability. Doh. So the only viable option I see
    is to select all the possible values from the database, create a php
    array with these values and run the built in php Levenshtein function
    against them all. This seems wasteful for something that will be so
    frequently used.

    Is there anyway I can relegate the Levenshtein algorithm back to MySQL
    from whence it came, without the use of user defined functions?

    Thanks,

    -- whit

    Whit Guest

  2. #2

    Default Re: Levenshtein Based Search Suggest

    Whit wrote: 

    I think you have confused user defined functions with stored procedures.
    UDF's are supported in MySQL all the way back -- certainly they are
    supported in 4.1.
    See http://dev.mysql.com/doc/refman/4.1/en/adding-udf.html

    You must write the functions in some compiled language, like C/C++. You
    can't write the function in the procedural SQL language, as you would
    with triggers and stored procedures in MySQL 5.0.

    Regards,
    Bill K.
    Bill Guest

  3. #3

    Default Re: Levenshtein Based Search Suggest

    Whit wrote: 

    Funny coincidence, I posted about making a Levenshtein UDF just a few
    days ago. If your target platform is Win32, perhaps I can send the DLL
    to you once I finish it.

    Cheers,
    Nicholas Sherlock

    --
    http://www.sherlocksoftware.org
    Nicholas Guest

  4. #4

    Default Re: Levenshtein Based Search Suggest

    Please forgive me, I am quite new to all this. After close examination
    and some manual-reading, I did in fact mean a stored procedure. A user
    defined function would certainly work, but I running on a host that I
    don't have control over, so that technique might prove problematic.

    I've spoken with my host and they said they would be willing to move me
    to a server with MySQL5. So turns out I can do stored proc's. Now I
    just have to learn them, then implement Levenshtein. Anyone have any
    slick tutorials that can walk me through strored procedures?

    Thanks,

    -- whit

    p.s. Nicholas, I am running on a *nix server, but even if I wasn't, I
    think learning stored procs will be good for me. If, er, ah, WHEN I can
    figure out how to do it I would be happy to send you the proc. :)

    Nicholas Sherlock wrote: 
    >
    > Funny coincidence, I posted about making a Levenshtein UDF just a few
    > days ago. If your target platform is Win32, perhaps I can send the DLL
    > to you once I finish it.
    >
    > Cheers,
    > Nicholas Sherlock
    >
    > --
    > http://www.sherlocksoftware.org[/ref]

    Whit Guest

  5. #5

    Default Re: Levenshtein Based Search Suggest

    How do I create the 2-d array to maintain the results of the dynamic
    algorithm? I can't seem to find an array structure in mysql procedures
    ....

    -- whit

    Bill Karwin wrote: 
    >
    > I think you have confused user defined functions with stored procedures.
    > UDF's are supported in MySQL all the way back -- certainly they are
    > supported in 4.1.
    > See http://dev.mysql.com/doc/refman/4.1/en/adding-udf.html
    >
    > You must write the functions in some compiled language, like C/C++. You
    > can't write the function in the procedural SQL language, as you would
    > with triggers and stored procedures in MySQL 5.0.
    >
    > Regards,
    > Bill K.[/ref]

    Whit Guest

  6. #6

    Default Re: Levenshtein Based Search Suggest

    Whit wrote: 

    Right, there is no array datatype in MySQL.

    I really don't think MySQL stored procedures are the best solution for
    this task. The stored procedure language is a pretty lackluster
    language for general purpose tasks.

    Personally, I never use stored procs.

    Regards,
    Bill K.
    Bill Guest

  7. #7

    Default Re: Levenshtein Based Search Suggest

    A user defined function would probably fit the bill ... but if I can't
    use these because of my host ... Are there any alternatives to using
    php to do the grunt work?

    -- whit

    Bill Karwin wrote: 
    >
    > Right, there is no array datatype in MySQL.
    >
    > I really don't think MySQL stored procedures are the best solution for
    > this task. The stored procedure language is a pretty lackluster
    > language for general purpose tasks.
    >
    > Personally, I never use stored procs.
    >
    > Regards,
    > Bill K.[/ref]

    Whit Guest

  8. #8

    Default Re: Levenshtein Based Search Suggest

    On Thu, 07 Sep 2006 19:28:28 -0700, Bill Karwin wrote: 
    >
    > Right, there is no array datatype in MySQL.
    >
    > I really don't think MySQL stored procedures are the best solution for
    > this task. The stored procedure language is a pretty lackluster
    > language for general purpose tasks.
    >
    > Personally, I never use stored procs.[/ref]

    2d array? Sounds like a temp table to me...

    --
    27. I will never build only one of anything important. All important systems
    will have redundant control panels and power supplies. For the same reason
    I will always carry at least two fully loaded weapons at all times.
    --Peter Anspach's list of things to do as an Evil Overlord
    Peter Guest

  9. #9

    Default Re: Levenshtein Based Search Suggest

    I wish I had an option, but I think a stored procedure is my only
    choice. I know it shant be pretty, but the alternative is a huge
    data-dump from mysql into a php script that does the work. I think not.

    So how could I implement a 2-d array in a stored proc? Temp table?

    Thanks for your consideration everybody,

    -- whit


    Bill Karwin wrote: 
    >
    > Right, there is no array datatype in MySQL.
    >
    > I really don't think MySQL stored procedures are the best solution for
    > this task. The stored procedure language is a pretty lackluster
    > language for general purpose tasks.
    >
    > Personally, I never use stored procs.
    >
    > Regards,
    > Bill K.[/ref]

    Whit Guest

  10. #10

    Default Re: Levenshtein Based Search Suggest

    Whit wrote: 

    Note that you only need two rows in Levenshtein, so if you have 1D
    arrays, you should be fine.

    Cheers,
    Nicholas Sherlock

    --
    http://www.sherlocksoftware.org
    Nicholas Guest

Similar Threads

  1. Please suggest
    By Support in forum ASP.NET Web Services
    Replies: 1
    Last Post: July 5th, 04:28 PM
  2. Replies: 7
    Last Post: October 31st, 06:28 AM
  3. What a little UPS you suggest ?
    By Ben Kamen in forum AIX
    Replies: 0
    Last Post: August 14th, 06:00 PM
  4. scoring/sorting db search results based on score
    By Dave in forum PHP Development
    Replies: 5
    Last Post: July 21st, 10:21 AM
  5. What do you suggest ?
    By Joachim Smit in forum Debian
    Replies: 0
    Last Post: July 13th, 04:40 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139