Trie Veri Yapısı: İhmal Edilen Bir Mücevher

Programcılar olarak hayatımızın ilk günlerinden itibaren hepimiz veri yapılarıyla ilgilendik: Diziler, bağlantılı listeler, ağaçlar, kümeler, yığınlar ve kuyruklar günlük arkadaşlarımızdır ve deneyimli programcılar bunları ne zaman ve neden kullanacağını bilir. Bu makalede, genellikle ihmal edilen bir veri yapısı olan trie'nin , kelime oyunları gibi belirli özelliklere sahip uygulama etki alanlarında gerçekten nasıl parladığını göreceğiz.

Trie Örneği Olarak Kelime Oyunları

Yeni başlayanlar için basit bir kelime bulmacası düşünelim: 4x4 harfli bir tahtada tüm geçerli kelimeleri bulun, bitişik harfleri yatay, dikey veya çapraz olarak birleştirin. Örneğin aşağıdaki panoda 'W', 'A', 'I' ve 'T' harflerinin birleşerek “WAIT” kelimesini oluşturduğunu görüyoruz.

Tüm geçerli kelimeleri bulmanın naif çözümü, tahtayı sol üst köşeden başlayarak keşfetmek ve ardından derinliği önce daha uzun dizilere doğru hareket ettirmek, tekrar ilk satırdaki ikinci harften başlayarak vb. 4x4'lük bir tahtada, dikey, yatay ve çapraz hareketlere izin veren, uzunlukları bir ile on altı karakter arasında değişen 12029640 dizi vardır.

Şimdi hedefimiz, bu geçerli kelime denetleyicisini, yani kelime dağarcığımızı uygulamak için en iyi veri yapısını bulmaktır. Akılda tutulması gereken birkaç nokta:

• Her kelimenin yalnızca tek bir kopyasına ihtiyacımız var, yani mantıksal açıdan bakıldığında kelime dağarcığımız bir kümedir.
• Herhangi bir kelime için aşağıdaki soruları cevaplamamız gerekiyor:
  • Geçerli karakter dizisi geçerli bir sözcük içeriyor mu?
  • Bu diziyle başlayan daha uzun kelimeler var mı? Değilse, daha derine inmek hiçbir geçerli kelime vermeyeceğinden, önce derinlik keşfimizi bırakabiliriz.

İkinci noktayı göstermek için aşağıdaki panoyu düşünün: Sözlükte “ASF” ile başlayan hiçbir kelime olmadığından sonraki hamleleri keşfetmenin bir anlamı yok.

Veri yapımızın bu soruları olabildiğince çabuk yanıtlamasını çok isteriz. ~O(1) erişim süresi (bir diziyi kontrol etmek için) ideal olacaktır!

Kelime arayüzünü şu şekilde tanımlayabiliriz (GitHub deposu için buraya bakın):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Veri Yapısını ve Alternatifleri Deneyin

include() yöntemini uygulamak, öğeleri verimli bir şekilde bulmanızı sağlayan bir destek veri yapısı gerektirirken, isPrefix() contains() , "bir sonraki büyük öğeyi" bulmamızı gerektirir, yani, kelime dağarcığını bir şekilde sıralı tutmamız gerekir.

Karma tabanlı kümeleri aday listemizden kolayca hariç tutabiliriz: böyle bir yapı bize include() için sabit zamanlı kontrol sağlarken, isPrefix() contains() oldukça kötü performans gösterir, en kötü durumda bütününü taramamızı gerektirir. Ayarlamak.

Tam tersi bir nedenle, sıralanmış bağlantılı listeleri de hariç tutabiliriz, çünkü bunlar listenin en azından aranan kelime veya önekten büyük veya ona eşit olan ilk öğeye kadar taranmasını gerektirir.

İki geçerli seçenek, sıralanmış bir dizi destekli liste veya bir ikili ağaç kullanıyor.
Sıralanmış dizi destekli listede, varsa mevcut diziyi veya sonraki büyük öğeyi O(log2(n)) pahasına bulmak için ikili aramayı kullanabiliriz; burada n , sözlükteki sözcük sayısıdır.

Standart java.util.ArrayList ve java.util.Collections.binarySeach kullanarak, her zaman bu şekilde sıralamayı koruyan dizi destekli bir kelime dağarcığı uygulayabiliriz:

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

İkili bir ağaç kullanmaya karar verirsek, uygulama daha da kısa ve zarif olabilirdi (yine, işte kodun bağlantısı):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

Her iki durumda da, her erişim yöntemi ( contains() ve isPrefix() ) için O(log n) performansı bekleyebiliriz. Alan gereksinimlerine gelince, hem dizi destekli uygulama hem de ağaç destekli uygulama O(n+M) gerektirir; burada n, sözlükteki kelime sayısıdır ve M, sözlüğün bayt boyutudur, yani uzunluğunun toplamıdır. sözlükteki dizeler.

