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

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

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

بنية الـ Trie

بنية شجرية تستخدم لتخزين السلاسل النصية، تدعم عمليات الإضافة، البحث والحذف بتعقيد خطي O(n). كل عقدة تحتوي على مصفوفة من المؤشرات لكل حرف من حروف الأبجدية المستخدمة، بالإضافة إلى متغير منطقي والذي يدل على نهاية السلسلة النصية. الكود البرمجي المعبر عن عقدة الـ Trie بلغة C++ هو:

const int ALPHABET_SIZE = 26;
struct TrieNode{
    bool end_of_string;
    TrieNode *pointer[ALPHABET_SIZE];
    TrieNode(){
        end_of_string = 0;
        for (int i=0;i<ALPHABET_SIZE;i++) pointer[i] = NULL;
    }
}*root = new TrieNode();

في الشكل يوجد لدينا Trie تخزن مجموعة من السلاسل النصية:

 ["CAR", "CAT", "CODE", "CODER", "PAPER", "TREE", 'TRIE'].

العقدة اﻷولى الفارغة هي جذر الـ Trie, العقد التي هي نهاية كلمة معلمة بلون أخضر فاتح. في هذا الشكل قمت فقط بإظهار المؤشرات غير الصفرية، لو أردت إضافة المؤشرات الصفرية أيضاً ستبدو البنية فوضوية بالكامل، هذا اﻷمر يجعل بنية الـ Trie غير فعالة بالنسبة لاستخدام الذاكرة، سوف أتحدث أكثر عن هذا اﻷمر لاحقاً.

• إضافة سلسلة نصية إلى الـ Trie:

ﻹضافة سلسلة نصية إلى الـ Trie يتم إضافة كل محرف من السلسلة كعقدة منفصلة، أبناء هذه العقدة هم مؤشرات إلى عقد أخرى، إذا كان الحرف في المصفوفة موجوداً في مصفوفة المؤشرات نتبع هذا المؤشر، وفي حال كان غير موجود يجب أن نقوم ببنائه. عندما نصل إلى نهاية السلسلة نضع قيمة المتغير المنطقي الذي يشير إلى نهاية السلسلة ليصبح 1. الكود البرمجي المعبر عن تابع ال insert بلغة C++ هو:

void insert(string str){
    TrieNode *cur = this;
    int n = str.length();
    for(int i=0;i<n;i++){
        int nx = str[i]-'A';
        if(cur->pointer[nx]==NULL)cur->pointer[nx] = new TrieNode();
        cur = cur->pointer[nx];
        if(i==n-1)cur->end_of_string = true;
    }
} 

• البحث عن سلسلة نصية في الـ Trie:

في عملية البحث نبدأ من جذر الشجرة ونتأكد إذا كان كل حرف من السلسلة موجوداً، عملية البحث تنتهي بالفشل في حال وصلنا لحرف غير موجود، أو وصلنا لنهاية السلسلة وكانت قيمة المتغير المنطقي مساوية للصفر، غير ذلك فإن البحث ناجح. الكود البرمجي المعبر عن تابع الـ search هو:

bool search(string str){
  TrieNode *cur = this;
  int n = str.length();
  for(int i=0;i<n;i++){
      int nx = str[i]-'A';
      if(cur->pointer[nx]==NULL)return false;
      cur = cur->pointer[nx];
  }
  return cur->end_of_string;
}

• الإكمال التلقائي لبادئة باستخدام الـ Trie:

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

vector<string> AutoComplete(string str){
  TrieNode *cur = this;
  vector<string>ret;
  int n = str.length();
  for(int i=0;i<n;i++){
      int nx = str[i]-'A';
      if(cur->pointer[nx]==NULL)return ret;
      cur = cur->pointer[nx];
  }
  return cur->bfs(str);
}

والكود البرمجي لخوارزمية البحث على التوازي:

vector<string> bfs(string str){
  vector<string>ret;
  queue<pair<TrieNode*, string> >q;
  TrieNode *cur = this;
  q.push({cur, str});
  while(!q.empty()){
      TrieNode *cur = q.front().first;
      string str = q.front().second;
      q.pop();
      if(cur->end_of_string==true){
          ret.push_back(str);
      }
      if(ret.size()==MX_SIZE)break;
      for(int i=0;i<ALPHABET_SIZE;i++){
          if(cur->pointer[i]!=NULL){
              q.push({cur->pointer[i], str+char(i+'A')});
          }
      }
  }
  return ret;
}

• محاسن ومساوئ استخدام الـ Trie:

