Dizgi eşleme algoritmalarının incelenmesi ve yeni bir dizgi eşleme algoritması
Yükleniyor...
Dosyalar
Tarih
2008
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Trakya Üniversitesi Fen Bilimleri Enstitüsü
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Bu tezde; günümüzde birçok alanda kullanılmakta olan dizgi eşleme algoritmaları incelenmiş, bu algoritmaların farklı alfabeler üzerindeki performansları belirlenerek, doğal dillerin yapısal farklılığının dizgi eşleme algoritmaları üzerindeki etkileri araştırılmıştır. Ayrıca alfabeyi oluşturan karakterleri gruplayarak bu grupların kullanım frekansına bağlı yeni ve hızlı bir dizgi eşleme algoritması sunulmuştur. Dördüncü bölümde verilen deneme sonuçlarına göre, algoritmalar alfabeler üzerinden ele alındığında ortalamada DNA alfabesi üzerinde en etkin algoritma Shift Or, rakam alfabesi üzerinde Berry-Ravindran, doğal dil alfabesi üzerinde ise en etkili algoritma Tuned Boyer Moore algoritması olarak tespit edilmiştir. Ortalamada DNA alfabesinde en kötü performansı Reverse Factor, rakam ve doğal dil alfabesinde ise en kötü performansı Forward Dawg Matching algoritması sergilemiştir. Araştırmada seçilen 8 farklı doğal dil için yapılan denemelerden elde edilen sonuçlara göre alfabe eleman sayısının algoritmaları etkilemesinin yanı sıra kullanılan doğal dillerin de algoritmaların performansını etkilediği belirlenmiştir. Bu çalışmada sunulan, kullanılan alfabedeki karakterleri gruplayarak arama işlemi gerçekleştiren ve doğal diller üzerinde dizgi eşleme yapabilen yeni dizgi eşleme algoritması, doğal diller üzerinde en etkin performans gösteren diğer algoritmalardan daha etkin bir performans sergilemiştir. ANAHTAR KELİMELER: Dizgi Eşleme, Dizgi Eşleme Algoritmaları, Yaklaşık Dizgi Eşleme, Doğal Dil, Karakter Gruplama.
In this thesis; pattern matching algorithms are examined, their efficiencies over different alphabets are determined and the effects of structural differences of natural languages over pattern matching algorithms are researched. Besides, a fast pattern matching algorithm, which depends on group frequency of alphabet characters is presented. According to the tests given in Section 4, the most efficient algorithms are; Shift Or for DNA alphabet, Berry-Ravindran for numeral alphabet and Tuned Boyer Moore for natural language alphabet. The worst algorithms are; Reverse Factor for DNA alphabet and Forward Dawg Matching for both numeral and natural language alphabets. According to the test results of 8 different natural languages, it is identified that a pattern matching algorithm performance is affected not only with the total number of alphabet characters but also with structures of natural languages. The new pattern matching algorithm that is presented in this thesis, which can make searching by grouping the alphabet characters and perform string matching on natural languages, had shown better performance on natural languages than other effective pattern matching algorithms. KEYWORDS: String Matching, String Matching Algorithms, Approximate String Matching, Natural Language, Character Groupping.
In this thesis; pattern matching algorithms are examined, their efficiencies over different alphabets are determined and the effects of structural differences of natural languages over pattern matching algorithms are researched. Besides, a fast pattern matching algorithm, which depends on group frequency of alphabet characters is presented. According to the tests given in Section 4, the most efficient algorithms are; Shift Or for DNA alphabet, Berry-Ravindran for numeral alphabet and Tuned Boyer Moore for natural language alphabet. The worst algorithms are; Reverse Factor for DNA alphabet and Forward Dawg Matching for both numeral and natural language alphabets. According to the test results of 8 different natural languages, it is identified that a pattern matching algorithm performance is affected not only with the total number of alphabet characters but also with structures of natural languages. The new pattern matching algorithm that is presented in this thesis, which can make searching by grouping the alphabet characters and perform string matching on natural languages, had shown better performance on natural languages than other effective pattern matching algorithms. KEYWORDS: String Matching, String Matching Algorithms, Approximate String Matching, Natural Language, Character Groupping.
Açıklama
Yüksek Lisans Tezi
Anahtar Kelimeler
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control, Dizgi Eşleme, String Matching, Doğal Dil, Natural Language
