خوارزمية مقارنة الكلمات

Question

أقوم بإنشاء أداة استيراد CSV للمشروع الذي أعمل عليه.يجب أن يكون العميل قادرًا على إدخال البيانات في برنامج Excel وتصديرها كملف CSV وتحميلها إلى قاعدة البيانات.على سبيل المثال لدي سجل CSV هذا:

   1,   John Doe,     ACME Comapny   (the typo is on purpose)

بالطبع، يتم الاحتفاظ بالشركات في جدول منفصل ويتم ربطها بمفتاح خارجي، لذلك أحتاج إلى اكتشاف معرف الشركة الصحيح قبل الإدخال.أخطط للقيام بذلك من خلال مقارنة أسماء الشركات في قاعدة البيانات بأسماء الشركات الموجودة في ملف CSV.يجب أن تُرجع المقارنة 0 إذا كانت السلاسل متماثلة تمامًا، وتُرجع بعض القيمة التي تصبح أكبر مع اختلاف السلاسل، لكن strcmp لا يقطعها هنا للأسباب التالية:

يجب أن يكون لدى "شركة ACME" و "Acme Comapny" مؤشر اختلاف صغير جدًا ، ولكن يجب أن يكون لدى "Acme Company" و "CMEA MPNYACO" مؤشر اختلاف كبير جدًا أو "ACME Company" و "ACME Comp." يجب أن يكون أيضًا مؤشر فرق صغير ، على الرغم من أن عدد الأحرف مختلف.أيضًا، يجب أن تُرجع "Acme Company" و"Company Acme" 0.

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

هل هناك خوارزمية معروفة للقيام بذلك ، أو ربما يمكننا اختراع واحدة :)؟

Answer 1

وأنت قد ترغب في التحقق من خوارزمية Levenshtein القطر كنقطة انطلاق. وسوف تقيم "المسافة" بين كلمتين.

هذا الموضوع SO على تنفيذ غرار جوجل "هل تعني...؟" النظام قد يوفر بعض الأفكار أيضا.

Answer 2

لا أعرف ما هي اللغة التي تقوم بالترميز بها، ولكن إذا كانت لغة PHP، فيجب عليك مراعاة الخوارزميات التالية:

ليفنشتاين ():يُرجع الحد الأدنى لعدد الأحرف التي يتعين عليك استبدالها أو إدراجها أو حذفها لتحويل سلسلة إلى أخرى.
ساوندكس():تقوم بإرجاع مفتاح soundex المكون من أربعة أحرف للكلمة، والذي يجب أن يكون هو نفس مفتاح أي كلمة مشابهة في النطق.
ميتافون ():مشابه لـ soundex، وربما أكثر فعالية بالنسبة لك.إنها أكثر دقة من soundex() لأنها تعرف القواعد الأساسية لنطق اللغة الإنجليزية.مفاتيح metaphone التي تم إنشاؤها ذات أطوال متغيرة.
مماثلة_نص ():تشبه الدالة levenshtein()‎، ولكنها يمكنها إرجاع قيمة مئوية بدلاً من ذلك.

Answer 3

ولقد كان بعض النجاح مع خوارزمية Levenshtein القطر ، وهناك أيضا <ل أ href = "http://en.wikipedia.org/wiki/Soundex" يختلط = "نوفولو noreferrer"> SOUNDEX .

ما هي اللغة أنك تنفيذ هذا في؟ نحن قد تكون قادرة على الإشارة إلى أمثلة محددة

Answer 4

ولقد نفذت في الواقع نظام مماثل. لقد استخدمت مسافة Levenshtein (كما غيرها من الملصقات اقترح بالفعل)، مع بعض التعديلات. المشكلة مع تحرير مسافة معدلة (تطبق على سلاسل كاملة) هو أنه حساس لكلمة إعادة ترتيب، وذلك "أكمي الرقمية الشركة العالمية للإعلام" ستكون مباراة سيئة ضد "الرقمية للإعلام العالمي شركة أكمي" وكان هذا reorderings شائع جدا في البيانات الخاصة بي.

وأنا تعديله بحيث إذا كانت المسافة تحرير السلاسل كلها كبيرة جدا، سقطت الخوارزمية إلى مطابقة الكلمات ضد بعضها البعض لايجاد جيدة مباراة كلمة إلى كلمة (التكلفة من الدرجة الثانية، ولكن كان هناك قطع إذا كان هناك كانت كلمات كثيرة جدا، لذلك عملت OK).

Answer 5

ولقد اتخذت SOUNDEX، Levenshtein، PHP التشابه، وmetaphone مزدوج وتعبئتها لهم حتى في C # في مجموعة واحدة من طرق الإرشاد على سلسلة.

<وأ href = "http://www.atalasoft.com/cs/blogs/stevehawley/archive/2009/01/26/string-similarity-and-extension-methods.aspx" يختلط = "نوفولو noreferrer" > بكل بلوق وظيفة هنا .

Answer 6

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

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

http://msdn.microsoft.com /en-us/library/aa259235٪28SQL.80٪29.aspx

Answer 7

وأنا تنفيذه في PHP، وأنا الآن أكتب قطعة من التعليمات البرمجية التي سيتم تفريق 2 السلاسل في الكلمات ومقارنة كل الكلمات من السلسلة الأولى مع كلمات السلسلة الثانية باستخدام levenshtein وقبول ادنى القيم الممكنة. إضافة سوء عندما انتهيت.

وشكرا جزيلا.

وتحديث: وهنا ما جئت مع:

function myLevenshtein( $str1, $str2 )
{
  // prepare the words
  $words1 = explode( " ",  preg_replace( "/\s+/", " ", trim($str1) ) );
  $words2 = explode( " ",  preg_replace( "/\s+/", " ", trim($str2) ) );

  $found = array(); // array that keeps the best matched words so we don't check them again
  $score = 0;       // total score
  // In my case, strings that have different amount of words can be good matches too
  // For example, Acme Company and International Acme Company Ltd. are the same thing
  // I will just add the wordcount differencre to the total score, and weigh it more later if needed
  $wordDiff = count( $words1 ) - count( $words2 );
  foreach( $words1 as $word1 )
  {
    $minlevWord = "";
    $minlev = 1000;
    $return = 0;
    foreach( $words2 as $word2 )
    {
      $return = 1;
      if( in_array( $word2, $found ) )
        continue;
      $lev = levenshtein( $word1, $word2 );
      if( $lev < $minlev )
      {
        $minlev = $lev;
        $minlevWord = $word2;
      }
    }
    if( !$return )
      break;
    $score += $minlev;
    array_push( $found, $minlevWord );
  }

  return $score + $wordDiff;
}