Deneme Uygulamaları: Denemeler Ne Zaman ve Neden Kullanılır?

Logaritmik performans ve doğrusal bellek fena değil. Ancak uygulama alanımızın bizi daha iyi performansa götürebilecek birkaç özelliği daha var:

• Tüm kelimelerin küçük harf olduğunu güvenle varsayabiliriz.
• Yalnızca az harfleri kabul ediyoruz; noktalama işareti, kısa çizgi, vurgu vb.
• Sözlük birçok çekimli biçim içerir: çoğullar, birleşik fiiller, birleşik kelimeler (örn. house –> housekeeper). Bu nedenle, birçok kelime aynı kökü paylaşır .
• Kelimelerin sınırlı bir uzunluğu vardır. Örneğin, 4x4 bir tahta üzerinde çalışıyorsak, 16 karakterden uzun tüm kelimeler atılabilir.

Trie'nin ("denemek" olarak telaffuz edilir) geldiği yer burasıdır. Peki tam olarak trie nedir? Denemeler, kitaplarda bulunan ancak nadiren standart kütüphanelerde bulunan ihmal edilen veri yapılarıdır.

Motivasyon için önce Computer Science'ın poster çocuğunu ele alalım: ikili ağaç. Şimdi, bir ikili ağacın performansını analiz ettiğimizde ve x işleminin O(log(n)) olduğunu söylediğimizde, sürekli olarak 2 günlük tabanından bahsediyoruz. Peki ya ikili ağaç yerine üçlü bir ağaç kullansak, burada her düğümün üç çocuğu vardır (veya üçten bir yelpaze). O zaman, log tabanı 3'ten bahsediyor olurduk. (Bu, yalnızca sabit bir faktörle de olsa bir performans artışıdır.) Esasen, ağaçlarımız daha geniş ama daha kısa olurdu ve tam olarak inmemiz gerekmediğinden daha az arama yapabilirdik. çok derin.

İşleri bir adım daha ileri götürürsek, veri türümüzün olası değerlerinin sayısına eşit dağılma özelliğine sahip bir ağacımız olsaydı ne olurdu?

Bu, denemenin arkasındaki motivasyondur. Ve tahmin edebileceğiniz gibi, bir trie gerçekten bir ağaçtır, tabiri caizse bir trie ağacı!

Ancak, dizeleri sıralamak için kullanacağınız çoğu ikili ağaçların aksine, tüm kelimeleri düğümlerinde depolayacak olan ikili ağaçların aksine, bir trie'nin her düğümü tek bir karaktere sahiptir (ve yakında göreceğimiz gibi, o bile değil) ve alfabenin uzunluğuna eşit bir maksimum yayılıma sahiptir. Bizim durumumuzda alfabenin uzunluğu 26'dır; bu nedenle trie düğümlerinin maksimum yayılımı 26'dır. Ve dengeli bir ikili ağaç log2(n) derinliğe sahipken, trie'nin maksimum derinliği bir kelimenin maksimum uzunluğuna eşittir! (Yine, daha geniş ama daha kısa.)

Bir trie içinde, aynı köke (ön ek) sahip kelimeler, gövdeye karşılık gelen hafıza alanını paylaşır.

Farkı görselleştirmek için beş kelimeden oluşan küçük bir sözlük düşünelim. Yunanca harflerin işaretçileri gösterdiğini varsayalım ve trie'de kırmızı karakterlerin geçerli sözcükleri tutan düğümleri gösterdiğine dikkat edin.

Java Denemesi Uygulaması

Bildiğimiz gibi, ağaçta alt öğelerin işaretçileri genellikle bir sol ve sağ değişkenle uygulanır, çünkü maksimum yayma ikiye sabitlenir.

26 harflik bir alfabeyi indeksleyen bir trie'de, her düğümün 26 olası çocuğu ve dolayısıyla 26 olası işaretçisi vardır. Böylece her düğüm, her değerin boş (böyle bir çocuk yoksa) veya başka bir düğüm olabileceği 26 (işaretçi) alt ağaçtan oluşan bir diziye sahiptir.

O halde, bir kelimeyi bir denemede nasıl ararız? Bir String s verildiğinde, ağaçta varsa, kelimenin son harfine karşılık gelen düğümü tanımlayacak yöntem şudur:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

LOWERCASE.getIndex(s.charAt(i)) yöntemi, alfabedeki i . karakterin konumunu döndürür. Döndürülen düğümde, bir Boolean özellik node , düğümün bir kelimenin son harfine, yani önceki örnekte kırmızı ile işaretlenmiş bir harfe karşılık geldiğini belirtir. Her düğüm, çocuk sayısının bir sayacını tuttuğundan, bu sayaç pozitifse, sözlükte geçerli dizeyi önek olarak alan daha uzun kelimeler vardır. Not: Düğümün, karşılık geldiği karaktere bir referans tutması gerekmez, çünkü trie'deki konumunda örtüktür.

