كيف يمكنني تحديد ما إذا كانت السلسلة العشوائية تبدو مثل اللغة الإنجليزية؟

Question

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

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

Answer 1

يمكنك بناء سلسلة ماركوف من نص إنجليزي ضخم.

بعد ذلك يمكنك إدخال الكلمات في سلسلة ماركوف والتحقق من مدى احتمالية أن تكون الكلمة إنجليزية.

انظر هنا: http://en.wikipedia.org/wiki/Markov_chain

في أسفل الصفحة يمكنك رؤية منشئ نص ماركوف.وما تريده هو عكس ذلك تماما.

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

Answer 2

الطريقة السهلة باستخدام مرشحات بايزي (مثال بايثون من http://sebsauvage.net/python/snyppets/#bayesian)

from reverend.thomas import Bayes
guesser = Bayes()
guesser.train('french','La souris est rentrée dans son trou.')
guesser.train('english','my tailor is rich.')
guesser.train('french','Je ne sais pas si je viendrai demain.')
guesser.train('english','I do not plan to update my website soon.')

>>> print guesser.guess('Jumping out of cliffs it not a good idea.')
[('english', 0.99990000000000001), ('french', 9.9999999999988987e-005)]

>>> print guesser.guess('Demain il fera très probablement chaud.')
[('french', 0.99990000000000001), ('english', 9.9999999999988987e-005)]

Answer 3

يمكنك التعامل مع هذا عن طريق ترميز سلسلة مرشح في بيجرامز- أزواج من الحروف المتجاورة - والتحقق من كل بيجرام مقابل جدول ترددات بيجرام الإنجليزية.

• بسيط:إذا كان أي بيجرام منخفضًا بدرجة كافية على جدول الترددات (أو غائبًا تمامًا)، فارفض السلسلة باعتبارها غير قابلة للتصديق.(تحتوي السلسلة على بيجرام "QZ"؟يرفض!)
• أقل بساطة:احسب المعقولية الإجمالية للسلسلة بأكملها، على سبيل المثال، من حيث حاصل ضرب ترددات كل بيجرام مقسومًا على متوسط ​​التردد لسلسلة إنجليزية صالحة بهذا الطول.سيسمح لك هذا بكل من (أ) قبول سلسلة ذات وحدات بيجرام فردية منخفضة التردد من بين وحدات بيجرام عالية التردد، و(ب) رفض سلسلة تحتوي على عدة وحدات بيجرام فردية منخفضة ولكن ليست أقل تمامًا من العتبة .

سيتطلب أي منهما بعض ضبط العتبة (العتبات)، والتقنية الثانية أكثر من الأولى.

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

قد تكون جداول Biggram وtrigram المستندة إلى مجموعة الأبحاث الحالية متاحة مجانًا أو للشراء (لم أجد أيًا منها متاحًا مجانًا ولكنني قمت فقط بإجراء بحث سريع على Google حتى الآن)، ولكن يمكنك حساب جدول bigram أو trigram بنفسك من أي جدول جيد. حجم النص الإنجليزي.ما عليك سوى التمرير عبر كل كلمة كرمز مميز وتسجيل كل بيجرام - يمكنك التعامل مع هذا كعلامة تجزئة مع بيجرام معين كمفتاح وعداد صحيح متزايد كقيمة.

إن مورفولوجيا اللغة الإنجليزية وصوتيات اللغة الإنجليزية (المعروف!) أقل من متساوي القياس، لذلك قد تولد هذه التقنية سلاسل "تشبه" اللغة الإنجليزية ولكنها تقدم نطقًا مزعجًا.هذه حجة أخرى للثلاثيجرامات بدلًا من الكبيرة، فالغرابة الناتجة عن تحليل الأصوات التي تستخدم عدة أحرف متتالية لإنتاج صوت معين سيتم تقليلها إذا امتد n-gram على الصوت بأكمله.(فكر في "المحراث" أو "تسونامي"، على سبيل المثال.)

Answer 4

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

Answer 5

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

سيكون حل بيرل سرداب::PassGen, ، والتي يمكنك تدريبها باستخدام القاموس (حتى تتمكن من تدريبها على لغات مختلفة إذا كنت بحاجة إلى ذلك).فهو يتنقل عبر القاموس ويجمع إحصائيات حول تسلسلات مكونة من حرف واحد أو حرفين أو ثلاثة أحرف، ثم يبني "كلمات" جديدة بناءً على الترددات النسبية.

Answer 6

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

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

Answer 7

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

اعتمادًا على متطلبات الأداء، يمكنك العمل على خوارزمية المسافة لأكواد soundex وقبول السلاسل ضمن تفاوت معين.

من السهل جدًا تنفيذ Soundex - انظر ويكيبيديا للحصول على وصف للخوارزمية.

مثال على تنفيذ ما تريد القيام به سيكون:

def soundex(name, len=4):
    digits = '01230120022455012623010202'
    sndx = ''
    fc = ''

    for c in name.upper():
        if c.isalpha():
            if not fc: fc = c
            d = digits[ord(c)-ord('A')]
            if not sndx or (d != sndx[-1]):
                sndx += d

    sndx = fc + sndx[1:]
    sndx = sndx.replace('0','')
    return (sndx + (len * '0'))[:len]

real_words = load_english_dictionary()
soundex_cache = [ soundex(word) for word in real_words ]

if soundex(candidate) in soundex_cache:
    print "keep"
else:
    print "discard"

من الواضح أنك ستحتاج إلى توفير تطبيق read_english_dictionary.

يحرر:سيكون مثالك على "KEAL" جيدًا، لأنه يحتوي على نفس رمز soundex (K400) مثل "KEEL".قد تحتاج إلى تسجيل الكلمات المرفوضة والتحقق منها يدويًا إذا كنت تريد الحصول على فكرة عن معدل الفشل.

Answer 8

هل يجب أن تكون كلمات إنجليزية حقيقية، أم مجرد سلاسل تبدو وكأنها كلمات إنجليزية؟

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

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

Answer 9

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

Answer 10

هذا يبدو وكأنه مهمة معقدة للغاية!خارج الجزء العلوي من رأسي، يحتاج الصوت الساكن إلى حرف متحرك إما قبله أو بعده.ومع ذلك، فإن تحديد ماهية الصوت سيكون أمرًا صعبًا للغاية!ربما ستحتاج إلى كتابة قائمة بها يدويًا.على سبيل المثال، "TR" جيد ولكن ليس "TD"، وما إلى ذلك.

Answer 11

من المحتمل أن أقوم بتقييم كل كلمة باستخدام خوارزمية SOUNDEX مقابل قاعدة بيانات للكلمات الإنجليزية.إذا كنت تفعل ذلك على خادم SQL، فمن السهل جدًا إعداد قاعدة بيانات تحتوي على قائمة بمعظم الكلمات الإنجليزية (باستخدام قاموس متاح مجانًا)، وقد تم تنفيذ SOUNDEX على خادم MSSQL كخوارزمية بحث متاحة.

من الواضح أنه يمكنك تنفيذ ذلك بنفسك إذا أردت، وبأي لغة - ولكنها قد تكون مهمة كبيرة.

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

Answer 12

أقترح النظر في اختبار فاي ومؤشر الصدفة. http://www.threaded.com/cryptography2.htm

Answer 13

أود أن أقترح بعض القواعد البسيطة والأزواج القياسية والثلاثية التوائم ستكون جيدة.

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

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

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