Relative_Levenshtein UDF contribution

Posted by IVO / on 01/27/2009 / 7 Comments

The regular (classic) Levenshtein() function computes the minimum number of differences between 2 strings (replacements, deletions, insertions). It is a natural integer number - but it gives no clue how similar are the given strings. I have combined information from several different places in Internet (I do not remember the exact locations, but I do not pretend that I am the author - I just made the things work together) and the result is function Relative_Levenshtein(), which computes the similarity (fractional number between 0 and 1, inclusive) between 2 strings. I also changed the original Joe Conway`s realization of Levenshtein() function to a faster one (1 cycle less).

PATCH is a ZIP file, which contains a standard diff patch file (ivo.patch) as well as the patched versions of:

1. fuzzystrmatch.c

2. fuzzystrmatch.h

3. fuzzystrmatch.sql.in

4. uninstall_fuzzystrmatch.sql

 

 

RSS Feed for this Blog    Comments Feed for this Post   

Comments

  • Boyko says:

    Ще го изпробвам тия дни :) Точно сега работя по задача, за която ми трябваше подобна реализация за pgsql. Ако всичко е ок, ще черпя.

    January 28, 2009 at 4:40 PM | Permalink

  • IVO says:

    Да знаеш, че налитам повече на хапване, отколкото на пийване (на него хич) ...
    Имам и друга функция fuzzy_match(), обаче съм я писал за MySQL - още не съм я преправил за PostgreSQL (не че е трудно, просто не ми е трябвала). Та с нея може да се търси дума в текст с допустим брой правописни грешки (или разлики). Например ако се търси думата "Solomon" с 1 допустима разлика - ще има съвпадение и за думата "Salomon". Същото го има в оригиналния UNIX-ски GREP.

    January 29, 2009 at 6:35 PM | Permalink

  • Boyko says:

    Няма проблем :) При това, яденето излиза по на далавера ;) Това което всъщност ми трябва е следното :
    Задача: Намери точен адрес или намери най близкото приближение, при условие, че клиента потенциално би сбъркал буква или две в това което търси. Този (горния) алгоритъм върши чудесна работа (доказано) и за мен е направо идеално, че го има на ниво UDF в PGSQL.

    January 29, 2009 at 9:06 PM | Permalink

  • IVO says:

    Кой точно алгоритъм имаш впредвид, че го има като UDF за PGSQL - Relative_Levenshtein, или fuzzy_match (дето още не съм го преправил) ? fuzzy_match мислех да го използвам първоначално когато някой дилър се опита да въведе клиент, който вече е въведен от друг дилър. Обаче за да има реален ефект (хватката с правописните грешки) - трябва да се прави сравнение между всяка от думите в 2-та низа. Прецених, че ще е по-просто, ако просто премахвам интервалите и пунктуационните символи (понеже може да има имена и на чужди езици) и сравнявам целите низове чрез Relative_Levenshtein.

    January 30, 2009 at 12:44 PM | Permalink

  • Ivan says:

    You can also download fuzzy.zip from the BGPUG code repository.

    February 2, 2009 at 11:20 AM | Permalink

  • Peter says:

    Браво! Аз използвам Soundex и Double Metaphone UDFs, като последният работи по-добре с кирилица (след транслитерация на латиница). Ако някой е навит да разгледа чисто теоретично въпроса с реализацията на алгоритъм подобен на Double Metaphone за низове с текст на кирилица, мисля ще е от полза за всички, които работят с такива документи, а не само с документи на латиница/английски език.

    September 25, 2009 at 3:44 PM | Permalink

  • IVO says:

    Не съм специалист по алгоритмите (все пак съм ТУ, а не СУ) - обаче двойния метафон ми се струва по-сложния вариант отколкото относителния Левенщайн - аргументът ми е, че метафона връща като резултат текстов низ - и в резултат пак трябва да сравняваш низове, само дето ще са по-кратки от оригиналните такива; Левенщайн връща като резултат число между 0 и 1, което директно показва колко подобни в изписването (а не в изговарянето) са два низа.

    November 4, 2009 at 2:24 PM | Permalink

 

Join this Group Now!

Forgot Password?

Bulgarian PostgreSQL User Group
Powered by Groupsite.com

Visibility Limited Membership By Invitation or Approved Request Default Profile Professional

Your Status Not Logged-In