مسافة ليفنشتاين:كيفية التعامل بشكل أفضل مع مواقف تبادل الكلمات؟

Question

لقد حققت بعض النجاح في مقارنة السلاسل باستخدام PHP com.levenshtein وظيفة.

ومع ذلك، بالنسبة لسلسلتين تحتويان على سلاسل فرعية تم تبديل مواضعها، تحسب الخوارزمية تلك السلاسل الفرعية الجديدة بالكامل.

على سبيل المثال:

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

يتم التعامل معها على أنها أقل قواسم مشتركة من:

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

أفضّل الخوارزمية التي رأت أن الأولين كانت أكثر مماثلة.

كيف يمكنني التوصل إلى وظيفة مقارنة يمكنها تحديد السلاسل الفرعية التي غيرت موضعها باعتبارها متميزة عن التعديلات؟

أحد الأساليب المحتملة التي فكرت بها هو وضع كل الكلمات الموجودة في السلسلة حسب الترتيب الأبجدي، قبل المقارنة.يؤدي ذلك إلى إخراج الترتيب الأصلي للكلمات تمامًا من المقارنة.ومع ذلك، فإن الجانب السلبي لذلك هو أن تغيير الحرف الأول فقط من الكلمة يمكن أن يؤدي إلى اضطراب أكبر بكثير مما يجب أن يسببه تغيير حرف واحد.

ما أحاول تحقيقه هو مقارنة حقيقتين عن الأشخاص وهما عبارة عن سلاسل نصية مجانية، وتحديد مدى احتمالية أن تشير هذه الحقائق إلى نفس الحقيقة.قد تكون الحقائق هي المدرسة التي التحق بها الشخص، أو اسم صاحب العمل أو الناشر، على سبيل المثال.قد يحتوي سجلان على نفس المدرسة بطريقة مختلفة، أو كلمات بترتيب مختلف، أو كلمات إضافية، وما إلى ذلك، لذلك يجب أن تكون المطابقة غامضة إلى حد ما إذا أردنا أن نخمن جيدًا أنهما يشيران إلى نفس المدرسة.حتى الآن يعمل بشكل جيد جدًا بالنسبة للأخطاء الإملائية (أنا أستخدم خوارزمية فينيقية مشابهة لـ metaphone فوق كل هذا) ولكن بشكل سيء للغاية إذا قمت بتبديل ترتيب الكلمات التي تبدو شائعة في المدرسة:"كلية xxx" مقابل "كلية xxx".

Answer 1

N-جرام

يستخدم N-جرام, ، التي تدعم عمليات نقل متعددة الأحرف عبر النص بأكمله.

الفكرة العامة هي أن تقوم بتقسيم السلسلتين المعنيتين إلى جميع السلاسل الفرعية الممكنة المكونة من 2-3 أحرف (n-grams) ومعاملة عدد n-grams المشتركة بين السلسلتين كمقياس للتشابه بينهما.يمكن بعد ذلك تسوية ذلك عن طريق قسمة الرقم المشترك على إجمالي عدد n-grams في السلسلة الأطول.هذا أمر تافه لحسابه، ولكنه قوي إلى حد ما.

بالنسبة للجمل سبيل المثال:

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

حصة أ و ب 18 2 جرام

مشاركة A وC فقط 8 2 جرام

بعيدا عن المكان 20 مجموع ممكن.

وقد تمت مناقشة هذا بمزيد من التفصيل في جرافانو وآخرون.ورق.

tf-idf وتشابه جيب التمام

البديل ليس تافهًا جدًا، ولكنه يرتكز على نظرية المعلومات، وهو استخدام المصطلح تردد المصطلح - تردد الوثيقة العكسي (tf-idf) لوزن الرموز المميزة، وبناء نواقل الجملة ثم استخدامها تشابه جيب التمام كمقياس التشابه.

الخوارزمية هي:

1. حساب ترددات الرمز المميز المكون من حرفين (tf) لكل جملة.
2. احسب ترددات الجملة العكسية (idf)، وهو لوغاريتم حاصل قسمة عدد جميع الجمل في المجموعة (في هذه الحالة 3) على عدد المرات التي يظهر فيها رمز مميز عبر جميع الجمل.في هذه الحالة ذ موجود في جميع الجمل بحيث لا يحتوي على محتوى معلومات (log(3/3)=0).
3. قم بإنتاج مصفوفة tf-idf عن طريق ضرب الخلايا المقابلة في جدولي tf وidf.
4. أخيرًا، احسب مصفوفة تشابه جيب التمام لجميع أزواج الجمل، حيث A وB عبارة عن أوزان من جدول tf-idf للرموز المميزة المقابلة.النطاق من 0 (غير مشابه) إلى 1 (متساوي).
   
   