Trie سهلة الكتابة، سريعة حيث أن جميع العمليات (إضافة، بحث، حذف، إكمال تلقائي) تتم بتعقيد خطي O(n) حيث n هو طول السلسلة النصية، ولكن بالنسبة للذاكرة فأنها ليست أفضل خيار، كل عقدة في الـ Trie تخزن مصفوفة مؤشرات بحجم الأبجدية المستخدمة، ومعظم هذه المؤشرات هي NULL. في حال استخدام حروف إنكليزيه صغيرة، حروف كبيرة، أرقام، علامات استفهام، محارف دولية… فإن هذا سيؤدي إلى استهلاك كبير للذاكرة، بشكل عام يمكن استخدام بنية الـ Trie مع كمية معطيات متوسطة الحجم بأبجدية صغيرة نسبياً.

أشجار البحث الثلاثية

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

struct TSTNode{
    bool end_of_string;
    TSTNode *left, *right, *middle;
    char value;
    TSTNode(){
        end_of_string = 0;
        left = NULL;
        right = NULL;
        middle = NULL;
    }
}*root;

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

["CAR", "CAT", "CODE", "CODER", "PAPER", "TREE", 'TRIE', 'TST']

• إضافة سلسلة نصية إلى شجرة البحث الثلاثية:

عملية الإضافة بسيطة للغاية، فقط نقوم بعملية مقارنة محارف بين محرف السلسلة والمحرف المخزن في العقدة الحالية، إذا كانا متساويين ننتقل إلى الابن الأوسط، إذا كان محرف السلسلة أصغر ننتقل إلى الابن اليساري، وغير ذلك ننتقل إلى الابن اليميني، نخزن قيمة الحرف في كل عقدة ونضع قيمة المتغير المنطقي مساوية للواحد في أخر عقدة، الكود البرمجي المعبر عن تابع ال insert بلغة C++ هو:

TSTNode *insert(TSTNode *head, string str, int idx){
  if(idx==str.length()){
      if(head==NULL)head = new TSTNode();
      head->end_of_string = true;
      return head;
  }
  if(head==NULL){
      head = new TSTNode();
      head->value = str[idx];
  }
  if(str[idx] == head->value)head->middle = insert(head->middle, str, idx+1);
  else if(str[idx] > head->value)head->right = insert(head->right, str, idx);
  else head->left = insert(head->left, str, idx);
  return head;
}

• البحث عن سلسلة نصية في شجرة البحث الثلاثية:

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

bool search(string str){
  TSTNode *root = this;
  int n = str.length();
  int i = 0;
  while(i<n){
      if(root==NULL)return 0;
      if(root->value == str[i]){
          root = root->middle;
          i++;
          continue;
      }
      if(root->value < str[i])root = root->right;
      else root = root->left;
  }
  return root->end_of_string;
}

• الإكمال التلقائي لبادئة باستخدام شجرة البحث الثلاثية:

مشابهة لنفس الفكرة المتبعة في بنية الـ Trie الكود البرمجي لتابع الـ autocomplete بلغة ال C++ هو:

vector<string> bfs(string str){
    vector<string>ret;
    queue<pair<TSTNode*, pair<string, int> > >q;
    TSTNode *cur = this;
    q.push({cur, {str, 1}});
    while(!q.empty()){
        TSTNode *cur = q.front().first;
        string str = q.front().second.first;
        bool add = q.front().second.second;
        q.pop();
        if(cur->end_of_string==true && add==true){
            ret.push_back(str);
        }
        if(ret.size()==MX_SIZE)break;
        if(cur->left!=NULL)q.push({cur->left, {str, 0}});
        if(cur->middle!=NULL)q.push({cur->middle, {str + cur->value, 1}});
        if(cur->right!=NULL)q.push({cur->right, {str, 0}});
    }
    return ret;
}
vector<string> AutoComplete(string str){
    vector<string>ret;
    TSTNode *root = this;
    int n = str.length();
    int i = 0;
    while(i<n){
        if(root==NULL)return ret;
        if(root->value == str[i]){
            root = root->middle;
            i++;
            continue;
        }
        if(root->value < str[i])root = root->right;
        else root = root->left;
    }
    return root->bfs(str);
}

• محاسن استخدام شجرة البحث الثلاثية

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

الكود البرمجي المستخدم بالكامل موجود في الرابط.

References

1. https://iq.opengenus.org/autocomplete-using-trie-data-structure/
2. https://iq.opengenus.org/autocomplete-with-ternary-search-tree/
3. http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/
4. Ternary Search Trees,” Jon Bentley, Bob Sedgewick (Dr. Dobb’s Journal, April 1998)