Results 1 to 2 of 2

Thread: MySQL Damerau-Levenshtein distance function

  1. #1
    Join Date
    Mar 2008
    Location
    pd
    Posts
    497
    Rep Power
    144

    MySQL Damerau-Levenshtein distance function

    I recently used someone's open-source Levenshtein distance function to generate search key suggestions. It was good, but Damerau-Levenshtein gives better results when users type characters in the wrong order.

    In case anybody is considering matching strings based on similarity and can add a function to their MySQL server to do it (it's not hard, no need to even stop the server process) I've published 3 C++ source code versions of the function on my blog: a basic function, one with a limit to greatly improve performance, and one with an extra hack in for that last 10% of performance increase.

    Seanís blog Blog Archive Damerau-Levenshtein algorithm: Levenshtein with transpositions

    Caveat: they've had very little testing. They seem to work just fine for me, but if anybody knows of another Damerau-Levenshtein function I can test them against, let me know and I'll do a proper comparison. PHP has a levenshtein function, but not a damerau-levenshtein, so far as I know.

  2. #2
    Join Date
    Mar 2008
    Location
    pd
    Posts
    497
    Rep Power
    144

    Java Damerau-Levenshtein edit distance / string matching methods

    Recently finished a code review of the Java version I wrote, and there were a few pesky bugs lingering in the code! I've extended the regression tests included in the code and made the code much more like the pseudo code in the Wikipedia article. I've also made an online test page available at spider.my, so you can test the methods there:

    Here's a comparison of 'webmastermalaysia' and 'webamstermalayisa':

    My Spider - Damerau Levenshtein demonstration

    There are 'performance' versions of the methods that return as soon as the strings are more different than a supplied threshold. If you're comparing large, mostly quite different strings, looking for a good match, the performance benefit can be enormous:

    My Spider - Damerau Levenshtein demonstration

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. php ob_start function
    By Redzuan9999 in forum Website Programming
    Replies: 2
    Last Post: 04-12-2007, 10:38 AM
  2. Does distance (location) of server host affect the speed?
    By EsLobos in forum Paid Hosting Discussion Forum
    Replies: 7
    Last Post: 31-07-2006, 12:02 PM
  3. print function
    By ardella in forum Website Programming
    Replies: 2
    Last Post: 13-05-2004, 12:50 AM
  4. stripslashes() function for JSP?
    By lcf in forum Website Programming
    Replies: 3
    Last Post: 21-04-2004, 10:06 PM
  5. mysql x boleh fully function la
    By dyda in forum Website Programming
    Replies: 3
    Last Post: 16-02-2004, 03:58 PM

Posting Permissions

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

Search Engine Optimization by vBSEO 3.5.0 RC1 PL1

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