Geri Dön

Enhancing Rope data structure for collaborative text editing

Eş zamanlı metin düzenleme için 'Rope' veri yapısının iyileştirilmesi

PDF İndir

  1. Tez No: 866244
  2. Yazar: SEMİH SANDAL
  3. Danışmanlar: DOÇ. DR. TOLGA OVATMAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 113

Özet

Rope veri yapısı, büyük string verileri için geliştirilen ve özellikle birleştirme (concatenation) gibi işlemlerde daha hızlı çözümler sunan bir veri yapısı olarak karşımıza çıkmaktadır. Geleneksel string veri operasyonları, büyük metin parçalarını bir araya getirirken zaman ve bellek açısından maliyetli olabilir. Ancak Rope, bu tür büyük metinlerin etkili bir şekilde birleştirilmesini sağlar, böylece metin birleştirme performansını artırır. Özellikle uzun belgeler veya metin tabanlı verilerle çalışan uygulamalar için ideal bir çözüm sunar. Günümüzdeki metin düzenleme ihtiyaçları, insanları aynı anda metinleri düzenleyebilecekleri ve paylaşabilecekleri platformlara yönlendirmiştir. Özellikle bulut tabanlı sistemlerin yaygınlaşması, eş zamanlı metin düzenleme platformlarının popülerliğini artırmıştır. Bu tür platformlar, farklı kullanıcıların aynı metin belgesini eş zamanlı olarak düzenleyebilmelerine olanak tanır. Kullanıcılar, farklı coğrafi konumlarda olsalar bile aynı metin üzerinde düzenleme yapabilirler. Bu bağlamda, Rope veri yapısı, birden fazla kullanıcının aynı anda metin düzenlemesini etkili bir şekilde desteklemek amacıyla uygun bir veri yapısı olabilmektedir. Eş zamanlı metin düzenlenen platformlarında kullanılan veri yapıları hakkında literatürde çok çalışma bulunmamaktadır. Bu tez ise Rope veri yapısının etkili ve verimli uygulamasını yaparak bu veri yapısını eş zamanlı metin düzenleme ortamına uygun hale getirmeye çalışmaktadır. Metin düzenleyicilerde geri alma (undo) işlemi sıkça kullanılan ve kullanıcılar için kritik öneme sahip bir özelliktir. Kullanıcılar, yanlışlıkla yaptıkları değişiklikleri geri alarak belgeyi önceki durumuna getirebilirler. Bu işlemin hızlı ve sorunsuz çalışması, bir metin düzenleyicinin kullanılabilirliğini büyük ölçüde etkileyebilir. Rope veri yapısının buradaki rolü, değişmez (immutable) yapısı sayesinde önceki versiyonları koruyarak geri alma işlemini performanslı bir şekilde gerçekleştirmesidir. Böylece kullanıcılar, bir önceki versiyona hızlıca dönebilirler. Geri alma işlemi için önerilen veri yapıları genellikle değişmez (immutable) yapılar arasından seçilir. Bu tür yapılar, bir kez oluşturulduktan sonra değiştirilemezler ve her bir versiyonu yani geçmiş durumu saklayabilirler. Rope veri yapısı temel olarak değişmez bir veri yapısı olsa da bazı operasyonlar eklendiğinde bu özelliğini yitirebilir. Örneğin, 'insert' operasyonu ile belgeye yeni metin eklenirken değişmezlik özelliği kaybedilebilir fakat bunun sonucu olarak performans kazanımı yaşanabilir. Bu çalışma, Rope'un bu operasyonunun değişmezliği koruyarak nasıl uygulandığını ve performansının nasıl etkilendiğini incelemiştir. Elde edilen sonuçlar, değişmezlik özelliğini koruduğu için bir miktar performans kaybına sebep olsa da geri alma operasyonu için Rope veri yapısını daha efektif yapmaktadır. Rope veri yapısının eş zamanlı metin düzenleme ortamı için uygun olmasını sağlayabilecek bir başka durum ise Rope'un içindeki ağaç yapısının dengeli olmasıdır. Bu ağaç yapısının dengeli olması metin yazan biri için 'insert' ve 'search' gibi operasyonları hızlandıracaktır. Bunun sonucu olarak kullanıcılar daha performansı yüksek bir metin düzenleyici kullanabileceklerdir. AVL ağaçları ve Red-Black ağaçları literatürde üzerine çok sayıda çalışma bulunan iki dengeli ağaçtır. Bu çalışmada Rope veri yapısının içinde bulunan ağaç, Red-Black ve AVL ağaçları ile güçlendirilmiştir. Bu iki ağacın tercih edilme sebeplerinden biri ise Rope ağacı ile olan yapısal benzerliklerdir. Bu çalışmada Rope ağacı, Red-Black ve AVL ağaçları ile güçlendirilirken karşılaşılan sorunların nasıl düzeltildiği ve nasıl bir yol izlendiği gösterilmektedir. Elde edilen bu yeni Ropelar ile 'insert', 'search' ve 'rebalance' operasyonları üzerinde performans ölçümleri yapılmıştır. Bu ölçümlerin sonunda AVL ve Red-Black ağaçları ile iyileştirilmiş Rope ağaçları dengeleme yaptıklarından dolayı, metin oluşturma işleminde bir miktar yavaşlamaya sebep olmuşlardır. Fakat metin Rope ağacı üzerinde dengeli bir şekilde tutulduğu için 'insert' ve 'search' operasyonlarda çok ciddi performans kazanımı sağlamıştır. Bunların yanında Rope ağacının kendi dengeleme mekanizması da bu testlere dahil edilmiştir ve performans ölçümleri yapılmıştır. Eş zamanlı metin düzenleme platformunun en önemli özelliklerinden biri de kullanıcıların aynı anda doküman üzerinde değişiklik yapmalarıdır. Bir kullanıcının yaptığı bir değişiklik dokümanın bütünlüğünü bozmadan ve diğer kullanıcıları bekletmeden tamamlanmalıdır. Bu sebeple bu platformun temelinde kullanılan veri yapısının eş zamanlı işlemlere uygun olması gerekmektedir. Bu sebeple bu çalışmada Rope veri yapısını eş zamanlı işlemlere uygun hale getirilerek performans ölçümleri yapılmıştır. Rope eş zamanlı ortam için uygun hale getirilirken literatürdeki paralel ve eş zamanlı algoritmalar konsetpinden yararlanılmıştır. Örneğin birden fazla kullanıcının olduğu durumlar için her bir kullanıcı 'thread' olarak varsayılmıştır ve threadler paralel olarak çalıştırılmıştır. Buna ek olarak doküman bütünlüğünün korunması için ve operasyonların paralel yürütülebilmesi için ilk olarak kilitlerden faydalanılmıştır. Bu kilitli yaklaşımlar Rope ağacı üzerinde bloklamaya sebep olabilecekleri için, bloklamayan paralel algoritmalar ile de Rope üzerinde başka iyileştirmeler yapılmıştır. Uygulanan bu bloklayan ve bloklamayan yaklaşımların performans ölçümleri yapılıp Rope ağacı üzerinde paralel 'insert' ve 'concatenate' operasyonları elde edilmiştir. Sonuç olarak bu çalışma ilk olarak Rope veri yapısını ve standart string operasyonlarını performansları açısından çeşitli string uzunlukları ile karşılaştırır. Bu karşılaştırma sonucunda Rope veri yapısının daha hızlı sonuç vermeye başladığı string uzunluğu hesaplanır. Bu hesaplamanın sonucunda bu eşikten yüksek değerler için Rope'un stringler yerine bir alternatif olabileceğinden bahsedilir. Geri alma operasyonu için, değişmez olan Rope veri yapısı üzerinde, değişmezliğini bozmadan 'insert' operasyonu kullanılarak çalışmalar ve deneyler yapılır. Bu operasyonun değişmezliği koruduğu ve korumadığı durumlar için performansta ne kadar bir fark oluşturabileceği gösterilmiştir. Bunlara ek olarak Rope, AVL ve Red-Black ağaçları ile güçlendirilerek iyileştirme çalıştırmaları yapılmıştır. Elde edilen bu çalışmanın deneyleri yapılarak daha hızlı 'insert' ve 'search' operasyonları elde edilmiştir. Red-Black ağaçlarının ve AVL ağaçlarının Rope ile birleştirilmesinden detaylı olarak bahsedilmektedir. Son olarak Rope veri yapısının operasyonlarından olan 'insert' ve 'concatenation' operasyonları bloklayan ve bloklamayan algoritmalar kullanılarak eş zamanlı çalışabilen operasyonlar haline getirilmiştir. Elde edilen bu operasyonlarda, metin düzenleme ortamındaki farklı sayıda eş zamanlı kullanıcılar hedef alınarak, aynı sayıda threadler oluşturulup performans ölçümleri yapılmıştır. Bu sonuçlar doğrultusunda bloklamayan algoritmaların Rope veri yapısı üzerinde daha hızlı sonuçlar verdiği gözlemlenmiştir.