Performans Analizi

Trie yapısının bu durumlarda gerçekten iyi performans göstermesini sağlayan şey, bir kelime veya önek arama maliyetinin sabit olması ve kelime dağarcığının boyutuna değil, yalnızca kelimedeki karakter sayısına bağlı olmasıdır.

Spesifik alanımızda, en fazla 16 karakterden oluşan dizelerimiz olduğundan, kelime dağarcığındaki bir kelimeyi bulmak için tam olarak 16 adım gerekirken, herhangi bir olumsuz cevap, yani kelime veya önek denemede değil, elde edilebilir. hem de en fazla 16 adımda! Hem dizi destekli sıralanmış liste hem de dizi karşılaştırmalarında gizlenen ağaç için çalışma süresi karmaşıklığını hesaplarken daha önce dizi uzunluğunu göz ardı ettiğimizi düşünürsek, burada da görmezden gelebilir ve aramanın yapıldığını güvenle belirtebiliriz. O(1) zamanında.

Alan gereksinimleri göz önüne alındığında (ve sözlüğün bayt boyutunu M ile belirttiğimizi hatırlayarak), en kötü durumda, iki dizenin bir önek paylaşmaması durumunda, trie'nin M düğümü olabilir. Ancak sözlükte yüksek derecede fazlalık olduğunu gözlemlediğimiz için yapılacak çok fazla sıkıştırma var. Örnek kodda kullanılan İngilizce sözlük 935.017 bayttır ve yaklaşık %73 sıkıştırma oranıyla 250.264 düğüm gerektirir.

Ancak buna rağmen, sıkıştırılmış bir deneme bile genellikle bir ağaç veya diziden daha fazla bellek gerektirir. Bunun nedeni, her düğüm için en az 26 x sizeof(pointer) bayt, artı nesne ve ek nitelikler için bir miktar ek yük gerekmesidir. 64 bitlik bir makinede, her düğüm 200 bayttan fazla gerektirirken, bir dize karakteri tek bir bayt veya UTF dizelerini düşünürsek iki bayt gerektirir.

Denemeler ve Performans Testleri

Peki ya performans? Kelime uygulamaları iki farklı durumda test edildi: 20.000.000 rastgele diziyi kontrol etmek ve aynı kelime listesinden rastgele oluşturulmuş 15.000 panodaki tüm kelimeleri bulmak.

Dört veri yapısı analiz edildi: bir dizi destekli sıralanmış liste, bir ikili ağaç, yukarıda açıklanan üçlü ve karakterlerin alfabe indeksine karşılık gelen bayt dizilerini kullanan bir deneme (küçük ve kolayca uygulanan bir performans optimizasyonu). İşte sonuçlar, ms cinsinden:

Tahtayı çözmek için yapılan ortalama hamle sayısı 2.188'dir. Her hareket için bir kelime araması ve bir önek araması yapılır, yani tüm panoları kontrol etmek için 32M'den fazla kelime araması ve 32M önek araması yapılmıştır. Not: Bunlar tek adımda yapılabilir, anlatımda netlik için ayrı tuttum. Bunları tek bir adımda sıkıştırmak, tahtaları çözme süresini neredeyse yarıya indirecek ve muhtemelen denemeyi daha da fazla destekleyecektir.

Yukarıda görülebileceği gibi, sözcük arama, dizeler kullanılırken bile trie ile daha iyi performans gösterir ve alfabe dizinlerini kullanırken daha da hızlıdır, ikincisi standart bir ikili ağaçtan iki kat daha hızlı performans gösterir. Hızlı trie-alfabe-indeks çözümünün liste ve ağaçtan dört kat daha hızlı olmasıyla, tahtaları çözmedeki fark daha da belirgindir.

Toplama

Trie, ağaçlardan ve listelerden çok daha fazla bellek gerektiren çok özel bir veri yapısıdır. Bununla birlikte, dizelerin ilk bölümünde sınırlı bir alfabe ve yüksek fazlalık gibi belirli etki alanı özellikleri geçerli olduğunda, performans optimizasyonunu ele almada çok etkili olabilir.

Referanslar

Denemeler ve alfabelerle ilgili kapsamlı bir açıklama, Robert Sedgewick'in “Algoritmalar, 4. Baskı” kitabının 5. bölümünde bulunabilir. Princeton'daki tamamlayıcı web sitesi, örneğimden daha kapsamlı bir Alfabe ve TrieST uygulaması için koda sahiptir.

Denemenin açıklaması ve çeşitli diller için uygulamalar Wikipedia'da da bulunabilir ve bu Boston Üniversitesi deneme kaynağına da bir göz atabilirsiniz.