طريقة فعالة حساب الشبه عشرات السلاسل عندما يكون حجم العينة كبير ؟

Question

دعنا نقول أن لديك قائمة من 10 ، 000 عناوين البريد الإلكتروني ، كنت ترغب في العثور على بعض ما أقرب "الجيران" في هذه القائمة يتم تحديد عناوين البريد الإلكتروني بشكل مريب بالقرب من عناوين البريد الإلكتروني الأخرى في القائمة الخاصة بك.

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

دعنا نقول أن أحدد "وثيقة مريبة إلى عنوان بريد إلكتروني آخر" كما سلسلتين وجود Levenshtein درجة أقل من N.

هل هناك طريقة أكثر فعالية للعثور على زوج من السلاسل التي يسجل أقل من هذا الحد إلى جانب مقارنة كل سلسلة إلى كل ممكن السلسلة في القائمة ؟ وبعبارة أخرى ، أن هذا النوع من المشاكل يمكن حلها أسرع من O(n^2)?

هو Levenshtein درجة سوء اختيار من الخوارزميات هذه المشكلة ؟

Answer 1

ونعم - يمكنك أن تجد جميع سلاسل على مسافة معينة من سلسلة في O (سجل ن) وقت باستخدام <لأ href = "http://blog.notdot.net/2007/4/Damn-Cool- خوارزميات الجزء-1-BK-الأشجار "يختلط =" نوفولو noreferrer "> BK-شجرة . حلول بديلة تنطوي على توليد كل سلسلة مع المسافة ن قد يكون أسرع لمسافة levenshtein 1، ولكن حجم العمل البالونات بسرعة خارج نطاق السيطرة لمسافات أطول.

Answer 2

ويمكنك أن تفعل ذلك مع Levenshtein في O(kl)، حيث k هي المسافة القصوى ول هو الحد الأقصى السلسلة.

وأساسا عندما تعلم كيفية حساب Levenshtein الأساسي ثم فإنه من السهل معرفة أن كل نتيجة وهذا هو أبعد من k من القطر الرئيسي يجب أن يكون أكبر من k. حتى إذا كنت حساب قطر رئيسي مع 2k + 1 العرض لن يكون كافيا.

إذا كان لديك 10000 عناوين البريد الإلكتروني لن تحتاج خوارزمية أسرع. يمكن الكمبيوتر حساب مع O(N^2) بسرعة كافية.

وLevenshtein أمر جيد جدا لهذا النوع من المشاكل.

وأيضا ما قد نظر هو تحويل رسائل البريد الإلكتروني مع SOUNDEX قبل مقارنة. ربما عليك الحصول على نتائج أفضل.

Answer 3

هذه المشكلة كما هو معروف تجميع و هو جزء من أكبر إلغاء البيانات المكررة المشكلة (حيث يمكنك أن تقرر أي عضو الكتلة هو "الحق" واحد), المعروف أيضا باسم دمج-تطهير.

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

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

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

أنا مرة تنفيذ هذه الخوارزمية على إلغاء البيانات المكررة من اسم/عنوان السجلات مع أحجام قوائم يجري حولها 10-50 مليون سجل وعملت سريع جدا (و المكررة بشكل جيد جدا).

عموما هذه المشاكل أصعب جزء من الدورة هو إيجاد قيمة التشابه عتبة.الفكرة هي للقبض على جميع dups w/o إنتاج الكثير من ايجابيات كاذبة.البيانات مع خصائص مختلفة يميل إلى تتطلب عتبات مختلفة.اختيار edit-المسافة خوارزمية مهم أيضا في بعض خوارزميات أفضل OCR الأخطاء في حين أن الآخرين أفضل من الأخطاء المطبعية و أخرى أفضل بالنسبة الأخطاء الصوتية (مثل عند الحصول على اسم عبر الهاتف).

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

المراجع:

هيرنانديز م.عام 1995 ، دمج/تطهير مشكلة قواعد البيانات الكبيرة.

Monge A.عام 1997 ، كفاءة المجال مستقلة خوارزمية للكشف عن ما يقرب من تكرار سجلات قاعدة البيانات.

Answer 4

أنا لا أعتقد أنك يمكن أن تفعل أفضل من O(n^2) ولكن يمكنك أن تفعل بعض أصغر التحسينات التي يمكن أن يكون ما يكفي من تسريع لجعل التطبيق الخاص بك للاستخدام:

• يمكن أولا فرز جميع عناوين البريد الإلكتروني من قبل ال جزء بعد @ فقط مقارنة عناوين أين هو نفسه
• يمكنك إيقاف حساب المسافة بين عنوانين عندما يصبح أكبر من n

تحرير:في الواقع يمكنك أن تفعل أفضل من O(n^2), فقط انظر نيك جونسون الإجابة أدناه.

Answer 5

10000 عناوين البريد الإلكتروني الصوت ليس كثيرا. للبحث التشابه في مساحة أكبر يمكنك استخدام التسقيف و <لأ href = "HTTP : //blogs.msdn.com/spt/archive/2008/06/10/set-similarity-and-min-hash.aspx "يختلط =" نوفولو noreferrer "> مين التجزئة . هذه الخوارزمية هو قليلا أكثر تعقيدا لتنفيذ، ولكن هي أكثر كفاءة على مساحة واسعة.

Answer 6

ومن الممكن أن نفعل ما هو أفضل، في حالة وجود عكس المشكلة.

وأفترض هنا أن 10.000 العناوين وجميلة "ثابتة"، وإلا سيكون لديك لإضافة آلية التحديث.

والفكرة هي استخدام المسافة Levenshtein، ولكن في الوضع "عكسي"، في بيثون:

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

وطريقة generate_level يولد كل الاختلافات الممكنة من المجموعة السابقة، ناقص الاختلافات الموجودة بالفعل في المستوى السابق. يحافظ على "الأصل" كقيمة المرتبطة المفتاح.

وبعد ذلك، لديك فقط لبحث كلمتك في مجموعة مختلفة:

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

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

وبعد ذلك البحث هو أكثر كفاءة بكثير من O (ن ^ 2)، على الرغم من إعطائها بالضبط من الصعب نوع من حيث أنها تعتمد على حجم مجموعات التي يتم إنشاؤها.

لمرجعية، إلقاء نظرة على العنوان التالي: http://norvig.com/spell-correct.html

Answer 7

ودعونا نقول لديك 3 سلاسل:

1 - "اي بي سي" 2 - "BCD" 3 - "الرفيق"

والمسافة L بين 1 و 2 هو 2 (طرح "أ"، إضافة 'د'). المسافة L بين 2 و 3 هو 2 (طرح 'ب'، تضيف 'ه').

وسؤالك هو ما إذا كان يمكننا أن نستنتج مسافة L بين 1 و 3 باستخدام مقارنات 2 أعلاه. الجواب هو لا.

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

وهكذا، أود أن أقول أن Levenshtein هو خيار الفقراء للحصول على قائمة كبيرة.

Answer 8

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