Deterministik çevrimsiz sonlu durum otomatı

Bilgisayar biliminde, deterministik çevrimsiz sonlu durum otomatı (DAFSA), bir dizeler kümesini temsil eden ve belirli bir dizeyin kümeye ait olup olmadığını, dize uzunluğuna orantılı sürede test etmeye olanak sağlayan bir veri yapısıdır. Bu tür otomatları inşa etmek ve sürdürmek için algoritmalar geliştirilmiştir ve bu algoritmalar, yapıyı minimum düzeyde tutacak şekilde çalışır.Jan Daciuk, Stoyan Mihov, Bruce Watson ve Richard Watson (2000). Minimal çevrimsiz deterministik sonlu durum otomatlarının artımlı inşası. Computational Linguistics, 26(1): 3–16. DAFSA, Yönlendirilmiş Çevrimsiz Kelime Grafiği (DAWG)Andrew Appel ve Guy Jacobsen (1988). Dünyanın En Hızlı Scrabble Programı. Communications of the ACM, 31(5): 572–578. olarak bilinen bir veri yapısının yeniden keşfidir, ancak aynı ad, daha önce son ek otomatı ile ilişkili farklı bir veri yapısına da verilmiştir.Anselm Blumer, Janet Blumer, Andrzej Ehrenfeucht, David Haussler ve Ross M. McConnell (1983). Bir kelimenin tüm alt dizeleri kümesi için doğrusal boyutlu sonlu otomatlar: Sonuçların özeti. Bulletin of the European Association for Theoretical Computer Science (EATCS), 21: 12–20.

DAFSA, tek bir kaynak köşesi (gelen kenarı olmayan bir köşe) olan yönlendirilmiş döngüsüz bir graf biçimindeki, sonlu durum tanıyıcı yapısının özel bir durumudur. Bu grafikte her kenar bir harf veya sembolle etiketlenmiştir ve her köşenin, her olası harf veya sembol için en fazla bir giden kenarı vardır. DAFSA'nın temsil ettiği dizeler, kaynak köşeden herhangi bir alıcı köşeye (çıkış kenarı olmayan köşe) giden yollardaki sembollerle oluşturulur. Aslında, bir deterministik sonlu durum otomatı, ancak ve ancak sonlu bir dize kümesini tanıyorsa döngüsüzdür.

 Tarihçe 
Blumer ve arkadaşları, Yönlendirilmiş Çevrimsiz Kelime Grafiği (DAWG) terimini ilk kez 1983 yılında tanımlamıştır. Appel ve Jacobsen, 1988 yılında aynı ismi farklı bir veri yapısı için kullanmıştır. Önceki çalışmalardan bağımsız olarak, Daciuk ve arkadaşları, bu ikinci veri yapısını 2000 yılında yeniden keşfetmiş, ancak ona DAFSA adını vermiştir.

Trie’larla Karşılaştırma
Aynı düğümlerin birden fazla yol aracılığıyla erişilebilir olmasına izin vererek, bir DAFSA, yakından ilişkili olan trie veri yapısına göre önemli ölçüde daha az düğüm kullanabilir. Örneğin, İngilizce'deki "tap", "taps", "top" ve "tops" sözcüklerini ele alalım. Bu dört sözcüğü temsil eden bir trie, her bir sözcüğün öneklerinden veya sözcüğün ardından gelen dize sonu işaretçisinden oluşan toplam 12 düğüm içerir. Buna karşılık bir DAFSA, aynı dört sözcüğü yalnızca altı düğüm kullanarak temsil edebilir: vi olmak üzere 0 ≤ i ≤ 5. Bu yapıda, v0'dan v1'e "t" harfiyle etiketli bir kenar bulunur. v1'den v2'ye "a" ve "o" harfleriyle etiketlenmiş iki ayrı kenar vardır. Ardından, v2'den v3'e "p" harfiyle, v3'ten v4'e "s" harfiyle etiketli kenarlar bulunur. Son olarak, hem v3 hem de v4'ten v5'e, dize sonunu belirten işaretle etiketlenmiş kenarlar çıkar.

Bu yapı, bellek kullanımı ile işlevsellik arasında bir ödünleşim ortaya koyar. Standart bir DAFSA, bir kelimenin veri yapısında bulunup bulunmadığını belirleyebilir; ancak bu kelimeyle ilişkili ek bilgilere erişim sunamaz. Buna karşın, bir trie yapısı bu tür yardımcı bilgileri her düğüme eklemeye olanak tanır.

DAFSA ile trie arasındaki temel fark, dizeleri depolarken son ek (suffix) ve iç içe (infix) tekrarların ortadan kaldırılmasıdır. Trie veri yapısı, tüm ortak öneklerin paylaştırılması sayesinde önek (prefix) tekrarını ortadan kaldırır. Örneğin, "doctors" ve "doctorate" kelimeleri arasında "doctor" öneki ortaktır ve trie bunu yalnızca bir kez depolar. DAFSA ise yalnızca önekleri değil, aynı zamanda ortak son ekleri de paylaştırır; bu, son ek kümeleri benzer olan kelimeler için geçerlidir. Bu özellik, özellikle İngilizce gibi çok sayıda ortak önek ve son ek içeren dillerdeki sözlük kümelerinde, bellek kullanımında önemli ölçüde azalma sağlar.

Bir DAFSA'daki uç (terminal) düğümlere birden fazla farklı yoldan erişilebildiği için, her bir yol ile ilişkili yardımcı bilgileri — örneğin bir kelimenin İngilizce dilindeki kullanım sıklığı gibi — doğrudan depolamak mümkün değildir. Ancak, her düğümde bu noktadan geçen benzersiz yolların sayısı saklanırsa, bu bilgi bir kelimenin dizinini bulmak ya da bir dizine karşılık gelen kelimeyi elde etmek için kullanılabilir. Bu durumda yardımcı bilgiler bir dizi (array) içinde tutulabilir.

Kaynakça


  — Veri yapısına erken dönemde yapılan atıflardan biridir.




— Python dilinde geliştirilmiş bir açık kaynak uygulama.

Dış Bağlantılar

 Yönlendirilmiş Çevrimsiz Kelime Grafiği (DAWG) – JohnPaul Adamovsky, bir dizi tamsayı kullanarak bir DAFSA'nın nasıl inşa edileceğini anlatmaktadır. 
 Caroline Kelime Grafiği (CWG) – JohnPaul Adamovsky, bir DAFSA hash fonksiyonu inşa etmek için yeni bir kodlama yöntemi kullanarak birden fazla tamsayı dizisi ile nasıl yapılacağını öğretmektedir.

Kategori:Sonlu durum makineleri