+- delphi4arab منتديات دلفي للعرب (https://delphi4arab.net/forum)
+-- قسم : منتديات دلفي التقنية (https://delphi4arab.net/forum/forumdisplay.php?fid=6)
+--- قسم : دلفي و التعامل مع قواعد البيانات (https://delphi4arab.net/forum/forumdisplay.php?fid=23)
+--- الموضوع : Levenshtein distance خوارزمية مقارنة (/showthread.php?tid=4932)
Levenshtein distance خوارزمية مقارنة - kachwahed - 19-02-2013
السلام عليكم ورحمة الله
Levenshtein distance إحدى أشهر خوارزميات المقارنة بين النصوص أو قياس النصوص String metric
نفس المبدأ أيضا خوارزمية Damerau–Levenshtein distance مع اختلاف (حالة التبديل).
يقوم مبدأ عمل الخوارزمية على حساب الفرق بين نصين Edit distance، حيث فرق نصين هو عدد التعديلات تقوم بها على نص لجعله مطابقا لنص آخر، مثال:
لجعل dlepn تعادل delphi يلزم القيام بثلاث تغييرات:
1- قلب الحرفين e وl
2- تبديل n بـ h
3- إضافة i إلى النهاية
ثلاث تعديلات، إذن:
PHP كود :
DamerauLevenshtein('dlepn', 'delphi') = 3
- تبديل الأحرف ABC-ACB
- إضافة: ABC-AB
- حذف: ABC-ABCD
- تغيير: ABC-ABD
قواعد البيانات:
باستخدام محرك SQL يدعم UDF يمكنك نقل الدالة (VBA في حالة Access مثلا)، ثم الاستعلام باستخدام الجداء أو CROSS JOIN مع شرط لتحديد دقة الربط أو التسامح Tolerance
مثال:
PHP كود :
SELECT Person.Name, Employee.Name, LevenshteinDistance([Person].[Name],[Employee].[Name]) AS Distance
FROM Person, Employee
WHERE (((Levenshtein([Person].[Name],[Employee].[Name]))<=2));
الاستخدامات:
التحاليل الرياضية، تحاليل DNA، التدقيق النحوي Spell check، قواعد البيانات، كشف الثغرات وغيرها...
لمن يفضل شرح مصور:
PHP كود :
http://www.youtube.com/watch?v=dUSqwTC8TM8
http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance
نسخة سريعة:
PHP كود :
uses
Math;
function LevenshteinDistance(const s, t: string): integer; {inline;} //<- D2005Up
var
d : array of array of integer;
n, m, i, j : integer;
begin
n := length(s);
m := length(t);
if n = 0 then Exit{(m)}; //<- D2009Up
if m = 0 then Exit{(n)}; //<- D2009Up
SetLength(d, n + 1, m + 1);
for i := 0 to n do d[i, 0] := i;
for j := 0 to m do d[0, j] := j;
for i := 1 to n do
for j := 1 to m do
d[i, j] := Min(Min(d[i-1, j]+1, d[i,j-1]+1), d[i-1,j-1]+Integer(s[i] <> t[j]));
Result := d[n, m];
end;
مرفق مثال لصاحبه من delphiarea وملف ق.ب. Access.
PHP كود :
http://www.delphiarea.com/articles/how-to-match-two-strings-approximately/
بالتوفيق.