Özet (Çeviri)

The Rope data structure is an alternative to strings and is developed specifically for handling large strings. It provides a faster solution for operations like concatenation. Thanks to this advantage, the Rope data structure is considered well-suited for use in text editors. The evolving needs of text editors have directed people towards platforms that allow collaborative text editing. With the widespread adoption of cloud systems, these platforms have become even more popular. As a result, people have started to prefer collaborative text editing over standard text editors. There is a limited number of studies in the literature regarding the data structures used in collaborative text editing platforms. This thesis aims to adapt the Rope data structure for use in collaborative text editing environments by developing effective and efficient implementations. Undoing operations, which are commonly used in text editors and have great importance for users, have various implementations. The faster implementations of these operations make the text editor preferred. While the implementations may not exhibit high efficiency in some operations, they significantly enhance the overall effectiveness of text editors. The data structures recommended for undoing operations are typically immutable, as they store version information, enabling rapid reverting to a previous version. Although the Rope data structure itself is immutable, there are certain operations where immutability requires further investigation, which is an aspect not extensively covered in the existing literature. This study implements the insert operation as immutable and measures its performance. As a result, while Rope becomes more effective, there is a slight decrease in efficiency for the insert operation. Another aspect that makes the Rope data structure suitable for collaborative text editing is the balanced tree structure it contains. This balanced tree structure accelerates operations like insert and search, which are crucial for text composition. Consequently, users can benefit from a text editor with higher performance. AVL trees and Red-Black trees are two well-researched and conventional examples of balanced trees. This study enhances Ropes with AVL and Red-Black tree. A crucial feature of collaborative text editing platforms is the ability of multiple users to make simultaneous changes to the document. Consequently, the underlying data structure must support concurrent transactions. This study demonstrates performance gains by making the Rope data structure suitable for concurrent operations. While making this, blocking and non-blocking concurrent algorithms were employed. In conclusion, this study firstly measures the efficiency of the Rope data structure compared to standard string operations in according to string lengths. The results indicate that Rope can be an alternative to strings for length above a certain threshold. The study also introduces an immutable insert operation to the Rope data structure for undoing operations and demonstrates the performance effect compared to a standard insert operation. Moreover, the study strengthens Rope by combining it with AVL trees and Red-Black trees, achieving faster insert and search operations. The integration of Red-Black and AVL trees with Rope is discussed in detail. Finally, the 'insert' and 'concatenation' operations, which are among the Rope operations, were turned into operations that can operate concurrently by using blocking and non-blocking algorithms, thus increasing performance.

