Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Dizi eşleme algoritmaları olarak da adlandırılan dizi arama algoritmaları, bir ya da birkaç dizinin (örüntü) daha büyük bir dizi ya da metin içindeki yerinin bulunmasını konu edinen önemli bir dizi algoritması sınıfıdır.
Σ bir (sonlu küme) olmak üzere örüntü ve aranan metin Σ kümesinin elemanlarından oluşan bir zincir olarak tanımlanabilmektedir. Σ olağan bir alfabe (Türkçede yer alan harfler kümesi) olabileceği gibi ikili alfabe (Σ = {0,1}) ve DNA alfabesi (Σ = {A,C,G,T}) biçiminde de bulunabilmektedir.
Dizinin kodlanma biçimi dizi arama algoritmalarının başarımını etkilemektedir. yöntemi kullanıldığında n. karakteri bulmak güçleşmekte; bu, gelişmiş dizi algoritmalarını yavaşlatıcı bir etken olarak öne çıkmaktadır. Bu sorunun üstesinden gelmenin yolu belirli karakterler yerine kod dizilerini eşleştirmektedir ancak bu yöntem, kodlamanın yanlış sonuçların önüne geçecek biçimde tasarlanmadığı durumlarda pek güvenilir değildir.
Temel sınıflandırma
Algoritmalar kullandıkları örüntü sayısına göre sınıflandırılabilmektedirler.
Tek örüntülü algoritmalar
m örüntünün, n aranan metnin uzunluğu olsun.
| Algoritma | Önişlem süresi | Eşleme süresi1 |
|---|---|---|
| Saf dizi arama algoritması | 0 | Θ((n-m+1) m) |
| Θ(m) | ortalama: Θ(n+m) en düşük: Θ((n-m+1) m) | |
| Sonlu durum makinesi tabanlı arama | Θ(m |Σ|) | Θ(n) |
| Θ(m) | Θ(n) | |
| Θ(m + |Σ|) | Ω(n/m), O(n) | |
| (Baeza-Yates-Gonnet) | Θ(m + |Σ|) | O(mn) |
1Sonuşmaz süreler O, Ω, and Θ gösterimi biçiminde ifade edilmektedir.
Boyer–Moore dizi arama algoritması, ilgili yazında kullanılan başlıca algoritma olarak kabul edilmektedir.
Sonlu örüntü kümesi kullanan algoritmalar
Sonsuz sayıda örüntü kullanan algoritmalar
Doğal olarak sayılamayan örüntüler genellikle ya da düzenli ifadeler biçiminde gösterilmektedir.
İkincil sınıflandırma
En sık kullanılan sınıflandırma yöntemlerinden biri önişlemi ana ölçüt olarak kabul etmektedir.
| Önişlem gerektirmeyen metin | Önişlem gerektiren metin | |
|---|---|---|
| Önişlem gerektirmeyen örüntüler | Temel algoritmalar | Dizin yöntemleri |
| Önişlem gerektiren algoritmalar | Yapısal arama motorları | İmza yöntemleri |
Saf dizi arama
Bir dizinin başka bir dizi içinde yer alıp almadığını anlamanın en basit olmasına karşın en verimsiz yolu dizinin her karakterini sırayla eşleştirmeye çalışmaktır. Bu yöntemde aranan dizi metnin ilk karakteriyle karşılaştırılır. Bu karakterlerin birbiriyle uyuşmaması durumunda aynı işlem metnin ikinci karakteri için yinelenir. Olağan koşullarda karakterlerin eşleşmediğini anlamak için ortalama olarak O(n + m) adım gerekliyken (n metnin, m örüntünün uzunluğunu göstermektedir) en elverişsiz durumda ("aaaab" dizisini "aaaaaaaaab" içinde aramak gibi) gerekli ortalama adım sayısı O(nm)'ye eşittir.
Sonlu dizi makinesi tabanlı arama
Bu yöntemde geri dönüşler, istenen diziyi içeren örüntüleri fark edebilen bir (DFA) oluşturularak ortadan kaldırılabilmektedir. yöntemiyle tasarlanan bu gereçlerin tutarı yüksek olsa da kullanımları görece kolaydır. Bu yöntem gelişigüzel düzenli ifadelere ilişkin aramalarda sıklıkla kullanılmaktadır.
Kısa yöntemler
, aranan diziyi sonek biçiminde algılayabilen bir oluştururken aramaya örüntünün sonundan başlamakta, böylece her adımda örüntü uzunluğu ölçüsünde yol kat edebilmektedir. Baeza–Yates önceki j karakterin aranan dizinin bir öneki olup olmadığını takip edebildiğinden bağdaştırılabilmektedir. Baeza-Yates'in bir uygulamasıdır.
Dizin yöntemleri
Görece hızlı çalışan arama algoritmaları metnin önişlemden geçirilmesini gerektirmektedir. ya da gibi oluşturularak örüntü daha kolay biçimde bulunabilmektedir. Bir sonek ağacı 
sürede hazırlanabilmekte ve metin içinde yer alan 
sayıdaki örüntü 
sürede bulunabilmektedir (alfabe büyüklüğü sabit olmak koşuluyla).
Diğer yöntemler
gibi bazı arama yöntemleri metin ve örüntüyü birebir eşlemek yerine bu iki dizi arasında bir "yakınlık" değeri hesaplamayı amaçlamaktadır. Bu tür yöntemler "bulanık" aramalar olarak da adlandırılmaktadır.
Notlar
- ^ Hume and Sunday (1991) Fast String Searching Software—Practice and Experience, Cilt 21(11), 1221–1248 (Kasım 1991)
Kaynakça
- R. S. Boyer & J. S. Moore, A fast string searching algorithm 12 Ocak 2012 tarihinde Wayback Machine sitesinde ., Carom. ACM 20, (10), 262–272 (1977)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein. Introduction to Algorithms, 2. basım. MIT Press & McGraw-Hill, 2001. . 32. Bölüm: Dizi Eşleme, s. 906–932
Dış bağlantılar
- Dev örüntü eşleme bağlantıları listesi 23 Mart 2009 tarihinde Wayback Machine sitesinde .
- StringSearch – Java'da yüksek başarımlı örüntü eşleme algoritmaları[]
- Dizi Eşleme Algoritmaları 18 Eylül 2009 tarihinde Wayback Machine sitesinde .
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Dizi esleme algoritmalari olarak da adlandirilan dizi arama algoritmalari bir ya da birkac dizinin oruntu daha buyuk bir dizi ya da metin icindeki yerinin bulunmasini konu edinen onemli bir dizi algoritmasi sinifidir S bir sonlu kume olmak uzere oruntu ve aranan metin S kumesinin elemanlarindan olusan bir zincir olarak tanimlanabilmektedir S olagan bir alfabe Turkcede yer alan harfler kumesi olabilecegi gibi ikili alfabe S 0 1 ve DNA alfabesi S A C G T biciminde de bulunabilmektedir Dizinin kodlanma bicimi dizi arama algoritmalarinin basarimini etkilemektedir yontemi kullanildiginda n karakteri bulmak guclesmekte bu gelismis dizi algoritmalarini yavaslatici bir etken olarak one cikmaktadir Bu sorunun ustesinden gelmenin yolu belirli karakterler yerine kod dizilerini eslestirmektedir ancak bu yontem kodlamanin yanlis sonuclarin onune gececek bicimde tasarlanmadigi durumlarda pek guvenilir degildir Temel siniflandirmaAlgoritmalar kullandiklari oruntu sayisina gore siniflandirilabilmektedirler Tek oruntulu algoritmalar m oruntunun n aranan metnin uzunlugu olsun Algoritma Onislem suresi Esleme suresi1Saf dizi arama algoritmasi 0 8 n m 1 m 8 m ortalama 8 n m en dusuk 8 n m 1 m Sonlu durum makinesi tabanli arama 8 m S 8 n 8 m 8 n 8 m S W n m O n Baeza Yates Gonnet 8 m S O mn 1Sonusmaz sureler O W and 8 gosterimi biciminde ifade edilmektedir Boyer Moore dizi arama algoritmasi ilgili yazinda kullanilan baslica algoritma olarak kabul edilmektedir Sonlu oruntu kumesi kullanan algoritmalar Sonsuz sayida oruntu kullanan algoritmalar Dogal olarak sayilamayan oruntuler genellikle ya da duzenli ifadeler biciminde gosterilmektedir Ikincil siniflandirmaEn sik kullanilan siniflandirma yontemlerinden biri onislemi ana olcut olarak kabul etmektedir Dizi arama algoritmasi siniflari Onislem gerektirmeyen metin Onislem gerektiren metinOnislem gerektirmeyen oruntuler Temel algoritmalar Dizin yontemleriOnislem gerektiren algoritmalar Yapisal arama motorlari Imza yontemleriSaf dizi arama Bir dizinin baska bir dizi icinde yer alip almadigini anlamanin en basit olmasina karsin en verimsiz yolu dizinin her karakterini sirayla eslestirmeye calismaktir Bu yontemde aranan dizi metnin ilk karakteriyle karsilastirilir Bu karakterlerin birbiriyle uyusmamasi durumunda ayni islem metnin ikinci karakteri icin yinelenir Olagan kosullarda karakterlerin eslesmedigini anlamak icin ortalama olarak O n m adim gerekliyken n metnin m oruntunun uzunlugunu gostermektedir en elverissiz durumda aaaab dizisini aaaaaaaaab icinde aramak gibi gerekli ortalama adim sayisi O nm ye esittir Sonlu dizi makinesi tabanli arama MOMMY sozcugunu fark edebilen bir Bu yontemde geri donusler istenen diziyi iceren oruntuleri fark edebilen bir DFA olusturularak ortadan kaldirilabilmektedir yontemiyle tasarlanan bu gereclerin tutari yuksek olsa da kullanimlari gorece kolaydir Bu yontem gelisiguzel duzenli ifadelere iliskin aramalarda siklikla kullanilmaktadir Kisa yontemler aranan diziyi sonek biciminde algilayabilen bir olustururken aramaya oruntunun sonundan baslamakta boylece her adimda oruntu uzunlugu olcusunde yol kat edebilmektedir Baeza Yates onceki j karakterin aranan dizinin bir oneki olup olmadigini takip edebildiginden bagdastirilabilmektedir Baeza Yates in bir uygulamasidir Dizin yontemleri Gorece hizli calisan arama algoritmalari metnin onislemden gecirilmesini gerektirmektedir ya da gibi olusturularak oruntu daha kolay bicimde bulunabilmektedir Bir sonek agaci 8 m displaystyle Theta m surede hazirlanabilmekte ve metin icinde yer alan z displaystyle z sayidaki oruntu O m z displaystyle O m z surede bulunabilmektedir alfabe buyuklugu sabit olmak kosuluyla Diger yontemler gibi bazi arama yontemleri metin ve oruntuyu birebir eslemek yerine bu iki dizi arasinda bir yakinlik degeri hesaplamayi amaclamaktadir Bu tur yontemler bulanik aramalar olarak da adlandirilmaktadir Notlar Hume and Sunday 1991 Fast String Searching Software Practice and Experience Cilt 21 11 1221 1248 Kasim 1991 KaynakcaR S Boyer amp J S Moore A fast string searching algorithm 12 Ocak 2012 tarihinde Wayback Machine sitesinde Carom ACM 20 10 262 272 1977 Thomas H Cormen Charles E Leiserson Ronald L Rivest amp Clifford Stein Introduction to Algorithms 2 basim MIT Press amp McGraw Hill 2001 ISBN 0 262 03293 7 32 Bolum Dizi Esleme s 906 932Dis baglantilarDev oruntu esleme baglantilari listesi 23 Mart 2009 tarihinde Wayback Machine sitesinde StringSearch Java da yuksek basarimli oruntu esleme algoritmalari olu kirik baglanti Dizi Esleme Algoritmalari 18 Eylul 2009 tarihinde Wayback Machine sitesinde