هيكل بيانات Trie: جوهرة مهملة

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

ألعاب الكلمات كمثال Trie

بالنسبة للمبتدئين ، دعنا نفكر في لغز كلمات بسيط: ابحث عن جميع الكلمات الصالحة في لوحة أحرف بحجم 4x4 ، وربط الأحرف المجاورة أفقيًا أو رأسيًا أو قطريًا. على سبيل المثال ، في اللوحة التالية ، نرى الأحرف "W" و "A" و "I" و "T" متصلة لتشكيل كلمة "WAIT".

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

الآن ، هدفنا هو العثور على أفضل بنية بيانات لتنفيذ مدقق الكلمات الصالحة هذا ، أي مفرداتنا. بعض النقاط التي يجب وضعها في الاعتبار:

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

لتوضيح النقطة الثانية ، ضع في اعتبارك اللوحة التالية: لا فائدة من استكشاف الحركات اللاحقة ، حيث لا توجد كلمات في القاموس تبدأ بـ "ASF".

نود أن يجيب هيكل البيانات لدينا على هذه الأسئلة في أسرع وقت ممكن. ~ O (1) وقت الوصول (لفحص التسلسل) سيكون مثاليًا!

يمكننا تحديد واجهة المفردات مثل هذا (انظر هنا للحصول على GitHub repo):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Trie Data Structure مقابل البدائل

يتطلب تنفيذ التابع contains() بنية بيانات داعمة تتيح لك العثور على العناصر بكفاءة ، بينما تتطلب طريقة isPrefix() إيجاد "العنصر الأكبر التالي" ، أي نحتاج إلى الاحتفاظ بالمفردات مرتبة بطريقة ما.

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

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

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

يمكننا تطبيق مفردات مدعومة بمصفوفة تحافظ دائمًا على ترتيب مثل هذا ، باستخدام معيار java.util.ArrayList و java.util.Collections.binarySeach :

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

إذا قررنا استخدام شجرة ثنائية ، فقد يكون التنفيذ أقصر وأكثر أناقة (مرة أخرى ، إليك رابط للكود):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

في كلتا الحالتين ، يمكننا توقع أداء O (تسجيل الدخول) لكل طريقة وصول ( contains() و isPrefix() ). بالنسبة لمتطلبات المساحة ، يتطلب كل من التنفيذ المدعوم بالصفيف والتنفيذ المدعوم من الشجرة O (n + M) حيث n هو عدد الكلمات في القاموس و M هو حجم بايت القاموس ، أي مجموع طول السلاسل في القاموس.

تطبيقات Trie: متى ولماذا تستخدم المحاولات

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

• يمكننا أن نفترض بأمان أن كل الكلمات صغيرة.
• نحن نقبل فقط الأحرف من a إلى z - بدون علامات ترقيم ولا واصلات ولا علامات تشكيل ، وما إلى ذلك.
• يحتوي القاموس على العديد من صيغ التصريف: صيغ الجمع ، تصريف الأفعال ، الكلمات المركبة (على سبيل المثال ، منزل -> مدبرة منزل). لذلك ، تشترك العديد من الكلمات في نفس الجذع .
• الكلمات لها طول محدود. على سبيل المثال ، إذا كنا نعمل على لوحة 4x4 ، فيمكن تجاهل كل الكلمات التي يزيد طولها عن 16 حرفًا.

هذا هو المكان الذي يأتي فيه trie (تُنطق "try"). ولكن ما هو trie بالضبط؟ المحاولات هي هياكل بيانات مهملة ، توجد في الكتب ولكن نادرًا ما توجد في المكتبات القياسية.

للتحفيز ، دعنا أولاً ننظر في ملصق الطفل لعلوم الكمبيوتر: الشجرة الثنائية. الآن ، عندما نحلل أداء الشجرة الثنائية ونقول أن العملية x هي O (log (n)) ، فإننا نتحدث باستمرار عن السجل 2. ولكن ماذا لو ، بدلاً من الشجرة الثنائية ، استخدمنا شجرة ثلاثية ، حيث كل عقدة لديها ثلاثة أطفال (أو ، مروحة من ثلاثة). بعد ذلك ، سنتحدث عن قاعدة السجل 3. (هذا تحسن في الأداء ، وإن كان بعامل ثابت فقط.) بشكل أساسي ، ستصبح أشجارنا أوسع ولكن أقصر ، ويمكننا إجراء عمليات بحث أقل لأننا لسنا بحاجة إلى النزول تمامًا عميق جدا.

أخذ الأمور خطوة إلى الأمام ، ماذا لو كان لدينا شجرة ذات انتشار مساوٍ لعدد القيم الممكنة لنوع البيانات لدينا؟

هذا هو الدافع وراء الثلاثي. وكما قد تكون خمنت ، فإن Trie هي بالفعل شجرة ، شجرة ثلاثية إذا جاز التعبير!

