ما هي الطريقة الأكثر فعالية لتتبع حرف معين مؤشر في سلسلة ؟

Question

تأخذ السلسلة التالية كمثال:

"الثعلب البني السريع"

الآن سؤال في السريع على مؤشر 4 من سلسلة (ابتداء من الساعة 0) f في الثعلب هو في مؤشر 16.الآن دعونا نقول المستخدم بإدخال بعض أكثر من نص في هذه السلسلة.

"سريع جدا البني الداكن فوكس"

الآن سؤال هو في الفهرس 9 و هو في مؤشر 26.

ما هو الأسلوب الأكثر فعالية من تتبع مؤشر الأصلية سؤال في السريع و في فوكس بغض النظر عن كيفية العديد من الشخصيات المضافة من قبل المستخدم ؟

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

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

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

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

Answer 1

دعنا نقول أن لديك سلسلة بعض من الحروف مثيرة للاهتمام.لجعل الأمور أسهل دعنا نقول أن الرسالة في الفهرس 0 هو دائما مثيرة للاهتمام و لم تضيف شيئا قبل ذلك—الحارس.أكتب أزواج (للاهتمام الرسالة المسافة السابقة مثيرة للاهتمام الرسالة).إذا كانت السلسلة هو "+سريع جدا البني الداكن فوكس" و كنت مهتما في س من 'سريعة' و من 'فوكس' ثم يمكنك أن تكتب:(+,0), (q,10), (f,17).(علامة + هو الحارس.)

الآن يمكنك وضع هذه متوازن الثنائية الشجرة التي في النظام اجتياز يعطي تسلسل الحروف في الترتيب التي تظهر في السلسلة.قد تعترف الآن جزئية مبالغ المشكلة:يمكنك تعزيز شجرة حتى أن العقد يحتوي على (رسالة, بعد, sum).المبلغ هو مجموع كل المسافات في الشجرة اليسرى.(ولذلك sum(x)=المسافة(يسار(خ))+مجموع(يسار(خ)).)

يمكنك الآن الاستعلام وتحديث هذه البيانات هيكل في لوغاريتمي الوقت.

القول الذي قمت بإضافته n الشخصيات إلى يسار الحرف ج قلت المسافة(ج)+=n ثم اذهب تحديث مجموع لجميع الآباء والأمهات من ج.

أن نسأل ما هو مؤشر ج يمكنك حساب مبلغ(ج)+مجموع(الأم(ج))+مجموع(الوالد(الوالدين(ج)))+...

Answer 2

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

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

Answer 3

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

Answer 4

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

إدراج أو حذف رسالة في هذا الهيكل فقط يحتاج O(log(N)) العمليات (تحديث الصور النقطية على طريق الجذر) وإيجاد أول قوع رسالة أيضا يأخذ O(log(N)) العمليات - التي تنحدر من جذور ، فإن أقصى اليسار الطفل الذي نقطية تحتوي على رسالة مثيرة للاهتمام.

تحرير:الداخلية العقد يجب أيضا الحفاظ على عدد من الأوراق في تمثيل الشجرة ، كفاءة حساب الرسالة المؤشر.