طناب (ساختمان داده)

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک طناب ساده که بر روی رشته «Hello my name is Simon» ساخته شده است.

در برنامه نویسی کامپیوتر طناب و یا بند ناف، یک ساختمان داده برای ذخیره‌سازی و اداره ی بهینه یک رشته بسیار طولانی است. به عنوان مثال، یک برنامه ویرایش متن ممکن است از یک طناب برای نمایش متن در حال ویرایش استفاده کند، به طوری که عملیاتی از قبیل درج، حذف، و یا دسترسی تصادفی به طور کارامد انجام بشود.[۱]

تعریف[ویرایش]

طناب یک درخت دودویی است. گرهٔ برگی (و همچنین برخی از گره‌های داخلی تک فرزند) شامل یک رشته کوتاه است. هر گره دارای یک "وزن" برابر با طول رشته خود به علاوه تمام وزن‌ها در زیردرخت سمت چپ آن است. بدین ترتیب یک گره با دو فرزند تمام رشته را به دو قسمت تبدیل می‌کند. زیر درخت سمت چپ اولین بخش از رشته ذخیره می‌کند. زیر درخت سمت راست بخش دوم ذخیره را می‌کند و وزن آن مجموع وزن فرزند سمت چپ و طول رشته خودش است.

درخت دودویی شامل سطوح مختلفی از گره‌ها است. سطح پایین شامل تمام گره‌های که حاوی یک رشته هستند و سطوح بالاتر دارای گره‌های کمتر و کمتری هستند. بالاترین سطح از یک گره ریشه تشکیل شده است. طناب با قرار دادن گره‌هایی با رشته‌های کوتاه در سطح پایین و سپس الصاق نیمی از گره‌ها به گره پدر به طور تصادفی در سطح بعدی، ساخته شده است. گره‌های بدون فرزند (به عنوان مثال، دو گره‌ای که رشته‌های " my_ "و" me_i " ذخیره کرده‌اند) به فرزند راست گره سمت چپ خود تبدیل می‌شوند. بدین ترتیب تشکیل زنجیره می‌دهند.

عملکرد[ویرایش]

راهنما[ویرایش]