ولكن ، على عكس معظم الأشجار الثنائية التي قد تستخدمها لفرز السلاسل ، تلك التي من شأنها تخزين كلمات كاملة في عقدها ، فإن كل عقدة من Trie تحمل حرفًا واحدًا (ولا حتى ذلك ، كما سنرى قريبًا) و لديه أقصى قدر من التهوية يساوي طول الأبجدية. في حالتنا ، طول الأبجدية هو 26 ؛ لذلك فإن عقد المثلث يكون أقصى عدد من مراوحها 26. وفي حين أن الشجرة الثنائية المتوازنة لها عمق log2 (n) ، فإن أقصى عمق للمثلث يساوي الحد الأقصى لطول الكلمة! (مرة أخرى ، أوسع ولكن أقصر.)

داخل مثلث ، تتشارك الكلمات التي لها نفس الجذع (البادئة) في منطقة الذاكرة التي تتوافق مع الجذع.

لتصور الاختلاف ، دعنا نفكر في قاموس صغير مكون من خمس كلمات. افترض أن الأحرف اليونانية تشير إلى مؤشرات ، ولاحظ أنه في المثلث ، تشير الأحرف الحمراء إلى العقد التي تحتوي على كلمات صحيحة .

تنفيذ Java Trie

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

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

كيف ، إذن ، يمكننا البحث عن كلمة في trie؟ إليك الطريقة التي ستحدد العقدة التي تتوافق مع الحرف الأخير من الكلمة ، إذا كانت موجودة في الشجرة ، في حالة وجود String s :

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

تقوم LOWERCASE.getIndex(s.charAt(i)) بإرجاع موضع الحرف i في الأبجدية. على العقدة التي تم إرجاعها ، تشير node الخاصية المنطقية إلى أن العقدة تتوافق مع الحرف الأخير من الكلمة ، أي حرف تم تمييزه باللون الأحمر في المثال السابق. نظرًا لأن كل عقدة تحتفظ بعداد لعدد الأطفال ، إذا كان هذا العداد موجبًا ، فهناك كلمات أطول في القاموس تحتوي على السلسلة الحالية كبادئة. ملاحظة: لا تحتاج العقدة حقًا إلى الاحتفاظ بإشارة إلى الشخصية التي تتوافق معها ، لأنها ضمنية في موضعها في المثلث.

تحليل الأداء

ما يجعل بنية trie تؤدي أداءً جيدًا حقًا في هذه المواقف هو أن تكلفة البحث عن كلمة أو بادئة ثابتة وتعتمد فقط على عدد الأحرف في الكلمة وليس على حجم المفردات.

في مجالنا المحدد ، نظرًا لأن لدينا سلاسل تتكون من 16 حرفًا على الأكثر ، فإن 16 خطوة بالضبط ضرورية للعثور على كلمة موجودة في المفردات ، بينما يمكن الحصول على أي إجابة سلبية ، أي الكلمة أو البادئة ليست في trie في 16 خطوة على الأكثر أيضًا! بالنظر إلى أننا تجاهلنا سابقًا طول السلسلة عند حساب تعقيد وقت التشغيل لكل من القائمة المصنفة المدعومة بالصفيف والشجرة المخفية في مقارنات السلسلة ، يمكننا أيضًا تجاهلها هنا ونذكر بأمان أن البحث قد تم في الوقت O (1) .

بالنظر إلى متطلبات المساحة (وتذكر أننا أشرنا بـ M إلى حجم بايت القاموس) ، يمكن أن تحتوي trie على عقد M في أسوأ الحالات ، إذا لم تشترك سلسلتان في بادئة. ولكن نظرًا لأننا لاحظنا وجود درجة عالية من التكرار في القاموس ، فهناك الكثير من الضغط الذي يتعين القيام به. قاموس اللغة الإنجليزية المستخدم في كود المثال هو 935،017 بايت ويتطلب 250،264 عقدة ، مع نسبة ضغط تبلغ حوالي 73٪.

ومع ذلك ، على الرغم من ذلك ، فحتى المثلثات المضغوطة تتطلب عادةً ذاكرة أكبر من الشجرة أو المصفوفة. هذا لأنه ، لكل عقدة ، يلزم ما لا يقل عن 26 × sizeof(pointer) بايت ، بالإضافة إلى بعض الحمل الزائد للكائن والسمات الإضافية. في جهاز 64 بت ، تتطلب كل عقدة أكثر من 200 بايت ، بينما يتطلب حرف السلسلة بايتًا واحدًا ، أو اثنين إذا أخذنا في الاعتبار سلاسل UTF.

المحاولات واختبارات الأداء

إذن ، ماذا عن الأداء؟ تم اختبار تطبيقات المفردات في حالتين مختلفتين: التحقق من 20.000.000 سلسلة عشوائية وإيجاد كل الكلمات في 15.000 لوحة تم إنشاؤها عشوائيًا من نفس قائمة الكلمات.

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

متوسط ​​عدد الحركات التي تم إجراؤها لحل اللوحة هو 2،188. لكل حركة ، يتم إجراء بحث عن كلمة والبحث عن البادئة ، أي للتحقق من جميع اللوحات ، تم إجراء أكثر من 32 مليون بحث لكلمة و 32 مليون بحث عن البادئة. ملحوظة: يمكن أن يتم ذلك في خطوة واحدة ، لقد أبقيتهم مفصولين للتوضيح في العرض. سيؤدي ضغطهم في خطوة واحدة إلى تقليل الوقت اللازم لحل الألواح إلى النصف تقريبًا ، وربما يفضل المثلث أكثر.

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

تغليف

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

مراجع

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

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