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

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

یک طناب ساده که بر روی رشته «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 به دو رشته جدید S₁ و S₂

S₁ = C₁, …, C_i'

S₂ = C_{i + 1}، …, C_m

پیچیدگی زمان: (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 کم کند.

چسباندن

تعریف:چسباندن(S1, S2) الحاق دو طناب، S₁ و S₂، به یک طناب واحد

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

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

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

درج

تعریف: چسباندن(i, S’): درج کردن رشته ’S در مکان i ام از رشته s ، برای ایجاد یک رشته جدید : C₁, …, C_i, S’, C_{i + 1}، …, C_m.

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

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

حذف

تعریف: حذف(i,j): حذف زیر رشته C_i, … , C_{i + j − 1} از رشته s برای تشکیل رشته جدید C₁, … , C_{i − 1}، C_{i + j}، … , C_m.

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

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

خروجی

تعریف: خروجی(i,j): بیرون دادن رشته C_i, … , C_{i + j − 1}.

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

برای خروجی رشته C_i, …, C_{i + j − 1} ، گره u، که شامل C_i و وزنu)>= j) ، را پیدا کنید و سپس از گره u شروع به پیمایش T بکنید . با شروع یک پیمایش میان ترتیب از گره u ( گره u متعلق به T است )، رشته C_i, … , C_{i + 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)

منابع

↑ Boehm, Hans-J (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.

[Boehm-1] Boehm, Hans-J (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.