حاول مقابل.لاحقة شجرة مقابل.مصفوفة لاحقة

Question

ما هي البنية التي توفر أفضل نتائج الأداء؟تري (شجرة البادئة)، شجرة لاحقة أو مجموعة لاحقة؟هل هناك هياكل أخرى مماثلة؟ما هي تطبيقات Java الجيدة لهذه الهياكل؟

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

Answer 1

كان تري أول بنية بيانات من هذا النوع تم اكتشافها.

شجرة اللاحقة هي تحسن على Trie (لها روابط لاحقة تسمح بالبحث عن الأخطاء الخطي ، وتقطيع شجرة لاحقة الفروع غير الضرورية في Trie ، وبالتالي فهي لا تتطلب مساحة كبيرة).

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

تري ليس للاستخدام في العالم الحقيقي لأنه يستهلك مساحة كبيرة.

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

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

في نفس عائلة هياكل البيانات:

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

يأخذها FCST إلى أبعد من ذلك ، فهي تنفذ شجرة لاحقة العينات مع صفيف لاحقة.

DFCST هو نسخة ديناميكية من FCST.

التوسع:

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

يستخدم CST 8 جيجابت ، ومع ذلك يتم تقليل سرعة عمليات شجرة لاحقة بشدة.

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

يمكن لـ FCST (شجرة اللاحقة المضغوطة بالكامل) إنشاء شجرة لاحقة في 800 إلى 1.5 جيجا. مع تدهور سرعة صغيرة إلى حد ما نحو CST.

يستخدم DFCST مساحة أكبر بنسبة 20 ٪ من FCST ، ويفقد السرعة للتنفيذ الثابت لـ FCST (ومع ذلك فإن الفهرس الديناميكي مهم للغاية).

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

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

Answer 2

ما هي العمليات التي تخطط للقيام بها؟ libdivsufsort كان في وقت واحد هو أفضل تطبيق لصفيف لاحقة في C.

Answer 3

باستخدام أشجار اللاحقة ، يمكنك كتابة شيء يطابق قاموسك مع نصك في وقت O (n+m+k) حيث يكون n رسائل في القاموس الخاص بك ، M هي رسائل في النص الخاص بك ، و K هو عدد التطابقات. المحاولات أبطأ بكثير لهذا الغرض. لست متأكدًا من صفيف لاحقة ، لذلك لا يمكنني التعليق على ذلك.

ومع ذلك ، فمن غير التميز رمزًا ولا أعرف أي مكتبات Java التي توفر الوظائف اللازمة.

Answer 4

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

هذا يبدو وكأنه تطبيق ل خوارزمية Aho-Corasick: قم ببناء تلقائي من القاموس (في الوقت الخطي) ، والذي يمكن استخدامه بعد ذلك للعثور على جميع أحداث أي من كلمات القاموس في نصوص متعددة (أيضًا في الوقت الخطي).

(الوصف في ملاحظات المحاضرة هذه, ، المرتبطة من قسم "الروابط الخارجية" في صفحة ويكيبيديا ، أسهل بكثير من القراءة من الوصف في الصفحة نفسها.)

Answer 5

تري مقابل شجرة لاحقة

يضمن كلا هيكلي البيانات البحث السريع جدًا، ويتناسب وقت البحث مع طول كلمة الاستعلام، ووقت التعقيد O(m) حيث m هو طول كلمة الاستعلام.

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

حاول :شجرة لتخزين السلاسل التي تحتوي على عقدة واحدة لكل بادئة مشتركة.يتم تخزين السلاسل في العقد الورقية الإضافية.

شجرة لاحقة:تمثيل مضغوط لثلاثية يتوافق مع لواحق سلسلة معينة حيث يتم دمج جميع العقد التي تحتوي على طفل واحد مع والديها.

بالتأكيد هي من :قاموس الخوارزميات وهياكل البيانات