تعديلات Levenshtein وMetaphone

فيما يتعلق بالإجابات الأخرى. داميرو – ليفنشتاين التعديل يدعم فقط نقل اثنين متجاورين الشخصيات. ميتافون تم تصميمه لمطابقة الكلمات التي تبدو متشابهة وليس لمطابقة التشابه.

Answer 2

ولها سهلا. مجرد استخدام مسافة Damerau-Levenshtein على الكلمات بدلا من الحروف.

Answer 3

وتنفجر على مسافات، فرز مجموعة، تنهار، ثم القيام Levenshtein.

Answer 4

ويمكنك أيضا محاولة هذا. (مجرد اقتراح إضافي)

$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

وهذا سوف تظهر أن 1 و 2 هي أكثر مماثل من واحد وثلاثة واثنين وثلاثة.

Answer 5

ولقد تم تنفيذ levenshtein في المدقق الإملائي.

وماذا كنت طالبا تعول التبديلات ك 1 تحرير.

وهذا أمر سهل إذا كنت ترغب فقط لحساب التبديلات من كلمة واحدة بعيدا. ولكن لتبديل لكلمات 2 أو أكثر بعيدا، إضافة إلى خوارزمية أسوأ !(max(wordorder1.length(), wordorder2.length())) سيناريو. إضافة subalgorithm غير الخطية إلى خوارزمية الدرجة الثانية بالفعل ليست فكرة جيدة.

وهذه هي الطريقة التي ستعمل.

if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

وفقط لالتبديلات مؤثرة. إذا كنت تريد جميع التبديلات، عليك أن لكل موقف العمل الى الوراء من تلك النقطة مقارنة

1[n] == 2[n-2].... 1[n] == 2[0]....

وهكذا ترون لماذا لا يشمل هذا في الطريقة القياسية.

Answer 6

هذه الإجابة وإجراء التغيير التالي:

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

وهذا هو لبحث القاموس في TRIE، ولكن من أجل مطابقة لكلمة واحدة، انها نفس الفكرة. تفعلونه فرع ومحددة، وفي أي لحظة، ويمكن إجراء أي تغيير تريد، طالما أنك تعطيه التكلفة.

Answer 7

والقضاء على كلمات مكررة بين السلسلتين ثم استخدام Levenshtein.

Answer 8

وأعتقد أن هذا هو مثال ساطع لاستخدام محرك البحث ناقلات الفضاء .

في هذه التقنية، ويصبح كل وثيقة أساسا متجه مع العديد من الأبعاد كما أن هناك كلمات مختلفة في الجسم بأكمله؛ وثائق مماثلة ثم احتلال المناطق المجاورة في هذا الفضاء النواقل. خاصية واحدة لطيفة من هذا النموذج هو أن الاستعلامات وثائق فقط: للرد على استفسار، يمكنك ببساطة حساب موقفهم في الفضاء ناقلات، ونتائجك هي الأقرب الوثائق التي يمكن العثور عليها. أنا متأكد من أن هناك الحصول على والذهاب حلول PHP هناك.

لfuzzify النتائج من الفضاء ناقلات، هل يمكن النظر إلى قيام النابعة / مماثلة تقنية معالجة اللغة الطبيعية، واستخدام levenshtein إنشاء الاستعلامات الثانوية للكلمات مماثلة التي تحدث في المفردات العامة الخاصة بك.

Answer 9

إذا كانت السلسلة الأولى هي A والثانية هي B:

1. قسّم A وB إلى كلمات
2. لكل كلمة في A، ابحث عن أفضل كلمة مطابقة في B (باستخدام levenshtein)
3. قم بإزالة هذه الكلمة من B ووضعها في B* في نفس فهرس الكلمة المطابقة في A.
4. الآن قارن بين A وB*

مثال:

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

يمكنك تحسين الخطوة 2 عن طريق القيام بذلك في عدة تمريرات، والعثور على التطابقات التامة فقط في البداية، ثم العثور على التطابقات القريبة للكلمات في A التي ليس لها رفيق في B* حتى الآن، ثم العثور على تطابقات أقل تقاربًا، وما إلى ذلك.