تعریف : (index(i: بازگرداندن کاراکتر به مکان i
پیچیدگی زمان: (O(log N در جایی که N طول طناب است.

برای بازیابی کاراکتر i ام، یک جستجوی بازگشتی از گره ریشه آغاز می‌کنیم:

// Note '': Assumes 1-based indexing''
 
function index(RopeNode node, integer i)
    if node.weight <i then
        return index(node.right, i - node.weight)
    else
        if exists(node.left) then
            return index(node.left, i)
        else
            return node.string[i]
        endif
    endif
end

به عنوان مثال، برای پیدا کردن کاراکتر در مکان i = ۱۰ در طناب زیر، از گره ریشه شروع کن، پیدا است که ۲۲ بزرگتر از ۱۰ است و یک فرزند در سمت چپ وجود دارد، بنابراین به فرزند سمت چپ برو. ۹ کمتر از ۱۰ است، بنابراین از ۱۰، ۹ را کم کن (قرار بده i = ۱) و به فرزند سمت راست برو. سپس چون ۷ بزرگتر از ۱ است و یک فرزند سمت چپ وجود دارد، به فرزند سمت چپ برو. ۶ بزرگتر از ۱ است و یک فرزند سمت چپ وجود دارد، پس دوباره به فرزند سمت چپ برو. در نهایت ۲ بیشتر از ۱ است، اما دیگر فرزندی در سمت چپ موجود نیست، پس کاراکتر موجود در index 1 از رشته کوتاه "NA"، پاسخ مورد نظر است.

527 × 362px

تقسیم[ویرایش]

تعریف: تقسیم (i, S): تقسیم رشته S به دو رشته جدید S1 و S2

S1 = C1, …, Ci'

S2 = Ci + 1, …, Cm

پیچیدگی زمان: (O(log N

دو حالت وجود دارد: حالت اول  : کاراکتر i ام در پایان آرایه است. همانند تصویر زیر و در حالت دوم، کاراکتر وسط آرایه قرار دارد. به عنوان مثال، برای تقسیم طناب ترسیم شده به دو بخش : از کاراکتر i ام بخواهید که گره v را در سطح پایین قرار بدهد و اتصال بین v و فرزن راست v یا ’v را بردارد. به گره پدر یعنی u برود و وزن ’v را از از u کم کند واز انجا که گره پدر، فرزند راست u، یعنی ’u را دارد، گره ’u را با اتصال به گره ’v و افزایش وزن ’u بوسیله وزن ’v، اصلاح کند. فرزند چپ سابق ’u به فرزند راست ’v تبدیل می‌شود. (تصویر دوم) و با همین روش تا گره پدر u، یعنی W ادامه دهد. وزن ’u را از وزن w کم کند. و سپس فرزند راست w که حالا ’w است را با اتصال به’u بهبود ببخشد. فرزند سابق ’w به فرزند راست ’u تبدیل می‌شود. و وزن ’w را به وسیله وزن ’u افزایش بدهد به گره پدر w یعنی x برود. از انجا که w فرزند راست x هست، پس تغییری ایجاد نمی‌شود سپس به گره پدر x یعنی y برود و وزن y را به وسیله ’w کم کند.

original
step1
step2

چسباندن[ویرایش]

تعریف:چسباندن(S1, S2) الحاق دو طناب، S1 و S2، به یک طناب واحد
پیچیدگی زمانی: (O(log N

این عمل عکس عمل تقسیم است و به طور متوسط به مدت زمان (O(log N برای تولید یک طناب به همراه یک درخت متوازن احتیاج دارد. (اگر محدودیت متوازن بودن درخت خروجی برداشته شود، عمل الحاق در یک زمان ثابت به سادگی با ایجاد یک گره ریشه و فرزندان چپ = S1 و راست = S2 می‌تواند اجرا شود. تخمین پیچیدگی عملیات دیگر بااین حال نیاز به طناب یا درختان متوازن به عنوان ورودی دارد)

توجه داشته باشید که این الحاق مخرب است، که در آن طناب‌های ورودی S1 وS2 بعد از انجام عملیات دیگر وجود ندارند. درزمان مقایسه با الحاق آرایه، باید به خاطر داشته باشید که عملیتات دوم معمولاً غیر مخرب است .

درج[ویرایش]

تعریف: چسباندن(i, S’): درج کردن رشته ’S در مکان i ام از رشته s ، برای ایجاد یک رشته جدید : C1, …, Ci, S’, Ci + 1, …, Cm.

پیچیدگی زمانی: (O(log N

این عملیات با انجام یک عمل تقسیم () و دو عمل چسباندن() ، انجام می شود و زمان انجام این عملیات ، برابر با مجموع زمان انجام سه عمل مذکور می باشد .

حذف[ویرایش]

تعریف: حذف(i,j): حذف زیر رشته Ci, … , Ci + j − 1 از رشته s برای تشکیل رشته جدید C1, … , Ci − 1, Ci + j, … , Cm.
پیچیدگی زمانی: (O(log N

این عملیات با انجام دو عمل تقسیم () و یک عمل چسباندن() ، انجام می شود . در ابتدا طناب را سه قسمت کنید ،این تقسیم که به ترتیب از کاراکتر i ام وi+j ام انجام می شود ، باعث می شود که رشته ای که می خواهیم حذف کنیم در گره ای دیگر ذخیره شود. سپس دو گره دیگر را به هم بچسبانید .

خروجی[ویرایش]

تعریف: خروجی(i,j): بیرون دادن رشته Ci, … , Ci + j − 1.
پیچیدگی زمانی: ( O( j + log N

برای خروجی رشته Ci, …, Ci + j − 1 ، گره u، که شامل Ci و وزنu)>= j) ، را پیدا کنید و سپس از گره u شروع به پیمایش T بکنید . با شروع یک پیمایش میان ترتیب از گره u ( گره u متعلق به T است )، رشته Ci, … , Ci + j − 1 را بدست بیاورید .

مقایسه با آرایه های یک پارچه[ویرایش]

مزایا:

  • طناب ها عملیات درج و حذف از متن را خیلی سریع تر از آرایه های یک پارچه با پیچیدگی (O(n ، انجام می دهند .
  • طناب ها به حافظه اضافی به مقدار (O(n برای انجام عمل احتیاجی ندارند در صورتی که آرایه ها برای عملیات کپی کردن به حافظه اضافی (O(n احتیاج دارند .
  • طناب ها به حافظه های اضافی پیوسته بزرگ احتیاجی ندارند .
  • در صورتی که از نمونه غیر مخرب عملیات ها استفاده شود ، طناب یک ساختمان داده پایدار محسوب می شود . برای نمونه ی برنامه ی ویرایش متن ، پایدار بودن طناب ، از سطوح متعدد خنثی سازی حمایت می کند .

معایب:

  • استفاده بیش از حد از حافظه ، در زمانی که هنوز اجرا نشده . این استفاده از حافظه ، بیشتر برای ذخیره سازی گره های پدر است و بین مقدار کلی حافظه ای که استفاده می شود و مدت زمان پردازش بخشی از داده ها ، تعادل وجود دارد . توجه داشته باشید که رشته هایی که بالاتر مثال زدیم ، برای ساختار های مدرن ، کاملاً کوچک و غیر واقعی هستند .در کل هزینه زمانی ، (O(n است واما اختیاراً این مقدار را کوچک در نظر می گیریم .
  • افزایش مدت زمان برای مدیریت حافظه اضافی.
  • افزایش پیچیدگی کد های منبع . که باعث ایجاد اشکالات زیادی می شود .

در جدول زیر ، سرعت خام انجام الگوریتم ها مقایسه نمی‌شود بلکه مقایسه در مورد خصوصیت های الگوریتم های پیاده سازی رشته و طناب است . رشته هایی که بر پایه ی آرایه ها ساخته شده‌اند ، هزینه کمتری دارند ( به عنوان مثال ) عملیات های تقسیم و چسباندن روی داده های کوچک تر ، سریع تر انجام می شوند . اگرچه زمانی که رشته های مذکور ، برای رشته های بزرگ تر به کار می روند ، پیچیدگی زمانی و استفاده از حافظه برای انجام عملیات های چسباندن و حذف کاراکتر ها ، به طرز غیر قابل قبولی زیاد می شوند . اما طناب ها ، با صرف نظر از حجم داده ها ، عملکرد پایدار تری دارند . علاوه بر این پیچیدگی حافظه ای رشته ها و آرایه ها هر دو (O(n است . به طور خلاصه طناب ها زمانی که داده ها بزرگ و اغلب اصلاح شده هستند ، مناسب هستند .

کارایی
عملکرد طناب رشته
فهرست[۱]
O(log n)
O(1)
تقسیم[۱]
O(log n)
O(1)
چسباندن (مخرب)
O(log n)
O(n)
چسباندن (غیر مخرب)
O(n)
O(n)
حرکت بر روی هر کارکتر[۱]
O(n)
O(n)
درج
O(log n)
O(n)
افزودن
O(log n)
O(1) حالت بهینه، O(n) بدترین حالت
حذف
O(log n)
O(n)
گزارش
O(j + log n)
O(j)
ساختن
O(n)
O(n)

منابع[ویرایش]

  1. ۱٫۰ ۱٫۱ ۱٫۲ ۱٫۳ Boehm, Hans-J; Atkinson, Russ; and Plass, Michael (December 1995). "Ropes: an Alternative to Strings" (PDF). Software—Practice & Experience (New York, NY, USA: John Wiley & Sons, Inc.) 25 (12): 1315–1330. DOI:10.1002/spe.4380251203. 
  • مشارکت‌کنندگان ویکی‌پدیا، «Rope (data structure)»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۹ بهمن ۱۳۹۲).