بشكل عام تري تستخدم لفهرس كلمات القاموس (معجم) أو أي مجموعات من الأوتار مثال d = {ABCD ، ABCDD ، BXCDF ، ..... ، zzzz}

شجرة لاحقة تستخدم لفهرس النص باستخدام نفس بنية البيانات "trie" على جميع لاحقة نصنا t = abcdabcg جميع لاحقة t = {abcdabcg ، abcdabc ، abcdab ، abcda ، abcd ، abc ، ab ، a}

الآن تبدو وكأنها مجموعة من السلاسل.نقوم ببناء محاولة على هذه المجموعة من السلاسل (جميع لواحق T).

بناء كل من بنية البيانات خطي، ويستغرق O(n) في الزمان والمكان.

في حالة القاموس (مجموعة من السلاسل):n = مجموع حروف كل الكلمات.في النص :ن = طول النص.

مصفوفة اللاحقة :هي تقنية لتمثيل شجرة اللاحقة في مساحة مضغوطة، وهي عبارة عن مجموعة من جميع مواضع البداية لواحق السلسلة.

إنها أبطأ من شجرة اللاحقة في وقت البحث.

لمزيد من المعلومات، انتقل إلى ويكيبيديا، هناك مقالة جيدة تتحدث عن هذا الموضوع.

Answer 6

أنا أفضل آلة لاحقة السيارات. يمكنك العثور على مزيد من التفاصيل من خلال موقع الويب الخاص بي:http://www.fogsail.net/2019/03/06/20190306/

أدخل وصف الصورة هنا

أولاً ، إذا استخدمت البناء العادي ، فسوف يستغرق الأمر O (n^2) للسفر كل اللاحقة

نستخدم Radix-Sort لفرز مجموعة لاحقة حسب الشخصية الأولى.

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

تظهر التفاصيل من قبل الصور (إهمال الصينية)

نقوم بتصنيف المصفوفة بالمفتاح الأول ، يتم تقديم النتيجة بواسطة Red Rectangle

𝑎𝑎𝑏𝑎𝑎𝑎𝑎𝑏,𝑎𝑏𝑎𝑎𝑎𝑎𝑏,....−−>𝑎𝑎𝑏𝑎𝑎𝑎𝑎𝑏,𝑎𝑎𝑎𝑎𝑎𝑎𝑏,....

أدخل وصف الصورة هنا

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1001 * 100 + 10;

struct suffixArray {
    int str[maxn], sa[maxn], rank[maxn], lcp[maxn];
    int c[maxn], t1[maxn], t2[maxn];
    int n;

    void init() { n = 0; memset(sa, 0, sizeof(sa)); }

    void buildSa(int Rdx) {
        int i, *x = t1, *y = t2;
        for(i = 0; i < Rdx; i++) c[i] = 0;
        for(i = 0; i < n; i++) c[x[i] = str[i]]++;
        for(i = 1; i < Rdx; i++) c[i] += c[i-1];
        for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;

        for(int offset = 1; offset <= n; offset <<= 1) {
            int p = 0;
            for(i = n-offset; i < n; i++) y[p++] = i;
            for(i = 0; i < n; i++) if(sa[i] >= offset) y[p++] = sa[i] - offset;

            // radix sort
            for(i = 0; i < Rdx; i++) c[i] = 0;
            for(i = 0; i < n; i++) c[x[y[i]]]++;
            for(i = 1; i < Rdx; i++) c[i] += c[i-1];
            for(i = n-1; i >= 0; i--) { sa[--c[x[y[i]]]] = y[i]; y[i] = 0; }

            // rebuild x and y
            swap(x, y); x[sa[0]] = 0; p = 1;
            for(i = 1; i < n; i++)
                x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+offset] == y[sa[i]+offset] ? p-1 : p++;
            if(p >= n) break;
            Rdx = p;
        }
    }

Answer 7

هذه تنفيذ خوارزمية الفرز المستحثة (تسمى SAIS) لديه إصدار Java لبناء صفائف لاحقة.