العثور على الكلمات من مدخلات عشوائية الحروف في بيثون.ما خوارزمية استخدام/مدونة بالفعل هناك ؟

Question

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

كنت تخطط للقيام بذلك في أي بايثون او روبي.شكرا مقدما على مساعدتكم يا شباب!

Answer 1

سأستخدم أ تري. إليك تطبيق في بيثون: http://jtauber.com/2005/02/trie.py (الائتمان لجيمس تاوبر)

Answer 2

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

الفكرة الرئيسية فهرس الكلمات من قبل أمرت تسلسل من الحروف.
على سبيل المثال "الكمبيوتر" يحصل مرتبطا باسم "cemoprtu".مهما كانت الرسومات عشوائية توفير الفرز في نوع و تستخدم مفتاح العثور على المباريات المحتملة.باستخدام trie الهياكل كما اقترح perimosocordiae ، التخزين الأساسية لهذه فرز مفاتيح الكلمات المرتبطة بها(s)/wordIds في "ورقة" العقد, كلمة البحث يمكن القيام به في O(n) الوقت, حيث n هو عدد الحروف (أو أفضل في المتوسط بسبب عدم الكلمات الموجودة).

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

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

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

Answer 3

لمؤشر القاموس الخاص بك ، قم بإنشاء خريطة (خريطة [حقيبة [char] ، قائمة [سلسلة]]). يجب أن تكون خريطة التجزئة حتى تتمكن من الحصول على البحث عن الكلمات. الحقيبة [char] هي معرف لكلمة فريدة من نوعها لترتيب الأحرف. إنها في الأساس خريطة تجزئة من char إلى int. char هو حرف معين في الكلمة و int هو عدد المرات التي تظهر فيها الحرف في الكلمة.

مثال:

{'a'=>3, 'n'=>1, 'g'=>1, 'r'=>1, 'm'=>1} => ["anagram"]
{'s'=>3, 't'=>1, 'r'=>1, 'e'=>2, 'd'=>1} => ["stressed", "desserts"]

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

Answer 4

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

Answer 5

هناك طريقتان للقيام بذلك. أحدهما هو التحقق من كل ترشيح للرسائل في الكلمة لمعرفة ما إذا كان المرشح في قاموس الكلمات الخاصة بك. هذه عملية O (n!) ، اعتمادًا على طول الكلمة.

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

لذا ابدأ ببناء قاموس هو مفتاحه عبارة عن سلسلة من الحروف مصنفة والتي تعد قيمتها قائمة بالكلمات التي هي جنسيات المفتاح:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> with open(r"c:\temp\words.txt", "r") as f:
        for line in f.readlines():
            if line[0].isupper(): continue
            word = line.strip()
            key = "".join(sorted(word.lower()))
            d[key].append(word)

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

>>> def contains(sorted_word, sorted_candidate):
        wchars = (c for c in sorted_word)
        for cc in sorted_candidate:
            while(True):
                try:
                    wc = wchars.next()
                except StopIteration:
                    return False
                if wc < cc: continue
                if wc == cc: break
                return False
        return True

الآن ابحث عن جميع مفاتيح المرشحين في القاموس التي تحتوي على الكلمة ، وتجميع جميع قيمها في قائمة واحدة:

>>> w = sorted("mythopoetic")
>>> result = []
>>> for k in d.keys():
        if contains(w, k): result.extend(d[k])
>>> len(result)
429
>>> sorted(result)[:20]
['c', 'ce', 'cep', 'ceti', 'che', 'chetty', 'chi', 'chime', 'chip', 'chit', 'chitty', 'cho', 'chomp', 'choop', 'chop', 'chott', 'chyme', 'cipo', 'cit', 'cite']

تستغرق تلك الخطوة الأخيرة حوالي ربع المركز الثاني على جهاز الكمبيوتر المحمول ؛ هناك 195k مفتاح في القاموس الخاص بي (أنا أستخدم ملف BSD Unix Words).