هيكل بيانات Trie (شجرة البادئة)

A Trie، (المعروف أيضًا باسم شجرة البادئة) هو نوع خاص من الشجرة المستخدمة لتخزين هياكل البيانات الترابطية

حصلت trie (تجربة منطوقة) على اسمها من re trie val - هيكلها يجعلها خوارزمية مطابقة نجمية.

سياق الكلام

Write your own shuffle method to randomly shuffle characters in a string. 
Use the words text file, located at /usr/share/dict/words, and your shuffle method to create an anagram generator that only produces real words.
Given a string as a command line argument, print one of its anagrams. 

لقد واجهت هذا التحدي هذا الأسبوع في Make School's Product Academy.

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

تتمثل إحدى طرق مواجهة هذا التحدي في:

  • عشوائيًا خلط الأحرف في السلسلة
  • ثم ، تحقق منه مقابل كل الكلمات الموجودة في / usr / share /ict / words للتحقق من أنها كلمة حقيقية.

ومع ذلك، يتطلب هذا النهج أن أتحقق من أن الشخصيات تعديلا عشوائيا في سلسلة جديدة مباريات واحدة من 235887 الكلمات في هذا الملف - أن وسائل 235887 عمليات ل كل سلسلة أنني أريد أن تحقق ككلمة الحقيقية.

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

def generateAnagram(string, language="en_US"): languageDict = enchant.Dict(language) numOfPossibleCombinationsForString = math.factorial(len(string)) for i in range(0, numOfPossibleCombinationsForString): wordWithShuffledCharacters = shuffleCharactersOf(string)
 if languageDict.check(wordWithShuffledCharacters): return wordWithShuffledCharacters return "There is no anagram in %s for %s." % (language, string)

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

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

تري

ثلاثي يخزن البيانات في "خطوات". كل خطوة هي عقدة في المثلث.

يُعد تخزين الكلمات حالة استخدام مثالية لهذا النوع من الشجرة ، نظرًا لوجود عدد محدود من الأحرف التي يمكن تجميعها معًا لعمل سلسلة.

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

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

لاحظ أن نهاية الكلمة يُرمز لها بـ "$". أنا أستخدم "$" لأنها شخصية فريدة لن تكون موجودة بأي كلمة بأي لغة.

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

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

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

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

قد تفكر: "انتظر ، ألا يستغرق الأمر وقتًا طويلاً لإنشاء ملف ثلاثي من هذا الملف النصي الذي يحتوي على 235،887 كلمة فيه؟ ما الهدف من تكرار كل حرف في كل كلمة؟ "

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

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

endOfWord = "$"
def generateTrieFromWordsArray(words): root = {} for word in words: currentDict = root for letter in word: currentDict = currentDict.setdefault(letter, {}) currentDict[endOfWord] = endOfWord return root
def isWordPresentInTrie(trie, word): currentDict = trie for letter in word: if letter in currentDict: currentDict = currentDict[letter] else: return False return endOfWord in currentDict

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

الخطوات التالية

أقترح التحقق من الريبو الثلاثي لـ Ray Wenderlich. على الرغم من كتابته بلغة Swift ، إلا أنه مصدر قيم لتفسيرات الخوارزميات المختلفة.

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

ومع ذلك ، فإن تطبيق الجذر أكثر تعقيدًا من التنفيذ. أقترح إلقاء نظرة على الريبو الجذري لـ Ray Wenderlich إذا كنت مهتمًا.

هذه أول مشاركة في سلسلة الخوارزمية وهياكل البيانات الخاصة بي. في كل منشور ، سأقدم مشكلة يمكن حلها بشكل أفضل باستخدام خوارزمية أو بنية بيانات لتوضيح الخوارزمية / بنية البيانات نفسها.

قم بنجمة ريبو خوارزمياتي على جيثب واتبعني على Twitter إذا كنت ترغب في المتابعة على طول!

هل اكتسبت قيمة من خلال قراءة هذا المقال؟ انقر هنا لمشاركتها على Twitter! إذا كنت ترغب في مشاهدة محتوى مثل هذا كثيرًا ، فاتبعني على Medium واشترك في رسالتي الإخبارية مرة كل شهر أدناه. لا تتردد في شراء القهوة لي أيضا.