اكتشاف إعادة التغريد باستخدام خوارزميات تجزئة بايثون غير المكلفة حسابيًا
https://stackoverflow.com/questions/815313
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لكي أتمكن من اكتشاف RT لتغريدة معينة، أخطط لتخزين تجزئات كل تغريدة منسقة في قاعدة البيانات.
ما هي خوارزمية التجزئة التي يجب أن أستخدمها؟الغموض بالطبع ليس ضروريا.مجرد طريقة بسيطة لتخزين البيانات كشيء يمكن مقارنته إذا كان هو نفسه، بطريقة فعالة.
كانت محاولتي الأولى لذلك باستخدام تجزئات md5.لكنني اعتقدت أنه يمكن أن تكون هناك خوارزميات تجزئة أكثر كفاءة، حيث أن الأمان غير مطلوب.
المحلول
وأنت تحاول تجزئة سلسلة أليس كذلك؟ أنواع مدمج يمكن تجزئته على الفور، فقط تفعل hash("some string") وتحصل على بعض كثافة العمليات. يستخدم لها وظيفة نفسه الثعبان لdictonarys، لذلك فمن المحتمل أن يكون الخيار الافضل.
نصائح أخرى
هل كنت حقا بحاجة الى تجزئة على الإطلاق؟ رسائل تويتر هي ما يكفي (ومساحة القرص رخيصة بما فيه الكفاية) القصيرة التي قد يكون من الأفضل لمجرد تخزين الرسالة كاملة، وليس تلتهم دورات على مدار الساعة لتجزئة عليه.
لست على دراية ببايثون (آسف، روبي يكتب هنا) ولكن يمكنك تجربة بعض الأشياء.
الافتراضات: من المحتمل أن تقوم بتخزين مئات الآلاف من التغريدات بمرور الوقت، لذا فإن مقارنة تجزئة واحدة مقابل "كل سجل" في الجدول لن تكون فعالة.كما أن ردود الفعل ليست دائمًا نسخًا كربونية من التغريدة الأصلية.بعد كل شيء، عادةً ما يتم تضمين اسم المؤلف الأصلي ويستهلك بعضًا من الحد الأقصى لعدد الأحرف وهو 140 حرفًا.لذا ربما يمكنك استخدام حل يتطابق بشكل أكثر دقة من التجزئة "الغبية"؟
وضع العلامات والفهرسة
وضع علامة وفهرس الأجزاء المكونة من الرسالة بطريقة قياسية.هذا يمكن أن يشمل معالجة hashed #.... ، at-marked @....وسلاسل URL كـ "علامات".بعد إزالة كلمات الضوضاء وعلامات الترقيم ، يمكنك أيضًا التعامل مع الكلمات المتبقية كعلامات أيضًا.
بحث سريع
قواعد البيانات فظيعة في العثور على عضوية متعددة المجموعة بسرعة كبيرة (سأفترض أنك تستخدم إما MySQL أو Postgresql ، والتي تكون فظيعة في هذا).بدلاً من ذلك ، جرب واحدة من محركات النص المجانية مثلبحث أبو الهول.إنها سريعة جدًا في حل عضوية مجموعة متعددة (أيالتحقق من وجود الكلمات الرئيسية).
باستخدام sphinx أو ما شابه ، نبحث عن جميع "العلامات" التي استخرجناها.من المحتمل أن يعيد هذا مجموعة نتيجة صغيرة من "التغريدات الأصلية المحتملة".ثم قارنها واحدًا تلو الآخر باستخدام خوارزمية مطابقة التشابه (هنا واحد في بيثون http://code.google.com/p/pylevenshtein/)
الآن اسمحوا لي أن أرحب بكم بحرارة في عالم تحليل النصوص.
حظ سعيد!
وأنا أردد تعليق كريس حول عدم استخدام تجزئة على الإطلاق (محرك قاعدة البيانات الخاصة بك يمكن نأمل الحقول المؤشر 140 حرف بكفاءة).
إذا لم ترغب في استخدام التجزئة، MD5 سيكون خياري الأول وكذلك (16 بايت)، تليها SHA-1 (20 بايت).
ومهما فعلت، لا تستخدم مبلغ من بين الشخصيات. أنا لا يمكن أن يأتي فورا مع وظيفة التي من شأنها أن الحصول على مزيد من الاصطدامات (جميع الجناس التجزئة نفسه)، بالإضافة إلى أنه أبطأ!
$ python -m timeit -s 'from hashlib import md5' 'd=md5("There once was a man named Michael Finnegan.").digest()'
100000 loops, best of 3: 2.47 usec per loop
$ python -m timeit 'd=sum(ord(c) for c in "There once was a man named Michael Finnegan.")'
100000 loops, best of 3: 13.9 usec per loop
وهناك عدد قليل من القضايا هنا. أولا، لRT ليست دائما متطابقة. بعض الناس إضافة تعليق. الآخرين تغيير URL للتتبع. البعض الآخر إضافة في شخص أنهم RT'ing (التي قد تكون أو لا تكون المنشئ).
وحتى إذا كنت تسير على تجزئة تويتر، تحتاج إلى أنها تغلي وصولا الى اللحوم من سقسقة، وتجزئة هذا فقط. حظا سعيدا.
وأعلاه، ذكر أحدهم أنه مع 32-بت، سوف تبدأ بعد اصطدام بنحو 65K تويت. وبطبيعة الحال، هل يمكن أن يكون التصادم على تويتر # 2. ولكن أعتقد أن الخلط بين مؤلف هذا التعليق، منذ 2 ^ 16 = ~ 65K، ولكن 2 ^ 32 = ~ 4 تريليون. بحيث يكون لديك مساحة أكبر قليلا هناك.
وربما تكون خوارزمية أفضل في محاولة لاستخلاص أجزاء "فريدة" من سقسقة، وبصمات ذلك. انها ليست تجزئة، انها بصمة بضع كلمات الرئيسية التي تحدد التفرد.
حسنا، تويت هي أحرف فقط 140 لفترة طويلة، لذلك يمكن تخزين حتى سقسقة كامل في قاعدة البيانات ...
ولكن إذا كنت تريد حقا أن "تجزئة" لهم بطريقة أو بأخرى، وسيلة بسيطة سيكون لمجرد اتخاذ مجموع قيم ASCII من جميع الشخصيات في تغريدة:
sum(ord(c) for c in tweet)
وبطبيعة الحال، كلما كان لديك مباراة من التجزئة، يجب عليك مراجعة تويت أنفسهم عن التشابه، لأن احتمال العثور على اثنين من التغريدات التي تعطي نفس "مبلغ-تجزئة" ربما لا يستهان به.
وحدة الرف بايثون؟ http://docs.python.org/library/shelve.html
