ابحث عن السلسلة الفرعية البادئة التي توفر أفضل ضغط

Question

مشكلة:

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

مثال:

"foo", "fool", "bar"

النتيجه هي:"foo" كالسلسلة الأساسية مع السلاسل "\0", "\0l", "bar" ويبلغ الطول الإجمالي 9 بايت. "\0" هو بايت الهروب.مجموع أطوال السلاسل الأصلية هو 10، لذا في هذه الحالة قمنا بحفظ بايت واحد فقط.

قد تبدو الخوارزمية الساذجة كما يلي:

for string in list
  for i = 1, i < length of string
      calculate total length based on prefix of string[0..i]
      if better than last best, save it
return the best prefix

سيعطينا ذلك الإجابة، لكنه شيء مثل O((n*m)^2)، وهو مكلف للغاية.

Answer 1

استخدم غابة من الأشجار البادئة (trie) ...

  f_2    b_1
 /       |
 o_2     a_1
 |       |
 o_2     r_1
 |
 l_1

ومن ثم، يمكننا العثور على أفضل نتيجة، وضمانها، من خلال تعظيمها (depth * frequency) والتي سيتم استبدالها بشخصية الهروب الخاصة بك.يمكنك تحسين البحث عن طريق إجراء بحث فرعي وعمق محدد أولاً عن الحد الأقصى.

على التعقيد:O(C)، كما هو مذكور في التعليق، يعتمد على بنائه وإيجاد الأمثل.إذا قمت بترتيب تردد العناصر الأولى (O(A) -- حيث A هو حجم أبجدية اللغات)، فستتمكن من قطع المزيد من الفروع، وستكون لديك فرصة جيدة للحصول على وقت خطي فرعي.

أعتقد أن هذا واضح، ولن أكتبه -- ما هو هذا الواجب المنزلي؟;)

Answer 2

سأحاول البدء بفرز القائمة.ثم تنتقل ببساطة من سلسلة إلى أخرى وتقارن الحرف الأول بالحرف الأول في السلسلة التالية.بمجرد حصولك على تطابق، ستنظر إلى الحرف التالي.ستحتاج إلى ابتكار طريقة لتتبع أفضل نتيجة حتى الآن.

Answer 3

حسنًا، ستكون الخطوة الأولى هي فرز القائمة.ثم قم بالمرور عبر القائمة، ومقارنة كل عنصر مع العنصر السابق، وتتبع أطول سلسلة مكونة من حرفين، و3 أحرف، و4 أحرف، وما إلى ذلك.ثم الشكل هو 20 بادئة مكونة من 3 أحرف أفضل من 15 بادئة مكونة من 4 أحرف.