Benzer Tezler

  1. Tez No

    406554

    Hafif raylı bir taşıtın taşıyıcı bojisinin titreşim analizi

    Vibration analysis of a trailer bogie of a lrv

    FATİH ZAFER TOPSAKAL

    Yüksek Lisans

    Türkçe

    Türkçe

    2015

    Makine MühendisliğiYıldız Teknik Üniversitesi

    Makine Teorisi ve Dinamiği Ana Bilim Dalı

    DOÇ. DR. SEMİH SEZER

  2. Tez No

    516596

    Tanker terminal bağlama operasyonlarının modellenmesi

    Modelling terminal mooring operations of tankers

    ALİ CEM KUZU

    Doktora

    Türkçe

    Türkçe

    2018

    Denizcilikİstanbul Teknik Üniversitesi

    Deniz Ulaştırma Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ÖZCAN ARSLAN

  3. Tez No

    73337

    Enhancing EFL students reading comprehension through concioussness-raising training on contextual guesswork

    Kelime anlamlarını tahmin etme yöntemleri konusunda öğrencilerin bilinçlendirilmesiyle okuduklarını anlamalarını arttırma: Afyon Kocatepe Anadolu Lisesi lise II sınıf öğrencileriyle bir uygulama

    HÜSEYİN KAFES

    Yüksek Lisans

    İngilizce

    İngilizce

    1998

    Eğitim ve ÖğretimAnadolu Üniversitesi

    İngiliz Dili Eğitimi Bilim Dalı

    YRD. DOÇ. DR. ÜMİT DENİZ TURAN

  4. Tez No

    767956

    Enhancing secondary school students' reading comprehension through metacognitive strategies

    Üstbilişsel stratejilerle ortaokul öğrencilerinin okuduğunu anlamalarını geliştirme

    ÜLVİYE KAYA

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Eğitim ve ÖğretimKocaeli Üniversitesi

    Yabancı Diller Eğitimi Ana Bilim Dalı

    PROF. DR. BANU İNAN KARAGÜL

  5. Tez No

    768110

    Developing residual shear strength of structural concrete panels exposed to high temperatures

    Yüksek sıcaklıklara maruz kalan yapısal beton panellerin katkı makas mukavemetinin geliştirilmesi

    ALI MUNEER MUNEAM AL-ZUHAIRI

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    İnşaat MühendisliğiAltınbaş Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    PROF. DR. ZEKİ HASGÜR

Geri Dön