في سيناريوهات مثل المنتديات وغرف الدردشة ، من أجل ضمان تجربة المستخدم ، نحتاج غالبًا إلى منع الكثير من الكلمات السيئة. للبحث عن الكلمات الرئيسية الفردية ، فهو أكثر كفاءة في الفهرس والطرق العادية. ومع ذلك ، إذا كان هناك العديد من الكلمات الرئيسية ، إذا قمت باستدعاء INDEXOF أو كلمات منتظمة بشكل متكرر لمطابقة النص الكامل ، فإن استهلاك الأداء مرتفع للغاية. نظرًا لأن السلسلة المستهدفة عادة ما تكون كبيرة في الحجم ، فمن الضروري التأكد من الحصول على النتيجة في اجتياز واحد. بناءً على مثل هذه الاحتياجات ، من السهل التفكير في طرق لمطابقة كل حرف في النص بأكمله بالتسلسل. على سبيل المثال ، بالنسبة لهذا النص: "قال مايك جوردان" فقط افعل ذلك "، لذلك كان مارك هو المبرمج". إذا كانت كلمة "مايك" و "مارك" هي "مايك" و "مارك" ، فيمكنك اجتياز الجملة بأكملها. عندما تجد "M" ، ثم تعرف على ما إذا كان يمكنك مطابقة "I" أو "A". إذا تمكنت من المطابقة حتى النهاية ، فستجد بنجاح كلمة رئيسية ، وإلا فإنك ستستمر في اجتيازها. ثم يجب أن يكون بنية الكلمات الرئيسية هكذا:
var keywords = {m: {i: {k: {e: {end: true}}}} ، a: {r: {k: {end: true}}}}}}مما سبق ، يمكننا أن نرى أن هذه البيانات هي بنية شجرة ، ولا تزال تستغرق وقتًا طويلاً لإنشاء بنية شجرة بناءً على مجموعة الكلمات الرئيسية ، بينما يتم تقديم الكلمات الرئيسية بالفعل ، حتى تتمكن من إنشاء بنية بيانات مسبقًا قبل المطابقة. الرمز كما يلي:
دالة BuildTree (الكلمات الرئيسية) {var tblcur = {} ، المفتاح ، str_key ، الطول ، j ، i ؛ var tblroot = tblcur ؛ لـ (j = الكلمات الرئيسية. طول = str_key.length ؛ لـ (i = 0 ؛ i <length ؛ i += 1) {key = str_key.charat (i) ؛ if (tblcur.hasownproperty (key)) {tblcur = tblcur [key] ؛ } else {tblcur = tblcur [key] = {} ؛ }} tblcur.end = true ؛ // الكلمة الرئيسية الأخيرة tblcur = tblroot ؛ } إرجاع tblroot ؛}يستخدم هذا الرمز عبارة مستمرة: tblcur = tblcur [key] = {}. أمر التنفيذ هنا هو ترتيب تنفيذ البيانات. نظرًا لأن مستوى تشغيل [] أعلى من = ، فإن أول شيء هو إنشاء سمة مفتاح في كائن TBLCUR. جنبا إلى جنب مع tblroot = tblcur = {} ، ترتيب التنفيذ هو:
var tblroot = tblcur = {} ؛ tblroot = tblcur ؛ tblcur ['key'] = undefined ؛ // now tblroot = {key: undefined} tblcur ['key'] = {} ؛ tblcur = tblcur ['key'] ؛من خلال الكود أعلاه ، يتم إنشاء بيانات الاستعلام المطلوبة. دعنا نلقي نظرة على طريقة الكتابة لواجهة الاستعلام.
لكل كلمة من السلسلة الهدف ، نبدأ من أعلى هذه الكلمات الرئيسية. أولاً ، الكلمات الرئيسية [A]. إذا كان هناك ، انظر إلى الكلمة الرئيسية [A] [B]. إذا كانت الكلمة الرئيسية الأخيرة [a] [b] ... [x] = true ، فهذا يعني أن المباراة ناجحة. إذا كانت الكلمة الرئيسية [a] [b] ... [x] = غير محددة ، فسيتم إعادة تشغيل المطابقة من الموضع التالي.
بحث الوظيفة (المحتوى) {var tblcur ، p_star = 0 ، n = content.length ، p_end ، match ، // ما إذا كنت يمكن العثور على match_key ، match_str ، arrmatch = [] ، // تخزين النتيجة arrlength = 0 ؛ // فهرس طول arrmatch بينما (p_star <n) {tblcur = tblroot ؛ // تتبع العودة إلى الجذر p_end = p_star ؛ match_str = "" ؛ تطابق = خطأ ؛ do {match_key = content.charat (p_end) ؛ if (! (tblcur = tblcur [match_key])) {// نهاية هذه المطابقة p_star += 1 ؛ استراحة؛ } آخر {match_str += match_key ؛ } p_end += 1 ؛ if (tblcur.end) // ما إذا كان يجب مطابقة ذيل {match = true ؛ }} بينما (صحيح) ؛ if (match) {// maximum match arrmatch [arrlength] = {key: match_str ، start: p_star - 1 ، end: p_end} ؛ arrlength += 1 ؛ p_star = p_end ؛ }} إرجاع arrmatch ؛}ما سبق هو جوهر نظام مطابقة الكلمات الرئيسية بأكملها. هنا نستخدم ميزات اللغة الخاصة بـ JS بشكل جيد للغاية ، والكفاءة عالية جدًا. لقد استخدمت 500000 كلمة "Soushen Ji" لاختبارها ووجدت 300 تعبيرات. تأثير المطابقة حوالي 1 ثانية. الأهم من ذلك ، نظرًا لأن النص المستهدف يتم اجتيازه في وقت واحد ، فإن طول النص المستهدف له تأثير ضئيل على وقت الاستعلام. عدد الكلمات الرئيسية التي لها تأثير أكبر على وقت الاستعلام هو عدد الكلمات الرئيسية. تعبر كل كلمة في النص الهدف الكلمات الرئيسية ، لذلك لها تأثير معين على الاستعلام.
تحليل بسيط
أعتقد أنك تتساءل عندما تقرأ المقال أعلاه. يمكنك اجتياز جميع الكلمات الرئيسية لكل كلمة. حتى لو كانت بعض الكلمات الرئيسية هي نفسها جزئيًا ، فإنها تستغرق وقتًا طويلاً للغاية لاجتيازها تمامًا. ومع ذلك ، يتم إنشاء خصائص الكائنات في JS باستخدام جدول التجزئة. تختلف بيانات هذا الهيكل تمامًا عن اجتياز الصفيف البسيط ، والكفاءة أعلى بكثير من تلك الخاصة بالتجارب القائم على الطلبات. قد لا يكون بعض الطلاب على دراية بهياكل البيانات ، لذلك سأتحدث بإيجاز عن المحتوى ذي الصلة لجدول التجزئة.
أولاً ، دعنا نلقي نظرة على تخزين البيانات.
يتكون تخزين البيانات في الذاكرة من جزأين ، والآخر هو القيمة والآخر هو العنوان. فكر في الذاكرة كقاموس Xinhua ، وشرح الكلمة هو القيمة ، والدليل هو العنوان. يتم فرز القاموس بواسطة Pinyin ، على سبيل المثال ، "Ni" مع نفس النطق مرتبة في نفس القطعة ، أي ، يتم ترتيب الصفيف بدقة في منطقة الذاكرة. هذا الهيكل عبارة عن صفيف ، يمكنك تحديد "NI" الرقم 1 و 10 للوصول إليه. مخطط الهيكل كما يلي:
ميزة المصفوفات هي أنها بسيطة في اجتيازها ، ويمكنها الوصول مباشرة إلى البيانات المقابلة من خلال الاشتراكات. ولكن من الصعب للغاية إضافة أو حذف عنصر معين. على سبيل المثال ، إذا كنت ترغب في حذف البند 6 ، فيجب نقل البيانات بعد البند 5 إلى الأمام بموقع واحد. إذا كنت ترغب في حذف الجزء الأول ، فيجب نقل الصفيف بأكمله ، والذي يستهلك الكثير.
من أجل حل مشكلة إضافة الصفيف والحذف ، تظهر القوائم المرتبطة. إذا قمنا بتقسيم القيمة إلى جزأين ، فسيتم استخدام جزء لتخزين القيمة الأصلية ، ويتم استخدام الجزء الآخر لتخزين عنوان ، والذي يشير إلى هيكل آخر ، وما إلى ذلك ، يشكل قائمة مرتبطة. الهيكل كما يلي:
يمكن رؤيته بوضوح من الشكل أعلاه أن إضافة وحذف القائمة المرتبطة أمر بسيط للغاية. ما عليك سوى إعادة كتابة العنصر المستهدف والبند التالي من العنصر السابق وسيتم إكماله. ومع ذلك ، من الصعب للغاية الاستعلام عن قيمة عنصر ما. يجب أن تعبر ذلك بدوره للوصول إلى الموقع المستهدف.
من أجل دمج مزايا هذين الهيكلين ، يجب أن تفكر في الهيكل التالي.
بنية البيانات هذه هي بنية جدول التجزئة. يتم تخزين عنوان رأس القائمة المرتبطة في الصفيف ، ويمكن تشكيل جدول بيانات ثنائي الأبعاد. أما بالنسبة لكيفية توزيع البيانات ، فهذه خوارزمية تجزئة ، ويجب أن تكون الترجمة العادية خوارزمية تجزئة. على الرغم من وجود العديد من أنواع الخوارزميات ، من حيث المبدأ ، فإنها تحل المفتاح من خلال وظيفة ، ثم يضعون البيانات وفقًا للنتائج التي تم الحصول عليها من الحل. بمعنى آخر ، يتم تشكيل رسم الخرائط بين المفتاح والعنوان الفعلي ، لذلك في هذا الوقت لم نعد نصل إلى الصفيف عن طريق الاشتراك في المصفوفة أو ببساطة اجتيازه ، ولكن بدلاً من ذلك حدد موقع البيانات بواسطة الوظيفة العكسية لوظيفة التجزئة. الكائن في JS هو بنية التجزئة. على سبيل المثال ، نحدد OBJ. OBJ.NAME من خلال التجزئة ، وقد يكون موقفه في الذاكرة 90 في الشكل أعلاه. عندما نريد تشغيل OBJ.Name ، ستساعدنا الطبقة الأساسية تلقائيًا في تحديد موقع 90 من خلال خوارزمية التجزئة ، مما يعني أننا نبدأ مباشرة في البحث عن القائمة المرتبطة من 12 عنصرًا من الصفيف ، بدلاً من عبور كتلة الذاكرة بأكملها من 0.
تحديد كائن obj {key: value} في JS. يتم تحويل المفتاح إلى سلسلة ثم تجسس للحصول على عنوان ذاكرة ، ثم وضع القيمة فيه. يتيح لنا ذلك أن نفهم سبب تمكننا من إضافة وحذف السمات حسب الرغبة ، ولماذا يمكننا أيضًا تعيين سمات للمصفوفات في JS ، ولا يوجد ما يسمى مجموعة الحدود عبر الحدود.
في المواقف التي يكون فيها حجم البيانات كبيرًا ، يتمتع جدول التجزئة بميزة واضحة للغاية لأنه يقلل من الكثير من الحسابات غير الضرورية من خلال خوارزمية التجزئة. إن تحسين الأداء المزعوم هو في الواقع جعل أجهزة الكمبيوتر أقل الحوسبة ؛ أكبر تحسين هو عدم حساب!
تحسين الخوارزميات
الآن بعد أن فهمت التنفيذ الأساسي للخوارزمية ، يمكنك التفكير في تحسين الخوارزمية في الماضي. ومع ذلك ، قبل التحسين ، يجب عليك التأكيد على شيء واحد: لا تتابع الأداء بشكل أعمى! على سبيل المثال ، في هذه الحالة ، يمكننا مطابقة ما يصل إلى 5000 كلمة على الأكثر ، وبالتالي فإن الخوارزمية الحالية كافية ، وجميع التحسينات غير ضرورية. السبب في أنني ما زلت أتحدث عن التحسين هو تحسين فهمي للخوارزمية والبرنامج ، بدلاً من القيام بتحسين 1MS.
لقد وجدنا أن أيا من كلماتنا الرئيسية لها كلمة واحدة ، لذلك سيكون مضيعة لنا لاجتياز الكلمات الرئيسية وفقًا لوحدة كلمة واحدة. التحسين هنا هو أن يكون الحد الأقصى للحد من الكلمة الرئيسية المسبقة والحد الأدنى للكلمة الرئيسية ، والبحث في وحدات الطول الدنيا في كل مرة. على سبيل المثال ، الكلمة الرئيسية في حالة الاختبار الخاصة بي هي المصطلح ، والأقصر هو 4 أحرف ، لذلك في كل مرة أتطابق فيها ، أقوم بمطابقة 4 أحرف معًا. إذا ضربت ، تابع البحث بعمق للعثور على الحد الأقصى للطول. بمعنى آخر ، عندما نقوم ببناء الشجرة لأول مرة ، يتم بناؤها أولاً مع الحد الأدنى للطول ، ثم يتم إضافتها حرفيًا.
يتم إجراء حساب بسيط. وفقًا لحالة الاختبار الخاصة بنا ، بالنسبة لـ 300 تعابير ، نحتاج فقط إلى مقارنة كلمة واحدة مرة واحدة ، وللاستعلام أحادي الكلمات ، نحتاج إلى مقارنة 4 مرات ، وكل مقارنة يتعين علينا الوصول إلى بنية الأشجار الخاصة بنا ، وهو استهلاك الأداء الذي يمكن تجنبه. الأهم من ذلك ، أن المقارنة هنا ليست مقارنة بين السلسلة. كلماتنا الرئيسية هنا موجودة كمفاتيح ، والتأثير هو نفس المفتاح في OBJ ، وهو تجزئة المفتاح ثم الوصول إلى العنوان المقابل! لذلك لا تقلق بشأن الفرق بين مقارنة كلمة واحدة ومقارنة أربع كلمات. لم نقارن الأوتار!
هذا كل شيء عن مطابقة الكلمات الرئيسية المتعددة. لن أقوم بنشر الإصدار المحسن من الرمز لأنه غير متوفر بشكل عام.