Levenshtein distance خوارزمية مقارنة

[kachwahed]

السلام عليكم ورحمة الله

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_i...n_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/ 


بالتوفيق.